TY - JOUR

T1 - A reciprocal preconditioner for structured matrices arising from elliptic problems with jumping coefficients

AU - Dolgov, Sergey

AU - Khoromskij, Boris N.

AU - Oseledets, Ivan

AU - Tyrtyshnikov, Eugene

N1 - Funding Information:
Corresponding author. E-mail addresses: sergey.v.dolgov@gmail.com (S. Dolgov), bokh@mis.mpg.de (B.N. Khoromskij), ivan.oseledets@gmail.com (I. Oseledets), tee@bach.inm.ras.ru (E. Tyrtyshnikov). 1 Supported by the RFBR grants 11-01-12137, 11-01-00549-a, 09-01-91332 (joint with DFG), the Government Contracts Π940, Π1112, 14.740.11.0345 and Priority Research Grant of the Presidium and of the Department of Mathematical Sciences of the Russian Academy of Sciences. 2 During this work the author was also a visiting professor at the University of Siedlce (Poland) and University of Chester (UK).

PY - 2012/5/1

Y1 - 2012/5/1

N2 - We present a new explicit preconditioner for a class of structured matrices Γ(a) defined by a function a. These matrices may arise from elliptic problems by a standard discretization scheme admitting jumps in the diffusion coefficient. When the grid is fixed, the matrix is determined by the diffusion coefficient a. Our preconditioner P is of the form P=Γ- 1(1)Γ(1/a)Γ- 1(1) and can be considered as an approximation to the inverse matrix to Γ(a). We prove that P and Γ- 1(a) are spectrally equivalent. However, the most interesting observation is that Γ(a)P has a cluster at unity. In the one-dimensional case this matrix is found to be equal to the identity plus a matrix of rank one. In more dimensions, a rigorous proof is given in the two-dimensional stratified case. Moreover, in a stratified case with M constant values for the coefficient a, a hypothesis is proposed that a wider set of M+1 points including unity is a proper cluster. In such cases the number of iterations does not depend dramatically on jumps of the diffusion coefficient. In more general cases, fast convergence is still demonstrated by many numerical experiments.

AB - We present a new explicit preconditioner for a class of structured matrices Γ(a) defined by a function a. These matrices may arise from elliptic problems by a standard discretization scheme admitting jumps in the diffusion coefficient. When the grid is fixed, the matrix is determined by the diffusion coefficient a. Our preconditioner P is of the form P=Γ- 1(1)Γ(1/a)Γ- 1(1) and can be considered as an approximation to the inverse matrix to Γ(a). We prove that P and Γ- 1(a) are spectrally equivalent. However, the most interesting observation is that Γ(a)P has a cluster at unity. In the one-dimensional case this matrix is found to be equal to the identity plus a matrix of rank one. In more dimensions, a rigorous proof is given in the two-dimensional stratified case. Moreover, in a stratified case with M constant values for the coefficient a, a hypothesis is proposed that a wider set of M+1 points including unity is a proper cluster. In such cases the number of iterations does not depend dramatically on jumps of the diffusion coefficient. In more general cases, fast convergence is still demonstrated by many numerical experiments.

KW - Elliptic operators

KW - Finite differences

KW - Finite elements

KW - Iterative methods

KW - Multi-dimensional matrices

KW - Numerical methods

KW - Poisson equation

KW - Preconditioners

KW - Structured matrices

UR - http://www.scopus.com/inward/record.url?scp=84857999258&partnerID=8YFLogxK

U2 - 10.1016/j.laa.2011.09.010

DO - 10.1016/j.laa.2011.09.010

M3 - Article

AN - SCOPUS:84857999258

SN - 0024-3795

VL - 436

SP - 2980

EP - 3007

JO - Linear Algebra and its Applications

JF - Linear Algebra and its Applications

IS - 9

ER -