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 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

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

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, 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, 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, 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, On the robustness of inverse scattering for penetrable, homogeneous objects with complicated boundary, 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

Cites Work