×

A recursive skeletonization factorization based on strong admissibility. (English) Zbl 1365.65286

Summary: We introduce the strong recursive skeletonization factorization (RS-S), a new approximate matrix factorization based on recursive skeletonization for solving discretizations of linear integral equations associated with elliptic partial differential equations in two and three dimensions (and other matrices with similar hierarchical rank structure). Unlike previous skeletonization-based factorizations, RS-S uses a simple modification of skeletonization, strong skeletonization, which compresses only far-field interactions. This leads to an approximate factorization in the form of a product of many block unit-triangular matrices that may be used as a preconditioner or moderate-accuracy direct solver, with dramatically reduced rank growth. We further combine the strong skeletonization procedure with alternating near-field compression to obtain the hybrid recursive skeletonization factorization (RS-WS), a modification of RS-S that exhibits reduced storage cost in many settings. Under suitable rank assumptions both RS-S and RS-WS exhibit linear computational complexity, which we demonstrate with a number of numerical examples.

MSC:

65R20 Numerical methods for integral equations
45A05 Linear integral equations
65N38 Boundary element methods for boundary value problems involving PDEs
65F05 Direct numerical methods for linear systems and matrix inversion
65F08 Preconditioners for iterative methods
65Y20 Complexity and performance of numerical algorithms
PDFBibTeX XMLCite
Full Text: DOI arXiv

References:

[1] S. Ambikasaran and E. Darve, {\it An \({O}({N} \log{N})\) A fast direct solver for partial hierarchically semi-separable matrices}, SIAM J. Sci. Comput., 57 (2013), pp. 477-501, . · Zbl 1292.65030
[2] S. Ambikasaran and E. Darve, {\it The Inverse Fast Multipole Method}, , 2014. · Zbl 1292.65030
[3] J. Bremer, {\it A fast direct solver for the integral equations of scattering theory on planar curves with corners}, J. Comput. Phys., 231 (2012), pp. 1879-1899, . · Zbl 1242.65251
[4] S. Chandrasekaran, P. Dewilde, M. Gu, W. Lyons, and T. Pals, {\it A fast solver for HSS representations via sparse matrices}, SIAM J. Matrix Anal. Appl., 29 (2007), pp. 67-81, . · Zbl 1135.65317
[5] S. Chandrasekaran, M. Gu, and T. Pals, {\it A fast ULV decomposition solver for hierarchically semiseparable representations}, SIAM J. Matrix Anal. Appl., 28 (2006), pp. 603-622, . · Zbl 1120.65031
[6] Y. Chen, {\it A fast, direct algorithm for the Lippmann-Schwinger integral equation in two dimensions}, Adv. Comput. Math., 16 (2002), pp. 175-190, . · Zbl 0993.65137
[7] H. Cheng, Z. Gimbutas, P.-G. Martinsson, and V. Rokhlin, {\it On the compression of low rank matrices}, SIAM J. Sci. Comput., 26 (2005), pp. 1389-1404, . · Zbl 1083.65042
[8] E. Corona, P.-G. Martinsson, and D. Zorin, {\it An \(O(N)\) direct solver for integral equations on the plane}, Appl. Comput. Harmon. Anal., 38 (2015), pp. 284-317, . · Zbl 1307.65180
[9] P. Coulier, H. Pouransari, and E. Darve, {\it The Inverse Fast Multipole Method: Using a Fast Approximate Direct Solver as a Preconditioner for Dense Linear Systems}, , 2015. · Zbl 1365.65068
[10] J. D. Dixon, {\it Estimating extremal eigenvalues and condition numbers of matrices}, SIAM J. Numer. Anal., 20 (1983), pp. 812-814, . · Zbl 0536.65022
[11] W. Fong and E. Darve, {\it The black-box fast multipole method}, J. Comput. Phys., 228 (2009), pp. 8712-8725, . · Zbl 1177.65009
[12] A. Gillman, P. Young, and P.-G. Martinsson, {\it A direct solver with \({O(N)}\) complexity for integral equations on one-dimensional domains}, Front. Math. China, 7 (2012), pp. 217-247, . · Zbl 1262.65198
[13] L. Greengard, D. Gueyffier, P.-G. Martinsson, and V. Rokhlin, {\it Fast direct solvers for integral equations in complex three-dimensional domains}, Acta Numer., 18 (2009), pp. 243-275, . · Zbl 1176.65141
[14] L. Greengard and V. Rokhlin, {\it A fast algorithm for particle simulations}, J. Comput. Phys., 73 (1987), pp. 325-348. · Zbl 0629.65005
[15] L. Greengard and V. Rokhlin, {\it A new version of the fast multipole method for the Laplace equation in three dimensions}, Acta Numer., 6 (1997), pp. 229-269, . · Zbl 0889.65115
[16] M. Gu and S. Eisenstat, {\it Efficient algorithms for computing a strong rank-revealing QR factorization}, SIAM J. Sci. Comput., 17 (1996), pp. 848-869, . · Zbl 0858.65044
[17] W. Hackbusch, {\it A sparse matrix arithmetic based on \(\mathcal{H} \)-matrices. Part} I: {\it Introduction to \(\mathcal{H} \)-matrices}, Computing, 62 (1999), pp. 89-108, . · Zbl 0927.65063
[18] W. Hackbusch and S. Börm, {\it Data-sparse approximation by adaptive \(\mathcal{H}^2\)-matrices}, Computing, 69 (2002), pp. 1-35, . · Zbl 1012.65023
[19] W. Hackbusch and B. Khoromskij, {\it A sparse \(\mathcal{H} \)-matrix arithmetic. Part} II: {\it Application to multi-dimensional problems}, Computing, 64 (2000), pp. 21-47, . · Zbl 0962.65029
[20] M. Hestenes and E. Stiefel, {\it Methods of conjugate gradients for solving linear systems}, J. Res. National Bureau of Standards, 49 (1952), pp. 409-436. · Zbl 0048.09901
[21] K. Ho and L. Greengard, {\it A fast direct solver for structured linear systems by recursive skeletonization}, SIAM J. Sci. Comput., 34 (2012), pp. A2507-A2532, . · Zbl 1259.65062
[22] K. Ho and L. Ying, {\it Hierarchical interpolative factorization for elliptic operators: Integral equations}, Commun. Pure Appl. Math., (2015), . · Zbl 1344.65123
[23] J. Kuczyski and H. Woniakowski, {\it Estimating the largest eigenvalue by the power and Lanc- zos algorithms with a random start}, SIAM J. Matrix Anal. Appl., 13 (1992), pp. 1094-1122, .
[24] P.-G. Martinsson, {\it 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, {\it A fast direct solver for boundary integral equations in two dimensions}, J. Comput. Phys., 205 (2005), pp. 1-23, . · Zbl 1078.65112
[26] P.-G. Martinsson and V. Rokhlin, {\it An accelerated kernel-independent fast multipole method in one dimension}, SIAM J. Sci. Comput., 29 (2007), pp. 1160-1178, . · Zbl 1154.65318
[27] W. McLean, {\it Strongly Elliptic Systems and Boundary Integral Equations}, Cambridge University Press, Cambridge, UK, 2000. · Zbl 0948.35001
[28] V. Minden, A. Damle, K. L. Ho, and L. Ying, {\it Fast Spatial Gaussian Process Maximum Likelihood Estimation via Skeletonization Factorizations}, , 2016. · Zbl 1378.65092
[29] V. Minden, A. Damle, K. L. Ho, and L. Ying, {\it A technique for updating hierarchical skeletonization-based factorizations of integral operators}, Multiscale Model. Simul., 14 (2016), pp. 42-64, . · Zbl 1329.65317
[30] X. Pan, J. Wei, Z. Peng, and X. Sheng, {\it A fast algorithm for multiscale electromagnetic problems using interpolative decomposition and multilevel fast multipole algorithm}, Radio Sci., 47 (2012), .
[31] D. A. Sushnikova and I. V. Oseledets, {\it “Compress and Eliminate” Solver for Symmetric Positive Definite Sparse Matrices}, , 2016. · Zbl 1391.65052
[32] J. Xia, S. Chandrasekaran, M. Gu, and X. S. Li, {\it Superfast multifrontal method for large structured linear systems of equations}, SIAM J. Matrix Anal. Appl., 31 (2010), pp. 1382-1411, . · Zbl 1195.65031
[33] L. Ying, G. Biros, and D. Zorin, {\it A kernel-independent adaptive fast multipole algorithm in two and three dimensions}, J. Comput. Phys., 196 (2004), pp. 591-626, . · Zbl 1053.65095
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. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.