A hierarchical low rank Schur complement preconditioner for indefinite linear systems. (English) Zbl 1392.65027
Summary: Nonsymmetric and highly indefinite linear systems can be quite difficult to solve by iterative methods. This paper combines ideas from the multilevel Schur low rank preconditioner developed by Y. Xi et al. [SIAM J. Matrix Anal. Appl. 37, No. 1, 235–259 (2016; Zbl 1376.65036)] with classic block preconditioning strategies in order to handle this case. The method to be described generates a tree structure \(\mathcal{T}\) that represents a hierarchical decomposition of the original matrix. This decomposition gives rise to a block structured matrix at each level of \(\mathcal{T}\). An approximate inverse of the original matrix based on its block \(LU\) factorization is computed at each level via a low rank property that characterizes the difference between the inverses of the Schur complement and another block of the reordered matrix. The low rank correction matrix is computed by several steps of the Arnoldi process. Numerical results illustrate the robustness of the proposed preconditioner with respect to indefiniteness for a few discretized partial differential equations and publicly available test problems.
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 |
Keywords:
block preconditioner; Schur complements; multilevel; low rank approximation; Krylov subspace methods; domain decomposition; nested dissection orderingCitations:
Zbl 1376.65036References:
| [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. 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.
