×

A grid-based multilevel incomplete LU factorization preconditioning technique for general sparse matrices. (English) Zbl 1024.65037

Summary: We design a grid-based multilevel incomplete LU preconditioner (GILUM) for solving general sparse matrices. This preconditioner combines a high accuracy ILU factorization with an algebraic multilevel recursive reduction. The GILUM preconditioner is a compliment to the domain-based multilevel block ILUT preconditioner. A major difference between these two preconditioners is the way that the coarse level nodes are chosen.
The approach of GILUM is analogous to that of the algebraic multigrid method. The GILUM approach avoids some controversial issues in the algebraic multigrid method such as how to construct the interlevel transfer operators and how to compute the coarse level operator. Numerical experiments are conducted to compare GILUM with other ILU preconditioners.

MSC:

65F35 Numerical computation of matrix norms, conditioning, scaling
65N55 Multigrid methods; domain decomposition for boundary value problems involving PDEs
65F10 Iterative numerical methods for linear systems
65F50 Computational methods for sparse matrices
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Axelsson, O.; Vassilevski, P. S., Algebraic multilevel preconditioning methods, SIAM J. Numer. Anal., 27, 6, 1569-1590 (1990) · Zbl 0715.65091
[2] V.A. Bandy, Black box multigrid for convection-diffusion equations on advanced computers, Ph.D. Thesis, University of Colorado, Denver, CO, 1996; V.A. Bandy, Black box multigrid for convection-diffusion equations on advanced computers, Ph.D. Thesis, University of Colorado, Denver, CO, 1996
[3] Bank, R. E.; Smith, R. K., The incomplete factorization multigraph algorithm, SIAM J. Sci. Comput., 20, 4, 1349-1364 (1999) · Zbl 0931.65021
[4] Bank, R. E.; Wagner, C., Multilevel ILU decomposition, Numer. Math., 82, 4, 543-576 (1999) · Zbl 0938.65063
[5] R.E. Bank, J. Xu, The hierarchical basis multigrid method and incomplete LU decomposition, in: D. Keyes, J. Xu (Eds.), Proceedings of the Seventh International Symposium on Domain Decomposition Methods for Partial Differential Equations, AMS, Providence, RI, 1994, pp. 163-173; R.E. Bank, J. Xu, The hierarchical basis multigrid method and incomplete LU decomposition, in: D. Keyes, J. Xu (Eds.), Proceedings of the Seventh International Symposium on Domain Decomposition Methods for Partial Differential Equations, AMS, Providence, RI, 1994, pp. 163-173 · Zbl 0817.65103
[6] Botta, E. F.F.; Wubs, F. W., Matrix renumbering ILU: an effective algebraic multilevel ILU preconditioner for sparse matrices, SIAM J. Matrix Anal. Appl., 20, 4, 1007-1026 (1999) · Zbl 0937.65057
[7] Braess, D., Towards algebraic multigrid for elliptic problems of second order, Computing, 55, 4, 379-393 (1995) · Zbl 0844.65088
[8] Brandt, A.; McCormick, S.; Ruge, J., Algebraic multigrid (AMG) for sparse equations, (Evans, D. J., Sparsity and its Applications (Loughborough 1983) (1985), Cambridge University Press: Cambridge University Press Cambridge, MA), 257-284 · Zbl 0548.65014
[9] Brezina, M.; Cleary, A. J.; Falgout, R. D.; Henson, V. E.; Jones, J. E.; Manteuffel, T. A.; McCormick, S. F.; Ruge, J. W., Algebraic multigrid based on element interpolation (AMGe), SIAM J. Sci. Comput., 22, 5, 1570-1592 (2000) · Zbl 0991.65133
[10] T.F. Chan, S. Go, J. Zou, Multilevel domain decomposition and multigrid methods for unstructured meshes: algorithms and theory, Technical Report CAM 95-24, Department of Mathematics, UCLA, Los Angeles, CA, 1995; T.F. Chan, S. Go, J. Zou, Multilevel domain decomposition and multigrid methods for unstructured meshes: algorithms and theory, Technical Report CAM 95-24, Department of Mathematics, UCLA, Los Angeles, CA, 1995
[11] Chang, Q. S.; Wong, Y. S.; Feng, L. Z., New interpolation formulas of using geometric assumptions in the algebraic multigrid method, Appl. Math. Comput., 50, 2-3, 223-254 (1992) · Zbl 0766.65025
[12] Chang, Q. S.; Wong, Y. S.; Fu, H. Q., On the algebraic multigrid method, J. Comput. Phys., 125, 279-292 (1996) · Zbl 0857.65037
[13] Chapman, A.; Saad, Y.; Wigton, L., High-order ILU preconditioners for CFD problems, Int. J. Numer. Meth. Fluids, 33, 6, 767-788 (2000) · Zbl 0959.76077
[14] Chow, E.; Heroux, M. A., An object-oriented framework for block preconditioning, ACM Trans. Math. Software, 24, 2, 159-183 (1998) · Zbl 0930.65052
[15] Chow, E.; Saad, Y., Experimental study of ILU preconditioners for indefinite matrices, J. Comput. Appl. Math., 86, 2, 387-414 (1997) · Zbl 0891.65028
[16] Cleary, A. J.; Falgout, R. D.; Henson, V. E.; Jones, J. E.; Manteuffel, T. A.; McCormick, S. F.; Miranda, G. N., J.W. Ruge. Robustness and scalability of algebraic multigrid, SIAM J. Sci. Comput., 21, 5, 1886-1908 (2000) · Zbl 0959.65049
[17] Davis, T., University of Florida sparse matrix collection, NA Digest, 97, 23 (1997)
[18] D’Azevedo, E. F.; Forsyth, F. A.; Tang, W. P., Ordering methods for preconditioned conjugate gradient methods applied to unstructured grid problems, SIAM J. Matrix Anal. Appl., 13, 944-961 (1992) · Zbl 0760.65028
[19] de Zeeuw, P. M., Matrix-dependent prolongations and restrictions in a blackbox multigrid solver, J. Comput. Appl. Math., 33, 1-25 (1990) · Zbl 0717.65099
[20] Dendy, J. E., Black box multigrid, J. Comput. Phys., 48, 3, 366-386 (1982) · Zbl 0495.65047
[21] Duff, I. S.; Meurant, G. A., The effect of reordering on preconditioned conjugate gradients, BIT, 29, 635-657 (1989) · Zbl 0687.65037
[22] Dutto, L. C., The effect of reordering on the preconditioned GMRES algorithm for solving the compressible Navier-Stokes equations, Int. J. Numer. Meth. Engrg., 36, 3, 457-497 (1993) · Zbl 0767.76026
[23] Elman, H. C., A stability analysis of incomplete LU factorization, Math. Comput., 47, 175, 191-217 (1986) · Zbl 0621.65024
[24] Elman, H. C., Approximate Schur complement preconditioners on serial and parallel computers, SIAM J. Sci. Statist. Comput., 10, 3, 581-605 (1989) · Zbl 0678.65018
[25] George, J. A.; Liu, J. W.H., The evolution of the minimum degree ordering algorithm, SIAM Rev., 31, 1-19 (1989) · Zbl 0671.65024
[26] Griebel, M.; Neunhoeffer, T., Parallel point- and domain-oriented multilevel methods for elliptic PDEs on workstation networks, J. Comput. Appl. Math., 66, 267-278 (1996) · Zbl 0858.65122
[27] 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. Comput., 31, 148-162 (1977) · Zbl 0349.65020
[28] Oosterlee, C. W.; Washio, T., An evaluation of parallel multigrid as a solver and a preconditioner for singularly perturbed problems, SIAM J. Sci. Comput, 19, 1, 87-110 (1998) · Zbl 0913.65109
[29] A. Ramage, A multigrid preconditioner for stabilised discretizations of advection-diffusion problems, Technical Report 33, Department of Mathematics, University of Strathclyde, Glasgow, UK, 1998; A. Ramage, A multigrid preconditioner for stabilised discretizations of advection-diffusion problems, Technical Report 33, Department of Mathematics, University of Strathclyde, Glasgow, UK, 1998 · Zbl 0939.65135
[30] A.A. Reusken, Approximate cyclic reduction preconditioning, Technical Report RANA 97-02, Department of Mathematics and Computing Science, Eindhoven University of Technology, The Netherlands, 1997; A.A. Reusken, Approximate cyclic reduction preconditioning, Technical Report RANA 97-02, Department of Mathematics and Computing Science, Eindhoven University of Technology, The Netherlands, 1997
[31] J.W. Ruge, K. Stüben, Algebraic multigrid, in: S. McCormick (Ed.), Multigrid Methods, Frontiers in Appl. Math., SIAM, Philadelphia, PA, 1987, pp. 73-130 (Chapter 4); J.W. Ruge, K. Stüben, Algebraic multigrid, in: S. McCormick (Ed.), Multigrid Methods, Frontiers in Appl. Math., SIAM, Philadelphia, PA, 1987, pp. 73-130 (Chapter 4)
[32] Saad, Y., ILUT: a dual threshold incomplete LU preconditioner, Numer. Linear Algebra Appl., 1, 4, 387-402 (1994) · Zbl 0838.65026
[33] Saad, Y., ILUM: a multi-elimination ILU preconditioner for general sparse matrices, SIAM J. Sci. Comput., 17, 4, 830-847 (1996) · Zbl 0858.65029
[34] Saad, Y., Iterative Methods for Sparse Linear Systems (1996), PWS Publishing: PWS Publishing New York · Zbl 1002.65042
[35] Y. Saad, M. Sosonkina, J. Zhang, Domain decomposition and multi-level type techniques for general sparse linear systems, in: J. Mandel, C. Farhat, X.-C. Cai (Eds.), Domain Decomposition Methods 10, Contemporary Mathematics, vol. 218, AMS, Providence, RI, 1998, pp. 174-190; Y. Saad, M. Sosonkina, J. Zhang, Domain decomposition and multi-level type techniques for general sparse linear systems, in: J. Mandel, C. Farhat, X.-C. Cai (Eds.), Domain Decomposition Methods 10, Contemporary Mathematics, vol. 218, AMS, Providence, RI, 1998, pp. 174-190 · Zbl 0909.65020
[36] Saad, Y.; Zhang, J., BILUM: block versions of multielimination and multilevel ILU preconditioner for general sparse linear systems, SIAM J. Sci. Comput., 20, 6, 2103-2121 (1999) · Zbl 0956.65026
[37] Saad, Y.; Zhang, J., BILUTM: a domain-based multilevel block ILUT preconditioner for general sparse matrices, SIAM J. Matrix Anal. Appl., 21, 1, 279-299 (1999) · Zbl 0942.65045
[38] Saad, Y.; Zhang, J., Diagonal threshold techniques in robust multi-level ILU preconditioners for general sparse linear systems, Numer. Linear Algebra Appl., 6, 4, 257-280 (1999) · Zbl 0982.65057
[39] Y. Saad, J. Zhang, A multi-level preconditioner with applications to the numerical simulation of coating problems, in: D.R. Kincaid, A.C. Elster (Eds.), Iterative Methods in Scientific Computing II, IMACS, New Brunswick, NJ, 1999, pp. 437-449; Y. Saad, J. Zhang, A multi-level preconditioner with applications to the numerical simulation of coating problems, in: D.R. Kincaid, A.C. Elster (Eds.), Iterative Methods in Scientific Computing II, IMACS, New Brunswick, NJ, 1999, pp. 437-449
[40] Saad, Y.; Zhang, J., Enhanced multilevel block ILU preconditioning strategies for general sparse linear systems, J. Comput. Appl. Math., 130, 99-118 (2001) · Zbl 1010.65014
[41] Starke, G., Multilevel minimal residual methods for nonsymmetric elliptic problems, Numer. Linear Algebra Appl., 3, 5, 351-367 (1996) · Zbl 0906.65116
[42] O. Tatebe, The multigrid preconditioned conjugate gradient method, in: N.D. Melson, T.A. Manteuffel, S.F. McCormick (Eds.), Proceedings of the Sixth Copper Mountain Conference on Multigrid Methods, Copper Mountain, CO, 1993, pp. 621-634; O. Tatebe, The multigrid preconditioned conjugate gradient method, in: N.D. Melson, T.A. Manteuffel, S.F. McCormick (Eds.), Proceedings of the Sixth Copper Mountain Conference on Multigrid Methods, Copper Mountain, CO, 1993, pp. 621-634 · Zbl 0939.65548
[43] Wagner, C.; Kinzelbach, W.; Wittum, G., Schur-complement multigrid – a robust method for groundwater flow and transport problems, Numer. Math., 75, 523-545 (1997) · Zbl 0876.76066
[44] Zhang, J., Two-grid analysis of minimal residual smoothing as a multigrid acceleration technique, Appl. Math. Comput., 96, 1, 27-45 (1998) · Zbl 0943.65150
[45] Zhang, J., Preconditioned Krylov subspace methods for solving nonsymmetric matrices from CFD applications, Comput. Meth. Appl. Mech. Engrg., 189, 3, 825-840 (2000) · Zbl 0991.76067
[46] Zhang, J., Sparse approximate inverse and multilevel block ILU preconditioning techniques for general sparse matrices, Appl. Numer. Math., 35, 1, 89-108 (2000)
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.