A Simple Proof of Gustafsson’s Conjecture in Case of Poisson Equation on Rectangular Domains ()
1. Introduction
Consider the standard five-point finite difference method for solving the Poisson equation with the Dirichlet boundary condition. Its associated matrix is a typical ill-conditioned matrix whose condition number is of size, where h is the grid size. In mitigating the large size, Dupont, Kendall and Rachfold [1] propose a preconditioning technique which works quite well for elliptic problems with convergence rate, which is a simple modification of incomplete LU (ILU) and called the modified ILU (MILU) preconditioning techni- que. The MILU requires all the same row sums for the preconditioner and the original matrices. Also, Gusta- fsson [2] [3] shows that the MILU preconditiong reduces the size to, while other popular precon- ditionings such as ILU and symmetric Gauss-Seidel (SGS) do not improve the order. Numerical study by Greenbaum and Rodrigue [4] indicates that further reduction is not possible with the same sparsity pattern.
The MILU preconditioing introduced by Axelsson [5] and developed by Gustafsson [2] adds some artificial diagonal perturbation on the orginal matrix. In [1] and [2] , it is found that a small positive perturbation improves the convergence rate quite well for many elliptic problems. We refer to [6] -[9] and references therein for more results and details.
The numerical experiments [10] with Dirichlet boundary condition, however, suggest that the perturbation is unnecessary. It is Gustafsson’s conjecture [2] [11] to prove the estimate for the unperturbed MILU preconditioing. Beauwens [12] considers a general setting that includes the five-point method, and proves the conjecture using the matrix-graph connectivity properties (see also [13] ). Beauwens’ proof deals with a Stieltjes matrix under several assumptions. Notay [14] also obtains an upper bound for the block MILU with the line partitioning. We also refer the reader to [15] -[18] for related works on Gustafsson’s conjecture.
We introduce a novel and heuristic proof for the conjecture in case of Poisson equation with Dirichlet boundary condition on rectangular domains. The MILU preconditioner is obtained from recursively calculating the row-sum equation at each grid node in the lexicographical ordering. In the case of the five-point method, it is well known [19] that the same matrix can be obtained in the Cuthill-Mckee ordering. The matrix entry on the
node depends only on and nodes, both of which lie on the same level of the Cuthill-Mckee ordering. So we can simplify the recursive equation in two dimensional grid
nodes into a recursive one in the level that is one dimensional. Due to the simplification, our proof is easy to follow and very short.
2. MILU Preconditioning
Consider the Poisson equation in a rectangular domain with the Dirichlet boun- dary condition on. The standard five-point finite difference method approximates the equation as
at each grid node. The approximations constitute a linear system. With the lexicographical ordering, we decompose the matrix as
where L, U, and D are its strictly lower and upper, and diagonal parts, respectively. MILU preconditioner is the matrix of the form, where the diagonal matrix E is obtained recursively as follows.
for
for
Here denotes the diagonal element of E corresponding to the node point, i.e.. and denote the entry and, respectively. Note that the above formula results from
the row sum property, with. Due to the Dirichlet boundary condition, and are either or 0, and.
Lemma 1. Let be a sequence defined recursively as
(1)
Then we have
Proof. Let be the sequence defined as (1). The lemma is shown by the mathematical induction. Assume that for Then
and this proves the lemma.
Theorem 1. Let be the MILU preconditioner for A. Then, for every diagonal element of E corresponding to the node, we have
and, therefore,
Proof. We shall show that for by mathematical induction on. Then follows the result from the previous lemma. When,. Assume that for all with. Then for any with,
Now, we are ready to estimate the condition number of the MILU preconditioned matrix. The fol- lowing analysis is a standard approach, for the details see [2] . Since is similar to
that is symmetric and positive definite, all the eigenvalues of are real and positive. Moreover, the minimum and maximum eigenvalues of are given as
(2)
and is written in the form
(3)
for the matrix (see (b) of Figure 1 for its entries). For arbitrary, we have
(4)
(a) (b)
Figure 1. Matrices A and R. (a) Matrix A; (b) Matrix B = M ? A.
Using the inequality and Theorem 1, we also have
Thus, we obtain the inequalities
(5)
In summary, we have the following.
Theorem 2. Let be an eigenvalue of the MILU preconditioned matrix, then and
(6)
Proof. Let be an eigenvalue of the MILU preconditioned matrix From (5), we have that
and applying these inequalities above into (2) and (3) gives
which shows the inequalites (6). On the other hand, the row sum property implies that 1 is an eigenvalue of. Thus, we have and we complete the proof.
Corollary 1. The ratio of the maximum and minimum eigenvalues of the MILU preconditioned matrix is bounded by.
Remark 1. Our analysis deals with the two dimensional Poisson equation. It naturally extends to the three dimensional equation in a dimension-by-dimension manner.
Acknowledgments
This work was supported by Basic Science Research Program through the National Research Foundation of Korea(NRF) funded by the Ministry of Education (2009-0093827).