CaltechAUTHORS
  A Caltech Library Service

An Adaptive Fast Solver for a General Class of Positive Definite Matrices Via Energy Decomposition

Hou, Thomas Y. and Huang, De and Lam, Ka Chun and Zhang, Pengchuan (2018) An Adaptive Fast Solver for a General Class of Positive Definite Matrices Via Energy Decomposition. Multiscale Modeling and Simulation, 16 (2). pp. 615-678. ISSN 1540-3459. doi:10.1137/17M1140686. https://resolver.caltech.edu/CaltechAUTHORS:20180718-150855095

[img] PDF - Published Version
See Usage Policy.

4MB
[img] PDF - Accepted Version
See Usage Policy.

4MB

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

Abstract

In this paper, we propose an adaptive fast solver for a general class of symmetric positive definite (SPD) matrices which include the well-known graph Laplacian. We achieve this by developing an adaptive operator compression scheme and a multiresolution matrix factorization algorithm which achieve nearly optimal performance on both complexity and well-posedness. To develop our adaptive operator compression and multiresolution matrix factorization methods, we first introduce a novel notion of energy decomposition for SPD matrix $A$ using the representation of energy elements. The interaction between these energy elements depicts the underlying topological structure of the operator. This concept of decomposition naturally reflects the hidden geometric structure of the operator which inherits the localities of the structure. By utilizing the intrinsic geometric information under this energy framework, we propose a systematic operator compression scheme for the inverse operator $A^{-1}$. In particular, with an appropriate partition of the underlying geometric structure, we can construct localized basis by using the concept of interior and closed energy. Meanwhile, two important localized quantities are introduced, namely, the error factor and the condition factor. Our error analysis results show that these two factors will be the guidelines for finding the appropriate partition of the basis functions such that prescribed compression error and acceptable condition number can be achieved. By virtue of this insight, we propose the patch pairing algorithm to realize our energy partition framework for operator compression with controllable compression error and condition number.


Item Type:Article
Related URLs:
URLURL TypeDescription
https://doi.org/10.1137/17M1140686DOIArticle
http://arxiv.org/abs/1707.08277arXivDiscussion Paper
ORCID:
AuthorORCID
Zhang, Pengchuan0000-0003-1155-9507
Additional Information:© 2018, Society for Industrial and Applied Mathematics. Submitted: 26 July 2017. Accepted: 29 January 2018. Published online: 05 April 2018. The work of the authors was supported in part by NSF grants DMS-1318377 and DMS-1613861. We would like to thank Prof. Houman Owhadi for the suggestions and discussions throughout the development of this work.
Funders:
Funding AgencyGrant Number
NSFDMS-1318377
NSFDMS-1613861
Subject Keywords:energy decomposition, graph Laplacian, SPD matrix, fast solver, operator compression, multiresolution matrix decomposition
Issue or Number:2
Classification Code:AMS subject classifications. 15A09, 65F08, 68R10
DOI:10.1137/17M1140686
Record Number:CaltechAUTHORS:20180718-150855095
Persistent URL:https://resolver.caltech.edu/CaltechAUTHORS:20180718-150855095
Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:87972
Collection:CaltechAUTHORS
Deposited By: George Porter
Deposited On:18 Jul 2018 22:27
Last Modified:16 Nov 2021 00:22

Repository Staff Only: item control page