Fast algorithms for hierarchically semiseparable matrices |
| |
| Authors: | Jianlin Xia Shivkumar Chandrasekaran Ming Gu Xiaoye S Li |
| |
| Institution: | 1. Department of Mathematics, Purdue University, West Lafayette, IN 47907, U.S.A.;2. Department of Electrical and Computer Engineering, University of California, Santa Barbara, CA 93106, U.S.A.;3. Department of Mathematics, University of California, Berkeley, CA 94720, U.S.A.;4. Lawrence Berkeley National Laboratory, MS 50F‐1650, One Cyclotron Rd., Berkeley, CA 94720, U.S.A. |
| |
| Abstract: | 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 © 2009 John Wiley & Sons, Ltd. |
| |
| Keywords: | HSS matrix postordering HSS tree low‐rank property fast HSS algorithms generalized HSS Cholesky factorization |
|
|
