2018/05/15 by Nick Alger, Vishwas Rao, Alger, Nick +7 · 1 citation
Engineering · Physics and Astronomy · #Advanced Numerical Methods in Computational Mathematics #Electromagnetic Scattering and Analysis #Electromagnetic Simulation and Numerical Methods #FOS: Mathematics #Numerical Analysis (math.NA)
paper · pdf · doi:10.48550/arxiv.1805.06018
openalex publication_date 2018/05/15 · openalex created_date 2025/10/10 · openalex updated_date 2026/08/01
We present an adaptive grid matrix-free operator approximation scheme based\non a "product-convolution" interpolation of convolution operators. This scheme\nis appropriate for operators that are locally translation-invariant, even if\nthese operators are high-rank or full-rank. Such operators arise in Schur\ncomplement methods for solving partial differential equations (PDEs), as\nHessians in PDE-constrained optimization and inverse problems, as integral\noperators, as covariance operators, and as Dirichlet-to-Neumann maps.\nConstructing the approximation requires computing the impulse responses of the\noperator to point sources centered on nodes in an adaptively refined grid of\nsample points. A randomized a-posteriori error estimator drives the adaptivity.\nOnce constructed, the approximation can be efficiently applied to vectors using\nthe fast Fourier transform. The approximation can be efficiently converted to\nhierarchical matrix (H-matrix) format, then inverted or factorized using\nscalable H-matrix arithmetic. The quality of the approximation degrades\ngracefully as fewer sample points are used, allowing cheap lower quality\napproximations to be used as preconditioners. This yields an automated method\nto construct preconditioners for locally translation-invariant Schur\ncomplements. We directly address issues related to boundaries and prove that\nour scheme eliminates boundary artifacts. We test the scheme on a spatially\nvarying blurring kernel, on the non-local component of an interface Schur\ncomplement for the Poisson operator, and on the data misfit Hessian for an\nadvection dominated advection-diffusion inverse problem. Numerical results show\nthat the scheme outperforms existing methods.\n