Journal
NUMERICAL LINEAR ALGEBRA WITH APPLICATIONS
Volume 17, Issue 6, Pages 953-976Publisher
WILEY
DOI: 10.1002/nla.691
Keywords
HSS matrix; postordering HSS tree; low-rank property; fast HSS algorithms; generalized HSS Cholesky factorization
Categories
Funding
- NSF [CCF-0515034, CCF-0830764]
- Direct For Computer & Info Scie & Enginr [0830764] Funding Source: National Science Foundation
- Division of Computing and Communication Foundations [0830764] Funding Source: National Science Foundation
Ask authors/readers for more resources
Semiseparable matrices and many other rank-structured matrices have been widely used in developing new fast matrix algorithms. In this paper, we generalize the hierarchically semiseparable (HSS) matrix representations and propose some fast algorithms for HSS matrices. We represent HSS matrices in terms of general binary HSS trees and use simplified postordering notation for HSS forms. Fast HSS algorithms including new HSS structure generation and HSS form Cholesky factorization are developed. Moreover, we provide a new linear complexity explicit ULV factorization algorithm for symmetric positive definite HSS matrices with a low-rank property. The corresponding factors can be used to solve the HSS systems also in linear complexity. Numerical examples demonstrate the efficiency of the algorithms. All these algorithms have nice data locality. They are useful in developing fast-structured numerical methods for large discretized PDEs (such as elliptic equations), integral equations, eigenvalue problems, etc. Some applications are shown. Copyright (C) 2009 John Wiley & Sons, Ltd.
Authors
I am an author on this paper
Click your name to claim this paper and add it to your profile.
Reviews
Recommended
No Data Available