×

Low-rank correction methods for algebraic domain decomposition preconditioners. (English) Zbl 1371.65029


MSC:

65F08 Preconditioners for iterative methods
65F10 Iterative numerical methods for linear systems
65Y05 Parallel numerical computation
65F50 Computational methods for sparse matrices
65N55 Multigrid methods; domain decomposition for boundary value problems involving PDEs
65F25 Orthogonalization in numerical linear algebra
35J05 Laplace operator, Helmholtz equation (reduced wave equation), Poisson equation
74B05 Classical linear elasticity
PDF BibTeX XML Cite
Full Text: DOI arXiv

References:

[3] S. Ambikasaran and E. Darve, An \(\mathcal{O}(n\log n)\) fast direct solver for partial hierarchically semi-separable matrices, J. Sci. Comput., 57 (2013), pp. 477–501. · Zbl 1292.65030
[4] 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
[5] P. R. Amestoy, T. A. Davis, and I. S. Duff, Algorithm 837: An approximate minimum degree ordering algorithm, ACM Trans. Math. Softw., 30 (2004), pp. 381–388. · Zbl 1070.65534
[6] A. Aminfar, S. Ambikasaran, and E. Darve, A fast block low-rank dense solver with applications to finite-element matrices, J. Comput. Phys., 304 (2016), pp. 170–188. · Zbl 1349.65595
[7] S. Balay, S. Abhyankar, M. F. Adams, J. Brown, P. Brune, K. Buschelman, V. Eijkhout, W. D. Gropp, D. Kaushik, M. G. Knepley, L. C. McInnes, K. Rupp, B. F. Smith, and H. Zhang, PETSc Users Manual, Tech. report ANL-95/11 - Revision 3.5, Argonne National Laboratory, Lemont, IL, 2014.
[8] S. Balay, S. Abhyankar, M. F. Adams, J. Brown, P. Brune, K. Buschelman, V. Eijkhout, W. D. Gropp, D. Kaushik, M. G. Knepley, L. C. McInnes, K. Rupp, B. F. Smith, and H. Zhang, PETSc Web Page, , 2014.
[9] S. Balay, W. D. Gropp, L. C. McInnes, and B. F. Smith, Efficient management of parallelism in object oriented numerical software libraries, in Modern Software Tools in Scientific Computing, E. Arge, A. M. Bruaset, and H. P. Langtangen, eds., Birkhäuser, Basel, 1997, pp. 163–202. · Zbl 0882.65154
[10] D. Braess, Finite Elements: Theory, Fast Solvers, and Applications in Solid Mechanics, 3rd ed., Cambridge University Press, Cambridge, UK, 2007. · Zbl 1118.65117
[11] X. Cai and Y. Saad, Overlapping domain decomposition algorithms for general sparse matrices, Numer. Linear Algebra Appl., 3 (1996), pp. 221–237. · Zbl 0851.65083
[12] X.-C. Cai and M. Sarkis, A restricted additive Schwarz preconditioner for general sparse linear systems, SIAM J. Sci. Comput., 21 (1999), pp. 792–797, . · Zbl 0944.65031
[13] Ü. V. Çatalyurek and C. Aykanat, Hypergraph-partitioning-based decomposition for parallel sparse-matrix vector multiplication, IEEE Trans. Parallel Distributed Syst., 10 (1999), pp. 673–693.
[14] S. Chandrasekaran, P. Dewilde, M. Gu, W. Lyons, and T. Pals, A fast solver for HSS representations via sparse matrices, SIAM J. Matrix Anal. Appl., 29 (2006), pp. 67–81, . · Zbl 1135.65317
[15] S. Chandrasekaran, M. Gu, and T. Pals, A fast ULV decomposition solver for hierarchically semiseparable representations, SIAM J. Matrix Anal. Appl., 28 (2006), pp. 603–622, . · Zbl 1120.65031
[16] E. Chow and Y. Saad, Approximate inverse preconditioners via sparse-sparse iterations, SIAM J. Sci. Comput., 19 (1998), pp. 995–1023, . · Zbl 0922.65034
[17] T. A. Davis, Direct Methods for Sparse Linear Systems, Fundam. Algorithms 2, SIAM, Philadelphia, 2006, .
[18] M. Dryja and O. Widlund, An Additive Variant of the Schwarz Alternating Method for the Case of Many Subregions, Courant Institute of Mathematical Sciences, New York University, New York, 1987.
[19] M. Dryja and O. Widlund, Additive Schwarz methods for elliptic finite element problems in three dimensions, in Proceedings of the 5th International Symposium on Domain Decomposition Methods for Partial Differential Equations, SIAM, Philadelphia, 1991, pp. 3–18. · Zbl 0772.65021
[20] 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
[21] P. Ghysels, X. S. Li, F.-H. Rouet, S. Williams, and A. Napov, An efficient multicore implementation of a novel HSS-structured multifrontal solver using randomized sampling, SIAM J. Sci. Comput., 38 (2016), pp. S358–S384, . · Zbl 1352.65092
[22] G. H. Golub and C. F. Van Loan, Matrix Computations, 4th ed., Johns Hopkins University Press, Baltimore, MD, 2013. · Zbl 1268.65037
[23] L. Grasedyck and W. Hackbusch, Construction and arithmetics of \(\mathcal{H}\)-matrices, Computing, 70 (2003), pp. 295–334. · Zbl 1030.65033
[24] L. Grigori, F. Nataf, and S. Yousef, Robust Algebraic Schur Complement Preconditioners Based on Low Rank Corrections, Rapport de recherche RR-8557, INRIA, Paris, France, 2014.
[25] W. Hackbusch, A sparse matrix arithmetic based on \(\mathcal{H}\)-matrices. Part I: Introduction to \(\mathcal{H}\)-matrices, Computing, 62 (1999), pp. 89–108.
[26] W. Hackbusch and S. Börm, Data-sparse approximation by adaptive \(\mathcal{H}^2\)-matrices, Computing, 69 (2002), pp. 1–35.
[27] W. Hackbusch and S. Börm, \(\mathcal{H}^2\)-matrix approximation of integral operators by interpolation, Appl. Numer. Math., 43 (2002), pp. 129–143. · Zbl 1019.65103
[28] 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
[29] N. Halko, P. G. Martinsson, and J. A. Tropp, Finding structure with randomness: Probabilistic algorithms for constructing approximate matrix decompositions, SIAM Rev., 53 (2011), pp. 217–288, . · Zbl 1269.65043
[30] B. Hendrickson and R. Leland, The Chaco User’s Guide Version 2, Sandia National Laboratories, Albuquerque, NM, 1994.
[31] A. S. Householder, Theory of Matrices in Numerical Analysis, Blaisdell, Johnson, CO, 1964. · Zbl 0161.12101
[32] 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
[33] G. Karypis and V. Kumar, A parallel algorithm for multilevel graph partitioning and sparse matrix ordering, J. Parallel Distributed Comput., 48 (1998), pp. 71–95.
[34] T. G. Kolda, Partitioning sparse rectangular matrices for parallel processing, in Solving Irregularly Structured Problems in Parallel (Berkeley, CA, 1998), Lecture Notes in Comput. Sci. 1457, Springer, Berlin, 1998, pp. 68–79.
[35] C. Lanczos, An iteration method for the solution of the eigenvalue problem of linear differential and integral operators, J. Research Nat. Bur. Standards, 45 (1950), pp. 255–282.
[36] S. Le Borne, \(\mathcal{H}\)-matrices for convection-diffusion problems with constant convection, Computing, 70 (2003), pp. 261–274. · Zbl 1033.65011
[37] 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
[38] 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
[39] R. Li and Y. Saad, GPU-accelerated preconditioned iterative linear solvers, J. Supercomputing, 63 (2013), pp. 443–466.
[40] R. Li, Y. Xi, and Y. Saad, Schur complement-based domain decomposition preconditioners with low-rank corrections, Numer. Linear Algebra Appl., 23 (2016), pp. 706–729. · Zbl 1399.65238
[41] 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
[42] B. N. Parlett, The Symmetric Eigenvalue Problem, Classics Appl. Math. 20, SIAM, Philadelphia, 1998, . · Zbl 0885.65039
[43] B. N. Parlett and D. S. Scott, The Lanczos algorithm with selective orthogonalization, Math. Comp., 33 (1979), pp. 217–238. · Zbl 0405.65015
[44] F. Pellegrini, Scotch and libScotch 5.1 User’s Guide, Université Bordeaux I, Talence, France, 2010; available online from .
[45] A. Pothen, H. D. Simon, and K.-P. Liou, Partitioning sparse matrices with eigenvectors of graphs, SIAM J. Matrix Anal. Appl., 11 (1990), pp. 430–452, . · Zbl 0711.65034
[46] F. Rouet, X. S. Li, P. Ghysels, and A. Napov, A distributed-memory package for dense hierarchically semi-separable matrix computations using randomization, ACM Trans. Math. Softw., 42 (2016), 27. · Zbl 1369.65043
[47] Y. Saad, A flexible inner-outer preconditioned GMRES algorithm, SIAM J. Sci. Comput., 14 (1993), pp. 461–469, . · Zbl 0780.65022
[48] Y. Saad, Iterative Methods for Sparse Linear Systems, 2nd ed., SIAM, Philadelphia, 2003, . · Zbl 1031.65046
[49] Y. Saad and M. Sosonkina, pARMS: A package for solving general sparse linear systems on parallel computers, in Parallel Processing and Applied Mathematics, R. Wyrzykowski, J. Dongarra, M. Paprzycki, and J. Waśniewski, eds., Lecture Notes in Comput. Sci. 2328, Springer, Berlin, Heidelberg, 2002, pp. 446–457. · Zbl 1057.65523
[50] 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
[51] H. D. Simon, The Lanczos algorithm with partial reorthogonalization, Math. Comp., 42 (1984), pp. 115–142. · Zbl 0546.65017
[52] B. Smith, P. Bjø rstad, and W. Gropp, Domain Decomposition: Parallel Multilevel Methods for Elliptic Partial Differential Equations, Cambridge University Press, New York, 1996.
[53] 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
[54] 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
[55] J. Xia, Efficient structured multifrontal factorization for general large sparse matrices, SIAM J. Sci. Comput., 35 (2013), pp. A832–A860, . · Zbl 1266.15022
[56] 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
[57] 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
[58] 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
[59] Y. Zhou, Y. Saad, M. L. Tiago, and J. R. Chelikowsky, Parallel self-consistent-field calculations via Chebyshev-filtered subspace acceleration, Phys. Rev. E, 74 (2006), 066704. · Zbl 1105.65111
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.