×

A hierarchical low rank Schur complement preconditioner for indefinite linear systems. (English) Zbl 1392.65027


MSC:

65F08 Preconditioners for iterative methods
65F10 Iterative numerical methods for linear systems
65F50 Computational methods for sparse matrices
65N55 Multigrid methods; domain decomposition for boundary value problems involving PDEs
65Y05 Parallel numerical computation

Citations:

Zbl 1376.65036
PDF BibTeX XML Cite
Full Text: DOI

References:

[1] W. E. Arnoldi, The principle of minimized iterations in the solution of the matrix eigenvalue problem, Quart. Appl. Math., 9 (1951), pp. 17–29. · Zbl 0042.12801
[2] O. Axelsson and B. Polman, Block preconditioning and domain decomposition methods II, J. Comput. Appl. Math., 24 (1988), pp. 55–72. · Zbl 0658.65094
[3] Z. Bai and J. W. Demmel, On swapping diagonal blocks in real Schur form, Linear Algebra Appl., 186 (1993), pp. 75–95. · Zbl 0783.65030
[4] M. Bebendorf, Why finite element discretizations can be factored by triangular hierarchical matrices, SIAM J. Numer. Anal., 45 (2007), pp. 1472–1494, . · Zbl 1152.65042
[5] M. Bebendorf and T. Fischer, On the purely algebraic data-sparse approximation of the inverse and the triangular factors of sparse matrices, Numerical Linear Algebra Appl., 18 (2011), pp. 105–122, . · Zbl 1249.65055
[6] M. Benzi, Preconditioning techniques for large linear systems: A survey, J. Comput. Phys., 182 (2002), pp. 418–477. · Zbl 1015.65018
[7] M. Benzi, G. H. Golub, and J. Liesen, Numerical solution of saddle point problems, Acta Numer., 14 (2005), pp. 1–137. · Zbl 1115.65034
[8] M. Benzi, D.B. Szyld, and A. Van Duin, Orderings for incomplete factorization preconditioning of nonsymmetric problems, SIAM J. Sci. Comput., 20 (1999), pp. 1652–1670. · Zbl 0940.65033
[9] M. Benzi and M. T\ruma, A sparse approximate inverse preconditioner for nonsymmetric linear systems, SIAM J. Sci. Comput., 19 (1998), pp. 968–994. · Zbl 0930.65027
[10] D. Cai, E. Chow, Y. Saad, and Y. Xi, SMASH: Structured matrix approximation by separation and hierarchy, Preprint ys-2016-10, University of Minnesota, Minneapolis, MN, 2016.
[11] E. Chow and Y. Saad, Approximate inverse techniques for block-partitioned matrices, SIAM J. Sci. Comput., 18 (1997), pp. 1657–1675. · Zbl 0888.65035
[12] E. Chow and Y. Saad, Experimental study of ILU preconditioners for indefinite matrices, J. Comput. Appl. Math., 86 (1997), pp. 387–414. · Zbl 0891.65028
[13] E. Chow and Y. Saad, Approximate inverse preconditioners via sparse-sparse iterations, SIAM J. Sci. Comput., 19 (1998), pp. 995–1023. · Zbl 0922.65034
[14] E. C. Cyr, J. N. Shadid, R. S. Tuminaro, R. P. Pawlowski, and L. Chacón, A new approximate block factorization preconditioner for two-dimensional incompressible (reduced) resistive MHD, SIAM J. Sci. Comput., 35 (2013), pp. B701–B730. · Zbl 1273.76269
[15] P. R. Amestoy, T. A. Davis, and I. S. Duff, An approximate minimum degree ordering algorithm, SIAM J. Matrix Anal. Appl., 17 (1996), pp. 886–905. · Zbl 0861.65021
[16] P. R. Amestoy, T. A. Davis, and I. S. Duff, Algorithm 837: An approximate minimum degree ordering algorithm, ACM Trans. Math. Software, 30 (2004), pp. 381–388. · Zbl 1070.65534
[17] T. A. Davis and Y. Hu, The University of Florida Sparse Matrix Collection, ACM Trans. Math. Software, 38 (2011), 1. · Zbl 1365.65123
[18] H. Elman, V. Howle, J. Shadid, R. Shuttleworth, and R. Tuminaro, Block preconditioners based on approximate commutators, SIAM J. Sci. Comput., 27 (2006), pp. 1651–1668. · Zbl 1100.65042
[19] H. C. Elman, D. J. Silvester, and A. J. Wathen, Finite Elements and Fast Iterative Solvers, Oxford University Press, Oxford, 2005. · Zbl 1083.76001
[20] Y. A. Erlangga, C. W. Oosterlee, and C. Vuik, A novel multigrid based preconditioner for heterogeneous Helmholtz problems, SIAM J. Sci. Comput., 27 (2006), pp. 1471–1492. · Zbl 1095.65109
[21] A. George, Nested dissection of a regular finite element mesh, SIAM J. Numer. Anal., 10 (1973), pp. 345–363. · Zbl 0259.65087
[22] M. Grote and T. Huckle, Parallel preconditioning with sparse approximate inverses, SIAM J. Sci. Comput., 18 (1997), pp. 838–853. · Zbl 0872.65031
[23] W. Hackbusch, A sparse matrix arithmetic based on \(\mathcal{H}\)-matrices. Part I: Introduction to \({H}\)-matrices, Computing, 62 (1999), pp. 89–108. · Zbl 0927.65063
[24] W. Hackbusch and B. N. Khoromskij, A sparse \({H}\)-matrix arithmetic. Part II: Application to multi-dimensional problems, Computing, 64 (2000), pp. 21–47. · Zbl 0962.65029
[25] P. Hénon and Y. Saad, A parallel multistage ILU factorization based on a hierarchical graph decomposition, SIAM J. Sci. Comput., 28 (2006), pp. 2266–2293. · Zbl 1126.65028
[26] V. E. Howle and R. C. Kirby, Block preconditioners for finite element discretization of incompressible flow with thermal convection, Numerical Linear Algebra Appl., 19 (2012), pp. 427–440. · Zbl 1274.76190
[27] V. E. Howle, R. C. Kirby, and G. Dillon, Block preconditioners for coupled fluids problems, SIAM J. Sci. Comput., 35 (2013), pp. S368–S385. · Zbl 1281.65055
[28] I. C. F. Ipsen, A note on preconditioning nonsymmetric matrices, SIAM J. Sci. Comput., 23 (2001), pp. 1050–1051. · Zbl 0998.65049
[29] V. Kalantzis, Y. Xi, and Y. Saad, Beyond AMLS: Domain Decomposition with Rational Filtering, preprint, , 2017.
[30] G. Karypis and V. Kumar, A fast and high quality multilevel scheme for partitioning irregular graphs, SIAM J. Sci. Comput., 20 (1998), pp. 359–392. · Zbl 0915.68129
[31] E.-J. Lee and J. Zhang, Hybrid reordering strategies for ILU preconditioning of indefinite sparse matrices, J. Appl. Math. Comput., 22 (2006), pp. 307–316. · Zbl 1104.65042
[32] R. Li and Y. Saad, Divide and conquer low-rank preconditioners for symmetric matrices, SIAM J. Sci. Comput., 35 (2013), pp. A2069–A2095. · Zbl 1362.65036
[33] R. Li and Y. Saad, GPU-accelerated preconditioned iterative linear solvers, J. Supercomput., 63 (2013), pp. 443–466.
[34] R. Li, Y. Xi, and Y. Saad, Schur complement-based domain decomposition preconditioners with low-rank corrections, Numerical Linear Algebra Appl., 23 (2016), pp. 706–729. · Zbl 1399.65238
[35] M. Magolu Monga Made, R. Beauwens, and G. Warzee, Preconditioning of discrete Helmholtz operators perturbed by a diagonal complex matrix, Internat. J. Numer. Meth. Biomed. Eng., 16 (2000), pp. 801–817. · Zbl 0972.65031
[36] K.-A. Mardal and R. Winther, Preconditioning discretizations of systems of partial differential equations, Numerical Linear Algebra Appl., 18 (2011), pp. 1–40. · Zbl 1249.65246
[37] M. F. Murphy, G. H. Golub, and A. J. Wathen, A note on preconditioning for indefinite linear systems, SIAM J. Sci. Comput., 21 (2000), pp. 1969–1972. · Zbl 0959.65063
[38] D. Osei-Kuffour, R. Li, and Y. Saad, Matrix reordering using multilevel graph coarsening for ILU preconditioning, SIAM J. Sci. Comput., 37 (2015), pp. A391–419. · Zbl 1315.65033
[39] D. Osei-Kuffuor and Y. Saad, Preconditioning Helmholtz linear systems, Appl. Numer. Math., 60 (2010), pp. 420–431, . · Zbl 1190.65048
[40] Y. Saad, A flexible inner-outer preconditioned GMRES algorithm, SIAM J. Sci. Comput., 14 (1993), pp. 461–469. · Zbl 0780.65022
[41] Y. Saad, ILUM: A multi-elimination ILU preconditioner for general sparse matrices, SIAM J. Sci. Comput., 17 (1996), pp. 830–847. · Zbl 0858.65029
[42] Y. Saad, Iterative Methods for Sparse Linear Systems, 2nd ed., SIAM, Philadelphia, 2003. · Zbl 1031.65046
[43] Y. Saad and B. Suchomel, ARMS: An algebraic recursive multilevel solver for general sparse linear systems, Numer. Linear Algebra Appl., 9 (2002), pp. 359–378. · Zbl 1071.65001
[44] G. Stewart, Algorithm 506: HQR3 and EXCHNG: Fortran subroutines for calculating and ordering the eigenvalues of a real upper Hessenberg matrix, ACM Trans. Math. Software, 2 (1976), pp. 275–280.
[45] M. B. van Gijzen, Y. A. Erlangga, and C. Vuik, Spectral analysis of the discrete Helmholtz operator preconditioned with a shifted Laplacian, SIAM J. Sci. Comput., 29 (2007), pp. 1942–1958. · Zbl 1155.65088
[46] Y. Xi, R. Li, and Y. Saad, An algebraic multilevel preconditioner with low-rank corrections for sparse symmetric matrices, SIAM J. Matrix Anal. Appl., 37 (2016), pp. 235–259. · Zbl 1376.65036
[47] Y. Xi and Y. Saad, Computing partial spectra with least-squares rational filters, SIAM J. Sci. Comput., 38 (2016), pp. A3020–A3045, . · Zbl 1351.65026
[48] Y. Xi and Y. Saad, A rational function preconditioner for indefinite sparse linear systems, SIAM J. Sci. Comput., 39 (2017), pp. A1145–A1167, . · Zbl 1368.65044
[49] Y. Xi and J. Xia, On the stability of some hierarchical rank structured matrix algorithms, SIAM J. Matrix Anal. Appl., 37 (2016), pp. 1279–1303, . · Zbl 1348.65064
[50] Y. Xi, J. Xia, S. Cauley, and V. Balakrishnan, Superfast and stable structured solvers for Toeplitz least squares via randomized sampling, SIAM J. Matrix Anal. Appl., 35 (2014), pp. 44–72. · Zbl 1300.65018
[51] J. Xia, S. Chandrasekaran, M. Gu, and X. Li, Fast algorithms for hierarchically semiseparable matrices, Numer. Linear Algebra Appl., 17 (2010), pp. 953–976. · Zbl 1240.65087
[52] J. Xia, Y. Xi, S. Cauley, and V. Balakrishnan, Fast sparse selected inversion, SIAM J. Matrix Anal. Appl., 36 (2015), pp. 1283–1314, . · Zbl 1323.65024
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. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.