A tensor-train accelerated solver for integral equations in complex geometries
From MaRDI portal
Publication:1685248
DOI10.1016/J.JCP.2016.12.051zbMATH Open1380.65434arXiv1511.06029OpenAlexW2962693312MaRDI QIDQ1685248FDOQ1685248
Authors: E. Corona, Abtin Rahimian, Denis Zorin 
Publication date: 13 December 2017
Published in: Journal of Computational Physics (Search for Journal in Brave)
Abstract: 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 and once the inverse is computed, it can be applied in . 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.
Full work available at URL: https://arxiv.org/abs/1511.06029
Recommendations
- An \(O(N)\) direct solver for integral equations on the plane
- Overlapping domain decomposition preconditioner for integral equations
- A fast direct solver for structured linear systems by recursive skeletonization
- Hierarchical interpolative factorization for elliptic operators: integral equations
- Fast quadrature techniques for retarded potentials based on TT/QTT tensor approximation
integral equationsfast multipole methodscomplex geometrieshierarchical matrix compression and inversionpreconditioned iterative solvertensor train decomposition
Complexity and performance of numerical algorithms (65Y20) Numerical methods for integral equations (65R20)
Cites Work
- Efficient numerical methods for non-local operators. \(\mathcal H^2\)-matrix compression, algorithms and analysis.
- Preconditioning techniques for large linear systems: A survey
- Fast algorithms for hierarchically semiseparable matrices
- A Fast $ULV$ Decomposition Solver for Hierarchically Semiseparable Representations
- A fast algorithm for particle simulations
- Tensor Decompositions and Applications
- Hierarchical matrices. A means to efficiently solve elliptic boundary value problems
- GMRES: A Generalized Minimal Residual Algorithm for Solving Nonsymmetric Linear Systems
- TT-cross approximation for multidimensional arrays
- Incomplete cross approximation in the mosaic-skeleton method
- Hierarchical Kronecker tensor-product approximations
- Bi-CGSTAB: A Fast and Smoothly Converging Variant of Bi-CG for the Solution of Nonsymmetric Linear Systems
- Tensor numerical methods for multidimensional PDEs: theoretical analysis and initial applications
- On the fast matrix multiplication in the boundary element method by panel clustering
- Title not available (Why is that?)
- Combining Fast Multipole Techniques and an Approximate Inverse Preconditioner for Large Electromagnetism Calculations
- A literature survey of low-rank tensor approximation techniques
- How Fast are Nonsymmetric Matrix Iterations?
- High-Order Corrected Trapezoidal Quadrature Rules for Singular Functions
- Linear integral equations
- Superfast Fourier transform using QTT approximation
- Fully discrete spectral boundary integral methods for Helmholtz problems on smooth closed surfaces in \(\mathbb R^3\)
- Approximation of \(2^d\times2^d\) matrices using tensor decomposition
- A Class of Spectral Two-Level Preconditioners
- Low-Rank Explicit QTT Representation of the Laplace Operator and Its Inverse
- Solution of Linear Systems and Matrix Inversion in the TT-Format
- Tensorisation of vectors and their efficient convolution
- \(O(d \log N)\)-quantics approximation of \(N\)-\(d\) tensors in high-dimensional numerical modeling
- Rapid solution of integral equations of classical potential theory
- Tensor ranks for the inversion of tensor-product binomials
- A fast direct solver for boundary integral equations in two dimensions
- A direct adaptive Poisson solver of arbitrary order accuracy
- Incremental spectral preconditioners for sequences of linear systems
- On the numerical solution of two‐point boundary value problems II
- A fast direct solver for structured linear systems by recursive skeletonization
- A short survey on preconditioning techniques for large-scale dense complex linear systems in electromagnetics
- On the Compression of Low Rank Matrices
- A Fast Solver for HSS Representations via Sparse Matrices
- A direct solver with \(O(N)\) complexity for integral equations on one-dimensional domains
- A fast 3D dual boundary element method based on hierarchical matrices
- High-order quadratures for the solution of scattering problems in two dimensions
- Tensor properties of multilevel Toeplitz and related matrices
- Approximate iterations for structured matrices
- On interpolation and integration in finite-dimensional spaces of bounded functions
- Boundary integral method for the flow of vesicles with viscosity contrast in three dimensions
- Preconditioning for Boundary Integral Equations
- Hierarchical LU decomposition-based preconditioners for BEM
- Algebraic wavelet transform via quantics tensor train decomposition
- Grid-based lattice summation of electrostatic potentials by assembled rank-structured tensor approximation
- Wavelet sparse approximate inverse preconditioners
- Iterative near-field preconditioner for the multilevel fast multipole algorithm
- Preconditioned, Adaptive, Multipole-Accelerated Iterative Methods for Three-Dimensional First-Kind Integral Equations of Potential Theory
- Parallel Hierarchical Solvers and Preconditioners for Boundary Element Methods
- Preconditioning
- Fast quadrature techniques for retarded potentials based on TT/QTT tensor approximation
- Corrected trapezoidal rules for a class of singular functions
- Superfast inversion of two-level Toeplitz matrices using Newton iteration and tensor-displacement structure
- Tensor-train ranks for matrices and their inverses
- High-order corrected trapezoidal quadrature rules for the Coulomb potential in three dimensions
- Title not available (Why is that?)
Cited In (8)
- State estimation in nonlinear parametric time dependent systems using tensor train
- Fast Low-Rank Kernel Matrix Factorization Using Skeletonized Interpolation
- Tensor train construction from tensor actions, with application to compression of large high order derivative tensors
- Fast stray field computation on tensor grids
- A two-step accelerated Levenberg-Marquardt method for solving multilinear systems in tensor-train format
- Overlapping domain decomposition preconditioner for integral equations
- Ubiquitous evaluation of layer potentials using quadrature by kernel-independent expansion
- Efficient randomized tensor-based algorithms for function approximation and low-rank kernel interactions
Uses Software
This page was built for publication: A tensor-train accelerated solver for integral equations in complex geometries
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1685248)
