Fast algorithms for hierarchically semiseparable matrices

DOI10.1002/nla.691zbMath1240.65087MaRDI QIDQ3090808

Xiaoye Sherry Li, Ming Gu, Jian-Lin Xia, Shivkumar Chandrasekaran

Publication date: 2 September 2011

Published in: Numerical Linear Algebra with Applications (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1002/nla.691

zbMATH Keywords

numerical examples; linear complexity; symmetric positive definite; HSS matrix; low-rank property; hierarchically semiseparable (HSS) matrix; ULV factorization; fast HSS algorithms; generalized HSS Cholesky factorization; postordering HSS tree

Mathematics Subject Classification ID

05C50: Graphs and linear algebra (matrices, eigenvalues, etc.)

15B48: Positive matrices and their generalizations; cones of matrices

65Y20: Complexity and performance of numerical algorithms

65F05: Direct numerical methods for linear systems and matrix inversion

Related Items

Solving Rank-Structured Sylvester and Lyapunov Equations, A Fast Contour-Integral Eigensolver for Non-Hermitian Matrices, Effective and Robust Preconditioning of General SPD Matrices via Structured Incomplete Factorization, Fast Spatial Gaussian Process Maximum Likelihood Estimation via Skeletonization Factorizations, A Robust Multilevel Approximate Inverse Preconditioner for Symmetric Positive Definite Matrices, On the Best Approximation of the Hierarchical Matrix Product, Fast structured Jacobi-Jacobi transforms, Low-Rank Updates and a Divide-And-Conquer Method for Linear Matrix Equations, Preserving Positive Definiteness in Hierarchically Semiseparable Matrix Approximations, Low-Rank Factorizations in Data Sparse Hierarchical Algorithms for Preconditioning Symmetric Positive Definite Matrices, Reconstruction of a compactly supported sound profile in the presence of a random background medium, Communication lower bounds and optimal algorithms for numerical linear algebra, Improving Multifrontal Methods by Means of Block Low-Rank Representations, Sparsifying Preconditioner for the Lippmann--Schwinger Equation, Butterfly Factorization, Directional Preconditioner for 2D High Frequency Obstacle Scattering, High Resolution Inverse Scattering in Two Dimensions Using Recursive Linearization, Computationally Efficient Boundary Element Methods for High-Frequency Helmholtz Problems in Unbounded Domains, A Parallel Geometric Multifrontal Solver Using Hierarchically Semiseparable Structure, A Distributed-Memory Package for Dense Hierarchically Semi-Separable Matrix Computations Using Randomization, A Direct Elliptic Solver Based on Hierarchically Low-Rank Schur Complements, Low-Rank Correction Methods for Algebraic Domain Decomposition Preconditioners, A Distributed-Memory Randomized Structured Multifrontal Method for Sparse Direct Solutions, On the Complexity of the Block Low-Rank Multifrontal Factorization, An Additive Overlapping Domain Decomposition Method for the Helmholtz Equation, Bridging the Gap Between Flat and Hierarchical Low-Rank Matrix Formats: The Multilevel Block Low-Rank Format, An Efficient High Order Method for Dislocation Climb in Two Dimensions, The Inverse Fast Multipole Method: Using a Fast Approximate Direct Solver as a Preconditioner for Dense Linear Systems, Fast Hierarchical Solvers For Sparse Matrices Using Extended Sparsification and Low-Rank Approximation, An algebraic multifrontal preconditioner that exploits the low‐rank property, Compressing Rank-Structured Matrices via Randomized Sampling, A survey of direct methods for sparse linear systems, LU factorization for matrices in quasiseparable form via orthogonal transformations, The LR Cholesky algorithm for symmetric hierarchical matrices, A direct solver for variable coefficient elliptic PDEs discretized via a composite spectral collocation method, An \(O(N)\) algorithm for constructing the solution operator to 2D elliptic boundary value problems in the absence of body loads, Data-sparse approximation on the computation of a weakly singular Fredholm equation: a stellar radiative transfer application, Acoustic inverse scattering via Helmholtz operator factorization and optimization, Fast and accurate numerical methods for solving elliptic difference equations defined on lattices, A fast direct solver for a class of elliptic partial differential equations, A direct solver with \(O(N)\) complexity for integral equations on one-dimensional domains, An efficient hybrid tridiagonal divide-and-conquer algorithm on distributed memory architectures, Parallel accelerated cyclic reduction preconditioner for three-dimensional elliptic PDEs with variable coefficients, A direct solver for elliptic PDEs in three dimensions based on hierarchical merging of Poincaré-Steklov operators, Large-scale stochastic linear inversion using hierarchical matrices. Illustrated with an application to crosswell tomography in seismic imaging, Efficient arithmetic operations for rank-structured matrices based on hierarchical low-rank updates, \(\mathcal H\)-FAINV: hierarchically factored approximate inverse preconditioners, A tensor-train accelerated solver for integral equations in complex geometries, A spectrally accurate direct solution technique for frequency-domain scattering problems with variable media, A high-order accurate accelerated direct solver for acoustic scattering from surfaces, A fast and stable algorithm for downdating the singular value decomposition, Effective matrix-free preconditioning for the augmented immersed interface method, A fast block low-rank dense solver with applications to finite-element matrices, Efficient preconditioning of \(hp\)-FEM matrices by hierarchical low-rank approximations, Distributed-memory hierarchical interpolative factorization, Time and space efficient generators for quasiseparable matrices, An \(\mathcal O(N\log N)\) fast direct solver for partial hierarchically semi-separable matrices. With application to radial basis function interpolation, Fast structured LU factorization for nonsymmetric matrices, An \(O(N)\) direct solver for integral equations on the plane, An Algebraic Multilevel Preconditioner with Low-Rank Corrections for Sparse Symmetric Matrices, A Fast Memory Efficient Construction Algorithm for Hierarchically Semi-Separable Representations, Superfast Divide-and-Conquer Method and Perturbation Analysis for Structured Eigenvalue Solutions, Hierarchical Interpolative Factorization for Elliptic Operators: Integral Equations, A Fast Algorithm for Simulating Multiphase Flows Through Periodic Geometries of Arbitrary Shape, On the Stability of Some Hierarchical Rank Structured Matrix Algorithms, An Efficient Multicore Implementation of a Novel HSS-Structured Multifrontal Solver Using Randomized Sampling, Parallel Randomized and Matrix-Free Direct Solvers for Large Structured Dense Linear Systems, An Accelerated Divide-and-Conquer Algorithm for the Bidiagonal SVD Problem, Multifrontal Hierarchically Solver for 3D Discretized Elliptic Equations, Fast Sparse Selected Inversion, A preconditioned low-rank CG method for parameter-dependent Lyapunov matrix equations, New fast divide-and-conquer algorithms for the symmetric tridiagonal eigenvalue problem, Schur complement-based domain decomposition preconditioners with low-rank corrections, Matrix Structures in Queuing Models, Matrices with Hierarchical Low-Rank Structures, A Hierarchical Low Rank Schur Complement Preconditioner for Indefinite Linear Systems, Hierarchical Interpolative Factorization for Elliptic Operators: Differential Equations, A Technique for Updating Hierarchical Skeletonization-Based Factorizations of Integral Operators, Fast Structured Direct Spectral Methods for Differential Equations with Variable Coefficients, I. The One-Dimensional Case

Uses Software

Cites Work