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.

[img] PDF - Published Version
See Usage Policy.

[img] PDF - Accepted Version
See Usage Policy.


Use this Persistent URL to link to this item:


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 Paper
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.
Funding AgencyGrant Number
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
Record Number:CaltechAUTHORS:20180718-150855095
Persistent URL:
Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:87972
Deposited By: George Porter
Deposited On:18 Jul 2018 22:27
Last Modified:16 Nov 2021 00:22

Repository Staff Only: item control page