×

zbMATH — the first resource for mathematics

“Compress and eliminate” solver for symmetric positive definite sparse matrices. (English) Zbl 1391.65052

MSC:
65F05 Direct numerical methods for linear systems and matrix inversion
65F50 Computational methods for sparse matrices
65F08 Preconditioners for iterative methods
PDF BibTeX XML Cite
Full Text: DOI arXiv
References:
[1] 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
[2] S. Ambikasaran and E. Darve, The Inverse Fast Multipole Method, preprint, arXiv:1309.1773, 2014. · Zbl 1292.65030
[3] 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
[4] A. Aminfar and E. Darve, A fast, memory efficient and robust sparse preconditioner based on a multifrontal approach with applications to finite-element matrices, Internat. J. Numer. Methods Engrg., (2015). · Zbl 1352.65451
[5] R. E. Bank, Marching algorithms and block Gaussian elimination, in Sparse Matrix Computations, Academic Press, New York, 1976, pp. 293–307. · Zbl 0345.65016
[6] M. Bebendorf, Hierarchical LU decomposition-based preconditioners for BEM, Computing, 74 (2005), pp. 225–247. · Zbl 1071.65031
[7] M. Bebendorf and W. Hackbusch, Existence of \(\mathcal{H}\)-matrix approximants to the inverse FE-matrix of elliptic operators with \(L^{∞}\)-coefficients, Numer. Math., 95 (2003), pp. 1–28. · Zbl 1033.65100
[8] J. N. Chadwick and D. S. Bindel, An Efficient Solver for Sparse Linear Systems Based on Rank-Structured Cholesky Factorization, preprint, arXiv:1507.05593, 2015.
[9] 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 (2007), pp. 67–81. · Zbl 1135.65317
[10] 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
[11] Y. Chen, T. A. Davis, W. W. Hager, and S. Rajamanickam, Algorithm 887: CHOLMOD, supernodal sparse Cholesky factorization and update/downdate, ACM Trans. Math. Software, 35 (2008), 22.
[12] P. Coulier, H. Pouransari, and E. Darve, The inverse fast multipole method: Using a fast approximate direct solver as a preconditioner for dense linear systems, SIAM J. Sci. Comput., 39 (2017), pp. A761–A796. · Zbl 1365.65068
[13] T. A. Davis, Algorithm 832: UMFPACK V4.3—an unsymmetric-pattern multifrontal method, ACM Trans. Math. Software, 30 (2004), pp. 196–199. · Zbl 1072.65037
[14] K. D. Devine, E. G. Boman, R. T. Heaphy, R. H. Bisseling, and U. V. Catalyurek, Parallel hypergraph partitioning for scientific computing, in Proceedings of the 20th International Parallel and Distributed Processing Symposium, IPDPS 2006, IEEE, Piscataway, NJ, 2006.
[15] A. George, Nested dissection of a regular finite element mesh, SIAM J. Numer. Anal., 10 (1973), pp. 345–363. · Zbl 0259.65087
[16] L. Grasedyck, W. Hackbusch, and R. Kriemann, Performance of \(\mathcal{H}-lu\) preconditioning for sparse matrices, Comput. Methods Appl. Math., 8 (2008), pp. 336–349. · Zbl 1156.65042
[17] W. Hackbusch, \(\mathcal{H}\)Lib Package, .
[18] K. L. Ho and L. Greengard, A fast direct solver for structured linear systems by recursive skeletonization, SIAM J. Sci. Comput., 34 (2012), pp. A2507–A2532. · Zbl 1259.65062
[19] K. L. Ho and L. Ying, Hierarchical interpolative factorization for elliptic operators: Differential equations, Comm. Pure Appl. Math., 69 (2015), pp. 1415–1451. · Zbl 1353.35142
[20] K. L. Ho and L. Ying, Hierarchical interpolative factorization for elliptic operators: Integral equations, Comm. Pure Appl. Math., 69 (2015), pp. 1314–1353. · Zbl 1344.65123
[21] W. Y. Kong, J. Bremer, and V. Rokhlin, An adaptive fast direct solver for boundary integral equations in two dimensions, Appl. Comput. Harmon. Anal., 31 (2011), pp. 346–369. · Zbl 1227.65118
[22] R. Li and Y. Saad, Divide and Conquer Low-Rank Preconditioning Techniques, Technical report ys-2012-3, Department of Computer Science and Engineering, University of Minnesota, Minneapolis, MN, 2012.
[23] Y. Li and L. Ying, Distributed-memory hierarchical interpolative factorization, Res. Math. Sci., 4 (2017). · Zbl 1375.65141
[24] P.-G. Martinsson, A fast direct solver for a class of elliptic partial differential equations, J. Sci. Comput., 38 (2009), pp. 316–330. · Zbl 1203.65066
[25] 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
[26] G. L. Miller, S.-H. Teng, and S. A. Vavasis, A unified geometric approach to graph separators, in Proceedings of IEEE 32nd Annual Symposium on Foundations of Computer Science, 1991, IEEE Computer Society, Los Alamitos, CA, 1991, pp. 538–547.
[27] E. Ng and B. W. Peyton, A supernodal Cholesky factorization algorithm for shared-memory multiprocessors, SIAM J. Sci. Comput., 14 (1993), pp. 761–769. · Zbl 0785.65014
[28] H. Pouransari, P. Coulier, and E. Darve, Fast Hierarchical Solvers for Sparse Matrices, preprint, arXiv:1510.07363, 2015. · Zbl 1365.65072
[29] S. Rajamanickam and E. G. Boman, Parallel partitioning with Zoltan: Is hypergraph partitioning worth it?, Contemp. Math., 588 (2012), pp. 37–52. · Zbl 1271.68199
[30] F.-H. 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. Software, 42 (2016), 27. · Zbl 1369.65043
[31] Y. Saad, ILUT: A dual threshold incomplete LU factorization, Numer. Linear Algebra, 1 (1994), pp. 387–402. · Zbl 0838.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.