Fast algorithms for hierarchically semiseparable matrices

DOI10.1002/NLA.691zbMath1240.65087OpenAlexW2089958289MaRDI 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 exampleslinear complexitysymmetric positive definiteHSS matrixlow-rank propertyhierarchically semiseparable (HSS) matrixULV factorizationfast HSS algorithmsgeneralized HSS Cholesky factorizationpostordering HSS tree

Mathematics Subject Classification ID

Graphs and linear algebra (matrices, eigenvalues, etc.) (05C50) Positive matrices and their generalizations; cones of matrices (15B48) Complexity and performance of numerical algorithms (65Y20) Direct numerical methods for linear systems and matrix inversion (65F05)

Related Items (only showing first 100 items - show all)

SuperDC: Superfast Divide-And-Conquer Eigenvalue Decomposition With Improved Stability for Rank-Structured Matrices ⋮ A fast and stable algorithm for downdating the singular value decomposition ⋮ LU factorization for matrices in quasiseparable form via orthogonal transformations ⋮ Fast multipole method for 3-D Poisson-Boltzmann equation in layered electrolyte-dielectric media ⋮ Approximate inversion of discrete Fourier integral operators ⋮ A hierarchical matrix approach for computing hydrodynamic interactions ⋮ Overlapping Domain Decomposition Preconditioner for Integral Equations ⋮ Effective matrix-free preconditioning for the augmented immersed interface method ⋮ A fast block low-rank dense solver with applications to finite-element matrices ⋮ A Hierarchical Low Rank Schur Complement Preconditioner for Indefinite Linear Systems ⋮ An efficient, memory-saving approach for the Loewner framework ⋮ 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 ⋮ Hierarchical Interpolative Factorization for Elliptic Operators: Differential Equations ⋮ An accelerated, high-order accurate direct solver for the Lippmann-Schwinger equation for acoustic scattering in the plane ⋮ Solving Rank-Structured Sylvester and Lyapunov Equations ⋮ Efficient preconditioning of \(hp\)-FEM matrices by hierarchical low-rank approximations ⋮ Large-scale stochastic linear inversion using hierarchical matrices. Illustrated with an application to crosswell tomography in seismic imaging ⋮ A fast direct solver for two dimensional quasi-periodic multilayered media scattering problems ⋮ An Accelerated Divide-and-Conquer Algorithm for the Bidiagonal SVD Problem ⋮ Acoustic inverse scattering via Helmholtz operator factorization and optimization ⋮ Error analysis of an accelerated interpolative decomposition for 3D Laplace problems ⋮ Distributed-memory hierarchical interpolative factorization ⋮ Time and space efficient generators for quasiseparable matrices ⋮ Multifrontal Hierarchically Solver for 3D Discretized Elliptic Equations ⋮ Fast and accurate numerical methods for solving elliptic difference equations defined on lattices ⋮ The LR Cholesky algorithm for symmetric hierarchical matrices ⋮ Fast Sparse Selected Inversion ⋮ A preconditioned low-rank CG method for parameter-dependent Lyapunov matrix equations ⋮ 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 Fast Contour-Integral Eigensolver for Non-Hermitian Matrices ⋮ Effective and Robust Preconditioning of General SPD Matrices via Structured Incomplete Factorization ⋮ A fast direct solver for a class of elliptic partial differential equations ⋮ 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 ⋮ New fast divide-and-conquer algorithms for the symmetric tridiagonal eigenvalue problem ⋮ Schur complement-based domain decomposition preconditioners with low-rank corrections ⋮ hm-toolbox: MATLAB Software for HODLR and HSS Matrices ⋮ Interpolative Decomposition Butterfly Factorization ⋮ Fast Factorization Update for General Elliptic Equations Under Multiple Coefficient Updates ⋮ An Algebraic Sparsified Nested Dissection Algorithm Using Low-Rank Approximations ⋮ Fast Spatial Gaussian Process Maximum Likelihood Estimation via Skeletonization Factorizations ⋮ A Robust Multilevel Approximate Inverse Preconditioner for Symmetric Positive Definite Matrices ⋮ Matrix Structures in Queuing Models ⋮ Matrices with Hierarchical Low-Rank Structures ⋮ An \(\mathcal O(N\log N)\) fast direct solver for partial hierarchically semi-separable matrices. With application to radial basis function interpolation ⋮ On the Best Approximation of the Hierarchical Matrix Product ⋮ Hierarchical Matrix Approximations of Hessians Arising in Inverse Problems Governed by PDEs ⋮ Fast algorithms for large dense matrices with applications to biofluids ⋮ Fast structured LU factorization for nonsymmetric matrices ⋮ A robust hierarchical solver for ill-conditioned systems with applications to ice sheet modeling ⋮ An \(O(N \log N)\) hierarchical random compression method for kernel matrices by sampling partial matrix entries ⋮ Fast structured Jacobi-Jacobi transforms ⋮ Low-Rank Updates and a Divide-And-Conquer Method for Linear Matrix Equations ⋮ Analytical Low-Rank Compression via Proxy Point Selection ⋮ Fast Approximation of the Gauss--Newton Hessian Matrix for the Multilayer Perceptron ⋮ Preserving Positive Definiteness in Hierarchically Semiseparable Matrix Approximations ⋮ Low-Rank Factorizations in Data Sparse Hierarchical Algorithms for Preconditioning Symmetric Positive Definite Matrices ⋮ Data-sparse approximation on the computation of a weakly singular Fredholm equation: a stellar radiative transfer application ⋮ Fast bilinear algorithms for symmetric tensor contractions ⋮ Robust and Effective eSIF Preconditioning for General Dense SPD Matrices ⋮ A Diagonal Sweeping Domain Decomposition Method with Source Transfer for the Helmholtz Equation ⋮ A direct solver with \(O(N)\) complexity for integral equations on one-dimensional domains ⋮ Compression, inversion, and approximate PCA of dense kernel matrices at near-linear computational complexity ⋮ An improved divide-and-conquer algorithm for the banded matrices with narrow bandwidths ⋮ A spectrally accurate direct solution technique for frequency-domain scattering problems with variable media ⋮ 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 ⋮ 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 ⋮ An Algebraic Multilevel Preconditioner with Low-Rank Corrections for Sparse Symmetric Matrices ⋮ A Fast Memory Efficient Construction Algorithm for Hierarchically Semi-Separable Representations ⋮ Improving the Complexity of Block Low-Rank Factorizations with Fast Matrix Arithmetic ⋮ Block Basis Factorization for Scalable Kernel Evaluation ⋮ An \(O(N)\) direct solver for integral equations on the plane ⋮ Superfast Divide-and-Conquer Method and Perturbation Analysis for Structured Eigenvalue Solutions ⋮ A direct solver for elliptic PDEs in three dimensions based on hierarchical merging of Poincaré-Steklov operators ⋮ Hierarchical Interpolative Factorization for Elliptic Operators: Integral Equations ⋮ A stable matrix version of the fast multipole method: stabilization strategies and examples ⋮ A Fast Algorithm for Simulating Multiphase Flows Through Periodic Geometries of Arbitrary Shape ⋮ Hierarchical Decompositions for the Computation of High-Dimensional Multivariate Normal Probabilities ⋮ Efficient mesh deformation based on radial basis function interpolation by means of the inverse fast multipole method ⋮ Efficient preconditioning of \(h p\)-FEM matrix sequences with slowly-varying coefficients: an application to topology optimization ⋮ On the Stability of Some Hierarchical Rank Structured Matrix Algorithms ⋮ Fast Solvers for Two-Dimensional Fractional Diffusion Equations Using Rank Structured Matrices ⋮ 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 ⋮ Efficient Construction of an HSS Preconditioner for Symmetric Positive Definite $\mathcal{H}^2$ Matrices ⋮ Robust and Accurate Stopping Criteria for Adaptive Randomized Sampling in Matrix-Free Hierarchically Semiseparable Construction ⋮ Sparse Cholesky Factorization by Kullback--Leibler Minimization ⋮ Block Low-Rank Matrices with Shared Bases: Potential and Limitations of the BLR$^2$ Format ⋮ Space-fractional diffusion with variable order and diffusivity: discretization and direct solution strategies ⋮ Efficient randomized tensor-based algorithms for function approximation and low-rank kernel interactions ⋮ Improving Multifrontal Methods by Means of Block Low-Rank Representations ⋮ A high-order accurate accelerated direct solver for acoustic scattering from surfaces ⋮ Interconnected hierarchical structures for fast direct elliptic solution ⋮ A Hierarchical Preconditioner for Wave Problems in Quasilinear Complexity ⋮ Divide-and-Conquer Methods for Functions of Matrices with Banded or Hierarchical Low-Rank Structure

Uses Software

• Unnamed Item
• iFEM

Cites Work

• Unnamed Item
• A fast direct solver for a class of elliptic partial differential equations
• A fast adaptive solver for hierarchically semiseparable representations
• A tree-based dataflow model for the unsymmetric multifrontal method
• Rapid solution of integral equations of scattering theory in two dimensions
• A sparse matrix arithmetic based on \({\mathfrak H}\)-matrices. I: Introduction to \({\mathfrak H}\)-matrices
• On a new class of structured matrices
• Existence of \(\mathcal H\)-matrix approximants to the inverse FE-matrix of elliptic operators with \(L^\infty\)-coefficients
• Fast and stable QR eigenvalue algorithms for generalized companion matrices and secular equations
• A fast direct solver for boundary integral equations in two dimensions
• Data-sparse approximation by adaptive \({\mathcal H}^2\)-matrices
• A sparse \({\mathcal H}\)-matrix arithmetic. II: Application to multi-dimensional problems
• Domain decomposition based \({\mathcal H}\)-LU preconditioning
• The QR iteration method for Hermitian quasiseparable matrices of an arbitrary order
• On the Numerical Rank of the Off-Diagonal Blocks of Schur Complements of Discretized Elliptic PDEs
• The Role of Elimination Trees in Sparse Factorization
• A note on the representation and definition of semiseparable matrices
• A QR-Based Solver for Rank Structured Matrices
• Fast Condition Estimation for a Class of Structured Eigenvalue Problems
• The Multifrontal Solution of Indefinite Sparse Symmetric Linear
• A Fast Adaptive Multipole Algorithm for Particle Simulations
• LAPACK Users' Guide
• The Multifrontal Method for Sparse Matrix Solution: Theory and Practice
• An introduction to hierarchical matrices
• Statistical Condition Estimation for the Roots of Polynomials
• Elimination Structures for Unsymmetric Sparse $LU$ Factors
• A Fast $ULV$ Decomposition Solver for Hierarchically Semiseparable Representations
• The Theory of Elimination Trees for Sparse Unsymmetric Matrices
• Some Fast Algorithms for Sequentially Semiseparable Representations
• Nested Dissection of a Regular Finite Element Mesh
• A bibliography on semiseparable matrices
• A fast algorithm for particle simulations

This page was built for publication: Fast algorithms for hierarchically semiseparable matrices