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

doi:10.1007/s11464-012-0188-3

Front Math Chin

2012, Vol. 7

Issue (2) : 217-247 https://doi.org/10.1007/s11464-012-0188-3

RESEARCH ARTICLE

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

Adrianna GILLMAN, Patrick M. YOUNG, Per-Gunnar MARTINSSON(

)

Department of Applied Mathematics, University of Colorado at Boulder, Boulder, CO 80309-0526, USA

Download: PDF(418 KB) HTML
Export: BibTeX | EndNote | Reference Manager | ProCite | RefWorks

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 H – and H ²-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

Corresponding Author(s): MARTINSSON Per-Gunnar,Email:martinss@colorado.edu

Issue Date: 01 April 2012

Cite this article:

Adrianna GILLMAN,Patrick M. YOUNG,Per-Gunnar MARTINSSON. A direct solver with O(N) complexity for integral equations on one-dimensional domains[J]. Front Math Chin, 2012, 7(2): 217-247.

URL:

https://academic.hep.com.cn/fmc/EN/10.1007/s11464-012-0188-3
https://academic.hep.com.cn/fmc/EN/Y2012/V7/I2/217

1	Atkinson K E. The Numerical Solution of Integral Equations of the Second Kind. Cambridge: Cambridge University Press, 1997 doi: 10.1017/CBO9780511626340
2	Barnes J, Hut P. A hierarchical O(n log n) force-calculation algorithm. Nature , 1986, 324(4): 446-449 doi: 10.1038/324446a0
3	Beylkin G, Coifman R, Rokhlin V. Wavelets in numerical analysis. In: Wavelets and Their Applications . Boston: Jones and Bartlett, 1992, 181-210
4	B?rm S. Efficient Numerical Methods for Non-local Operators: H 2-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 doi: 10.1016/j.jcp.2009.12.001
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 doi: 10.1007/s00211-002-0199-1
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 doi: 10.1002/nla.691
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 doi: 10.1137/030602678
10	Gillman A. Fast direct solvers for elliptic partial differential equations. Ph D Thesis . Boulder: University of Colorado at Boulder, 2011
11	Golub G H, Van Loan C F. Matrix Computations. 3rd ed. Johns Hopkins Studies in the Mathematical Sciences. Baltimore: Johns Hopkins University Press, 1996
12	Grasedyck L, Kriemann R, Le Borne S. Domain decomposition based H-LU preconditioning. Numer Math , 2009, 112: 565-600 doi: 10.1007/s00211-009-0218-6
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 doi: 10.1017/S0962492906410011
14	Greengard L, Rokhlin V. A fast algorithm for particle simulations. J Comput Phys , 1987, 73(2): 325-348 doi: 10.1016/0021-9991(87)90140-9
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 doi: 10.1137/0917055
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 doi: 10.1007/s006070050015
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 doi: 10.1016/j.jcp.2008.06.022
19	Kapur S, Rokhlin V. High-order corrected trapezoidal quadrature rules for singular functions. SIAM J Numer Anal , 1997, 34: 1331-1356 doi: 10.1137/S0036142995287847
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 doi: 10.1137/100786617
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 doi: 10.1016/j.jcp.2004.10.033
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 doi: 10.1049/ip-map:19960400
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 doi: 10.1137/0910031
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. In: System Theory, the Schur Algorithm and Multidimensional Analysis. Oper Theory Adv Appl , Vol 176. Basel: Birkh?user, 2007, 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 doi: 10.1002/cpa.3160470806
27	Xiao H, Rokhlin V, Yarvin N. Prolate spheroidal wavefunctions, quadrature and interpolation. Inverse Problems , 2001, 17(4): 805-838 doi: 10.1088/0266-5611/17/4/315
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)

[1]	Boling GUO, Jun WU. Local regularity properties for 1D mixed nonlinear Schrödinger equations on half-line[J]. Front. Math. China, 2020, 15(6): 1121-1142.
[2]	Huaiyu JIAN, Hongbo ZENG. Existence and uniqueness for variational problem from progressive lens design[J]. Front. Math. China, 2020, 15(3): 491-505.
[3]	Yunxia WEI, Yanping CHEN, Xiulian SHI, Yuanyuan ZHANG. Spectral method for multidimensional Volterra integral equation with regular kernel[J]. Front. Math. China, 2019, 14(2): 435-448.
[4]	Yutian LEI, Chao MA. Optimal integrability of some system of integral equations[J]. Front Math Chin, 2014, 9(1): 81-91.
[5]	Ran ZHANG, Benxi ZHU, Hehu XIE. Spectral methods for weakly singular Volterra integral equations with pantograph delays[J]. Front Math Chin, 2013, 8(2): 281-299.
[6]	Zhanwen YANG, Hermann BRUNNER. Blow-up behavior of Hammerstein-type delay Volterra integral equations[J]. Front Math Chin, 2013, 8(2): 261-280.
[7]	Marek KOLK, Arvet PEDAS. Numerical solution of Volterra integral equations with singularities[J]. Front Math Chin, 2013, 8(2): 239-259.
[8]	Xianjuan LI, Tao TANG. Convergence analysis of Jacobi spectral collocation methods for Abel-Volterra integral equations of second kind[J]. Front Math Chin, 2012, 7(1): 69-84.
[9]	Ishtiaq ALI, Hermann BRUNNER, Tao TANG. Spectral methods for pantograph-type differential and integral equations with multiple delays[J]. Front Math Chin, 2009, 4(1): 49-61.
[10]	CHEN Shuxing. Initial boundary value problems for quasilinear symmetric hyperbolic systems with characteristic boundary[J]. Front. Math. China, 2007, 2(1): 87-102.
[11]	TAO Xiangxing. Noncontinuous data boundary value problems for Schr╫dinger equation in Lipschitz domains[J]. Front. Math. China, 2006, 1(4): 589-603.

Viewed

Full text

Abstract

Cited

Shared

Discussed