TY - JOUR

T1 - An O (N) direct solver for integral equations on the plane

AU - Corona, Eduardo

AU - Martinsson, Per Gunnar

AU - Zorin, Denis

N1 - Publisher Copyright:
© 2014 Elsevier Inc. All rights reserved.

PY - 2015/3/1

Y1 - 2015/3/1

N2 - An efficient direct solver for volume integral equations with O(N) complexity for a broad range of problems is presented. The solver relies on hierarchical compression of the discretized integral operator, and exploits that off-diagonal blocks of certain dense matrices have numerically low rank. Technically, the solver is inspired by previously developed direct solvers for integral equations based on "recursive skeletonization" and "Hierarchically Semi-Separable" (HSS) matrices, but it improves on the asymptotic complexity of existing solvers by incorporating an additional level of compression. The resulting solver has optimal O(N) complexity for all stages of the computation, as demonstrated by both theoretical analysis and numerical examples. The computational examples further display good practical performance in terms of both speed and memory usage. In particular, it is demonstrated that even problems involving 107 unknowns can be solved to precision 10-10 using a simple Matlab implementation of the algorithm executed on a single core.

AB - An efficient direct solver for volume integral equations with O(N) complexity for a broad range of problems is presented. The solver relies on hierarchical compression of the discretized integral operator, and exploits that off-diagonal blocks of certain dense matrices have numerically low rank. Technically, the solver is inspired by previously developed direct solvers for integral equations based on "recursive skeletonization" and "Hierarchically Semi-Separable" (HSS) matrices, but it improves on the asymptotic complexity of existing solvers by incorporating an additional level of compression. The resulting solver has optimal O(N) complexity for all stages of the computation, as demonstrated by both theoretical analysis and numerical examples. The computational examples further display good practical performance in terms of both speed and memory usage. In particular, it is demonstrated that even problems involving 107 unknowns can be solved to precision 10-10 using a simple Matlab implementation of the algorithm executed on a single core.

KW - Direct solvers

KW - Fast algorithms

KW - Fast multipole methods

KW - Hierarchical matrix compression

KW - Integral equations

KW - Interpolative decomposition

UR - http://www.scopus.com/inward/record.url?scp=84921862711&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=84921862711&partnerID=8YFLogxK

U2 - 10.1016/j.acha.2014.04.002

DO - 10.1016/j.acha.2014.04.002

M3 - Article

AN - SCOPUS:84921862711

SN - 1063-5203

VL - 38

SP - 284

EP - 317

JO - Applied and Computational Harmonic Analysis

JF - Applied and Computational Harmonic Analysis

IS - 2

ER -