A Caltech Library Service

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

Owhadi, Houman (2017) Multigrid with rough coefficients and Multiresolution operator decomposition from Hierarchical Information Games. SIAM Review, 59 (1). pp. 99-149. ISSN 0036-1445.

[img] PDF - Published Version
Creative Commons Attribution.

[img] PDF - Submitted Version
See Usage Policy.


Use this Persistent URL to link to this item:


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.

Item Type:Article
Related URLs:
URLURL TypeDescription Paper
Owhadi, Houman0000-0002-5677-1600
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).
Funding AgencyGrant Number
Air Force Office of Scientific Research (AFOSR)FA9550-12-1-0389
Air Force Office of Scientific Research (AFOSR)FA9550-16-1-0054
Defense Advanced Research Projects Agency (DARPA)UNSPECIFIED
Department of Energy (DOE)DE-AC52-06NA25396
Subject Keywords:multigrid, multiresolution, game theory, wavelets, information based complexity, decision theory
Issue or Number:1
Classification Code:AMS subject classifications. 68T99, 65N55, 65F99, 65N75, 62C99, 42C40, 60G42, 68Q25
Record Number:CaltechAUTHORS:20160223-133809979
Persistent URL:
Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:64685
Deposited By: Kristin Buxton
Deposited On:23 Feb 2016 21:52
Last Modified:03 Oct 2019 09:40

Repository Staff Only: item control page