Superfast Multifrontal Method for Large Structured Linear Systems of Equations

DOI10.1137/09074543XzbMath1195.65031MaRDI QIDQ3584165

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

Publication date: 19 August 2010

Published in: SIAM Journal on Matrix Analysis and Applications (Search for Journal in Brave)

zbMATH Keywords

numerical results Gaussian elimination parallel computations nested dissection hierarchically semiseparable matrix low-rank property nearly linear complexity structured direct solver superfast multifrontal method

Mathematics Subject Classification ID

Computational methods for sparse matrices (65F50) Parallel numerical computation (65Y05) Complexity and performance of numerical algorithms (65Y20) Direct numerical methods for linear systems and matrix inversion (65F05)

Related Items (89)

A multilevel approach for trace system in HDG discretizations ⋮ L-sweeps: a scalable, parallel preconditioner for the high-frequency Helmholtz equation ⋮ SuperDC: Superfast Divide-And-Conquer Eigenvalue Decomposition With Improved Stability for Rank-Structured Matrices ⋮ A Direct Elliptic Solver Based on Hierarchically Low-Rank Schur Complements ⋮ Trace transfer-based diagonal sweeping domain decomposition method for the Helmholtz equation: algorithms and convergence analysis ⋮ Sweeping preconditioner for the Helmholtz equation: Hierarchical matrix representation ⋮ Existence of $\mathcal {H}$-matrix approximants to the inverses of BEM matrices: The simple-layer operator ⋮ Linear-scaling selected inversion based on hierarchical interpolative factorization for self Green's function for modified Poisson-Boltzmann equation in two dimensions ⋮ A fast block low-rank dense solver with applications to finite-element matrices ⋮ Multigrid-based `shifted-Laplacian' preconditioning for the time-harmonic elastic wave equation ⋮ Fast Algorithms for High Frequency Wave Propagation ⋮ A new multilevel method for electrostatic problems through hierarchical loop basis ⋮ An efficient, memory-saving approach for the Loewner framework ⋮ Hierarchical orthogonal factorization: sparse least squares problems ⋮ Fast Structured Direct Spectral Methods for Differential Equations with Variable Coefficients, I. The One-Dimensional Case ⋮ Hierarchical Interpolative Factorization for Elliptic Operators: Differential Equations ⋮ A fast nested dissection solver for Cartesian 3D elliptic problems using hierarchical matrices ⋮ A fast direct solver for scattering from periodic structures with multiple material interfaces in two dimensions ⋮ Efficient preconditioning of $hp$-FEM matrices by hierarchical low-rank approximations ⋮ Nested Domain Decomposition with Polarized Traces for the 2D Helmholtz Equation ⋮ A fast direct solver for two dimensional quasi-periodic multilayered media scattering problems ⋮ Acoustic inverse scattering via Helmholtz operator factorization and optimization ⋮ Distributed-memory hierarchical interpolative factorization ⋮ Fast and accurate numerical methods for solving elliptic difference equations defined on lattices ⋮ Fast Sparse Selected Inversion ⋮ A convergence analysis for a sweeping preconditioner for block tridiagonal systems of linear equations ⋮ Efficient arithmetic operations for rank-structured matrices based on hierarchical low-rank updates ⋮ Low-Rank Correction Methods for Algebraic Domain Decomposition Preconditioners ⋮ 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 ⋮ A Distributed-Memory Randomized Structured Multifrontal Method for Sparse Direct Solutions ⋮ On the Complexity of the Block Low-Rank Multifrontal Factorization ⋮ A fast, memory efficient and robust sparse preconditioner based on a multifrontal approach with applications to finite‐element matrices ⋮ FMM-LU: A Fast Direct Solver for Multiscale Boundary Integral Equations in Three Dimensions ⋮ An $O(N)$ algorithm for constructing the solution operator to 2D elliptic boundary value problems in the absence of body loads ⋮ Simple non-extensive sparsification of the hierarchical matrices ⋮ Second‐order accurate hierarchical approximate factorizations for solving sparse linear systems ⋮ hm-toolbox: MATLAB Software for HODLR and HSS Matrices ⋮ Randomized preprocessing versus pivoting ⋮ Multi-core parallel robust structured multifrontal factorization method for large discretized PDEs ⋮ $\mathcal {H}$-matrix approximability of the inverses of FEM matrices ⋮ Fast Factorization Update for General Elliptic Equations Under Multiple Coefficient Updates ⋮ A fast direct solver for elliptic problems on general meshes in 2D ⋮ An Algebraic Sparsified Nested Dissection Algorithm Using Low-Rank Approximations ⋮ An Algebraic Multigrid-Based Physical Factorization Preconditioner for the Multi-Group Radiation Diffusion Equations in Three Dimensions ⋮ An Adaptive High Order Direct Solution Technique for Elliptic Boundary Value Problems ⋮ Bridging the Gap Between Flat and Hierarchical Low-Rank Matrix Formats: The Multilevel Block Low-Rank Format ⋮ Hierarchical interpolative factorization preconditioner for parabolic equations ⋮ High scalable non-overlapping domain decomposition method using a direct method for finite element analysis ⋮ Fast algorithms for large dense matrices with applications to biofluids ⋮ Fast structured LU factorization for nonsymmetric matrices ⋮ An $O(N \log N)$ hierarchical random compression method for kernel matrices by sampling partial matrix entries ⋮ A survey on direct solvers for Galerkin methods ⋮ An Enriched Multiscale Mortar Space for High Contrast Flow Problems ⋮ 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 ⋮ A Recursive Skeletonization Factorization Based on Strong Admissibility ⋮ A parallel shared-memory implementation of a high-order accurate solution technique for variable coefficient Helmholtz problems ⋮ The Inverse Fast Multipole Method: Using a Fast Approximate Direct Solver as a Preconditioner for Dense Linear Systems ⋮ An algebraic multifrontal preconditioner that exploits the low‐rank property ⋮ Compressing Rank-Structured Matrices via Randomized Sampling ⋮ An improved divide-and-conquer algorithm for the banded matrices with narrow bandwidths ⋮ A survey of direct methods for sparse linear systems ⋮ Fast construction of hierarchical matrix representation from matrix-vector multiplication ⋮ A spectrally accurate direct solution technique for frequency-domain scattering problems with variable media ⋮ 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 ⋮ The method of polarized traces for the 2D Helmholtz equation ⋮ Preconditioners for hierarchical matrices based on their extended sparse form ⋮ An $O(N)$ direct solver for integral equations on the plane ⋮ 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 ⋮ ${\mathscr{H}} $-matrix approximability of inverses of discretizations of the fractional Laplacian ⋮ Randomized linear algebra for model reduction. I. Galerkin methods and error estimation ⋮ A Fast Algorithm for Simulating Multiphase Flows Through Periodic Geometries of Arbitrary Shape ⋮ Efficient preconditioning of $h p$-FEM matrix sequences with slowly-varying coefficients: an application to topology optimization ⋮ Fast Alternating BiDirectional Preconditioner for the 2D High-Frequency Lippmann--Schwinger Equation ⋮ Parallel Randomized and Matrix-Free Direct Solvers for Large Structured Dense Linear Systems ⋮ A Power Schur Complement Low-Rank Correction Preconditioner for General Sparse Linear Systems ⋮ Robust and Accurate Stopping Criteria for Adaptive Randomized Sampling in Matrix-Free Hierarchically Semiseparable Construction ⋮ Variational training of neural network approximations of solution maps for physical models ⋮ Subspace Iteration Randomization and Singular Value Problems ⋮ Bridging and Improving Theoretical and Computational Electrical Impedance Tomography via Data Completion ⋮ A high-order accurate accelerated direct solver for acoustic scattering from surfaces ⋮ Interconnected hierarchical structures for fast direct elliptic solution ⋮ A Parallel Geometric Multifrontal Solver Using Hierarchically Semiseparable Structure ⋮ A Distributed-Memory Package for Dense Hierarchically Semi-Separable Matrix Computations Using Randomization ⋮ A Hierarchical Preconditioner for Wave Problems in Quasilinear Complexity ⋮ Hierarchical Orthogonal Factorization: Sparse Square Matrices

This page was built for publication: Superfast Multifrontal Method for Large Structured Linear Systems of Equations