×

zbMATH — the first resource for mathematics

Fast algorithms for hierarchically semiseparable matrices. (English) Zbl 1240.65087
Summary: 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.

MSC:
65F05 Direct numerical methods for linear systems and matrix inversion
65Y20 Complexity and performance of numerical algorithms
15B48 Positive matrices and their generalizations; cones of matrices
05C50 Graphs and linear algebra (matrices, eigenvalues, etc.)
Software:
iFEM; LAPACK
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Chandrasekaran, A fast adaptive solver for hierarchically semiseparable representations, CALCOLO 42 pp 171– (2005) · Zbl 1168.65330
[2] Chandrasekaran S Gu M Pals T Fast and stable algorithms for hierarchically semi-separable representations 2004
[3] Chandrasekaran, A superfast algorithm for Toeplitz systems of linear equations, SIAM Journal on Matrix Analysis and Applications 29 pp 1247– (2007)
[4] Delvaux, A QR-based solver for rank structured matrices, SIAM Journal on Matrix Analysis and Applications 30 pp 464– (2008) · Zbl 1162.65325
[5] Chandrasekaran S Dewilde P Gu M Pals T Sun X van der Veen AJ White D Fast stable solvers for sequentially semi-separable linear systems of equations and least squares problems 2003
[6] Bini, Fast and stable QR eigenvalue algorithms for generalized companion matrices and secular equations, Numerische Mathematik 100 pp 373– (2005) · Zbl 1072.65068
[7] Chandrasekaran, Operator Theory: Advances and Applications 179 pp 111– (2007)
[8] Eidelman, The QR iteration method for Hermitian quasiseparable matrices of an arbitrary order, Linear Algebra and its Applications 404 pp 305– (2005) · Zbl 1079.65038
[9] Laub, Statistical condition estimation for the roots of polynomials, SIAM Journal on Scientific Computing 31 pp 624– (2008) · Zbl 1186.65058
[10] Laub, Fast condition estimation for a class of structured eigenvalue problems, SIAM Journal on Matrix Analysis and Applications 30 pp 1658– (2009) · Zbl 1223.65026
[11] Van Barel M Vandebril R Mastronardi N Delvaux S Vanberghen Y Rank structured matrix operations
[12] Bebendorf, Existence of matrix approximants to the inverse FE-matrix of elliptic operators with L -Coefficients, Numerische Mathematik 95 pp 1– (2003) · Zbl 1033.65100
[13] Grasedyck L Kriemann R Le Borne S Parallel black box domain decomposition based H -LU preconditioning 2005 · Zbl 1178.65140
[14] Grasedyck, Lecture Notes in Computational Science and Engineering, in: Domain Decomposition Methods in Science and Engineering XVI pp 661– (2006)
[15] Xia, Superfast multifrontal method for structured linear systems of equations, SIAM Journal on Matrix Analysis and Applications 31 pp 1382– (2009)
[16] Gohberg, Linear complexity algorithms for semiseparable matrices, Integral Equations and Operator Theory 8 pp 780– (1985)
[17] Martinsson, A fast direct solver for boundary integral equations in two dimensions, Journal of Computational Physics 205 pp 1– (2005) · Zbl 1078.65112
[18] Rokhlin, Rapid solution of integral equations of scattering theory in two dimensions, Journal of Computational Physics 86 pp 414– (1990) · Zbl 0686.65079
[19] Hackbusch, A Sparse matrix arithmetic based on -matrices. Part I: introduction to -matrices, Computing 62 pp 89– (1999) · Zbl 0927.65063
[20] Hackbusch, An introduction to hierarchical matrices, Mathematica Bohemica 127 pp 229– (2002) · Zbl 1007.65032
[21] Hackbusch, A sparse -matrix arithmetic. Part-II: Application to multi-dimensional problems, Computing 64 pp 21– (2000) · Zbl 0962.65029
[22] Börm, Introduction to hierarchical matrices with applications, Engineering Analysis with Boundary Elements 27 pp 405– (2003)
[23] Hackbusch, Lectures on Applied Mathematics pp 9– (2000)
[24] Hackbusch, Data-sparse approximation by adaptive -matrices, Computing 69 pp 1– (2002) · Zbl 1012.65023
[25] Eidelman, On a new class of structured matrices, Integral Equations and Operator Theory 34 pp 293– (1999) · Zbl 0934.15002
[26] Chandrasekaran, Some fast algorithms for sequentially semiseparable representations, SIAM Journal on Matrix Analysis and Applications 27 pp 341– (2005) · Zbl 1091.65063
[27] Vandebril, A note on the representation and definition of semiseparable matrices, Numerical Linear Algebra with Applications 12 pp 839– (2005) · Zbl 1164.15341
[28] Vandebril, A bibliography on semiseparable matrices, CALCOLO 42 pp 249– (2005) · Zbl 1168.15312
[29] Chandrasekaran, A fast ULV decomposition solver for hierarchically semiseparable representations, SIAM Journal on Matrix Analysis and Applications 28 pp 603– (2006) · Zbl 1120.65031
[30] Dewilde, A hierarchical semi-separable Moore-Penrose equation solver, Operator Theory: Advances and Applications 167 pp 69– (2006) · Zbl 1143.65336
[31] Sheng Z Dewilde P van der Meijs N Iterative solution methods based on the hierarchically semi-separable representation 343 349
[32] Carrier, A fast adaptive multipole algorithm for particle simulations, SIAM Journal on Scientific and Statistical Computing 9 pp 669– (1988) · Zbl 0656.65004
[33] Greengard, A fast algorithm for particle simulations, Journal of Computational Physics 73 pp 325– (1987) · Zbl 0629.65005
[34] Chandrasekaran S Dewilde P Gu M On the numerical rank of the off-diagonal blocks of Schur complements of discretized elliptic PDEs 2009 · Zbl 1209.65032
[35] Martinsson, A fast direct solver for a class of elliptic partial differential equations, Journal of Scientific Computing 38 pp 316– (2009) · Zbl 1203.65066
[36] Eisenstat, The theory of elimination trees for sparse unsymmetric matrices, SIAM Journal on Matrix Analysis and Applications 26 pp 686– (2005) · Zbl 1079.65025
[37] Gilbert, Elimination structures for unsymmetric sparse LU factors, SIAM Journal on Matrix Analysis and Applications 14 pp 334– (1993) · Zbl 0769.65010
[38] Liu, The role of elimination trees in sparse factorization, SIAM Journal on Matrix Analysis and Applications 18 pp 134– (1990) · Zbl 0697.65013
[39] Demmel, Applied Numerical Linear Algebra (1997)
[40] Golub, Matrix Computations (1989)
[41] Anderson, LAPACK Users’ Guide (1999) · Zbl 0934.65030
[42] George, Nested dissection of a regular finite element mesh, SIAM Journal on Numerical Analysis 10 pp 345– (1973) · Zbl 0259.65087
[43] Duff, The multifrontal solution of indefinite sparse symmetric linear equations, ACM Transactions on Mathematical Software 9 pp 302– (1983) · Zbl 0515.65022
[44] Eisenstat, A tree-based dataflow model for the unsymmetric multifrontal method, Electronic Transactions on Numerical Analysis 21 pp 1– (2005) · Zbl 1120.65316
[45] Liu, The multifrontal method for sparse matrix solution: theory and practice, SIAM Review 34 pp 82– (1992) · Zbl 0919.65019
[46] Chen L Xu J Zhu Y Local multilevel preconditioners for elliptic equations 2009
[47] Chen L i FEM: An innovative finite element methods package in MATLAB 2009
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.