An algebraic multilevel preconditioner with low-rank corrections for sparse symmetric matrices.(English)Zbl 1376.65036

MSC:

 65F08 Preconditioners for iterative methods 65Y05 Parallel numerical computation 65Y20 Complexity and performance of numerical algorithms 65N22 Numerical solution of discretized equations for boundary value problems involving PDEs 65N55 Multigrid methods; domain decomposition for boundary value problems involving PDEs

Software:

SparseMatrix; BILUM; ILUM; ARMS; BDDCML; BDDC; AMD
Full Text:

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] M. Benzi and M. T\accent23uma, A sparse approximate inverse preconditioner for nonsymmetric linear systems, SIAM J. Sci. Comput., 19 (1998), pp. 968–994. · Zbl 0930.65027 [4] M. Bollhöfer, J. I. Aliaga, A. F. Martín, and E. S. Quintana-Ortí, ILUPACK, in Encyclopedia of Parallel Computing, Springer, New York, 2011, pp. 917–926. [5] 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 [6] E. Chow and Y. Saad, Approximate inverse preconditioners via sparse-sparse iterations, SIAM J. Sci. Comput., 19 (1998), pp. 995–1023. · Zbl 0922.65034 [7] E. Chow and Y. Saad, Preconditioned Krylov subspace methods for sampling multivariate Gaussian distributions, SIAM J. Sci. Comput., 36 (2014), pp. A588–A608. · Zbl 1296.60087 [8] E. Corona, P.-G. Martinsson, and D. Zorin, An $$O(N)$$ direct solver for integral equations on the plane, Appl. Comput. Harmon. Anal., 38 (2015), pp. 284–317. · Zbl 1307.65180 [9] T. A. Davis and Y. Hu, The University of Florida Sparse Matrix Collection, ACM Trans. Math. Software, 38 (2011), 1. · Zbl 1365.65123 [10] O. Dubois and M. J. Gander, Convergence behavior of a two-level optimized Schwarz preconditioner, in Domain Decomposition Methods in Science and Engineering XVIII, Springer, Berlin, Heidelberg, 2009, pp. 177–184. · Zbl 1183.65030 [11] B. Engquist and L. Ying, Sweeping preconditioner for the Helmholtz equation: Hierarchical matrix representation, Comm. Pure Appl. Math., 64 (2011), pp. 697–735. · Zbl 1229.35037 [12] A. George, Nested dissection of a regular finite element mesh, SIAM J. Numer. Anal., 10 (1973), pp. 345–363. · Zbl 0259.65087 [13] A. Gillman and P. G. Martinsson, A direct solver with $$O(N)$$ complexity for variable coefficient elliptic PDEs discretized via a high-order composite spectral collocation method, SIAM J. Sci. Comput., 36 (2014), pp. A2023–A2046. · Zbl 1303.65099 [14] W. Hackbusch, A sparse matrix arithmetic based on $$\mathcal{H}$$-matrices. Part I: Introduction to $$\mathcal{H}$$-matrices, Computing, 62 (1999), pp. 89–108. [15] W. Hackbusch and B. N. Khoromskij, A sparse $$\mathcal{H}$$-matrix arithmetic. Part II: Application to multi-dimensional problems, Computing, 64 (2000), pp. 21–47. · Zbl 0962.65029 [16] P. Hé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 [17] M. R. Hestenes and E. L. Stiefel, Methods of conjugate gradients for solving linear systems, J. Research Nat. Bur. Standards, 49 (1952), pp. 409–436. · Zbl 0048.09901 [18] K. L. Ho and L. Ying, Hierarchical Interpolative Factorization for Elliptic Operators: Differential Equations, preprint, http://arxiv.org/abs/1307.2895 arXiv:1307.2895v1 [math.NA], 2013. [19] 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 [20] S. Le Borne, $$\mathcal{H}$$-matrices for convection-diffusion problems with constant convection, Computing, 70 (2003), pp. 261–274. · Zbl 1033.65011 [21] S. Le Borne and L. Grasedyck, $$\mathcal{H}$$-matrix preconditioners in convection-dominated problems, SIAM J. Matrix Anal. Appl., 27 (2006), pp. 1172–1183. · Zbl 1102.65051 [22] 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 [23] R. Li and Y. Saad, GPU-accelerated preconditioned iterative linear solvers, J. Supercomput., 63 (2013), pp. 443–466. [24] R. Li and Y. Saad, Low-Rank Correction Methods for Algebraic Domain Decomposition Preconditioners, Technical Report ys-2014-4, Department of Computer Science, University of Minnesota, Minneapolis, MN, 2014; available online at http://arxiv.org/abs/1505.04341. · Zbl 1371.65029 [25] R. Li, Y. Xi, and Y. Saad, Schur Complement Based Domain Decomposition Preconditioners with Low-Rank Corrections, Technical Report ys-2014-3, Department of Computer Science and Engineering, University of Minnesota, Minneapolis, MN, 2014; available online at http://arxiv.org/abs/1505.04340. · Zbl 1399.65238 [26] J. Mandel, B. Sousedík, and J. Šístek, Adaptive BDDC in three dimensions, Math. Comput. Simulation, 82 (2012), pp. 1812–1831. · Zbl 1255.65225 [27] P. G. Martinsson and V. Rokhlin, A fast direct solver for boundary integral equations in two dimensions, J. Comput. Phys., 205 (2005), pp. 1–23. · Zbl 1078.65112 [28] J. K. Merikoski and R. Kumar, Inequalities for spreads of matrix sums and products, Appl. Math. E-Notes, 4 (2004), pp. 150–159. · Zbl 1083.15027 [29] OpenMP Architecture Review Board, OpenMP Application Program Interface, Version 3.1, 2011. [30] Y. Saad, A flexible inner-outer preconditioned GMRES algorithm, SIAM J. Sci. Comput., 14 (1993), pp. 461–469. · Zbl 0780.65022 [31] Y. Saad, ILUM: A multi-elimination ILU preconditioner for general sparse matrices, SIAM J. Sci. Comput., 17 (1996), pp. 830–847. · Zbl 0858.65029 [32] Y. Saad, Iterative Methods for Sparse Linear Systems, 2nd ed., SIAM, Philadelphia, 2003. · Zbl 1031.65046 [33] Y. Saad, Numerical Methods for Large Eigenvalue Problems, revised ed., SIAM, Philadelphia, 2011. · Zbl 1242.65068 [34] Y. Saad and M. H. 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 [35] 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 [36] Y. Saad and J. Zhang, BILUM: Block versions of multielimination and multilevel ILU preconditioner for general sparse linear systems, SIAM J. Sci. Comput., 20 (1999), pp. 2103–2121. · Zbl 0956.65026 [37] B. Smith, Domain Decomposition Algorithms for the Partial Differential Equations of Linear Elasticity, Ph.D. thesis, Courant Institute, New York University, New York, 1990. [38] B. Smith, P. Bjørstad, and W. Gropp, Domain Decomposition: Parallel Multilevel Methods for Elliptic Partial Differential Equations, Cambridge University Press, New York, 1996. · Zbl 0857.65126 [39] B. Sousedík, J. Šístek, and J. Mandel, Adaptive-multilevel BDDC and its parallel implementation, Computing, 95 (2013), pp. 1087–1119. · Zbl 1307.65175 [40] A. St-Cyr, M. J. Gander, and S. J. Thomas, Optimized multiplicative, additive, and restricted additive Schwarz preconditioning, SIAM J. Sci. Comput., 29 (2007), pp. 2402–2425. · Zbl 1154.65017 [41] A. Toselli and O. B. Widlund, Domain Decomposition Methods: Algorithms and Theory, Springer Ser. Comput. Math. 34, Springer-Verlag, Berlin, 2005. · Zbl 1069.65138 [42] Y. Xi and Y. Saad, Least-Squares Rational Filters for the Solution of Interior Eigenvalue Problems, Technical Report ys-2015-5, Department of Computer Science and Engineering, University of Minnesota, Minneapolis, MN, 2015. [43] 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 [44] Y. Xi, J. Xia, and R. Chan, A fast randomized eigensolver with structured LDL factorization update, SIAM J. Matrix Anal. Appl., 35 (2014), pp. 974–996. · Zbl 1305.65125 [45] J. Xia, Efficient structured multifrontal factorization for general large sparse matrices, SIAM J. Sci. Comput., 35 (2013), pp. A832–A860. · Zbl 1266.15022 [46] J. Xia, Randomized sparse direct solvers, SIAM J. Matrix Anal. Appl., 34 (2013), pp. 197–227. · Zbl 1269.65029 [47] J. Xia, S. Chandrasekaran, M. Gu, and X. S. Li, Fast algorithms for hierarchically semiseparable matrices, Numer. Linear Algebra Appl., 17 (2010), pp. 953–976. · Zbl 1240.65087 [48] J. Xia, S. Chandrasekaran, M. Gu, and X. S. Li, Superfast multifrontal method for large structured linear systems of equations, SIAM J. Matrix Anal. Appl., 31 (2009), pp. 1382–1411. · Zbl 1195.65031 [49] J. Xia and M. Gu, Robust approximate Cholesky factorization of rank-structured symmetric positive definite matrices, SIAM J. Matrix Anal. Appl., 31 (2010), pp. 2899–2920. · Zbl 1217.65061
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.