Sine transform based preconditioners for elliptic problems
Publication in refereed journal



摘要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 + Sigma)Sigma(-1)(L-t + Sigma) denote the block Cholesky factorization of A with lower block triangular matrix L and diagonal block matrix Sigma. We propose a preconditioner M = (<(L) over cap> + <(Sigma) over cap>)Sigma(-1)(<(L) over cap>(t) + <(Sigma) over cap>) with block diagonal matrix <(Sigma) over cap> and lower block triangular matrix <(L) over cap>. The diagonal blocks of and the subdiagonal blocks of <(L) over cap> are respectively the optimal sine transform approximations to the diagonal blocks of <(Sigma) over cap> 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-l 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 MlNV methods. Extension to higher-dimensional domains will also be discussed. (C) 1997 by John Wiley & Sons, Ltd.
著者Chan RH, Wong CK
期刊名稱Numerical Linear Algebra with Applications
頁次351 - 368
關鍵詞elliptic partial differential equation; preconditioned conjugate gradient method; sine transform
Web of Science 學科類別Mathematics; MATHEMATICS; Mathematics, Applied; MATHEMATICS, APPLIED

上次更新時間 2020-01-12 於 00:41