Sine Transform Based Preconditioners for Elliptic Problems

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² 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.