The Multifrontal Method for Sparse Matrix Solution: Theory and Practice
The main purpose of the paper is to give a uniform presentation of the multifrontal method of \textit{I. S. Duff} and \textit{J. K. Reid} [ACM Trans. Math. Software. 9, 302-325 (1983; Zbl 0515.65022)], one of the significant advances in direct methods for large sparse linear systems solution. The method reorganizes the overall factorization of a sparse matrix into a sequence of partial factorizations of dense smaller matrices. The method has proved to be extremely valuable in many large-scale finite element applications, in the solution of the Navier-Stokes equation, in the solution of separable optimization problems and also in the linear programming. Most formulations of the multifrontal method in the literature rely heavily on the context of the finite element method. The author's exposition is purely from the matrix point of view. The notions of the frontal matrix, update matrix and assembly tree, essential for the method, are all formally defined in terms of the sparse matrix structure. The author's aim is to put the terminologies, notation and algorithm formulation into a standard framework for future references and development. After the presentation -- in the paragraph 2 -- of some basic background on sparse Cholesky factorization, the author introduces the elimination tree structure and defines formally the sequence of frontal and update matrices (paragraph 3). In the next section he considers the way these matrices can be formed. For this purpose, a matrix extend-add operator is defined. Although the author defines frontal and update matrices in terms of elimination tree structure, a more general form of an assembly tree can be used; a new general definition of an assembly tree is also given in the section. In the section 5 some issues related to the storage and manipulation of these frontal and update matrices are considered. An algorithm to generate the best postordering of the tree in minimizing the storage for the stack of full triangular matrices is given here. In the two next sections the supernodal version of the method as well as useful implementation techniques are described and discussed. Finally, in the paragraph 8 the author considers the usage of the multifrontal method in various different computational environments: virtual-memory paging systems, limited core-memory systems and vector and parallel supercomputing machines. No experimental results are presented; rather, references are provided to related papers in the literature.
- Multifrontal Computation with the Orthogonal Factors of Sparse Matrices
- Sparse matrix approximations for multigrid methods
- A combined unifrontal/multifrontal method for unsymmetric sparse matrices
- scientific article; zbMATH DE number 741180
- Sparse Matrix Methods in Optimization
- Streamlined solutions to multilevel sparse matrix problems
- Sparse Matrix Factorizations for Fast Linear Solvers with Application to Laplacian Systems
- scientific article; zbMATH DE number 1153374
- Efficient structured multifrontal factorization for general large sparse matrices
- Hypermatrix oriented supernode amalgamation
- Parallel exact sampling and evaluation of Gaussian Markov random fields
- A review of frontal methods for solving linear systems
- A parallel solver for the hp-version of finite element methods
- A parallel multifrontal algorithm and its implementation
- Listing all potential maximal cliques of a graph
- Free-surface film flow over topography: full three-dimensional finite element solutions
- An adaptive DPG method for high frequency time-harmonic wave propagation problems
- New parallel sparse direct solvers for multicore architectures
- Processor-efficient sparse matrix-vector multiplication
- Multiprocessing a sparse matrix code on the Alliant FX/8
- Sparse Cholesky factorization on FPGA using parameterized model
- Sparse semidefinite programs with guaranteed near-linear time complexity via dualized clique tree conversion
- Interconnected hierarchical structures for fast direct elliptic solution
- A multilevel approach for trace system in HDG discretizations
- A coupled HDG-FV scheme for the simulation of transient inviscid compressible flows
- Discrete least-squares finite element methods
- Sparsifying preconditioner for the time-harmonic Maxwell's equations
- A robust multilevel preconditioner based on a domain decomposition method for the Helmholtz equation
- A fast block low-rank dense solver with applications to finite-element matrices
- An asynchronous direct solver for banded linear systems
- Distributed-memory hierarchical interpolative factorization
- Sparse matrix factorization in the implicit finite element method on petascale architecture
- A parallel solver for adaptive finite element discretizations
- A shared- and distributed-memory parallel general sparse direct solver
- An adaptive multigrid solver for DPG methods with applications in linear acoustics and electromagnetics
- \({\mathcal{H}} \)-matrix approximability of inverses of FEM matrices for the time-harmonic Maxwell equations
- Recursive sweeping preconditioner for the three-dimensional Helmholtz equation
- A robust multilevel method for the time-harmonic Maxwell equation with high wave number
- Sparse matrix approximations for multigrid methods
- An efficient multicore implementation of a novel HSS-structured multifrontal solver using randomized sampling
- Analysis of scattering by conducting objects covered with arbitrarily magnetised plasma using finite element-boundary integral-fast multipole algorithm
- Fast algorithms for high frequency wave propagation
- An efficient analyse phase for element problems.
- A fast, memory efficient and robust sparse preconditioner based on a multifrontal approach with applications to finite-element matrices
- Enhancing performance and robustness of ILU preconditioners by blocking and selective transposition
- State-defect constraint pairing graph coarsening method for Karush-Kuhn-Tucker matrices arising in orthogonal collocation methods for optimal control
- Fast algorithms for hierarchically semiseparable matrices
- Solving the Cahn-Hilliard variational inequality with a semi-smooth Newton method
- Performance models and workload distribution algorithms for optimizing a hybrid CPU-GPU multifrontal solver
- Sweeping preconditioner for the Helmholtz equation: hierarchical matrix representation
- Hierarchical interpolative factorization for elliptic operators: differential equations
- Design Features of a Frontal Code for Solving Sparse Unsymmetric Linear Systems Out-of-Core
- A fast nested dissection solver for Cartesian 3D elliptic problems using hierarchical matrices
- Applications of statistical condition estimation to the solution of linear systems
- scientific article; zbMATH DE number 4005436 (Why is no real title available?)
- On the storage requirement in the out-of-core multifrontal method for sparse factorization
- On threshold pivoting in the multifrontal method for sparse indefinite systems
- A fast direct solver for elliptic problems on general meshes in 2D
- A Navier-Stokes solver for complex three-dimensional turbulent flows adopting non-linear modelling of the Reynolds stresses
- scientific article; zbMATH DE number 741126 (Why is no real title available?)
- scientific article; zbMATH DE number 741180 (Why is no real title available?)
- scientific article; zbMATH DE number 741182 (Why is no real title available?)
- scientific article; zbMATH DE number 741210 (Why is no real title available?)
- A generalized envelope method for sparse factorization by rows
- A combined unifrontal/multifrontal method for unsymmetric sparse matrices
- FPGA implementation of a Cholesky algorithm for a shared-memory multiprocessor architecture
- Effective preconditioning through minimum degree ordering interleaved with incomplete factorization
- A survey on direct solvers for Galerkin methods
- Sparse approximate multifrontal factorization with butterfly compression for high-frequency wave equations
- Efficient Direct Space-Time Finite Element Solvers for Parabolic Initial-Boundary Value Problems in Anisotropic Sobolev Spaces
- RCHOL: Randomized Cholesky Factorization for Solving SDD Linear Systems
- Sparse approximate multifrontal factorization with butterfly compression for high-frequency wave equations
- Exact or approximate inference in graphical models: why the choice is dictated by the treewidth, and how variable elimination can be exploited
- Improving multifrontal methods by means of block low-rank representations
- Distributed primal–dual interior-point methods for solving tree-structured coupled convex problems using message-passing
- A parallel sparse direct solver via hierarchical DAG scheduling
- A parallel geometric multifrontal solver using hierarchically semiseparable structure
- Logarithmic barriers for sparse matrix cones
- Efficient structured multifrontal factorization for general large sparse matrices
- 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
- scientific article; zbMATH DE number 2209876 (Why is no real title available?)
- A fast multifrontal solver for nonlinear multi-physics problems
- An algebraic multifrontal preconditioner that exploits the low-rank property.
- A survey of direct methods for sparse linear systems
- An integrated Davidson and multigrid solution approach for very large scale symmetric eigenvalue problems
- Efficient computation of the compositional model for gas condensate reservoirs
- Acoustic inverse scattering via Helmholtz operator factorization and optimization
- An Incomplete Cholesky Preconditioner Based on Orthogonal Approximations
- Linear optimization over homogeneous matrix cones
- Modeling 1D Distributed-Memory Dense Kernels for an Asynchronous Multifrontal Sparse Solver
- Novel stochastic descriptors of a Markovian SIRD model for the assessment of the severity behind epidemic outbreaks
- Sparse approximate multifrontal factorization with composite compression methods
- Efficient direct space-time finite element solvers for the wave equation in second-order formulation
- Sparse linear least-squares problems
- Approximation algorithms for treewidth, pathwidth, and treedepth -- a short survey
- Hierarchical interpolative factorization for self Green's function in 3D modified Poisson-Boltzmann equations
- Hierarchical node method for solving large-scale sparse linear equations in parallel
- A stochastic SIRD model with imperfect immunity for the evaluation of epidemics
- On the use of block low rank preconditioners for primal domain decomposition methods
- A block Lanczos method for the symmetric generalized eigenvalue complementarity problem
- Multi-core parallel robust structured multifrontal factorization method for large discretized PDEs
- Convergence acceleration of direct trajectory optimization using novel Hessian calculation methods
- Analysis of the solution phase of a parallel multifrontal approach
This page was built for publication: The Multifrontal Method for Sparse Matrix Solution: Theory and Practice
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3990664)