×

A rational function preconditioner for indefinite sparse linear systems. (English) Zbl 1368.65044


MSC:

65F08 Preconditioners for iterative methods
65F50 Computational methods for sparse matrices
35J05 Laplace operator, Helmholtz equation (reduced wave equation), Poisson equation
65N22 Numerical solution of discretized equations for boundary value problems involving PDEs
PDF BibTeX XML Cite
Full Text: DOI

References:

[1] 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
[2] 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
[3] O. Axelsson and P. S. Vassilevski, A black box generalized conjugate gradient solver with inner iterations and variable-step preconditioning, SIAM J. Matrix Anal. Appl., 12 (1991), pp. 625–644. · Zbl 0748.65028
[4] J. Baglama, D. Calvetti, G. H. Golub, and L. Reichel, Adaptively preconditioned GMRES algorithms, SIAM J. Sci. Comput., 20 (1998), pp. 243–269. · Zbl 0954.65026
[5] R. E. Bank and C. Wagner, Multilevel ILU decomposition, Numer. Math., 82 (1999), pp. 543–576. · Zbl 0938.65063
[6] M. Benzi, G. H. Golub, and J. Liesen, Numerical solution of saddle point problems, Acta Numer., 14 (2005), pp. 1–137. · Zbl 1115.65034
[7] J.-P. Berenger, A perfectly matched layer for the absorption of electromagnetic waves, J. Comput. Phys., 114 (1994), pp. 185–200. · Zbl 0814.65129
[8] M. Bollhöfer, A robust and efficient ILU that incorporates the growth of the inverse triangular factors, SIAM J. Sci. Comput., 25 (2003), pp. 86–103.
[9] M. Bollhöfer, J. I. Aliaga, A. F. Martín, and E. S. Quintana-Ortí, ILUPACK, in Encyclopedia of Parallel Computing, Springer, New York, 2011, pp. 917–926.
[10] M. Bollhöfer, M. J. Grote, and O. Schenk, Algebraic multilevel preconditioner for the Helmholtz equation in heterogeneous media, SIAM J. Sci. Comput., 31 (2009), pp. 3781–3805. · Zbl 1203.65273
[11] M. Bollhöfer and Y. Saad, Multilevel preconditioners constructed from inverse-based ILUs, SIAM J. Sci. Comput., 27 (2005), pp. 1627–1650. · Zbl 1104.65037
[12] E. F. F. Botta and F. W. Wubs, Matrix renumbering ILU: An effective algebraic multilevel ILU preconditioner for sparse matrices, SIAM J. Matrix Anal. Appl., 20 (1999), pp. 1007–1026. · Zbl 0937.65057
[13] A. Chapman and Y. Saad, Deflated and augmented Krylov subspace techniques, Numer. Linear Algebra Appl., 4 (1997), pp. 43–66. · Zbl 0889.65028
[14] W. C. Chew and W. H. Weedon, A 3Dperfectly matched medium from modified Maxwell’s equations with stretched coordinates, Microw. Opt. Tech. Lett., 7 (1994), pp. 599–604.
[15] E. Chow and Y. Saad, Experimental study of ILU preconditioners for indefinite matrices, J. Comput. Appl. Math., 87 (1997), pp. 387–414. · Zbl 0891.65028
[16] E. de Sturler, Inner-outer methods with deflation for linear systems with multiple right-hand sides, in Proceedings of the Householder Symposium on Numerical Algebra, Pontresina, Switzerland, 1996, pp. 193–196.
[17] H. C. Elman, A stability analysis of incomplete LU factorizations, Math. Comp., 47 (1986), pp. 191–217. · Zbl 0621.65024
[18] B. Engquist and L. Ying, Sweeping preconditioner for the Helmholtz equation: Hierarchical matrix representation, Commun. Pure Appl. Math., 64 (2011), pp. 697–735. · Zbl 1229.35037
[19] B. Engquist and L. Ying, Sweeping preconditioner for the Helmholtz equation: Moving perfectly matched layers, Multiscale Model. Simul., 9 (2011), pp. 686–710. · Zbl 1228.65234
[20] J. Erhel, K. Burrage, and B. Pohl, Restarted GMRES preconditioned by deflation, J. Comput. Appl. Math., 69 (1996), pp. 303–318. · Zbl 0854.65025
[21] Y. A. Erlangga, C. Vuik, and C. W. Oosterlee, Comparison of multigrid and incomplete LU shifted-Laplace preconditioners for the inhomogeneous Helmholtz equation, Appl. Numer. Math., 56 (2006), pp. 648–666. · Zbl 1094.65041
[22] Y. A. Erlangga, C. W. Oosterlee, and C. Vuik, A novel multigrid based preconditioner for heterogeneous Helmholtz problems, SIAM J. Sci. Comput., 27 (2005), pp. 1471–1492. · Zbl 1095.65109
[23] O. G. Ernst and M. J. Gander, Why it is difficult to solve Helmholtz problems with classical iterative methods, in Numerical Analysis of Multiscale Problems, Lect. Notes Comput. Sci. Eng. 83, Springer, Heidelberg, 2012, pp. 325–363. · Zbl 1248.65128
[24] M. J. Gander and F. Nataf, AILU: A preconditioner based on the analytic factorization of the elliptic operator, Numer. Linear Algebra Appl., 7 (2000), pp. 505–526. · Zbl 1051.65054
[25] M. J. Gander and F. Nataf, AILU for Helmholtz problems: a new preconditioner based on the analytic parabolic factorization, J. Comput. Acoust., 9 (2001), pp. 1499–1506. · Zbl 1360.76181
[26] A. George, Nested dissection of a regular finite element mesh, SIAM J. Numer. Anal., 10 (1973), pp. 345–363. · Zbl 0259.65087
[27] 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
[28] L. Giraud, S. Gratton, X. Pinel, and X. Vasseur, Flexible GMRES with deflated restarting, SIAM J. Sci. Comput., 32 (2010), pp. 1858–1878. · Zbl 1215.65057
[29] G. H. Golub and Q. Ye, Inexact preconditioned conjugate gradient method with inner-outer iteration, SIAM J. Sci. Comput, 21 (1997), pp. 1305–1320. · Zbl 0955.65022
[30] I. Gustafsson, A class of first order factorization methods, BIT, 18 (1978), pp. 142–156. · Zbl 0386.65006
[31] S. Güttel, E. Polizzi, P. Tang, and G. Viaud, Zolotarev quadrature rules and load balancing for the FEAST eigensolver, SIAM J. Sci. Comput., 37 (2015), pp. A2100–A2122. · Zbl 1321.65055
[32] N. Hale, N. J. Higham, and L. N. Trefethen, Computing \(A^α, \log(A)\), and related matrix functions by contour integrals, SIAM. J. Numer. Anal., 46 (2008), pp. 2505–2523. · Zbl 1176.65053
[33] N. J. Higham, Functions of Matrices: Theory and Computation, SIAM, Philadelphia, 2008. · Zbl 1167.15001
[34] J. Kestyn, E. Polizzi, and P. Tang, FEAST Eigensolver for Non-Hermitian Problems, [math.NA], 2015.
[35] 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
[36] Z. Li, Y. Saad, and M. Sosonkina, pARMS: A parallel version of the algebraic recursive multilevel solver, Numer. Linear. Algebra Appl., 10 (2003), pp. 485–509. · Zbl 1071.65532
[37] F. Liu and L. Ying, Additive sweeping preconditioner for the Helmholtz equation, Multiscale Model. Simul., 14 (2016), pp. 799–822. · Zbl 1338.65077
[38] F. Liu and L. Ying, Recursive sweeping preconditioner for the three-dimensional Helmholtz equation, SIAM J. Sci. Comput., 38 (2016), pp. A814–A832. · Zbl 1376.65035
[39] S. MacLachlan, D. Osei-Kuffuor, and Y. Saad, Modification and compensation strategies for threshold-based incomplete factorizations, SIAM J. Sci. Comput., 34 (2012), pp. A48–A75. · Zbl 1241.65032
[40] S. MacLachlan and Y. Saad, A greedy strategy for coarse-grid selection, SIAM J. Sci. Comput., 29 (2007), pp. 1825–1853. · Zbl 1154.65016
[41] M. Magolu monga Made, R. Beauwens, and G Warzée, Preconditioning of discrete Helmholtz operators perturbed by a diagonal complex matrix, Comm. Numer. Methods Engrg., 16 (2000), pp. 801–817. · Zbl 0972.65031
[42] M. Magolu Monga Made, R. Beauwens, and G. Warzée, Preconditioning of discrete Helmholtz operators perturbed by a diagonal complex matrix, Comm. Numer. Methods Engrg., 16 (2000), pp. 801–817. · Zbl 0972.65031
[43] T. A. Manteuffel, Shifted incomplete Cholesky factorization, in Sparse Matrix Proceedings 1978, SIAM, Philadelphia, 1979, pp. 41–61.
[44] R. B. Morgan, A restarted GMRES method augmented with eigenvectors, SIAM J. Matrix Anal. Appl., 16 (1995), pp. 1154–1171. · Zbl 0836.65050
[45] R. B. Morgan, GMRES with deflated restarting, SIAM J. Sci. Comput., 24 (2002), pp. 20–37. · Zbl 1018.65042
[46] Y. Notay, Flexible conjugate gradients, SIAM J. Sci. Comput., 22 (2000), pp. 1444–1460. · Zbl 0980.65030
[47] D. Osei-Kuffuor and Y. Saad, Preconditioning Helmholtz linear systems, Appl. Numer. Math., 60 (2010), pp. 420–431. · Zbl 1190.65048
[48] E. Polizzi, Density-matrix-based algorithm for solving eigenvalue problems, Phys. Rev. B, 79 (2009), p. 115112.
[49] Y. Saad, A flexible inner-outer preconditioned GMRES algorithm, SIAM J. Sci. Comput., 14 (1993), pp. 461–469. · Zbl 0780.65022
[50] Y. Saad, ILUT: A dual threshold incomplete LU factorization, Numer. Linear Algebra Appl., 1 (1994), pp. 387–402. · Zbl 0838.65026
[51] Y. Saad, ILUM: A multi-elimination ILU preconditioner for general sparse matrices, SIAM J. Sci. Comput., 17 (1996), pp. 830–847. · Zbl 0858.65029
[52] Y. Saad, Iterative Methods for Sparse Linear Systems, 2nd ed., SIAM, Philadelphia, 2003. · Zbl 1031.65046
[53] Y. Saad, Numerical Methods for Large Eigenvalue Problems, SIAM, Philadelphia, 2011. · Zbl 1242.65068
[54] Y. Saad and M. Schultz, GMRES: A generalized minimal residual algorithm for solving nonsymmetric linear systems, SIAM J. Sci. Statist. Comput., 7 (1986), pp. 856–869. · Zbl 0599.65018
[55] 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
[56] T. Sakurai and H. Sugiura, A projection method for generalized eigenvalue problems using numerical integration, J. Comput. Appl. Math., 159 (2003), pp. 119–128. · Zbl 1037.65040
[57] T. Sakurai and H. Tadano, CIRR: A Rayleigh-Ritz type method with contour integral for generalized eigenvalue problems, Hokkaido Math. J., 36 (2007), pp. 745–757. · Zbl 1156.65035
[58] V. Simoncini and D. B. Szyld, Flexible inner-outer Krylov subspace methods, SIAM J. Numer. Anal., 40 (2002), pp. 2219–2239. · Zbl 1047.65021
[59] P. Tang and E. Polizzi, FEAST as a subspace iteration eigensolver accelerated by approximate spectral projection, SIAM J. Matrix Anal. Appl., 35 (2014), pp. 354–390. · Zbl 1303.65018
[60] 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
[61] C. Vuik, New insights in GMRES-like methods with variable preconditioners, J. Comput. Appl. Math., 61 (1995), pp. 189–204. · Zbl 0844.65021
[62] S. Wang, M. V. de Hoop, and J. Xia, On \(3\)D modeling of seismic wave propagation via a structured parallel multifrontal direct Helmholtz solver, Geophys. Prospect., 59 (2011), pp. 857–873.
[63] Y. Xi, R. Li, and Y. Saad, An algebraic multilevel low-rank preconditioner for sparse symmetric matrices, SIAM J. Matrix Anal. Appl., 37 (2016), pp. 235–259. · Zbl 1376.65036
[64] 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
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.