A direct solver with O(N) complexity for integral equations on one-dimensional domains

Abstract

An algorithm for the direct inversion of the linear systems arising from Nyström discretization of integral equations on one-dimensional domains is described. The method typically has O(N) complexity when applied to boundary integral equations (BIEs) in the plane with non-oscillatory kernels such as those associated with the Laplace and Stokes’ equations. The scaling coefficient suppressed by the “big-O” notation depends logarithmically on the requested accuracy. The method can also be applied to BIEs with oscillatory kernels such as those associated with the Helmholtz and time-harmonic Maxwell equations; it is efficient at long and intermediate wave-lengths, but will eventually become prohibitively slow as the wave-length decreases. To achieve linear complexity, rank deficiencies in the off-diagonal blocks of the coefficient matrix are exploited. The technique is conceptually related to the ℋ- and ℋ²-matrix arithmetic of Hackbusch and co-workers, and is closely related to previous work on Hierarchically Semi-Separable matrices.

Keywords

Direct solver / integral equation / fast direct solver / boundary value problem / boundary integral equation / hierarchically semi-separable matrix

References

[1.] Atkinson K. E. The Numerical Solution of Integral Equations of the Second Kind, 1997, Cambridge: Cambridge University Press

[2.] Barnes J., Hut P. A hierarchical O(n log n) force-calculation algorithm. Nature, 1986, 324(4): 446-449

[3.] Beylkin G., Coifman R., Rokhlin V. Wavelets in numerical analysis. Wavelets and Their Applications, 1992, Boston: Jones and Bartlett, 181-210

[4.] Börm S. Efficient Numerical Methods for Non-local Operators: ℋ²-matrix Compression, Algorithms and Analysis. European Mathematics Society, 2010

[5.] Bremer J., Rokhlin V. Efficient discretization of Laplace boundary integral equations on polygonal domains. J Comput Phys, 2010, 229: 2507-2525

[6.] Chandrasekaran S., Gu M. A divide-and-conquer algorithm for the eigendecomposition of symmetric block-diagonal plus semiseparable matrices. Numer Math, 2004, 96(4): 723-731

[7.] Chandrasekaran S., Gu M., Li X. S., Xia J. Superfast multifrontal method for large structured linear systems of equations. SIAM J Matrix Anal Appl, 2009, 31: 1382-1411

[8.] Chandrasekaran S., Gu M., Li X. S., Xia J. Fast algorithms for hierarchically semiseparable matrices. Numer Linear Algebra Appl, 2010, 17: 953-976

[9.] Cheng H., Gimbutas Z., Martinsson P. G., Rokhlin V. On the compression of low rank matrices. SIAM J Sci Comput, 2005, 26(4): 1389-1404

[10.] Gillman A. Fast direct solvers for elliptic partial differential equations, 2011, Boulder: University of Colorado at Boulder

[11.] Golub G. H., Van Loan C. F. Matrix Computations, 1996 3rd ed. Baltimore: Johns Hopkins University Press

[12.] Grasedyck L., Kriemann R., Le Borne S. Domain decomposition based H-LU preconditioning. Numer Math, 2009, 112: 565-600

[13.] Greengard L., Gueyffier D., Martinsson P. G., Rokhlin V. Fast direct solvers for integral equations in complex three-dimensional domains. Acta Numer, 2009, 18: 243-275

[14.] Greengard L., Rokhlin V. A fast algorithm for particle simulations. J Comput Phys, 1987, 73(2): 325-348

[15.] Gu M., Eisenstat S. C. Efficient algorithms for computing a strong rank-revealing QR factorization. SIAM J Sci Comput, 1996, 17(4): 848-869

[16.] Hackbusch W. The panel clustering technique for the boundary element method (invited contribution). In: Boundary Elements IX, Vol 1 (Stuttgart, 1987), Comput Mech Southampton. 1987, 463–474

[17.] Hackbusch W. A sparse matrix arithmetic based on H-matrices; Part I: Introduction to H-matrices. Computing, 1999, 62: 89-108

[18.] Helsing J., Ojala R. Corner singularities for elliptic problems: Integral equations, graded meshes, quadrature, and compressed inverse preconditioning. J Comput Phys, 2008, 227: 8820-8840

[19.] Kapur S., Rokhlin V. High-order corrected trapezoidal quadrature rules for singular functions. SIAM J Numer Anal, 1997, 34: 1331-1356

[20.] Martinsson P. G. A fast randomized algorithm for computing a hierarchically semiseparable representation of a matrix. SIAM J Matrix Anal Appl, 2011, 32(4): 1251-1274

[21.] Martinsson P. G., Rokhlin V. A fast direct solver for boundary integral equations in two dimensions. J Comp Phys, 2005, 205(1): 1-23

[22.] Michielssen E., Boag A., Chew W. C. Scattering from elongated objects: direct solution in O(N log²N) operations. IEE Proc Microw Antennas Propag, 1996, 143(4): 277-283

[23.] O’Donnell S. T., Rokhlin V. A fast algorithm for the numerical evaluation of conformal mappings. SIAM J Sci Stat Comput, 1989, 10: 475-487

[24.] Schmitz P, Ying L. A fast direct solver for elliptic problems on general meshes in 2d. 2010

[25.] Sheng Z., Dewilde P., Chandrasekaran S. Algorithms to solve hierarchically semiseparable systems. System Theory, the Schur Algorithm and Multidimensional Analysis. Oper Theory Adv Appl, Vol 176, 2007, Basel: Birkhäuser, 255-294

[26.] Starr P., Rokhlin V. On the numerical solution of two-point boundary value problems. II. Comm Pure Appl Math, 1994, 47(8): 1117-1159

[27.] Xiao H., Rokhlin V., Yarvin N. Prolate spheroidal wavefunctions, quadrature and interpolation. Inverse Problems, 2001, 17(4): 805-838

[28.] Young P, Hao S, Martinsson P G. A high-order Nyström discretization scheme for boundary integral equations defined on rotationally symmetric surfaces. J Comput Phys (to appear)