SUPR
A dyadic algorithm for inverting sparse matrices
Dnr:

NAISS 2024/22-228

Type:

NAISS Small Compute

Principal Investigator:

Hanqing Wu

Affiliation:

Lunds universitet

Start Date:

2024-02-16

End Date:

2025-03-01

Primary Classification:

10105: Computational Mathematics

Webpage:

Allocation

Abstract

The field of high-dimensional statistics often requires the computation of precision matrices, which are typically the inverse of sparse covariance matrices. The current standard method for inverting these matrices is Gaussian elimination, a process that can be computationally intensive and time-consuming. This research aims to investigate a faster method of inverting sparse matrices using a novel dyadic algorithm. This algorithm leverages the dyadic structure inherent in many sparse matrices to expedite the inversion process. The proposed dyadic algorithm theoretically achieves a complexity of O(n^2 logn) which is significantly faster than the Gaussian elimination method. The research will involve a thorough examination of this algorithm, including its design, implementation, and performance in various scenarios. We anticipate that this method will greatly accelerate the computation of precision matrices in high-dimensional statistics. By improving the efficiency of this critical process, our research could have far-reaching implications for the field, potentially enabling more complex analyses and contributing to advancements in various statistical applications.