Sparse Recovery of Elliptic Solvers from Matrix-Vector Products

DOI10.1137/22M154226XMaRDI QIDQ6154205zbMATH OpenOpenAlexFDO

Authors Florian Schäfer, Houman Owhadi

Publication date 19 March 2024

Published in SIAM Journal on Scientific Computing (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/2110.05351

zbMATH Keywords

Cholesky factorizationelliptic PDElearning solution operatorsnumerical homogenizationprincipal component analysissparsity

Mathematics Subject Classification ID

Fractional partial differential equations (35R11) Bayesian problems; characterization of Bayes procedures (62C10) Direct numerical methods for linear systems and matrix inversion (65F05) Computational methods for sparse matrices (65F50) Numerical methods for low-rank matrix approximation; matrix compression (65F55) Error bounds for boundary value problems involving PDEs (65N15) Numerical solution of discretized equations for boundary value problems involving PDEs (65N22) Multigrid methods; domain decomposition for boundary value problems involving PDEs (65N55) Parallel numerical computation (65Y05) Artificial neural networks and deep learning (68T07)

Abstract: In this work, we show that solvers of elliptic boundary value problems in $d$ dimensions can be approximated to accuracy $epsilon$ from only $Oleft(log(N)lo{g}^d(N/epsilon)ight)$ matrix-vector products with carefully chosen vectors (right-hand sides). The solver is only accessed as a black box, and the underlying operator may be unknown and of an arbitrarily high order. Our algorithm (1) has complexity $Oleft(Nlo{g}^2(N)lo{g}^{2d}(N/epsilon)ight)$ and represents the solution operator as a sparse Cholesky factorization with $Oleft(Nlog(N)lo{g}^d(N/epsilon)ight)$ nonzero entries, (2) allows for embarrassingly parallel evaluation of the solution operator and the computation of its log-determinant, (3) allows for $Oleft(log(N)lo{g}^d(N/epsilon)ight)$ complexity computation of individual entries of the matrix representation of the solver that, in turn, enables its recompression to an $Oleft(Nlo{g}^d(N/epsilon)ight)$ complexity representation. As a byproduct, our compression scheme produces a homogenized solution operator with near-optimal approximation accuracy. By polynomial approximation, we can also approximate the continuous Green's function (in operator and Hilbert-Schmidt norm) to accuracy $epsilon$ from $Oleft(lo{g}^{1+d}left(epsilo{n}^{-1}ight)ight)$ solutions of the PDE. We include rigorous proofs of these results. To the best of our knowledge, our algorithm achieves the best-known trade-off between accuracy $epsilon$ and the number of required matrix-vector products.

Recommendations

• Approximation of solution operators of elliptic partial differential equations by \({\mathcal H}\)- and \({\mathcal H}^2\)-matrices
• An O(N) algorithm for constructing the solution operator to 2D elliptic boundary value problems in the absence of body loads
• Sparse Compression of Expected Solution Operators
• Approximation of integral operators by Green quadrature and nested cross approximation
• A fast direct solver for a class of elliptic partial differential equations

Cites work

• A Multiscale Neural Network Based on Hierarchical Matrices
• A multiscale neural network based on hierarchical nested bases
• A survey of direct methods for sparse linear systems
• BCR-net: A neural network based on the nonstandard wavelet form
• Compressing Rank-Structured Matrices via Randomized Sampling
• Compression, inversion, and approximate PCA of dense kernel matrices at near-linear computational complexity
• Fast algorithm for extracting the diagonal of the inverse matrix with application to the electronic structure analysis of metallic systems
• Fast construction of hierarchical matrix representation from matrix-vector multiplication
• Graph colouring algorithms
• Hierarchical Matrix Approximations of Hessians Arising in Inverse Problems Governed by PDEs
• Learning elliptic partial differential equations with randomized linear algebra
• Numerical homogenization beyond scale separation
• Operator-adapted wavelets, fast solvers, and numerical homogenization. From a game theoretic approach to numerical approximation and algorithm design
• SelInv---An Algorithm for Selected Inversion of a Sparse Symmetric Matrix
• Sparse Cholesky Factorization by Kullback--Leibler Minimization
• Sparse Compression of Expected Solution Operators
• The Bramble--Hilbert Lemma for Convex Domains
• The Random Feature Model for Input-Output Maps between Banach Spaces

Cited in

(4)

• Operator learning using random features: a tool for scientific computing
• Operator learning with Gaussian processes
• An operator learning perspective on parameter-to-observable maps
• Fixed-sparsity matrix approximation from matrix-vector products

This page was built for publication: Sparse Recovery of Elliptic Solvers from Matrix-Vector Products

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6154205)