CaltechAUTHORS
  A Caltech Library Service

Fast eigenpairs computation with operator adapted wavelets and hierarchical subspace correction

Xie, Hehu and Zhang, Lei and Owhadi, Houman (2019) Fast eigenpairs computation with operator adapted wavelets and hierarchical subspace correction. SIAM Journal on Numerical Analysis, 57 (6). pp. 2519-2550. ISSN 0036-1429. https://resolver.caltech.edu/CaltechAUTHORS:20190923-154306921

[img] PDF - Published Version
See Usage Policy.

2592Kb
[img] PDF - Submitted Version
See Usage Policy.

2663Kb

Use this Persistent URL to link to this item: https://resolver.caltech.edu/CaltechAUTHORS:20190923-154306921

Abstract

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).


Item Type:Article
Related URLs:
URLURL TypeDescription
https://doi.org/10.1137/18M1194079DOIArticle
https://arxiv.org/abs/1806.00565arXivDiscussion Paper
ORCID:
AuthorORCID
Zhang, Lei0000-0001-9031-4318
Owhadi, Houman0000-0002-5677-1600
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.
Funders:
Funding AgencyGrant Number
Science Challenge ProjectTZ2016002
National Natural Science Foundation of China11771434
National Natural Science Foundation of China91330202
Chinese Academy of SciencesUNSPECIFIED
National Natural Science Foundation of China11871339
National Natural Science Foundation of China11861131004
National Natural Science Foundation of China11571314
Air Force Office of Scientific Research (AFOSR)FA9550-16-1-0054
Air Force Office of Scientific Research (AFOSR)FA9550-18-1-0271
Office of Naval Research (ONR)N00014-18-1-2363
Defense Advanced Research Projects Agency (DARPA)UNSPECIFIED
Subject Keywords:multiscale eigenvalue problem, gamblet decomposition, multigrid iteration, subspace correction, numerical homogenization
Issue or Number:6
Classification Code:AMS subject classifications: 65N30, 65N25, 65L15, 65B99
Record Number:CaltechAUTHORS:20190923-154306921
Persistent URL:https://resolver.caltech.edu/CaltechAUTHORS:20190923-154306921
Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:98807
Collection:CaltechAUTHORS
Deposited By: Tony Diaz
Deposited On:23 Sep 2019 23:05
Last Modified:23 Jul 2020 18:24

Repository Staff Only: item control page