Volume 16, pp. 1-29, 2003.

Preconditioning strategies for 2D finite difference matrix sequences

Stefano Serra Capizzano and Cristina Tablino Possio

Abstract

In this paper we are concerned with the spectral analysis of the sequence of preconditioned matrices $\{P_n^{-1}{A}_n(a,m_1,m_2,k){\}}_n$, where $n=(n_1,n_2)$, $N(n)=n_1{n}_2$ and where $A_n(a,m_1,$ $m_2,k)\in {\mathbf{R}}^{N(n)\times N(n)}$ is the symmetric two-level matrix coming from a high–order Finite Difference (FD) discretization of the problem $$\{\begin{array}{ll}{\displaystyle (-1{)}^k(\frac{{\partial }^k}{\partial x^k}(a(x,y)\frac{{\partial }^k}{\partial x^k}u(x,y))+\frac{{\partial }^k}{\partial y^k}(a(x,y)\frac{{\partial }^k}{\partial y^k}u(x,y)))=f(x,y)}& \text{on}\mathrm{\Omega }=(0,1{)}^2,\\ {\displaystyle {(\frac{{\partial }^s}{\partial {\nu }^s}u(x,y))}_{|\partial \mathrm{\Omega }}=0s=0,\dots ,k-1}& \text{on}\partial \mathrm{\Omega },\end{array}$$ with $\nu$ denoting the unit outward normal direction and where $m_1$ and $m_2$ 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 $\{A_n(1,m_1,m_2,k){\}}_n$ and a Toeplitz based sequence that adds to the Toeplitz structure the informative content given by the suitable scaled diagonal part of $A_n(a,m_1,m_2,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)$.

Full Text (PDF) [330 KB], BibTeX

Key words

finite differences, Toeplitz and Vandermonde matrices, clustering and preconditioning, spectral distribution.

AMS subject classifications

65F10, 65N22, 65F15.

Links to the cited ETNA articles

[33]	Vol. 11 (2000), pp. 55-84 Stefano Serra Capizzano and Cristina Tablino Possio: High-order finite difference schemes and Toeplitz based preconditioners for elliptic problems