Abstract
In this chapter, we give a brief overview of a particular class of preconditioners known as incomplete factorizations. They can be thought of as approximating the exact LU factorization of a given matrix A (e.g., computed via Gaussian elimination) by disallowing certain fill-ins. As opposed to other PDE-based preconditioners such as multigrid and domain decomposition, this class of preconditioners is primarily algebraic in nature and can in principle be applied to general sparse matrices. When applied to PDE problems, they are usually not optimal in the sense that the condition number of the preconditioned system grows as the mesh size h is reduced, although usually at a slower rate than for the unpreconditioned system. On the other hand, they are often quite robust with respect to other more algebraic features of the problem such as rough and anisotropic coefficients and strong convection terms.
We will describe the basic ILU and (modified) MILU preconditioners. Then we will review briefly several variants: more fill, relaxed ILU, shifted ILU, ILQ, as well as block and multilevel variants. We will also touch on a related class of approximate factorization methods which arise more directly from approximating a partial differential operator by a product of simpler operators.
Finally, we will discuss parallelization aspects, including reordering, series expansion, and domain decomposition techniques. Generally, this class of preconditioner does not possess a high degree of parallelism in its original form. Re-ordering and approximation by truncating certain series expansion will increase the parallelism, but usually with a deterioration in convergence rate. Domain decomposition offers a compromise.
The work of this author was partially supported by the National Science Foundation under contract ASC 92-01266, the Army Research Office under contracts DAAL03-91-G-0150 and DAAL03-91-C-0047 (Univ. Tenn. subcontract ORA4466.04 Amendment 1), and the Office of Naval Research under contract ONR-N00014-92-J-1890.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Ashcraft, C. and Grimes, R., 1988. “On vectorizing incomplete factorizations and SSOR preconditioners,” SIAM J. Sci. Stat. Comp. 9, pp. 122–151.
Axelsson, O., 1972. “A generalized SSOR method,” BIT 12, pp. 443–467.
Axelsson, O., 1984. “A survey of vectorizable preconditioning methods for large scale finite element matrix problems,” in Colloquium topics in applied numerical analysis, J. G. Verwer, ed., CWI Syllabi 4&5, Amsterdam.
Axelsson, O., 1985. “Incomplete block matrix factorization preconditioning methods. The ultimate answer?” J. Comp. Appl. Math. 12&13, pp. 3–18.
Axelsson, O., 1986. “A general incomplete block-matrix factorization method,” Lin. Alg. Appl. 74, pp. 179–190.
Axelsson, O., 1992. “Bounds of eigenvalues of preconditioners matrices,” SIAM J. Matrix Anal. Applic. 13, pp. 847–862.
Axelsson, O., 1994. Iterative solution methods, Cambridge Univ. Press, Cambridge.
Axelsson, O. and Barker, A. V., 1984. Finite element solution of boundary value problems. Theory and computation, Academic Press, New York.
Axelsson, O. and Eijkhout, V., 1989. “Vectorizable preconditioned for elliptic difference equations in three space dimensions,” J. Comp. Appl. Math. 27, pp. 299–321.
Axelsson, O. and Lindskog, G., 1986. “On the eigenvalue distribution of a class of preconditioning matrices,” Numer. Math. 48, pp. 479–498.
Axelsson, O. and Munksgaard, N., 1983. “Analysis of incomplete factorizations with fixed storage allocation,” in Preconditioning Methods — Theory and Applications, D. Evans, ed., Gordon and Breach, New York, pp. 265–293.
Axelsson, O. and Polman, B., 1986. “On approximate factorization methods for block-matrices suitable for vector and parallel processors,” Lin. Alg. Appl. 77, pp. 3–26.
Axelsson, O. and Polman, B., 1988. “A robust preconditioner based on algebraic substructuring and two-level grids,” in Robust multigrid methods, W. Hackbusch, ed., Notes on Numerical Fluid Mechanics 23, Vieweg, Braunschweig, pp. 1–26.
Bank, R., Dupont, T., and Yserentant, H., 1988. “The hierarchical basis multigrid method,” Numer. Math. 52, pp. 427–458.
Bank, R. E. and Xu, J., 1994. “The hierarchical basis multigrid method and incomplete LU decomposition,” Technical report, U.C. San Diego, Dept. of Math.
Barrett, R., Berry, M., Chan, T. F., Demmel, J., Donato, J., Dongarra, J., Eijkhout, V., Pozo, R., Romine, C., and Van der Vorst, H., 1994. Templates for the solution of linear systems: building blocks for iterative methods, SIAM, Philadelphia.
Barszcz, E., Fatoohi, R., Venkatakrishnan, V., and Weeratunga, S., 1994. “Triangular systems for CFD applications on parallel architectures,” Technical report, NAS Applied Research Branch, NASA Ames Research Center.
Beam, R. M. and Warming, R. F., 1978. “An implicit scheme for the compressible Navier-Stokes equations,” AIAA J. 16, pp. 393–402.
Beauwens, R., 1973a. “On the analysis of factorization procedures,” Technical report, Internal report, Univ. Libre de Bruxelles.
Beauwens, R., 1973b. “An order relation between factorization iterative methods,” Technical report, Internal report, Univ. Libre de Bruxelles.
Beauwens, R., 1979. “Factorization iterative methods, M-operators and H-operators,” Numer. Math. 31, pp. 335–357.
Beauwens, R., 1989. “Approximate factorizations with S/P consistently ordered M-factors,” BIT 29, pp. 658–681.
Beauwens, R. and Ben Bouzid, M., 1988. “Existence and conditioning properties of sparse approximate block factorizations,” SIAM Numer. Anal. 25, pp. 941–956.
Beauwens, R. and Quenon, L., 1976. “Existence criteria for partial matrix factorizations in iterative methods,” SIAM J. Numer. Anal. 13, pp. 615–643.
Berryman, H., Saltz, J., Gropp, W., and Mirchandaney, R., 1990. “Krylov methods preconditioned with incompletely factored matrices on the CM-2,” J. Par. Dist. Comp. 8, pp. 186–190.
Brand, C. and Heinemann, Z. E., 1989. “A new iterative solution technique for reservoir simulation equations on locally refined grids,” Soc. Petroleum Eng., TR 18410.
Buleev, N. I., 1960. “A numerical method for the solution of two-dimensional and three-dimensional equations of diffusion,” Math. Sb. 51, pp. 227–238.
Chan, T. F., 1990. “Hierarchical algorithms and architectures for parallel scientific computing,” in Proc. ACM Int. Conf. Supercomputing, Amsterdam, pp. 318–329.
Chan, T. F., 1991. “Fourier analysis of relaxed incomplete factorization preconditioners,” SIAM J. Sci. Stat. Comp. 12, pp. 668–680.
Chan, T. F. and Elman, H., 1989. “Fourier analysis of iterative methods for elliptic problems,” SIAM Review 31, pp. 20–49.
Chan, T. F. and Goovaerts, D., 1990. “A note on the efficiency of domain decomposed incomplete factorizations,” SIAM J. Sci. Stat Comp. 11, pp. 794–803.
Chan, T. F., Kuo, Jay C. C., and Tong, C. H., 1989. “Parallel elliptic preconditioners: Fourier analysis and performance on the Connection Machine,” Comp. Phys. Commun. 53, pp. 237–252.
Chan, T. F. and Mathew, T., 1992. “The interface probing technique in domain decomposition,” SIAM J. Matrix Anal. Applic. 13, pp. 212–238.
Chan, T. F. and Meurant, G., 1990. “Fourier analysis of block preconditioners,” Technical Report CAM 90-04, Dept. of Math., UCLA, Los Angeles.
Chan, T. F. and Resasco, D., 1985. “A survey of preconditioners for domain decomposition,” Technical Report DCS/RR-414, Dept. of Comp. Sci., Yale Univ.
Chan, T. F. and Vassilevski, P., 1995. “A framework for block ILU factorizations using block size reduction,” Math. Comp., 64, pp. 129–156.
Ciarlet, P., Jr., 1994. “Repeated red-black ordering: a new approach,” Numer. Alg., 7, pp. 295–324.
Clift, S. S. and Tang, W. P., 1994. “Weighted graph based ordering techniques for preconditioned conjugate gradient methods,” Technical report, Dept. of Comp. Sci., Univ. of Waterloo.
Concus, P., Golub, G. H., and Meurant, G., 1985. “Block preconditioning for the conjugate gradient method,” SIAM J. Sci. Stat. Comp. 6, pp. 220–252.
D’Azevedo, E. F., Forsyth, P. A., and Tang, W. P., 1992. “Drop tolerance preconditioning for incompressible viscous flow,” Int. J. Comp. Math. 44, pp. 301–312.
D’Azevedo, E. F., Forsyth, P. A., and Tang, W. P., 1992. “Ordering methods for preconditioned conjugate gradient methods applied to unstructured grid problems,” SIAM J. Matrix Anal. Applic. 13, pp. 944–961.
de Sturler, E., 1994. “IBLU preconditioners based on overlap** subdomains,” in Domain decomposition methods for partial differential equations (Proc. 7th Int. Symp.), D. E. Keyes and J. Xu, eds., AMS, Providence, pp. 395–400.
Demmel, J. W., Heath, M. T., and Van der Vorst, H., 1993. “Parallel linear algebra,” Acta Numerica 2, pp. 111–198.
Doi, S., 1991. “On parallelism and convergence of incomplete LU factorizations,” App. Numer. Math. 7, pp. 417–436.
Doi, S. and Hoshi, A., 1992. “Large numbered multicolor MILU preconditioning on SX-3/14,” Int. J. Comp. Math. 44, pp. 143–152.
Doi, S. and Lichnewsky, A., 1991. “An ordering theory of incomplete LU factorizations on regular grids,” INRIA Report 1452, INRIA, Rocquencourt, France.
Doi, S. and Lichnewsky, A., 1991. “A graph theory approach for analyzing the effects of ordering on ILU preconditioning,” Technical Report 1452, INRIA, Rocquencourt, France.
Donato, J. M., 1991. Iterative methods for scalar and coupled systems of elliptic equations, Ph.D. thesis, Dept. of Math., Univ. Calif. at Los Angeles.
Donato, J. M. and Chan, T. F., 1992. “Fourier analysis of incomplete factorization preconditioners for three-dimensional anisotropic problems,” SIAM J. Sci. Stat. Comp. 13, pp. 319–338.
Dongarra, J. J., Duff, I. S., Sorensen, D. C., and Van der Vorst, Henk A., 1991. Solving Linear Systems on Vector and Shared Memory Computers, SIAM, Philadelphia.
Dubois, D. F., Greenbaum, A., and Rodrigue, G. H., 1979. “Approximating the inverse of a matrix for use in iterative algorithms on vector processors,” Computing 22, pp. 257–268.
Duff, I. S. and Meurant, G. A., 1989. “The effect of ordering on preconditioned conjugate gradients,” BIT 29, pp. 635–657.
Dupont, T., Kendall, R., and Rachford, H., 1968. “An approximate factorization procedure for solving self-adjoint elliptic difference equations,” SIAM J. Numer. Anal. 5, pp. 559–573.
Eijkhout, V., 1991. “Analysis of parallel incomplete point factorizations,” Lin. Alg. Appl. 154-156, pp. 723–740.
Eijkhout, V., 1992. “Beware of unperturbed modified incomplete point factorizations,” in Proc. IMACS Int. Symp. on Iterative Methods in Linear Algebra, Brussels, R. Beauwens and P. de Groen, eds., IMACS, Brunswick.
Eisenstat, S. C., 1981. “Efficient implementation of a class of preconditioned conjugate gradient methods,” SIAM J. Sci. Stat. Comp. 2, pp. 1–4.
Elman, H. and Agrón, E., 1989. “Ordering techniques for the preconditioned conjugate gradient method on parallel computers,” Comp. Phys. Comm. 53, pp. 253–269.
Elman, H. C., 1986. “A stability analysis of incomplete LU factorization,” Math. Comp. 47, 191–217.
Evans, D. J., 1968. “The use of pre-conditioning in iterative methods for solving linear equations with symmetric positive definite matrices,” J. Inst. Maths. Applics. 4, pp. 295–314.
George, A. and Liu, J., 1981. Computer solution of large sparse positive definite systems, Prentice-Hall, Englewood Cliffs.
Golub, G., Greenbaum, A., and Luskin, M., eds., 1993. Recent advances in iterative methods, Springer Verlag, Berlin.
Golub, G. H. and Van Loan, C. F., 1989. Matrix Computations, second edition, Johns Hopkins University Press, Baltimore.
Gustafsson, I., 1978. “A class of first-order factorization methods,” BIT 18, pp. 142–156.
Gustafsson, I., 1983. “Modified incomplete Cholesky (MIC) methods,” in Preconditioning Methods — Theory and Applications, D. Evans, ed., Gordon and Breach, New York, pp. 265–293.
Hackbusch, W., 1994. Iterative solution of large sparse linear systems of equations, Applied Math. Sci. Series, No. 95, Springer Verlag, Berlin.
Hackbusch, W. and Wittum, G., eds., 1993. Incomplete Decompositions (ILU) — Algorithms, Theory, and Applications, Vieweg, Braunschweig.
Il’in, V. P., 1988. “Incomplete factorization methods,” Sov. J. Numer. Anal Math. Modelling 3, pp. 179–198.
Jameson, A. and Türkei, E., 1981. “Implicit schemes and LU decomposition, ” Math. Comp. 37, pp. 385–397.
Kershaw, D. S., 1978. “The incomplete Cholesky-conjugate gradient method for the iterative solution of systems of linear equations, ” J. Comp. Phys. 26, pp. 43–65.
Kettler, R., 1982. “Analysis and comparison of relaxation schemes in robust multigrid and preconditioned conjugate gradient methods,” in Multigrid methods, W. Hackbusch and U. Trottenberg, eds. Lecture Notes in Mathematics 1228, Springer Verlag, Berlin, pp. 502–534.
Kuo, J. C. C. and Chan, T. F., 1990. “Two-color Fourier analysis of iterative algorithms for elliptic problems with red/black ordering,” SIAM J. Sci. Stat. Comp. 11, pp. 767–793.
Magolu, M. M., 1992. “Modified block-approximate factorization strategies,” Numer. Math. 61, pp. 91–110.
Magolu, M. M., 1993. “Analytical bounds for block approximate factorization methods,” Lin. Alg. Appl. 179, pp. 33–57.
Manteuffel, T. A., 1980. “An incomplete factorization technique for positive definite linear systems,” Math. Comp. 34, pp. 473–497.
Meijerink, J. A. and Van der Vorst, H. A., 1977. “An iterative solution method for linear systems of which the coefficient matrix is a symmetric M-matrix,” Math. Comp. 31, pp. 148–162.
Meijerink, J. A. and Van der Vorst, H. A., 1981. “Guidelines for the usage of incomplete decompositions in solving sets of linear equations as they occur in practical problems,” J. Comp. Phys. 44, pp. 134–155.
Meurant, G., 1984. “The block preconditioned conjugate gradient method on vector computers,” BIT 24, pp. 623–633.
Meurant, G., 1988. “Domain decomposition methods for partial differential equations on parallel computers,” Int. J. Super-comput. Applics. 2, pp. 5–12.
Notay, Y., 1989. “Solving positive (semi)definite linear systems by preconditioned iterative methods,” in Preconditioned Conjugate Gradient Methods, O. Axelsson and L. Yu. Kolotilina, eds., Lecture Notes in Mathematics 1457, Springer Verlag, Berlin, pp. 105–125.
Notay, Y., 1994. “DRIC: a dynamic version of the RIC method,” Numer. Lin. Alg. Applics., 1, pp. 511–532.
Oliphant, T. A., 1961. “An implicit numerical method for solving two-dimensional time-dependent diffusion problems,” Quart. Appl. Math. 19, pp. 221–229.
Oliphant, T. A., 1962. “An extrapolation process for solving linear systems,” Quart. Appl. Math. 20, pp. 257–267.
Ortega, J. M., 1988. Introduction to vector and parallel solution of linear systems, Plenum Press, New York.
Osterby, O. and Zlatev, Z., 1983. Direct methods for sparse matrices, Lecture Notes in Computer Science 157, Springer Verlag, Berlin.
Pommerell, C., 1992. Solution of large unsymmetric systems of linear equations, Series in Micro-electronics 17, Hartung-Gorre, Konstanz.
Radicati di Brozolo, G. and Vitaletti, M., 1986. “Sparse matrix-vector product and storage representations on the IBM3090 with Vector Facility,” Technical Report 513-4098, IBM-ECSEC, Rome.
Saad, Y., 1988. “Preconditioning techniques for indefinite and non-symmetric linear systems,”, J. Comp. Appl. Math. 24, pp. 89–105.
Schlichting, J. and Van der Vorst, H. A., 1989. “Solving 3D block bidiagonal linear systems on vector computers,” J. Comp, Appl. Math. 27, pp. 323–330.
Stone, H., 1968. “Iterative solution of implicit approximations of multidimensional partial differential equations,” SIAM J. Numer. Anal. 5, pp. 530–558.
Tong, C. H., 1989. “The preconditioned conjugate gradient method on the Connection Machine,” Scientific Application of the Connection Machine, H. Simon, ed., World Scientific Press, pp. 188–213.
Tong, C. H., 1990. Parallel preconditioned conjugate gradient methods for elliptic partial differential equations, Ph.D. thesis, Dept. of Comp. Sci., Univ. of Calif. at Los Angeles.
van der Ploeg, A., 1994. Preconditioning for sparse matrices with applications, Ph.D. thesis, Rijksuniversiteit Groningen, The Netherlands.
Van der Vorst, H., 1981. “Iterative solution methods for certain sparse linear systems with a nonsymmetric matrix arising from PDE-problems,” J. Comp. Phys. 44, pp. 1–19.
Van der Vorst, H., 1990. “The convergence behaviour of preconditioned CG and CGS in the presence of rounding errors,” in Preconditioned conjugate gradient methods, O. Axelsson and L. Y. Kolotilina, eds., Lecture notes in Mathematics 1457, Springer Verlag, Berlin.
Van der Vorst, H. A., 1987. “Large tridiagonal and block tridiagonal linear systems on vector and parallel computers,” Parallel Computing 5, pp. 45–54.
Van der Vorst, H. A., 1989. “ICCG and related methods for 3D problems on vector computers,” Computer Physics Communications 53, pp. 223–235.
Van der Vorst, H. A., 1982. “A vectorizable variant of some ICCG methods,” SIAM J. Sci. Stat. Comp. 3, pp. 350–356.
Van der Vorst, H. A., 1989. “High performance preconditioning,” SIAM J. Sci. Stat. Comp. 10, pp. 1174–1185.
Van der Vorst, Henk A. and Sleijpen, Gerard G. L., 1993. “The effect of incomplete decomposition preconditioning on the convergence of conjugate gradients,” in Incomplete Decompositions (ILU) — Algorithms, Theory, and Applications, W. Hackbusch and G. Wittum, eds., Notes on Numerical Fluid Dynamics 41, Vieweg, Braunschweig, pp. 179–187.
Varga, R. S., 1960. “Factorization and normalized iterative methods,” in Boundary problems in differential equations, R. E. Langer, ed., Univ. of Wisconsin Press, Madison, pp. 121–142.
Varga, R. S., 1962. Matrix Iterative Analysis, Prentice-Hall Inc., Englewood Cliffs, NJ.
Varga, R. S., Saff, E. B., and Mehrman, V., 1980. “Incomplete factorization of matrices and connection with h-matrices,” SIAM J. Numer. Anal 17, pp. 787–793.
Washio, T. and Hayami, K., 1994. “Parallel block preconditioning based on SSOR and MILU,” Numer. Lin. Alg. with Applic., 1, pp. 533–553.
Wesseling, P., 1982a. “A robust and efficient multigrid method,” in Multigrid Methods W. Hackbusch and U. Trottenberg, eds., Lecture Notes in Mathematics 1228, Springer Verlag, Berlin, pp. 614–630.
Wesseling, P., 1982b. “Theoretical and practical aspects of a multigrid method,” SIAM J. Sci. Stat. Comp. 3, pp. 387–407.
Wittum, G., 1989. “On the robustness of ILU smoothing,” SIAM J. Sci. Stat. Comp. 10, pp. 699–717.
Wittum, G., 1991. “An ILU-based smoothing correction scheme,” in Parallel algorithms for PDEs, W. Hackbusch, ed., Notes on Numerical Fluid Mechanics 31, Vieweg, Braunschweig, pp. 228–240.
Wosnicki, Z., 1973. Two-sweep iterative methods for solving large linear systems and their application to the numerical solution of multi-group multi-dimensional neutron diffusion equation” Ph.D. thesis, Inst. of Nuclear Research, Swierk.
Young, D. P., Melvin, R. G., Johnson, F. T., Bussoletti, J. E., Wigton, L. B., and Samanth, S. S., 1989. “Application of sparse matrix solvers as effective preconditioners,” SIAM J. Sci. Stat. Comp. 10, pp. 1186–1199.
Zlatev, Z., 1991. Computational methods for general sparse matrices, Kluwer, Dordrecht.
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 1997 Springer Science+Business Media Dordrecht
About this chapter
Cite this chapter
Chan, T.F., Van der Vorst, H.A. (1997). Approximate and Incomplete Factorizations. In: Keyes, D.E., Sameh, A., Venkatakrishnan, V. (eds) Parallel Numerical Algorithms. ICASE/LaRC Interdisciplinary Series in Science and Engineering, vol 4. Springer, Dordrecht. https://doi.org/10.1007/978-94-011-5412-3_6
Download citation
DOI: https://doi.org/10.1007/978-94-011-5412-3_6
Publisher Name: Springer, Dordrecht
Print ISBN: 978-94-010-6277-0
Online ISBN: 978-94-011-5412-3
eBook Packages: Springer Book Archive