Sine Transform Based Preconditioners for Elliptic Problems

Raymond H. CHAN, C. K. WONG*

*Corresponding author for this work

Research output: Journal PublicationsJournal Article (refereed)peer-review

13 Citations (Scopus)


We consider applying the preconditioned conjugate gradient (PCG) method to solving linear systems Ax = b where the matrix A comes from the discretization of second-order elliptic operators with Dirichlet boundary conditions. Let (L+Σ) Σ-1 (Lt + Σ) denote the block Cholesky factorization of A with lower block triangular matrix L and diagonal block matrix Σ. We propose a preconditioner M = (L̂ + Σ̂) Σ̂-1 (L̂t + Σ̂) with block diagonal matrix Σ̂ and lower block triangular matrix L̂. The diagonal blocks of Σ̂ and the subdiagonal blocks of L̂ are respectively the optimal sine transform approximations to the diagonal blocks of Σ and the subdiagonal blocks of L. We show that for two-dimensional domains, the construction cost of M and the cost for each iteration of the PCG algorithm are of order O (n2 log n). Furthermore, for rectangular regions, we show that the condition number of the preconditioned system M-1 A is of order O (1). In contrast, the system preconditioned by the MILU and MINV methods are of order O (n). We will also show that M can be obtained from A by taking the optimal sine transform approximations of each sub-block of A. Thus, the construction of M is similar to that of Level-1 circulant preconditioners. Our numerical results on two-dimensional square and L-shaped domains show that our method converges faster than the MILU and MINV methods. Extension to higher-dimensional domains will also be discussed.

Original languageEnglish
Pages (from-to)351-368
Number of pages18
JournalNumerical Linear Algebra with Applications
Issue number5
Publication statusPublished - Sept 1997
Externally publishedYes


  • Elliptic partial differential equation
  • Preconditioned conjugate gradient method
  • Sine transform


Dive into the research topics of 'Sine Transform Based Preconditioners for Elliptic Problems'. Together they form a unique fingerprint.

Cite this