A Simple Proof of Gustafsson’s Conjecture in Case of Poisson Equation on Rectangular Domains
Abstract: We 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 size of the condition number is as big as . Among ILU, SGS, modified ILU (MILU) and other ILU-type preconditioners, Gustafson shows that only MILU achieves an enhancement of the condition number in different order as . His seminal work, however, is not for the MILU but for a perturbed version of MILU and he observes that without the perurbation, it seems to reach the same result in practice. In this work, we give a simple proof of Gustafsson's conjecture on the unnecessity of perturbation in case of Poisson equation on rectangular domains. Using the Cuthill-Mckee ordering, we 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.
Cite this paper: Yoon, G. and Min, C. (2015) A Simple Proof of Gustafsson’s Conjecture in Case of Poisson Equation on Rectangular Domains. American Journal of Computational Mathematics, 5, 75-79. doi: 10.4236/ajcm.2015.52005.
References

   Dupont, T., Kendall, R. and Rachford, H. (1968) An Approximate Factorization Procedure for Solving Self-Adjoint Elliptic Difference Equations. SIAM Journal on Numerical Analysis, 5, 559-573.
http://dx.doi.org/10.1137/0705045

   Gustafsson, I. (1978) A Class of First Order Factorization Methods. BIT Numerical Mathematics, 18, 142-156.
http://dx.doi.org/10.1007/BF01931691

   Greenbaum, A. (1997) Iterative Methods for Solving Linear Systems. SIAM, Philadelphia.
http://dx.doi.org/10.1137/1.9781611970937

   Greenbaum, A. and Rodrigue, G.H. (1989) Optimal Preconditioners of a Given Sparsity Pattern. BIT Numerical Mathematics, 29, 610-634.
http://dx.doi.org/10.1007/BF01932737

   Axelsson, O. (1972) A Generalized SSOR Method. BIT Numerical Mathematics, 13, 443-467.
http://dx.doi.org/10.1007/BF01932955

   Axelsson, O. (1994) Iterative Solution Methods. Cambridge University Press, Cambridge.

   Chan, T.F. and van der Vorst, H.A. (1997) Approximate and Incomplete Factorizations. In: Keyes, D.E., Sameh, A. and Venkatakrishnan, V., Eds., Parallel Numerical Algorithms, ICASE/LaRC Interdisciplinary Series in Science and Engineering, 4, Kluwer Academic, Dordrecht, 167-202.

   Hackbusch, W. (1994) Iterative Solution of Large Sparse Linear Systems of Equations. Applied Math. Sci. Series, No 95, Springer-Verlag, New York.
http://dx.doi.org/10.1007/978-1-4612-4288-8

   Notay, Y. (1992) Upper Eigenvalue Bounds and Related Modified Incomplete Factorization Strategies. In: Beauwens, R. and de Groen, P., Eds., Iterative Methods in Linear Algebra, Amsterdam, North-Holland, 551-562.

   Bruaset, A.M. and Tveito, A. (1992) RILU Preconditioning; A Computational Study. Journal of Computational and Applied Mathematics, 39, 259-275.
http://dx.doi.org/10.1016/0377-0427(92)90203-A

   Gustafsson, I. (1979) Stability and Rate of Convergence of Modified Incomplete Cholesky Factorization Method. Research Report 79.02R, Department of Computer Sciences, Chalmers University of Technology and University of Göteborg, Göteborg, Sweden.

   Beauwens, R. (1984) Upper Eigenvalue Bounds for Pencils of Matrices. Linear Algebra and Its Applications, 62, 87-104.
http://dx.doi.org/10.1016/0024-3795(84)90088-0

   Beauwens, R. (1985) On Axelsson’s Perturbations. Linear Algebra and Its Applications, 68, 221-242.
http://dx.doi.org/10.1016/0024-3795(85)90214-9

   Notay, Y. (1991) Conditioning Analysis of Modified Block Incomplete Factorizations. Linear Algebra and Its Applications, 154-156, 711-722.
http://dx.doi.org/10.1016/0024-3795(91)90400-Q

   Axelsson, O. and Eijkhout, V. (1987) Robust Vectorizable Preconditioners for Three-Dimensional Elliptic Difference Equations with Anisotropy. In: te Riele, H.J.J., Dekker, Th.J. and van der Vorst, H.A., Eds., Algorithm and Applications on Vector and Parallel Computers, North-Holland Publishing Co., Amsterdam, 279-306.

   Axelsson, O. (1989) On the Eigenvalue Distribution of Relaxed Incomplete Factorization Methods and the Rate of Convergence of Conjugate Gradient Methods. Technical Report, Department of Mathematics, Catholic University, Nijmegen, The Netherland.

   Beauwens, R., Notay, Y. and Tombuyses, B. (1994) S/P images of Upper Triangular M-Matrices. Numerical Linear Algebra with Applications, 1, 19-31.
http://dx.doi.org/10.1002/nla.1680010104

   Notay, Y. (1991) Conditioning of Stieltjes Matrices by S/P Consistently Ordered Approximate Factorizations. Applied Numerical Mathematics, 10, 381-396.
http://dx.doi.org/10.1016/0168-9274(92)90058-L

   Min, C. and Gibou, F. (2012) On the Performance of a Simple Parallel Implementation of the ILU-PCG for the Poisson Equation on Irregular Domains. Journal of Computational Physics, 231, 4531-4536.
http://dx.doi.org/10.1016/j.jcp.2012.02.023

Top