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 April 5, 2018 | Published + Accepted Version
Journal Article Open

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

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.

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.

Attached Files

Published - 17m1140686.pdf

Accepted Version - 1707.08277

Files

17m1140686.pdf
Files (8.5 MB)
Name Size Download all
md5:4b73649c1d70508f665a6d5aa70f46ea
4.4 MB Download
md5:7961e93fb75bf2c66813c1674da8340c
4.2 MB Preview Download

Additional details

Created:
August 19, 2023
Modified:
October 18, 2023