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

DOI:
https://doi.org/10.1090/S0025-5718-1995-1257575-9

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.

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

Retrieve articles in *Mathematics of Computation*
with MSC:
65F30

Retrieve articles in all journals with MSC: 65F30

Additional Information

DOI:
https://doi.org/10.1090/S0025-5718-1995-1257575-9

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