  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.
