2 January 2019 in SIAM Journal on Scientific Computing
The estimation of large sparse inverse covariance matrices is a ubiquitous statistical problem in many application areas such as mathematical finance, geology, health, and many others. The $\ell_1$-regularized Gaussian maximum likelihood (ML) method is a common approach for recovering inverse covariance matrices for datasets with a very limited number of samples. A highly efficient ML-based method is the quadratic approximate inverse covariance (QUIC) method. In this work, we build on the advancements of QUIC algorithm by introducing a highly performant sparse version of QUIC (SQUIC) for large-scale applications. The proposed algorithm focuses on exploiting the potential sparsity in three components of the QUIC algorithm, namely, construction sample covariance matrix, matrix factorization, and matrix inversion operations. For each component, we present two approaches and provide supporting numerical results based on a set of synthetic datasets and a stylized financial autoregressive model. Testing conducted on a single modern multicore machine show that using advanced sparse matrix technology, SQUIC can recover large-scale inverse covariance matrices of datasets with up to $1$ million random variables within minutes. In comparison to competing ML-based algorithms, SQUIC is orders of magnitude faster with comparable recovery rates.
1 January 2008 in SIAM Review
We propose efficient preconditioning algorithms for an eigenvalue problem arising in quantum physics, namely, the computation of a few interior eigenvalues and their associated eigenvectors for large-scale sparse real and symmetric indefinite matrices of the Anderson model of localization. We compare the Lanczos algorithm in the 1987 implementation by Cullum and Willoughby with the shift-and-invert techniques in the implicitly restarted Lanczos method and in the Jacobi–Davidson method. Our preconditioning approaches for the shift-and-invert symmetric indefinite linear system are based on maximum weighted matchings and algebraic multilevel incomplete $LDL^T$ factorizations. These techniques can be seen as a complement to the alternative idea of using more complete pivoting techniques for the highly ill-conditioned symmetric indefinite Anderson matrices. We demonstrate the effectiveness and the numerical accuracy of these algorithms. Our numerical examples reveal that recent algebraic multilevel preconditioning solvers can accelerate the computation of a large-scale eigenvalue problem corresponding to the Anderson model of localization by several orders of magnitude.
1 January 2006 in SIAM Journal on Scientific Computing
This paper analyzes dropping strategies in a multilevel incomplete LU decomposition context and presents a few strategies for obtaining related ILUs with enhanced robustness. The analysis shows that the incomplete LU factorization resulting from dropping small entries in Gaussian elimination produces a good preconditioner when the inverses of these factors have norms that are not too large. As a consequence a few strategies are developed whose goal is to achieve this feature. A number of "templates" for enabling implementations of these factorizations are presented. Numerical experiments show that the resulting ILUs offer a good compromise between robustness and efficiency.
1 December 2007 in Computer Physics Communications
1 January 2009 in SIAM Journal on Scientific Computing
An algebraic multilevel (ML) preconditioner is presented for the Helmholtz equation in heterogeneous media. It is based on a multilevel incomplete $LDL^T$ factorization and preserves the inherent (complex) symmetry of the Helmholtz equation. The ML preconditioner incorporates two key components for efficiency and numerical stability: symmetric maximum weight matchings and an inverse-based pivoting strategy. The former increases the block-diagonal dominance of the system, whereas the latter controls $\|L^{-1}\|$ for numerical stability. When applied recursively, their combined effect yields an algebraic coarsening strategy, similar to algebraic multigrid methods, even for highly indefinite matrices. The ML preconditioner is combined with a Krylov subspace method and applied as a “black-box” solver to a series of challenging two- and three-dimensional test problems, mainly from geophysical seismic imaging. The numerical results demonstrate the robustness and efficiency of the ML preconditioner, even at higher frequency regimes.