Remote Access Mathematics of Computation
Green Open Access

Mathematics of Computation

ISSN 1088-6842(online) ISSN 0025-5718(print)



A framework for block ILU factorizations using block-size reduction

Authors: Tony F. Chan and Panayot S. Vassilevski
Journal: Math. Comp. 64 (1995), 129-156
MSC: Primary 65F30
MathSciNet review: 1257575
Full-text PDF

Abstract | References | Similar Articles | Additional Information

Abstract: We propose a block ILU factorization technique for block tridiagonal matrices that need not necessarily be M-matrices. The technique explores reduction by a coarse-vector restriction of the block size of the approximate Schur complements computed throughout the factorization process. Then on the basis of the Sherman-Morrison-Woodbury formula these are easily inverted. We prove the existence of the proposed factorization techniques in the case of (nonsymmetric, in general) M-matrices. For block tridiagonal matrices with positive definite symmetric part we show the existence of a limit version of the factorization (exact inverses of the reduced matrices are needed). The theory is illustrated with numerical tests.

References [Enhancements On Off] (What's this?)

  • [1] O. Axelsson, A survey of vectorizable preconditioning methods for large scale finite element matrices, Colloquium Topics in Applied Numerical Analysis (J. G. Verwer, ed.), Syllabus 4, Center of Mathematics and Informatics (CWI), Amsterdam, 1983, pp. 21-47. MR 805542
  • [2] -, A general incomplete block-matrix factorization method, Linear Algebra Appl. 74 (1986), 179-190. MR 822145 (87g:65044)
  • [3] O. Axelsson, S, Brinkkemper, and V.P. Il'in, On some versions of incomplete block-matrix factorization methods, Linear Algebra Appl. 38 (1984), 3-15. MR 739275 (85g:65042)
  • [4] O. Axelsson and V.L. Eijkhout, Robust vectorizable preconditioners for three-dimensional elliptic difference equations with anisotropy, Algorithms and Applications on Vector and Parallel Computers (H.J.J. te Riele, Th.J. Dekker, and H. van der Vorst, eds.), North-Holland, Amsterdam, 1987, pp. 279-306. MR 974124 (90f:65180)
  • [5] O. Axelsson and B. Polman, On approximate factorization methods for block-matrices suitable for vector and parallel processors, Linear Algebra Appl. 77 (1986), 3-26. MR 837856 (87i:65061)
  • [6] -, A robust preconditioner based on algebraic substructuring and two-level grids, Robust Multigrid Methods (W. Hackbusch, ed.), Notes Numer. Fluid Mech., vol. 23, Vieweg, Braunschweig, 1989, pp. 1-26. MR 993362 (90e:65036)
  • [7] A. Berman and R.J. Plemmons, Nonnegative matrices in the mathematical sciences, Academic Press, New York, 1979. MR 544666 (82b:15013)
  • [8] T.F. Chan and T.P. Mathew, The interface probing technique in domain decomposition, SIAM J. Matrix Anal. Appl. 13 (1992), 212-238. MR 1146663 (92i:65183)
  • [9] T.F. Chan and P.S. Vassilevski, A framework for block-ILU factorization using block size reduction, CAM Report # 92-29, Department of Mathematics, UCLA, 1992.
  • [10] P. Concus, G.H, Golub, and G. Meurant, Block preconditioning for the conjugate gradient method, SIAM J. Sci. Statist. Comput. 6 (1985), 220-252. MR 773293 (87c:65035a)
  • [11] S. Demko, W.F. Moss, and P.W. Smith, Decay rates of inverses of band matrices, Math. Comp. 43 (1984), 491-499. MR 758197 (85m:15002)
  • [12] R.E. Ewing, R.D. Lazarov and P.S. Vassilevski, Local refinement techniques for elliptic problems on cell-centered grids, I. Error analysis, Math. Comp. 56 (1991), 437-462. MR 1066831 (91m:65256)
  • [13] W. Hackbusch, Multigrid methods and applications, Springer-Verlag, New York, 1985. MR 814495 (87e:65082)
  • [14] G.H. Golub and C. van Loan, Matrix computations, The Johns Hopkins University Press, Baltimore and London, 1991.
  • [15] R. Kettler, Analysis and comparison of relaxed schemes in robust multigrid and preconditioned conjugate gradient methods, Multigrid Methods, Proceedings (W. Hackbusch and U. Trottenberg, eds.), Lecture Notes in Math., vol. 960, Springer-Verlag, Berlin and New York, 1982, pp. 502-534. MR 685786 (84c:65132)
  • [16] D.E. Keyes and W.D. Gropp, A comparison of domain decomposition techniques for elliptic differential equations and their parallel implementation, SIAM J. Sci. Statist. Comput. 8 (1987), 166-202. MR 879402 (88g:65101)
  • [17] L. Kolotilina and B. Polman, On incomplete block factorization methods of generalized SSOR type for H-matrices, Linear Algebra Appl. 177 (1992), 111-136. MR 1195973 (93k:65028)
  • [18] G. Meurant, The block-preconditioned conjugate gradient method on vector computers, BIT 24 (1984), 623-633. MR 764833 (86d:65134)
  • [19] B. Polman, Incomplete blockwise factorizations of (block) H-matrices, Linear Algebra Appl. 90 (1987), 119-132. MR 884115 (89a:65054)
  • [20] R. Varga, Matrix iterative analysis, Prentice-Hall, Englewood Cliffs, NJ, 1961. MR 0158502 (28:1725)
  • [21] P.S. Vassilevski, On some ways of approximating inverses of banded matrices in connection with deriving preconditioners based on incomplete block-factorizations, Computing 43 (1990), 277-296. MR 1045063 (91a:65073)
  • [22] -, Algorithms for construction of preconditioners based on incomplete block-factorizations, Internat. J. Numer. Methods. Engrg. 27 (1989), 609-622. MR 1036927 (91a:65118)
  • [23] P.S. Vassilevski, S.I. Petrova, and R.D. Lazarov, Finite difference schemes on triangular cell-centered grids with local refinement, SIAM J. Sci. Statist. Comput. 13 (1992), 1287-1313. MR 1185647 (93m:65156)
  • [24] G. Wittum, An ILU-based smoothing correction scheme, Parallel Algorithms for PDEs (W. Hackbusch, ed.), Notes Numer. Fluid Mech., Vieweg, Braunschweig, 1990, pp. 228-240. MR 1167881

Similar Articles

Retrieve articles in Mathematics of Computation with MSC: 65F30

Retrieve articles in all journals with MSC: 65F30

Additional Information

Keywords: Block ILU factorization, M-matrices, positive definite matrices, second-order elliptic equation, finite differences, Sherman-Morrison-Woodbury formula
Article copyright: © Copyright 1995 American Mathematical Society

American Mathematical Society