Welcome to the new version of CaltechAUTHORS. Login is currently restricted to library staff. If you notice any issues, please email coda@library.caltech.edu
Published November 5, 2019 | Submitted + Published
Journal Article Open

Fast eigenpairs computation with operator adapted wavelets and hierarchical subspace correction


We present a method for the fast computation of the eigenpairs of a bijective positive symmetric linear operator L. The method is based on a combination of operator adapted wavelets (gamblets) with hierarchical subspace correction. First, gamblets provide a raw but fast approximation of the eigensubspaces of L by block-diagonalizing L into sparse and well-conditioned blocks. Next, the hierarchical subspace correction method computes the eigenpairs associated with the Galerkin restriction of L to a coarse (low-dimensional) gamblet subspace and then corrects those eigenpairs by solving a hierarchy of linear problems in the finer gamblet subspaces (from coarse to fine, using multigrid iteration). The proposed algorithm is robust to the presence of multiple (a continuum of) scales and is shown to be of near-linear complexity when L is an (arbitrary local, e.g., differential) operator mapping H^s₀(Ω) to H^(−s)(Ω) (e.g., an elliptic PDE with rough coefficients).

Additional Information

© 2019 Society for Industrial and Applied Mathematics. Received by the editors June 13, 2018; accepted for publication (in revised form) August 14, 2019; published electronically November 5, 2019. The work of the first author was partially supported by the Science Challenge project TZ2016002, the National Natural Science Foundation of China grants 11771434, 91330202, and the National Center for Mathematics and Interdisciplinary Science, CAS. The work of the second author was partially supported by the National Natural Science Foundation of China grants 11871339, 11861131004, and 11571314. The work of the third author was supported by the Air Force Office of Scientific Research (AFOSR) DARPA EQUiPS program under award number FA9550-16-1-0054 (Computational Information Games), the Air Force Office of Scientific Research under award number FA9550-18-1-0271 (Games for Computation and Learning), and the Office of Naval Research under award N00014-18-1-2363 (Toward Scalable Universal Solvers for Linear Systems). We thank Florian Schaefer for stimulating discussions. We thank two anonymous reviewers whose comments have greatly improved this manuscript.

Attached Files

Published - 18m1194079.pdf

Submitted - 1806.00565.pdf


Files (5.4 MB)
Name Size Download all
2.7 MB Preview Download
2.7 MB Preview Download

Additional details

August 19, 2023
October 18, 2023