Papers › Sparse recovery of elliptic solvers from matrix-vector products
Sparse recovery of elliptic solvers from matrix-vector products
Florian Schäfer, Houman Owhadi
The archive published only this paper's code-link row. Authors, date and abstract are from arXiv's metadata (CC0), read from the Kaggle arXiv metadata snapshot of 2026-09-12 where its title matched the archive's; the title is the archive's.
In this work, we show that solvers of elliptic boundary value problems in d dimensions can be approximated to accuracy ϵ from only 𝒪(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 𝒪(Nlog²(N)log²ᵈ(N / ϵ)) and represents the solution operator as a sparse Cholesky factorization with 𝒪(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 𝒪(log(N)logᵈ(N / ϵ)) complexity computation of individual entries of the matrix representation of the solver that, in turn, enables its recompression to an 𝒪(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 𝒪(log^(1 + 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.
In Syntology Open this paper in Syntology's Atlas, the map of the papers in Syntology's graph and their citations.
Code
Repository list and official/mentioned flags are the archive's, frozen 2025-07-28. Reachability, where shown, is from one Syntology probe window (2026-09-16 to 2026-09-18); repositories not probed show nothing. GitHub stars are not tracked.
Code Syntology ran Syntology
Not run by Syntology. Nothing on this page verifies that the listed code works.
Results from the paper archive 2025-07-28
No leaderboard rows for this paper in the archive.
Report a problem or propose a change · a person checks every report against the paper or source before anything changes; decisions are listed on /corrections