Volume 11, pp. 55-84, 2000.

High-order finite difference schemes and Toeplitz based preconditioners for elliptic problems

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,m,k)A_n(a,m,k){\}}_n,$$ where $A_n(a,m,k)$ is the $n\times n$ symmetric matrix coming from a high–order Finite Difference discretization of the problem $$\{\begin{array}{l}{\displaystyle (-{)}^k\left(\frac{d^k}{d{x}^k}(a(x)\frac{d^k}{d{x}^k}u(x))\right)=f(x)\text{on}\mathrm{\Omega }=(0,1),}\\ {\displaystyle {(\frac{d^s}{d{x}^s}u(x))}_{|\partial \mathrm{\Omega }}=0s=0,\dots ,k-1.}\end{array}$$ The coefficient function $a(x)$ is assumed to be positive or with a finite number of zeros. The matrix $P_n(a,m,k)$ is a Toeplitz based preconditioner constructed as $D_n^{1/2}(a,m,k)A_n(1,m,k)D_n^{1/2}(a,m,k)$, where $D_n(a,m,k)$ is the suitably scaled diagonal part of $A_n(a,m,k)$. The main result is the proof of the asymptotic clustering around unity of the eigenvalues of the preconditioned matrices. In addition, the “strength” of the cluster shows some interesting dependencies on the order $k$, on the regularity features of $a(x)$ and on the presence of the zeros of $a(x)$. The multidimensional case is analyzed in depth in a twin paper [38].

Full Text (PDF) [704 KB], BibTeX

Key words

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

AMS subject classifications

65N22, 65F10, 15A12.

ETNA articles which cite this article

Vol. 16 (2003), pp. 1-29 Stefano Serra Capizzano and Cristina Tablino Possio: Preconditioning strategies for 2D finite difference matrix sequences