Experimental study of ILU preconditioners for indefinite matrices. (English) Zbl 0891.65028
Incomplete LU factorization preconditioners have been applied successfully for many cases of general nonsymmetric and indefinite matrices. However, for them to be useful for general matrices, there are still numerical difficulties including very small pivots, unstable triangular solvers, inaccuracy due to dropping, and zero pivots. Furthermore, these four problems usually occur together. So, there is a need to gain a better practical understanding of LU preconditioners and help improve their reliability.
This paper shows how these problems evince themselves, how these problems can be detected, and how these problems can sometimes be circumvented through pivoting, scaling, reordering, perturbing diagonal elements, and preserving symmetric structure. Numerical experiments demonstrate that the proposed techniques are efficient.
This paper shows how these problems evince themselves, how these problems can be detected, and how these problems can sometimes be circumvented through pivoting, scaling, reordering, perturbing diagonal elements, and preserving symmetric structure. Numerical experiments demonstrate that the proposed techniques are efficient.
Reviewer: Liu Xinguo (Qingdao)
MSC:
| 65F10 | Iterative numerical methods for linear systems |
| 65F50 | Computational methods for sparse matrices |
| 65F35 | Numerical computation of matrix norms, conditioning, scaling |
Keywords:
instability; incomplete LU factorization preconditioners; numerical experiments; pivoting; scaling; reorderingReferences:
| [1] | Axelsson, O., Iterative Solution Methods (1994), Cambridge University Press: Cambridge University Press Cambridge · Zbl 0795.65014 |
| [2] | Axelsson, O.; Kolotilina, L. Yu., Diagonally compensated reduction and related preconditioning methods, Numer. Linear Algebra Appl., 1, 155-177 (1994) · Zbl 0837.65023 |
| [3] | Axelsson, O.; Lindskog, G., On the eigenvalue distribution of a class of preconditioning methods, Numer. Math., 48, 479-498 (1986) · Zbl 0564.65016 |
| [4] | Axelsson, O.; Lindskog, G., On the rate of convergence of the preconditioned conjugate gradient method, Numer. Math., 48, 499-523 (1986) · Zbl 0564.65017 |
| [5] | Botta, E. F.F.; van der Ploeg, A.; Wubs, F. W., Nested grids ILU-decomposition (NGILU), J. Comp. Appl. Math., 66, 515-526 (1996) · Zbl 0858.65028 |
| [6] | Bruaset, A. M.; Tveito, A.; Winther, R., On the stability of relaxed incomplete LU factorizations, Math. Comp., 54, 701-719 (1990) · Zbl 0701.65021 |
| [7] | Buleev, N. I., (Rep. BNL-TR-551 (1973), Brookhaven National Laboratory: Brookhaven National Laboratory Upton, New York), English transl. · Zbl 0105.10401 |
| [8] | Bunch, J. R.; Kaufman, L., Some stable methods for calculating inertia and solving symmetric linear systems, Math. Comp., 31, 162-179 (1977) · Zbl 0355.65023 |
| [9] | Chan, T. F.; Van der Vorst, H. A., Approximate and incomplete factorizations, (Technical Report 871 (1994), Department of Mathematics: Department of Mathematics University of Utrecht) · Zbl 0865.65015 |
| [10] | Chapman, A.; Saad, Y.; Wigton, L., High-order ILU preconditioners for CFD problems, (Technical Report UMSI 96/14 (1996), Minnesota Supercomputer Institute, University of Minnesota: Minnesota Supercomputer Institute, University of Minnesota Minneapolis, Minnesota) · Zbl 0959.76077 |
| [11] | Chow, E.; Saad, Y., ILUS: an incomplete LU preconditioner in sparse skyline format, Internat. J. Numer. Methods Fluids, 25, 739-748 (1997) · Zbl 0896.76037 |
| [12] | D’Azevdo, E. F.; Forsyth, P. A.; Tang, W.-P., Towards a cost-effective ILU preconditioner with high level fill, BIT, 32, 442-463 (1992) · Zbl 0761.65017 |
| [13] | Duff, I. S.; Gould, N. I.M.; Reid, J. K.; Scott, J. A., The factorization of sparse indefinite matrices, IMA J. Numer. Anal., 11, 181-204 (1991) · Zbl 0739.65018 |
| [14] | Duff, I. S.; Meurant, G. A., The effect of ordering on preconditioned conjugate gradients, BIT, 29, 635-657 (1989) · Zbl 0687.65037 |
| [15] | Dutto, L. C., The effect of ordering on preconditioned GMRES algorithms, for solving the compressible Navier-Stokes equations, Internat. J. Numer. Methods Eng., 36, 457-497 (1993) · Zbl 0767.76026 |
| [16] | Elman, H. C., A stability analysis of incomplete LU factorizations, Math. Comp., 47, 191-217 (1986) · Zbl 0621.65024 |
| [17] | Elman, H. C., Relaxed and stabilized incomplete factorizations for non-self-adjoint linear systems, BIT, 29, 890-915 (1989) · Zbl 0694.65011 |
| [18] | Engelman, M., FIDAP: Examples Manual, Revision 6.0 (1991), Fluid Dynamics International: Fluid Dynamics International Evanston, IL |
| [19] | Engelman, M. S.; Hasbani, I., Matrix-free solution algorithms in a finite element context, (Technical Report 88-1 (1988), Fluid Dynamics International: Fluid Dynamics International Evanston, Illinois) |
| [20] | George, A.; Liu, J. W., Computer Solution of Large Sparse Positive Definite Systems (1981), Prentice-Hall: Prentice-Hall Englewood Cliffs, NJ · Zbl 0516.65010 |
| [21] | Gustafsson, I., A class of first-order factorization methods, BIT, 18, 142-156 (1978) · Zbl 0386.65006 |
| [22] | Jennings, A.; Malik, G. M., Partial elimination, J. Inst. Maths Appl., 20, 307-316 (1977) · Zbl 0367.65019 |
| [23] | Kershaw, D. S., The incomplete Cholesky-conjugate gradient method for the iterative solution of systems of linear equations, J. Comput. Phys., 26, 43-65 (1978) · Zbl 0367.65018 |
| [24] | Manteuffel, T. A., An incomplete factorization technique for positive definite linear systems, Math. Comp., 34, 473-497 (1980) · Zbl 0422.65018 |
| [25] | Meijerink, J. A.; Van der Vorst, H. A., An iterative solution method for linear systems of which the coefficient matrix is a symmetric M-matrix, Math. Comp., 31, 148-162 (1977) · Zbl 0349.65020 |
| [26] | Meijerink, J. A.; Van der Vorst, H. A., Guidelines for the usage of incomplete decompositions in solving sets of linear equations as they occur in practical problems, J. Comput. Phys., 44, 134-155 (1981) · Zbl 0472.65028 |
| [27] | Munksgaard, N., Solving sparse symmetric sets of linear equations by preconditioned conjugate gradients, ACM Trans. Math. Software, 6, 206-219 (1980) · Zbl 0438.65035 |
| [28] | Oliphant, T. A., An implicit numerical method for solving two-dimensional time-dependent diffusion problems, Quart. Appl. Math., 19, 221-229 (1961) · Zbl 0105.10702 |
| [29] | Oliphant, T. A., An extrapolation process for solving linear systems, Quart. Appl. Math., 20, 257-267 (1962) · Zbl 0109.34601 |
| [30] | Ortega, J. M., Introduction to Parallel and Vector Solution of Linear Systems (1988), Plenum Press: Plenum Press New York · Zbl 0669.65017 |
| [31] | Østerby, O.; Zlatev, Z., (Direct Methods for Sparse Matrices, Lecture Notes in Computer Science, vol. 157 (1983), Springer: Springer Berlin) · Zbl 0516.65011 |
| [32] | Parter, S. V., The use of linear graphs in Gauss elimination, SIAM Rev., 3, 119-130 (1961) · Zbl 0102.11302 |
| [33] | Robert, Y., Regular incomplete factorizations of real positive definite matrices, Linear Algebra Appl., 48, 105-117 (1982) · Zbl 0502.65018 |
| [34] | Saad, Y., Preconditioning techniques for indefinite and nonsymmetric linear systems, J. Comput. Appl. Math., 24, 89-105 (1988) · Zbl 0662.65028 |
| [35] | Saad, Y., ILUT: A dual threshold incomplete ILU factorization, Numer. Linear Algebra Appl., 1, 387-402 (1994) · Zbl 0838.65026 |
| [36] | Saad, Y., Preconditioned Krylov subspace methods for CFD applications, (Habashi, W. G., Proc. Internat. Workshop on Solution Techniques for Large-Scale CFD Problems. Proc. Internat. Workshop on Solution Techniques for Large-Scale CFD Problems, Montréal, Québec (1994)), 179-195 |
| [37] | Van der Vorst, H. A., Iterative solution methods for certain sparse linear systems with a non-symmetric matrix arising from PDE-problems, J. Comput. Phys., 44, 1-19 (1981) · Zbl 0472.65027 |
| [38] | Van der Vorst, H. A., Stabilized incomplete LU-decompositions as preconditionings for the Tchebycheff iteration, (Evans, D. J., Preconditioning methods: Analysis and Applications (1983), Gordon and Breach: Gordon and Breach New York) · Zbl 0767.65024 |
| [39] | Varga, R. S., Factorization and normalized iterative methods, (Langer, R. E., Boundary Problems in Differential Equations (1960), University of Wisconsin Press: University of Wisconsin Press Santa Barbara, CA), 121-142 · Zbl 0100.12501 |
| [40] | Varga, R. S.; Saff, E. B.; Mehrman, V., Incomplete factorizations of matrices and connections with H-matrices, SIAM J. Numer. Anal., 17, 787-793 (1980) · Zbl 0477.65020 |
| [41] | Watts-, J. W., A conjugate gradient truncated direct method for the iterative solution of the reservoir simulation pressure equation, Soc. Pet. Eng. J., 21, 345-353 (1981) |
| [42] | Wittum, G., On the robustness of ILU-smoothing, SIAM J. Sci. Stat. Comput., 10, 699-717 (1989) · Zbl 0677.65096 |
| [43] | A. Yu. Yeremin, private communication, 1995.; A. Yu. Yeremin, private communication, 1995. |
| [44] | Zlatev, Z.; Barker, V. A.; Thomsen, P. G., SLEST: a Fortran IV subroutine for solving sparse systems of linear equations, User’s guide, (Technical Report NI-78-01 (1978), Numerisk Institut: Numerisk Institut Lyngby, Denmark) |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
