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 February 7, 2017 | Published + Submitted
Journal Article Open

Multigrid with rough coefficients and Multiresolution operator decomposition from Hierarchical Information Games


We introduce a near-linear complexity (geometric and meshless/algebraic) multigrid/multiresolution method for PDEs with rough (L∞) coefficients with rigorous a priori accuracy and performance estimates. The method is discovered through a decision/game theory formulation of the problems of (1) identifying restriction and interpolation operators, (2) recovering a signal from incomplete measurements based on norm constraints on its image under a linear operator, and (3) gambling on the value of the solution of the PDE based on a hierarchy of nested measurements of its solution or source term. The resulting elementary gambles form a hierarchy of (deterministic) basis functions of H^1_0 (Ω) (gamblets) that (1) are orthogonal across subscales/subbands with respect to the scalar product induced by the energy norm of the PDE, (2) enable sparse compression of the solution space in H^1_0 (Ω), and (3) induce an orthogonal multiresolution operator decomposition. The operating diagram of the multigrid method is that of an inverted pyramid in which gamblets are computed locally (by virtue of their exponential decay) and hierarchically (from fine to coarse scales) and the PDE is decomposed into a hierarchy of independent linear systems with uniformly bounded condition numbers. The resulting algorithm is parallelizable both in space (via localization) and in bandwidth/subscale (subscales can be computed independently from each other). Although the method is deterministic, it has a natural Bayesian interpretation under the measure of probability emerging (as a mixed strategy) from the information game formulation, and multiresolution approximations form a martingale with respect to the filtration induced by the hierarchy of nested measurements.

Additional Information

© 2017 Published by SIAM under the terms of the Creative Commons 4.0 license. Received by the editors March 27, 2015; accepted for publication (in revised form) March 4, 2016; published electronically February 7, 2017. This work was supported by the Air Force Office of Scientific Research and the DARPA EQUiPS Program under awards FA9550-12-1-0389 (Scientific Computation of Optimal Statistical Estimators) and FA9550-16-1-0054 (Computational Information Games) and the U.S. Department of Energy Office of Science, Office of Advanced Scientific Computing Research, through the Exascale Co-Design Center for Materials in Extreme Environments (ExMatEx, LANL contract DE-AC52-06NA25396, Caltech subcontract 273448).

Attached Files

Published - 15m1013894.pdf

Submitted - 1503.03467v3.pdf


Files (12.5 MB)
Name Size Download all
3.9 MB Preview Download
8.6 MB Preview Download

Additional details

August 19, 2023
October 17, 2023