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

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, On the robustness of inverse scattering for penetrable, homogeneous objects with complicated boundary, Efficient inversion of matrix $\varphi $-functions of low order, Robust fast direct integral equation solver for three-dimensional doubly periodic scattering problems with a large number of layers, FMM-LU: A Fast Direct Solver for Multiscale Boundary Integral Equations in Three Dimensions, Exact computations with quasiseparable matrices, A hybrid stochastic interpolation and compression method for kernel matrices, Second‐order accurate hierarchical approximate factorizations for solving sparse linear systems, On the application of a hierarchically semi-separable compression for space-fractional parabolic problems with varying time steps, Linear-Cost Covariance Functions for Gaussian Random Fields, HODLR$d$D: a new black-box fast algorithm for $N$-body problems in $d$-dimensions with guaranteed error bounds. Applications to integral equations and support vector machines, Iterative and doubling algorithms for Riccati‐type matrix equations: A comparative introduction, Fast hierarchical low-rank view factor matrices for thermal irradiance on planetary surfaces, Evaluation of Inner Products of Implicitly Defined Finite Element Functions on Multiply Connected Planar Mesh Cells, Scalable Physics-Based Maximum Likelihood Estimation Using Hierarchical Matrices, 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, Efficient Construction of an HSS Preconditioner for Symmetric Positive Definite $\mathcal{H}^2$ Matrices, Sparse Cholesky Factorization by Kullback--Leibler Minimization, Block Low-Rank Matrices with Shared Bases: Potential and Limitations of the BLR$^2$ Format, A Hierarchical Preconditioner for Wave Problems in Quasilinear Complexity, Divide-and-Conquer Methods for Functions of Matrices with Banded or Hierarchical Low-Rank Structure, SuperDC: Superfast Divide-And-Conquer Eigenvalue Decomposition With Improved Stability for Rank-Structured Matrices, Overlapping Domain Decomposition Preconditioner for Integral Equations, 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, Hierarchical Matrix Approximations of Hessians Arising in Inverse Problems Governed by PDEs, Analytical Low-Rank Compression via Proxy Point Selection, Fast Approximation of the Gauss--Newton Hessian Matrix for the Multilayer Perceptron, Robust and Effective eSIF Preconditioning for General Dense SPD Matrices, A Diagonal Sweeping Domain Decomposition Method with Source Transfer for the Helmholtz Equation, Improving the Complexity of Block Low-Rank Factorizations with Fast Matrix Arithmetic, Block Basis Factorization for Scalable Kernel Evaluation, Fast Solvers for Two-Dimensional Fractional Diffusion Equations Using Rank Structured Matrices, Robust and Accurate Stopping Criteria for Adaptive Randomized Sampling in Matrix-Free Hierarchically Semiseparable Construction, Improving Multifrontal Methods by Means of Block Low-Rank Representations, Compression, inversion, and approximate PCA of dense kernel matrices at near-linear computational complexity, 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, An improved divide-and-conquer algorithm for the banded matrices with narrow bandwidths, A stable matrix version of the fast multipole method: stabilization strategies and examples, 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, Interconnected hierarchical structures for fast direct elliptic solution, 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, An efficient, memory-saving approach for the Loewner framework, An accelerated, high-order accurate direct solver for the Lippmann-Schwinger equation for acoustic scattering in the plane, Error analysis of an accelerated interpolative decomposition for 3D Laplace problems, Fast algorithms for large dense matrices with applications to biofluids, 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 bilinear algorithms for symmetric tensor contractions, A spectrally accurate direct solution technique for frequency-domain scattering problems with variable media, 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, 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, A fast direct solver for two dimensional quasi-periodic multilayered media scattering problems, 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, Hierarchical Decompositions for the Computation of High-Dimensional Multivariate Normal Probabilities, 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