A Simple Proof of Gustafsson’s Conjecture in Case of Poisson Equation on Rectangular Domains

DOI: 10.4236/ajcm.2015.52005   PDF   HTML   XML   3,159 Downloads   3,627 Views   Citations

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.

Share and Cite:

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.

Conflicts of Interest

The authors declare no conflicts of interest.

References

[1] 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
[2] Gustafsson, I. (1978) A Class of First Order Factorization Methods. BIT Numerical Mathematics, 18, 142-156.
http://dx.doi.org/10.1007/BF01931691
[3] Greenbaum, A. (1997) Iterative Methods for Solving Linear Systems. SIAM, Philadelphia.
http://dx.doi.org/10.1137/1.9781611970937
[4] 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
[5] Axelsson, O. (1972) A Generalized SSOR Method. BIT Numerical Mathematics, 13, 443-467.
http://dx.doi.org/10.1007/BF01932955
[6] Axelsson, O. (1994) Iterative Solution Methods. Cambridge University Press, Cambridge.
[7] 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.
[8] 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
[9] 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.
[10] 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
[11] 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.
[12] 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
[13] 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
[14] 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
[15] 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.
[16] 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.
[17] 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
[18] 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
[19] 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

  
comments powered by Disqus

Copyright © 2020 by authors and Scientific Research Publishing Inc.

Creative Commons License

This work and the related PDF file are licensed under a Creative Commons Attribution 4.0 International License.