NEW EFFICIENT AND ROBUST HSS CHOLESKY FACTORIZATION OF SPD MATRICES.
Saved in:
| 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 |
| FullText | Text: Availability: 0 |
|---|---|
| Header | DbId: egs DbLabel: Engineering Source An: 89041377 AccessLevel: 6 PubType: Academic Journal PubTypeId: academicJournal PreciseRelevancyScore: 0 |
| IllustrationInfo | |
| Items | – Name: Title Label: Title Group: Ti Data: NEW EFFICIENT AND ROBUST HSS CHOLESKY FACTORIZATION OF SPD MATRICES. – Name: Author Label: Authors Group: Au Data: <searchLink fieldCode="AR" term="%22SHENGGUO+LI%22">SHENGGUO LI</searchLink><relatesTo>1</relatesTo><i> nudtlsg@gmail.com</i><br /><searchLink fieldCode="AR" term="%22MING+GU%22">MING GU</searchLink><relatesTo>2</relatesTo><i> mgu@math.berkeley.edu</i><br /><searchLink fieldCode="AR" term="%22WU%2C+CINNA+JULIE%22">WU, CINNA JULIE</searchLink><relatesTo>2</relatesTo><i> cinnawu@math.berkeley.edu</i><br /><searchLink fieldCode="AR" term="%22JIANLIN+XIA%22">JIANLIN XIA</searchLink><relatesTo>3</relatesTo><i> xiaj@math.purdue.edu</i> – Name: TitleSource Label: Source Group: Src Data: <searchLink fieldCode="JN" term="%22SIAM+Journal+on+Matrix+Analysis+%26+Applications%22">SIAM Journal on Matrix Analysis & Applications</searchLink>. 2012, Vol. 33 Issue 3, p886-904. 19p. – Name: Subject Label: Subjects Group: Su Data: <searchLink fieldCode="DE" term="%22Robust+control%22">Robust control</searchLink><br /><searchLink fieldCode="DE" term="%22Semiseparable+matrices%22">Semiseparable matrices</searchLink><br /><searchLink fieldCode="DE" term="%22Factorization%22">Factorization</searchLink><br /><searchLink fieldCode="DE" term="%22Mathematical+transformations%22">Mathematical transformations</searchLink><br /><searchLink fieldCode="DE" term="%22Mathematical+sequences%22">Mathematical sequences</searchLink><br /><searchLink fieldCode="DE" term="%22Schur+complement%22">Schur complement</searchLink><br /><searchLink fieldCode="DE" term="%22Approximation+theory%22">Approximation theory</searchLink> – Name: Abstract Label: Abstract Group: Ab Data: 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] – Name: AbstractSuppliedCopyright Label: Group: Ab Data: <i>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.</i> (Copyright applies to all Abstracts.) |
| PLink | https://search.ebscohost.com/login.aspx?direct=true&site=eds-live&db=egs&AN=89041377 |
| RecordInfo | BibRecord: BibEntity: Identifiers: – Type: doi Value: 10.1137/110851110 Languages: – Code: eng Text: English PhysicalDescription: Pagination: PageCount: 19 StartPage: 886 Subjects: – SubjectFull: Robust control Type: general – SubjectFull: Semiseparable matrices Type: general – SubjectFull: Factorization Type: general – SubjectFull: Mathematical transformations Type: general – SubjectFull: Mathematical sequences Type: general – SubjectFull: Schur complement Type: general – SubjectFull: Approximation theory Type: general Titles: – TitleFull: NEW EFFICIENT AND ROBUST HSS CHOLESKY FACTORIZATION OF SPD MATRICES. Type: main BibRelationships: HasContributorRelationships: – PersonEntity: Name: NameFull: SHENGGUO LI – PersonEntity: Name: NameFull: MING GU – PersonEntity: Name: NameFull: WU, CINNA JULIE – PersonEntity: Name: NameFull: JIANLIN XIA IsPartOfRelationships: – BibEntity: Dates: – D: 01 M: 07 Text: 2012 Type: published Y: 2012 Identifiers: – Type: issn-print Value: 08954798 Numbering: – Type: volume Value: 33 – Type: issue Value: 3 Titles: – TitleFull: SIAM Journal on Matrix Analysis & Applications Type: main |
| ResultId | 1 |
