TY - JOUR
T1 - A Tensor-Train accelerated solver for integral equations in complex geometries
AU - Corona, Eduardo
AU - Rahimian, Abtin
AU - Zorin, Denis
N1 - Funding Information:
We extend our thanks to Sergey Dolgov, Leslie Greengard, Ivan Oseledets, and Mark Tygert for stimulating conversations about various aspects of this work. We are also grateful to Matthew Morse, Michael O'Neil, and Shravan Veerapaneni for critical reading of this work and providing valuable feedback. We thank Kenneth Ho and Lexing Ying for kindly supplying the HIF code. Support for this work was provided by the US National Science Foundation (NSF) under grant DMS-1320621. E.C. acknowledges the support of the US National Science Foundation (NSF) through grant DMS-1418964.
Publisher Copyright:
© 2017 Elsevier Inc.
PY - 2017/4/1
Y1 - 2017/4/1
N2 - We present a framework using the Quantized Tensor Train (QTT) decomposition to accurately and efficiently solve volume and boundary integral equations in three dimensions. We describe how the QTT decomposition can be used as a hierarchical compression and inversion scheme for matrices arising from the discretization of integral equations. For a broad range of problems, computational and storage costs of the inversion scheme are extremely modest O(logN) and once the inverse is computed, it can be applied in O(NlogN). We analyze the QTT ranks for hierarchically low rank matrices and discuss its relationship to commonly used hierarchical compression techniques such as FMM and HSS. We prove that the QTT ranks are bounded for translation-invariant systems and argue that this behavior extends to non-translation invariant volume and boundary integrals. For volume integrals, the QTT decomposition provides an efficient direct solver requiring significantly less memory compared to other fast direct solvers. We present results demonstrating the remarkable performance of the QTT-based solver when applied to both translation and non-translation invariant volume integrals in 3D. For boundary integral equations, we demonstrate that using a QTT decomposition to construct preconditioners for a Krylov subspace method leads to an efficient and robust solver with a small memory footprint. We test the QTT preconditioners in the iterative solution of an exterior elliptic boundary value problem (Laplace) formulated as a boundary integral equation in complex, multiply connected geometries.
AB - We present a framework using the Quantized Tensor Train (QTT) decomposition to accurately and efficiently solve volume and boundary integral equations in three dimensions. We describe how the QTT decomposition can be used as a hierarchical compression and inversion scheme for matrices arising from the discretization of integral equations. For a broad range of problems, computational and storage costs of the inversion scheme are extremely modest O(logN) and once the inverse is computed, it can be applied in O(NlogN). We analyze the QTT ranks for hierarchically low rank matrices and discuss its relationship to commonly used hierarchical compression techniques such as FMM and HSS. We prove that the QTT ranks are bounded for translation-invariant systems and argue that this behavior extends to non-translation invariant volume and boundary integrals. For volume integrals, the QTT decomposition provides an efficient direct solver requiring significantly less memory compared to other fast direct solvers. We present results demonstrating the remarkable performance of the QTT-based solver when applied to both translation and non-translation invariant volume integrals in 3D. For boundary integral equations, we demonstrate that using a QTT decomposition to construct preconditioners for a Krylov subspace method leads to an efficient and robust solver with a small memory footprint. We test the QTT preconditioners in the iterative solution of an exterior elliptic boundary value problem (Laplace) formulated as a boundary integral equation in complex, multiply connected geometries.
KW - Complex geometries
KW - Fast multipole methods
KW - Hierarchical matrix compression and inversion
KW - Integral equations
KW - Preconditioned iterative solver
KW - Tensor Train decomposition
UR - http://www.scopus.com/inward/record.url?scp=85009288360&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=85009288360&partnerID=8YFLogxK
U2 - 10.1016/j.jcp.2016.12.051
DO - 10.1016/j.jcp.2016.12.051
M3 - Article
AN - SCOPUS:85009288360
SN - 0021-9991
VL - 334
SP - 145
EP - 169
JO - Journal of Computational Physics
JF - Journal of Computational Physics
ER -