View in EDS

NEW EFFICIENT AND ROBUST HSS CHOLESKY FACTORIZATION OF SPD MATRICES.

Saved in:
Bibliographic Details
Title: NEW EFFICIENT AND ROBUST HSS CHOLESKY FACTORIZATION OF SPD MATRICES.
Authors: SHENGGUO LI1 nudtlsg@gmail.com, MING GU2 mgu@math.berkeley.edu, WU, CINNA JULIE2 cinnawu@math.berkeley.edu, JIANLIN XIA3 xiaj@math.purdue.edu
Source: SIAM Journal on Matrix Analysis & Applications. 2012, Vol. 33 Issue 3, p886-904. 19p.
Subjects: Robust control, Semiseparable matrices, Factorization, Mathematical transformations, Mathematical sequences, Schur complement, Approximation theory
Abstract: In this paper, we propose a robust Cholesky factorization method for symmetric positive definite (SPD), hierarchically semiseparable (HSS) matrices. Classical Cholesky factorizations and some semiseparable methods need to sequentially compute Schur complements. In contrast, we develop a strategy involving orthogonal transformations and approximations which avoids the explicit computation of the Schur complement in each factorization step. The overall factorization requires fewer floating point operations and has better data locality when compared to the recent HSS method in [J. Xia and M. Gu, SIAM J. Matrix Anal. Appl., 31 (2010), pp. 2899-2920]. Our strategy utilizes a robustness technique so that an approximate generalized Cholesky factorization is guaranteed to exist. We test three different methods for compressing the off-diagonal blocks in each iteration, i.e., rank-revealing QR, SVD, and SVD with random sampling. In our comparisons, we find that, with high probability, using SVD with random sampling is fast and stable. The complexity of the methods proposed in this paper is analyzed and shown to be O(N²k), where N is the dimension of matrix and k is the maximum off-diagonal (numerical) rank. Numerical results from applications show the efficiency of our method and its effectiveness as a preconditioner. Moreover, our techniques are helpful in improving the scalability and robustness of other rank-structured methods. [ABSTRACT FROM AUTHOR]
Copyright of SIAM Journal on Matrix Analysis & Applications is the property of Society for Industrial & Applied Mathematics and its content may not be copied or emailed to multiple sites without the copyright holder's express written permission. Additionally, content may not be used with any artificial intelligence tools or machine learning technologies. However, users may print, download, or email articles for individual use. This abstract may be abridged. No warranty is given about the accuracy of the copy. Users should refer to the original published version of the material for the full abstract. (Copyright applies to all Abstracts.)
Database: Engineering Source
Description
Abstract:In this paper, we propose a robust Cholesky factorization method for symmetric positive definite (SPD), hierarchically semiseparable (HSS) matrices. Classical Cholesky factorizations and some semiseparable methods need to sequentially compute Schur complements. In contrast, we develop a strategy involving orthogonal transformations and approximations which avoids the explicit computation of the Schur complement in each factorization step. The overall factorization requires fewer floating point operations and has better data locality when compared to the recent HSS method in [J. Xia and M. Gu, SIAM J. Matrix Anal. Appl., 31 (2010), pp. 2899-2920]. Our strategy utilizes a robustness technique so that an approximate generalized Cholesky factorization is guaranteed to exist. We test three different methods for compressing the off-diagonal blocks in each iteration, i.e., rank-revealing QR, SVD, and SVD with random sampling. In our comparisons, we find that, with high probability, using SVD with random sampling is fast and stable. The complexity of the methods proposed in this paper is analyzed and shown to be O(N²k), where N is the dimension of matrix and k is the maximum off-diagonal (numerical) rank. Numerical results from applications show the efficiency of our method and its effectiveness as a preconditioner. Moreover, our techniques are helpful in improving the scalability and robustness of other rank-structured methods. [ABSTRACT FROM AUTHOR]
ISSN:08954798
DOI:10.1137/110851110