An algebraic sparsified nested dissection algorithm using low-rank approximations. (English) Zbl 1441.65048

The authors are interested in solving large symmetric positive-definite (SPD) sparse linear systems \(Ax=b\), \(A\in \mathbb{R}^{N\times N}\) and propose a new algorithm based on nested dissection, sparsification, and low-rank compression.
The approach is based on the idea of hierarchical interpolative factorization described by K. L. Ho and L. Ying [Commun. Pure Appl. Math. 69, No. 8, 1415–1451 (2016; Zbl 1353.35142)]. However, there are several differences, improvements, and novel capabilities. For example: the algorithm is completely general and can be applied to any symmetric positive definite matrix. The only required input is the sparse matrix itself. If some geometry information is available, it can be used to improve the quality of the ordering and clustering; inclusion of an additional step for scaling a diagonal block in the algorithm, greatly improving the accuracy of the preconditioner for only a small additional cost; the use of orthogonal (instead of interpolative) transformation, improving stability and ensuring that the preconditioner remains SPD when \(A\) is SPD. The authors evaluate the algorithm on some large problems show it exhibits near-linear scaling. The factorization time is roughly \(O(N)\), and the number of iterations grows slowly with \(N\).


65F50 Computational methods for sparse matrices
65F08 Preconditioners for iterative methods
65F10 Iterative numerical methods for linear systems
65Y20 Complexity and performance of numerical algorithms


Zbl 1353.35142
Full Text: DOI arXiv


[1] S. Ambikasaran, Fast Algorithms for Dense Numerical Linear Algebra and Applications, Ph.D. thesis, Stanford University, Stanford, CA, 2013.
[2] P. Amestoy, C. Ashcraft, O. Boiteau, A. Buttari, J.-Y. L’Excellent, and C. Weisbecker, Improving multifrontal methods by means of block low-rank representations, SIAM J. Sci. Comput., 37 (2015), pp. A1451-A1474, https://doi.org/10.1137/120903476. · Zbl 1314.05111
[3] P. R. Amestoy, I. S. Duff, J.-Y. L’Excellent, and J. Koster, MUMPS: A general purpose distributed memory sparse solver, in Applied Parallel Computing, Springer, Berlin, Heidelberg, 2000, pp. 121-130.
[4] E. Anderson, Z. Bai, C. Bischof, L. S. Blackford, J. Demmel, J. Dongarra, J. Du Croz, A. Greenbaum, S. Hammarling, A. McKenney, and D. Sorensen, LAPACK Users’ Guide, SIAM, Philadelphia, 1999, https://doi.org/10.1137/1.9780898719604.
[5] J. Barnes and P. Hut, A hierarchical \(\mathcal{O}(N \log N)\) force-calculation algorithm, Nature, 324 (1986), pp. 446-449.
[6] M. Bebendorf, Efficient inversion of the Galerkin matrix of general second-order elliptic operators with nonsmooth coefficients, Math. Comp., 74 (2005), pp. 1179-1199. · Zbl 1330.65173
[7] M. Bebendorf and W. Hackbusch, Existence of \(\mathcal{H} \)-matrix approximants to the inverse FE-matrix of elliptic operators with \(L_\infty \)-coefficients, Numer. Math., 95 (2003), pp. 1-28. · Zbl 1033.65100
[8] M. J. Berger and S. H. Bokhari, A partitioning strategy for nonuniform problems on multiprocessors, IEEE Trans. Comput., 36 (1987), pp. 570-580.
[9] J. H. Bramble, Multigrid Methods, Vol. 294, CRC Press, 1993. · Zbl 0786.65094
[10] A. Brandt, S. McCormick, and J. Ruge, Algebraic Multigrid (AMG) for Automatic Multigrid Solutions with Application to Geodetic Computations, Report, Institute for Computational Studies, Fort Collins, CO, 1982.
[11] T. F. Chan, Rank revealing QR factorizations, Linear Algebra Appl., 88 (1987), pp. 67-82. · Zbl 0624.65025
[12] S. Chandrasekaran, P. Dewilde, M. Gu, T. Pals, X. Sun, A.-J. van der Veen, and D. White, Some fast algorithms for sequentially semiseparable representations, SIAM J. Matrix Anal. Appl., 27 (2005), pp. 341-364, https://doi.org/10.1137/S0895479802405884. · Zbl 1091.65063
[13] S. Chandrasekaran, P. Dewilde, M. Gu, and N. Somasunderam, On the numerical rank of the off-diagonal blocks of Schur complements of discretized elliptic PDEs, SIAM J. Matrix Anal. Appl., 31 (2010), pp. 2261-2290, https://doi.org/10.1137/090775932. · Zbl 1209.65032
[14] S. Chandrasekaran, M. Gu, and W. Lyons, A Fast and Stable Adaptive Solver for Hierarchically Semi-separable Representations, unpublished, 2004.
[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, https://doi.org/10.1137/S0895479803436652. · Zbl 1120.65031
[16] C. Chen, L. Cambier, E. G. Boman, S. Rajamanickam, R. S. Tuminaro, and E. Darve, A robust hierarchical solver for ill-conditioned systems with applications to ice sheet modeling, J. Comput. Phys., 396 (2019), pp. 819-836.
[17] 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.
[18] H. Cheng, Z. Gimbutas, P.-G. Martinsson, and V. Rokhlin, On the compression of low rank matrices, SIAM J. Sci. Comput., 26 (2005), pp. 1389-1404, https://doi.org/10.1137/030602678. · Zbl 1083.65042
[19] M. Christie and M. Blunt, Tenth SPE Comparative Solution Project: A Comparison of Upscaling Techniques, Society of Petroleum Engineers, 2001.
[20] T. A. Davis and Y. Hu, The University of Florida sparse matrix collection, ACM Trans. Math. Software, 38 (2011), 1. · Zbl 1365.65123
[21] M. Faverge, G. Pichon, P. Ramet, and J. Roman, On the use of \(\mathcal{H} \)-matrix arithmetic in PaStiX: A preliminary study, in Workshop on Fast Direct Solvers, Toulouse, France, 2015; available online from https://hal.inria.fr/hal-01187882.
[22] R. P. Fedorenko, A relaxation method for solving elliptic difference equations, Comput. Math. Math. Phys., 1 (1962), pp. 1092-1096. · Zbl 0163.39303
[23] J. Feliu-Fabà, K. L. Ho, and L. Ying, Recursively Preconditioned Hierarchical Interpolative Factorization for Elliptic Partial Differential Equations, preprint, https://arxiv.org/abs/1808.01364, 2018. · Zbl 1437.65172
[24] W. Fong and E. Darve, The black-box fast multipole method, J. Comput. Phys., 228 (2009), pp. 8712-8725. · Zbl 1177.65009
[25] A. George, Nested dissection of a regular finite element mesh, SIAM J. Numer. Anal., 10 (1973), pp. 345-363, https://doi.org/10.1137/0710032. · Zbl 0259.65087
[26] 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, https://doi.org/10.1137/15M1010117. · Zbl 1352.65092
[27] G. H. Golub and C. F. Van Loan, Matrix Computations, Vol. 4, Johns Hopkins University Press, Baltimore, MD, 2013. · Zbl 1268.65037
[28] L. Grasedyck, R. Kriemann, and S. Le Borne, Domain decomposition based \(\mathcal{H} \)-LU preconditioning, Numer. Math., 112 (2009), pp. 565-600. · Zbl 1178.65140
[29] L. Greengard and V. Rokhlin, A fast algorithm for particle simulations, J. Comput. Phys., 73 (1987), pp. 325-348, https://doi.org/10.1016/0021-9991(87)90140-9. · Zbl 0629.65005
[30] M. Gu and S. C. Eisenstat, Efficient algorithms for computing a strong rank-revealing QR factorization, SIAM J. Sci. Comput., 17 (1996), pp. 848-869, https://doi.org/10.1137/0917055. · Zbl 0858.65044
[31] W. Hackbusch, A sparse matrix arithmetic based on \(\mathcal{H} \)-matrices. Part I: Introduction to \(\mathcal{H} \)-matrices, Computing, 62 (1999), pp. 89-108. · Zbl 0927.65063
[32] W. Hackbusch, Multi-grid Methods and Applications, Springer Ser. Comput. Math. 4, Springer, Berlin, Heidelberg, 2013. · Zbl 0595.65106
[33] W. Hackbusch and S. Börm, Data-sparse approximation by adaptive \(\mathcal{H}^2\)-matrices, Computing, 69 (2002), pp. 1-35. · Zbl 1012.65023
[34] 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
[35] P. Hénon, P. Ramet, and J. Roman, PaStiX: A high-performance parallel direct solver for sparse symmetric positive definite systems, Parallel Comput., 28 (2002), pp. 301-321. · Zbl 0984.68208
[36] M. R. Hestenes and E. Stiefel, Methods of conjugate gradients for solving linear systems, J. Research Nat. Bur. Standards, 49 (1952), pp. 409-436. · Zbl 0048.09901
[37] K. L. Ho and L. Ying, Hierarchical interpolative factorization for elliptic operators: Differential equations, Comm. Pure Appl. Math., 69 (2016), pp. 1415-1451. · Zbl 1353.35142
[38] 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, https://doi.org/10.1137/S1064827595287997. · Zbl 0915.68129
[39] E. Liberty, F. Woolfe, P.-G. Martinsson, V. Rokhlin, and M. Tygert, Randomized algorithms for the low-rank approximation of matrices, Proc. Natl. Acad. Sci. USA, 104 (2007), pp. 20167-20172. · Zbl 1215.65080
[40] R. J. Lipton, D. J. Rose, and R. E. Tarjan, Generalized nested dissection, SIAM J. Numer. Anal., 16 (1979), pp. 346-358, https://doi.org/10.1137/0716027. · Zbl 0435.65021
[41] L. Miranian and M. Gu, Strong rank revealing LU factorizations, Linear Algebra Appl., 367 (2003), pp. 1-16. · Zbl 1020.65016
[42] C. C. Paige and M. A. Saunders, Solution of sparse indefinite systems of linear equations, SIAM J. Numer. Anal., 12 (1975), pp. 617-629, https://doi.org/10.1137/0712047. · Zbl 0319.65025
[43] H. Pouransari, P. Coulier, and E. Darve, Fast hierarchical solvers for sparse matrices using extended sparsification and low-rank approximation, SIAM J. Sci. Comput., 39 (2017), pp. A797-A830, https://doi.org/10.1137/15M1046939. · Zbl 1365.65072
[44] A. Prokopenko, C. M. Siefert, J. J. Hu, M. Hoemmen, and A. Klinvex, Ifpack \(2\) User’s Guide 1.0, Tech. Report SAND2016-5338, Sandia National Labs, Albuquerque, NM, 2016.
[45] Y. Saad, ILUT: A dual threshold incomplete LU factorization, Numer. Linear Algebra Appl., 1 (1994), pp. 387-402. · Zbl 0838.65026
[46] Y. Saad, Iterative Methods for Sparse Linear Systems, 2nd ed., SIAM, Philadelphia, 2003, https://doi.org/10.1137/1.9780898718003. · Zbl 1031.65046
[47] 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, https://doi.org/10.1137/0907058. · Zbl 0599.65018
[48] 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, https://doi.org/10.1137/S106482759732753X. · Zbl 0956.65026
[49] P. G. Schmitz and L. Ying, A fast direct solver for elliptic problems on general meshes in 2d, J. Comput. Phys., 231 (2012), pp. 1314-1338. · Zbl 1408.65022
[50] K. Stüben, A review of algebraic multigrid, J. Comput. Appl. Math., 128 (2001), pp. 281-309. · Zbl 0979.65111
[51] D. A. Sushnikova and I. V. Oseledets, “Compress and eliminate” solver for symmetric positive definite sparse matrices, SIAM J. Sci. Comput., 40 (2018), pp. A1742-A1762, https://doi.org/10.1137/16M1068487. · Zbl 1391.65052
[52] I. K. Tezaur, M. Perego, A. G. Salinger, R. S. Tuminaro, and S. F. Price, Albany/FELIX: A parallel, scalable and robust, finite element, first-order stokes approximation ice sheet solver built for advanced analysis, Geo. Model Dev. (Online), 8 (2015).
[53] H. A. van der Vorst, Bi-CGSTAB: A fast and smoothly converging variant of Bi-CG for the solution of nonsymmetric linear systems, SIAM J. Sci. Statist. Comput., 13 (1992), pp. 631-644, https://doi.org/10.1137/0913035. · Zbl 0761.65023
[54] J. Xia, Efficient structured multifrontal factorization for general large sparse matrices, SIAM J. Sci. Comput., 35 (2013), pp. A832-A860, https://doi.org/10.1137/120867032. · Zbl 1266.15022
[55] J. Xia, Randomized sparse direct solvers, SIAM J. Matrix Anal. Appl., 34 (2013), pp. 197-227, https://doi.org/10.1137/12087116X. · Zbl 1269.65029
[56] 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, https://doi.org/10.1137/09074543X. · Zbl 1195.65031
[57] 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
[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, https://doi.org/10.1137/090750500. · Zbl 1217.65061
[59] J. Xia and Z. Xin, Effective and robust preconditioning of general SPD matrices via structured incomplete factorization, SIAM J. Matrix Anal. Appl., 38 (2017), pp. 1298-1322, https://doi.org/10.1137/17M1124152. · Zbl 1386.15033
[60] K. Yang, H. Pouransari, and E. Darve, Sparse hierarchical solvers with guaranteed convergence, Internat. J. Numer. Methods Engrg., 120 (2019), pp. 964-986.
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.