Share This Article:

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

Abstract Full-Text HTML XML Download Download as PDF (Size:261KB) PP. 75-79
DOI: 10.4236/ajcm.2015.52005    2,998 Downloads   3,405 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.

Conflicts of Interest

The authors declare no conflicts of interest.

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

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