Premium
Sine transform based preconditioners for elliptic problems
Author(s) -
Chan Raymond H.,
Wong C. K.
Publication year - 1997
Publication title -
numerical linear algebra with applications
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.02
H-Index - 53
eISSN - 1099-1506
pISSN - 1070-5325
DOI - 10.1002/(sici)1099-1506(199709/10)4:5<351::aid-nla103>3.0.co;2-4
Subject(s) - mathematics , preconditioner , block matrix , conjugate gradient method , circulant matrix , matrix (chemical analysis) , diagonal , cholesky decomposition , discretization , condition number , mathematical analysis , eigenvalues and eigenvectors , linear system , combinatorics , algorithm , geometry , physics , materials science , quantum mechanics , composite material
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 ( L t + Σ) 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 ( n 2 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. © 1997 John Wiley & Sons, Ltd.