Direct methods for sparse linear systems

By Timothy A. Davis. 2006

1,636 citations recorded by the source corpus.

Subfields: Computational Theory and Mathematics, Numerical Analysis

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Computational Theory and Mathematics

In Numerical Analysis

Citations in the corpus

Effective Bayesian Modeling of Groups of Related Count Time Series (2014, methodology): “ix H latter is implemented in the Stan modeling language (Stan^ is nearly block-diagonal except for the variables that belong to G. This makes it efﬁcient to compute ^ by sparse matrix solvers (e.g., Davis, 2006). From the graphical model structure (Fig. 3) and the observation model (4), the predict”
Fitting Linear Mixed-Effects Models Using lme4 (2014, background): “forms for actual computation with sparse matrices are compressed sparse column (CSC) or compressed sparse row (CSR, Davis 2006, Chapter 2).”
General quantitative genetic methods for comparative biology: phylogenies, taxonomies and multi‐trait models for continuous and categorical characters (2010, methodology): “Last and most importantly, the pattern of zeros in S)1 allows GLS/mixed model equations to be re-ordered in such a way that the number of arithmetic operations needed to solve them is drastically reduced (for an introduction to sparse matrix methods, see Davis, 2006).”
A dimensional split preconditioner for Stokes and linearized Navier-Stokes equations (2011, methodology): “The systems can be solved very efficiently with a sparse Cholesky factorization with an approximate minimum degree (AMD) ordering; see [1,12].”
G2o: A general framework for graph optimization (2011, methodology): “But surprisingly CSparse is the fastest solver on the smaller instances like the MIT dataset where it outperforms both CHOLMOD and PCG.”
Dynamics of a large scale rigid–flexible multibody system composed of composite laminated plates (2011, methodology): “If b is a dense vector, the classical algorithm [32] for solving Ly = b can be illustrated by the pseudo-codes shown in Fig.”
Comparison of model reduction techniques for large mechanical systems (2008, background): “, CSparse [24] or TAUCS [30], can efficiently handle factorization methods, and thus the direct solving of large sparse linear systems.”
CasADi: a software framework for nonlinear optimization and optimal control (2018, methodology): “By default, the CSparse [28] plugin is used, but this can be changed by passing an option to the rootfinder constructor.”
Estimating the Multilevel Rasch Model: With the lme4 Package (2007, background): “Davis (2006) gives a general introduction to sparse matrix methods and describes his Csparse library of C functions that implement these methods.”
Numerical methods for nonlinear hillslope transport laws (2011, methodology): “This matrix operator is sparse, containing at most nine elements per row (corresponding to the nine‐point neighborhood centered on i, j), which permits the use of efficient algorithms for finding the solution [Saad, 2003; Davis, 2006].”
Accuracy and convergence properties of the fixed‐stress iterative solution of two‐way coupled poromechanics (2015, background): “The major advantages of direct methods are their reliability, robustness, and ease of implementation [29].”
Operator Splitting for a Homogeneous Embedding of the Linear Complementarity Problem (2020, methodology): “The ﬁrst way is a direct method, which solves the system exactly by initially computing a sparse permuted LDL (cid:62) factorization of the matrix [17], caching this factorization, and reusing it every iteration thereafter.”
Incremental smoothing and mapping (2008, background): “Davis has done much research in the areas of variable ordering and factorization updates, and provides highly optimized software libraries [18, 19, 17] for various such tasks.”
A Randomized Algorithm for Approximating the Log Determinant of a Symmetric Positive Definite Matrix (2015, methodology): “One approach would be to use direct methods such as Cholesky decomposition of A [6, 12].”
MCMC methods for multi-response generalized linear mixed models (2010, methodology): “This can involve repeatedly solving a very large but sparse set of mixed model equations, and the computational cost of doing this is minimized by using the CSparse C libraries for solving sparse linear systems (Davis 2006).”
Finite difference methods for ordinary and partial differential equations - steady-state and time-dependent problems (2007, methodology): “The backslash command in MATLAB can be used to solve systems using sparse storage, and it implements highly efficient direct methods using sophisticated algorithms for dynamically ordering the equations to minimize fill-in, as described by Davis [24].”
MFEM: a modular finite element methods library (2019, background): “artial assembly kernels, described in further detail in Subsection 6.3. Comprehensive support for a number of external numerical libraries, e.g., PETSc [11], SuperLU [63], STRUMPACK [44], SuiteSparse [30], SUNDIALS [49], and PUMI [55] is also included, which gives access to many additional linear an”
The Cosmic Linear Anisotropy Solving System (CLASS). Part II: Approximation schemes (2011, methodology): “We created a small sparse matrix package for our purpose based on [18].”