Sparse Recovery of Elliptic Solvers from Matrix-Vector Products

.In this work, we show that solvers of elliptic boundary value problems in \(d\) dimensions can be approximated to accuracy \(ε\) from only \({O} (log (N)logᵈ(N/ ε ))\) 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 \({O} (Nlog^2(N)log²ᵈ(N/ ε ) )\) and represents the solution operator as a sparse Cholesky factorization with \({O} (Nlog (N)logᵈ(N/ ε ))\) nonzero entries, (2) allows for embarrassingly parallel evaluation of the solution operator and the computation of its log-determinant, (3) allows for \({O}(log (N)logᵈ(N/ ε ) )\) complexity computation of individual entries of the matrix representation of the solver that, in turn, enables its recompression to an \({O} (Nlogᵈ(N/ ε ) )\) 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 \(ε\) from \(O (log1 + d(ε⁻¹ ))\) 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 \(ε\) 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]).KeywordsCholesky factorizationelliptic PDEnumerical homogenizationsparsityprincipal component analysislearning solution operatorsMSC codes65N5565N2265N15