Fast symmetric factorization of hierarchical matrices with applications

Abstract

We present a fast direct algorithm for computing symmetric factorizations, i.e. $A=W{W}^T$, of symmetric positive-definite hierarchical matrices with weak-admissibility conditions. The computational cost for the symmetric factorization scales as $\mathcal{O}(n{\log }^{2}n)$ for hierarchically off-diagonal low-rank matrices. Once this factorization is obtained, the cost for inversion, application, and determinant computation scales as $\mathcal{O}(n\log n)$. In particular, this allows for the near optimal generation of correlated random variates in the case where $A$ is a covariance matrix. This symmetric factorization algorithm depends on two key ingredients. First, we present a novel symmetric factorization formula for low-rank updates to the identity of the form $I+UK{U}^T$. This factorization can be computed in $\mathcal{O}(n)$ time if the rank of the perturbation is sufficiently small. Second, combining this formula with a recursive divide-and-conquer strategy, near linear complexity symmetric factorizations for hierarchically structured matrices can be obtained. We present numerical results for matrices relevant to problems in probability \& statistics (Gaussian processes), interpolation (Radial basis functions), and Brownian dynamics calculations in fluid mechanics (the Rotne-Prager-Yamakawa tensor).

18 pages, 8 figures, 1 table

References in corpus (2)

• A Fast Block Low-Rank Dense Solver with Applications to Finite-Element Matrices
• The Inverse Fast Multipole Method

Cited by in corpus (6)

• The Inverse Fast Multipole Method
• Estimating Model Uncertainty of Neural Networks in Sparse Information Form
• Hierarchical off-diagonal low-rank approximation of Hessians in inverse problems, with application to ice sheet model initializaiton
• Linear-Cost Covariance Functions for Gaussian Random Fields
• Fast increased fidelity approximate Gibbs samplers for Bayesian Gaussian process regression
• Efficient construction of an HSS preconditioner for symmetric positive definite ${\mathcal{H}}^2$ matrices