A framework for block ILU factorizations using block-size reduction

Chan, Tony F.; Vassilevski, Panayot S.

doi:10.1090/S0025-5718-1995-1257575-9

A framework for block ILU factorizations using block-size reduction
HTML articles powered by AMS MathViewer

by Tony F. Chan and Panayot S. Vassilevski PDF

Math. Comp. 64 (1995), 129-156 Request permission

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

O. Axelsson, A survey of vectorizable preconditioning methods for large scale finite element matrix problems, Colloquium topics in applied numerical analysis, Vol. 1 (Amsterdam, 1983/1984) CWI Syllabi, vol. 4, Math. Centrum, Centrum Wisk. Inform., Amsterdam, 1984, pp. 21–47. MR 805542
O. Axelsson, A general incomplete block-matrix factorization method, Linear Algebra Appl. 74 (1986), 179–190. MR 822145, DOI 10.1016/0024-3795(86)90121-7
O. Axelsson, S. Brinkkemper, and V. P. Il′in, On some versions of incomplete block-matrix factorization iterative methods, Linear Algebra Appl. 58 (1984), 3–15. MR 739275, DOI 10.1016/0024-3795(84)90200-3
O. Axelsson and V. Eijkhout, Robust vectorizable preconditioners for three-dimensional elliptic difference equations with anisotropy, Algorithms and applications on vector and parallel computers (Amsterdam, 1985–86) Spec. Topics Supercomput., vol. 3, North-Holland, Amsterdam, 1987, pp. 279–306. MR 974124
Owe Axelsson and Ben Polman, On approximate factorization methods for block matrices suitable for vector and parallel processors, Linear Algebra Appl. 77 (1986), 3–26. Special volume on parallel computing. MR 837856, DOI 10.1016/0024-3795(86)90159-X
O. Axelsson and B. Polman, A robust preconditioner based on algebraic substructuring and two-level grids, Robust multi-grid methods (Kiel, 1988) Notes Numer. Fluid Mech., vol. 23, Friedr. Vieweg, Braunschweig, 1989, pp. 1–26. MR 993362
Abraham Berman and Robert J. Plemmons, Nonnegative matrices in the mathematical sciences, Computer Science and Applied Mathematics, Academic Press [Harcourt Brace Jovanovich, Publishers], New York-London, 1979. MR 544666
Tony F. C. Chan and Tarek P. Mathew, The interface probing technique in domain decomposition, SIAM J. Matrix Anal. Appl. 13 (1992), no. 1, 212–238. MR 1146663, DOI 10.1137/0613018

A framework for block-ILU factorization using block size reduction

P. Concus, G. H. Golub, and G. Meurant, Block preconditioning for the conjugate gradient method, SIAM J. Sci. Statist. Comput. 6 (1985), no. 1, 220–252. MR 773293, DOI 10.1137/0906018
Stephen Demko, William F. Moss, and Philip W. Smith, Decay rates for inverses of band matrices, Math. Comp. 43 (1984), no. 168, 491–499. MR 758197, DOI 10.1090/S0025-5718-1984-0758197-9
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), no. 194, 437–461. MR 1066831, DOI 10.1090/S0025-5718-1991-1066831-5
Wolfgang Hackbusch, Multigrid methods and applications, Springer Series in Computational Mathematics, vol. 4, Springer-Verlag, Berlin, 1985. MR 814495, DOI 10.1007/978-3-662-02427-0

Matrix computations

Rob Kettler, Analysis and comparison of relaxation schemes in robust multigrid and preconditioned conjugate gradient methods, Multigrid methods (Cologne, 1981) Lecture Notes in Math., vol. 960, Springer, Berlin-New York, 1982, pp. 502–534. MR 685786
David E. Keyes and William D. Gropp, A comparison of domain decomposition techniques for elliptic partial differential equations and their parallel implementation, SIAM J. Sci. Statist. Comput. 8 (1987), no. 2, S166–S202. Parallel processing for scientific computing (Norfolk, Va., 1985). MR 879402, DOI 10.1137/0908020
Lily Kolotilina and Ben Polman, On incomplete block factorization methods of generalized SSOR type for $H$-matrices, Linear Algebra Appl. 177 (1992), 111–136. MR 1195973, DOI 10.1016/0024-3795(92)90320-A
Gérard Meurant, The block preconditioned conjugate gradient method on vector computers, BIT 24 (1984), no. 4, 623–633. MR 764833, DOI 10.1007/BF01934919
Ben Polman, Incomplete blockwise factorizations of (block) $H$-matrices, Linear Algebra Appl. 90 (1987), 119–132. MR 884115, DOI 10.1016/0024-3795(87)90310-7
Richard S. Varga, Matrix iterative analysis, Prentice-Hall, Inc., Englewood Cliffs, N.J., 1962. MR 0158502
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), no. 3, 277–296 (English, with German summary). MR 1045063, DOI 10.1007/BF02242922
P. S. Vassilevski, Algorithms for construction of preconditioners based on incomplete block-factorizations of the matrix, Internat. J. Numer. Methods Engrg. 27 (1989), no. 3, 609–622. MR 1036927, DOI 10.1002/nme.1620270312
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), no. 6, 1287–1313. MR 1185647, DOI 10.1137/0913073
Gabriel Wittum, An ILU-based smoothing correction scheme, Parallel algorithms for partial differential equations (Kiel, 1990) Notes Numer. Fluid Mech., vol. 31, Friedr. Vieweg, Braunschweig, 1991, pp. 228–240. MR 1167881