Preconditioning strategies for 2D finite difference matrix sequences

Serra Capizzano, Stefano ; Tablino Possio, Cristina

Electronic transactions on numerical analysis, Tome 16 (2003), pp. 1-29

Résumé

In this paper we are concerned with the spectral analysis of the sequence of preconditioned matrices P - 1 n $An(a, m1, m2, k)$n, where n = (n1, n2), $N(n) = n1n2$ and where $An(a, m1, m2, k) \in RN(n)\times N(n)$ is the symmetric two-level matrix coming from a high-order Finite Difference (FD) discretization of the problem ###$ \partial k \partial k \partial k $###$ ( a(x, y) u(x, y) + a(x, y) u(x, y) = f$ (x, y) on $\Omega $= (0, 1)2,

$###$

- 1)k $\partial k $###$ \partial $xk $\partial $xk $\partial $yk $\partial $yk $\partial s $###$ u(x, y) = 0$ s = 0, . . . , k

$###$

- 1 on $\partial \Omega , $###$ \partial \nu s |\partial \Omega $with $\nu $denoting the unit outward normal direction and where m1 and m2 are parameters identifying the precision order of the used FD schemes. We assume that the coefficient $a(x, y)$ is nonnegative and that the set of the possible zeros can be represented by a finite collection of curves. The proposed preconditioning matrix sequences correspond to two different choices: the Toeplitz sequence ${An(1, m1, m2, k)}$n and a Toeplitz based sequence that adds to the Toeplitz structure the informative content given by the suitable scaled diagonal part of $An(a, m1, m2, k)$. The former case gives rise to optimal preconditioning sequences under the assumption of positivity and boundedness of a. With respect to the latter, the main result is the proof of the asymptotic clustering at unity of the eigenvalues of the preconditioned matrices, where the "strength" of the cluster depends on the order k, on the regularity features of $a(x, y)$ and on the presence of zeros of $a(x, y)$.

Détail

Classification : 65F10, 65N22, 65F15
Keywords: finite differences, Toeplitz and vandermonde matrices, clustering and preconditioning, spectral distribution