Sparse Recovery of Elliptic Solvers from Matrix-Vector Products
Florian Schäfer, Houman Owhadi · SIAM Journal on Scientific Computing · 2024
Abstract. In this work, we show that solvers of elliptic boundary value problems in [Formula: see text] dimensions can be approximated to accuracy [Formula: see text] from only [Formula: see text] 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 [Formula: see text] and represents the solution operator as a sparse Cholesky factorization with [Formula: see text] nonzero entries, (2) allows for embarrassingly parallel evaluation of the solution operator and the computation of its log-determinant, (3) allows for [Formula: see text] complexity computation of individual entries of the matrix representation of the solver that, in turn, enables its recompression to an [Formula: see text] 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 [Formula: see text] from [Formula: see text] 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 [Formula: see text] and the number of required matrix-vector products. Reproducibility of computational results. This paper has been awarded the “SIAM Reproducibility Badge: Code and data available” as a recognition that the authors have followed reproducibility principles valued by SISC and the scientific computing community. Code and data that allow readers to reproduce the results in this paper are available at https://github.com/f-t-s/sparse_recovery_of_elliptic_solution_operators_from_matrix-vector_products and in the supplementary materials ( CompressingSolvers.jl-main.zip [2.50MB], sparse_recovery_of_elliptic_solution_operators_from_matrix-vector_products-main.zip [54.8KB]). [Formula: see text]