The inverse fast multipole method: using a fast approximate direct dolver as a preconditioner for dense linear systems. (English) Zbl 1365.65068


65F05 Direct numerical methods for linear systems and matrix inversion
65F08 Preconditioners for iterative methods
65F35 Numerical computation of matrix norms, conditioning, scaling


Full Text: DOI arXiv


[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, , 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] M. Bebendorf, Hierarchical Matrices: A Means to Efficiently Solve Elliptic Boundary Value Problems, Springer, Berlin, 2008. · Zbl 1151.65090
[5] M. Bebendorf and S. Rjasanow, Adaptive low-rank approximation of collocation matrices, Computing, 70 (2003), pp. 1–24. · Zbl 1068.41052
[6] M. Bonnet, Boundary Integral Equation Methods for Solids and Fluids, John Wiley & Sons, Chichester, UK, 1995.
[7] S. Börm, Data-sparse approximation of non-local operators by \(\mathcal{H}^2\)-matrices, Linear Algebra Appl., 422 (2007), pp. 380–403. · Zbl 1115.65041
[8] S. Börm, L. Grasedyck, and W. Hackbusch, Introduction to hierarchical matrices with applications, Eng. Anal. Bound. Elem., 27 (2003), pp. 405–422. · Zbl 1035.65042
[9] M. D. Buhmann, Radial Basis Functions: Theory and Implementations, Cambridge University Press, Cambridge, UK, 2003. · Zbl 1038.41001
[10] B. Carpentieri, I. S. Duff, L. Giraud, and M. Magolu monga Made, Sparse symmetric preconditioners for dense linear systems in electromagnetism, Numer. Linear Algebra Appl., 11 (2004), pp. 753–771. · Zbl 1164.65340
[11] J. Carrier, L. Greengard, and V. Rokhlin, A fast adaptive multipole algorithm for particle simulations, SIAM J. Sci. Stat. Comput., 9 (1988), pp. 669–686. · Zbl 0656.65004
[12] M. Chandrasekaran, S. 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
[13] 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
[14] S. H. Christiansen and J.-C. Nédélec, A preconditioner for the electric field integral equation based on Calderon formulas, SIAM J. Numer. Anal., 40 (2002), pp. 1100–1135. · Zbl 1021.78010
[15] 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
[16] M. Darbas, E. Darrigrand, and Y. Lafranche, Combining analytic preconditioner and fast multipole Method for the 3-D Helmholtz equation, J. Comput. Phys., 236 (2013), pp. 289–316. · Zbl 1286.78004
[17] E. Darve, The fast multipole method: Numerical implementation, J. Comput. Phys., 160 (2000), pp. 195–240. · Zbl 0974.78012
[18] S. Delong, F. B. Usabiaga, R. Delgado-Buscalioni, B. E. Griffith, and A. Donev, Brownian dynamics without Green’s functions, J. Chem. Phys., 140 (2014), 134110.
[19] W. Fong and E. Darve, The black-box fast multipole method, J. Comput. Phys., 228 (2009), pp. 8712–8725. · Zbl 1177.65009
[20] A. Gillman and P.-G. Martinsson, An O(N) algorithm for constructing the solution operator to 2D elliptic boundary value problems in the absence of body loads, Adv. Comput. Math., 40 (2014), pp. 773–796. · Zbl 1295.65107
[21] G. H. Golub and C. F. Van Loan, Matrix Computations, 3rd ed., John Hopkins University Press, Baltimore, MD, 1996. · Zbl 0865.65009
[22] L. Greengard and V. Rokhlin, A fast algorithm for particle simulations, J. Comput. Phys., 73 (1987), pp. 325–348. · Zbl 0629.65005
[23] G. Guennebaud et al., Eigen v3, , 2010.
[24] N. A. Gumerov and R. Duraiswami, Fast radial basis function interpolation via preconditioned Krylov iteration, SIAM J. Sci. Comput., 29 (2007), pp. 1876–1899. · Zbl 1154.65303
[25] W. Hackbusch, A sparse matrix arithmetic based on \(\mathscr{H}\)-matrices. Part I: Introduction to \(\mathscr{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, \(\mathscr{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. Khoromskij, A sparse \(\mathscr{H}\)-matrix arithmetic: General complexity estimates, J. Comput. Appl. Math., 125 (2000), pp. 479–501. · Zbl 0977.65036
[29] W. Hackbusch, B. N. Khoromskij, and R. Kriemann, Hierarchical matrices based on a weak admissibility criterion, Computing, 73 (2004), pp. 207–243. · Zbl 1063.65035
[30] W. Hackbusch and Z. Nowak, On the fast matrix multiplication in the boundary element method by panel clustering, Numer. Math., 54 (1989), pp. 463–491. · Zbl 0641.65038
[31] 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
[32] K. L. Ho and L. Greengard, A fast direct solver for structured linear systems by recursive skeletonization, SIAM J. Sci. Comput., 34 (2012), pp. 2507–2532. · Zbl 1259.65062
[33] 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
[34] K. L. Ho and L. Ying, Hierarchical interpolative factorization for elliptic operators: Integral equations, Comm. Pure Appl. Math., 69 (2016), pp. 1314–1353. · Zbl 1344.65123
[35] G. C. Hsiao, Boundary element methods—an overview, Appl. Numer. Math., 56 (2006), pp. 1356–1369. · Zbl 1237.65133
[36] B. Kallemov, A. Pal Singh Bhalla, B. E. Griffith, and A. Donev, An Immersed Boundary Method for Rigid Bodies, Commun. Appl. Math. Comput. Sci., 11 (2016), pp. 79–141, . · Zbl 1382.76191
[37] R. E. Kalman, Mathematical description of linear dynamical systems, SIAM J. Control Optim., 1 (1963), pp. 152–192. · Zbl 0145.34301
[38] 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
[39] U. Langer and D. Pusch, Data-sparse algebraic multigrid methods for large scale boundary element equations, Appl. Numer. Math., 54 (2005), pp. 406–424. · Zbl 1073.65135
[40] J. Lee, J. Zhang, and C. Lu, Incomplete LU preconditioning for large scale dense complex linear systems from electromagnetic wave scattering problems, J. Comput. Phys., 185 (2003), pp. 158–175. · Zbl 1017.65027
[41] B. Lizé, Fast Direct Solver for the Boundary Element Method in Electromagnetism and Acoustics: \(\mathcal{H}\)-Matrices. Parallelism and Industrial Applications, Ph.D. thesis, Université Paris 13, Paris, 2014.
[42] 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
[43] N. Nishimura, Fast multipole accelerated boundary integral equation methods, Appl. Mech. Rev., 55 (2002), pp. 299–324.
[44] T. Pals, Multipole for Scattering Computations: Spectral Discretization, Stabilization, Fast Solvers, Ph.D. thesis, University of California, Santa Barbara, CA, 2004.
[45] A. Piche, G.-P. Piau, O. Urrea, G. Sabanowski, B. Lize, J. Robert, G. Sylvand, P. Benjamin, A. Thain, R. Perraud, and G. Peres, BEM/MoM fast direct computation for antenna sitting and antenna coupling on large aeronautic plateforms, in Proceedings of the 2014 IEEE Conference on Antenna Measurements & Applications (CAMA), 2014, , 2014, 7003376.
[46] H. Pouransari, P. Coulier, and E. Darve, Fast Hierarchical Solvers for Sparse Matrices, SIAM J. Sci. Comput., accepted. · Zbl 1365.65072
[47] H. Pouransari and E. Darve, Optimizing the adaptive fast multipole method for fractal sets, SIAM J. Sci. Comput., 37 (2015), pp. A1040–A1066. · Zbl 1316.28010
[48] S. Rjasanow and O. Steinbach, The Fast Solution of Boundary Integral Equations, Mathematical and Analytical Techniques with Applications to Engineering, Springer, New York, 2007. · Zbl 1119.65119
[49] V. Rokhlin, Rapid solution of integral equations of classical potential theory, J. Comput. Phys., 60 (1985), pp. 187–207. · Zbl 0629.65122
[50] J. Rotne and S. Prager, Variational treatment of hydrodynamic interaction in polymers, J. Chem. Phys., 50 (1969), pp. 4831–4837.
[51] Y. Saad, Krylov subspace methods for solving large unsymmetric linear systems, Math. Comp., 37 (1981), pp. 105–126. · Zbl 0474.65019
[52] Y. Saad, A flexible inner-outer preconditioned GMRES algorithm, SIAM J. Sci. Comput., 14 (1993), pp. 461–469. · Zbl 0780.65022
[53] Y. Saad and M. H. Schultz, GMRES: A generalized minimal residual algorithm for solving nonsymmetric linear systems, SIAM J. Sci. Stat. Comput., 7 (1986), pp. 856–869. · Zbl 0599.65018
[54] S. Sauter, The panel clustering method in 3-d BEM, in Wave Propagation in Complex Media, G. Papanicolaou, ed., The IMA Volumes in Mathematics and its Applications 96, Springer, New York, 1998, pp. 199–224. · Zbl 0901.65070
[55] Z. Sheng, P. Dewilde, and S. Chandrasekaran, Algorithms to solve hierarchically semi-separable systems, in System Theory, the Schur Algorithm and Multidimensional Analysis, D. Alpay and V. Vinnikov, eds., Operator Theory: Advances and Applications 176, Birkhäuser, Basel, 2007, pp. 255–294. · Zbl 1123.65020
[56] U. Trottenberg, C. W. Oosterlee, and A. Schuller, Multigrid, Academic Press, London, 2000.
[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, S. Chandrasekaran, M. Gu, and X. S. Li, Superfast multifrontal method for large structured linear systems of equations, SIAM J. Matrix Anal. Appl., 31 (2010), pp. 1382–1411. · Zbl 1195.65031
[59] L. Ying, G. Biros, and D. Zorin, 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. 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.