Exact Solution of Sparse Linear Systems via Left-Looking Roundoff-Error-Free LU Factorization in Time Proportional to Arithmetic Work
From MaRDI portal
Publication:5232110
DOI10.1137/18M1202499zbMath1431.65060WikidataQ127870759 ScholiaQ127870759MaRDI QIDQ5232110
Adolfo R. Escobedo, Timothy A. Davis, Erick Moreno-Centeno, Christopher J. Lourenco
Publication date: 29 August 2019
Published in: SIAM Journal on Matrix Analysis and Applications (Search for Journal in Brave)
sparse linear systemsroundoff errorssparse matrix algorithmsLu factorizationssolving linear systemsexact linear solutionssparse IPGE word length
Computational methods for sparse matrices (65F50) Factorization of matrices (15A23) Linear programming (90C05) Roundoff error (65G50) Direct numerical methods for linear systems and matrix inversion (65F05)
Related Items
Algorithm 1021: SPEX Left LU, Exactly Solving Sparse Linear Systems via a Sparse Left-looking Integer-preserving LU Factorization, Exactly Solving Sparse Rational Linear Systems via Roundoff-Error-Free Cholesky Factorizations, A preconditioning method with auxiliary crack tip subproblems for dynamic crack propagation based on XFEM, Exact QR factorizations of rectangular matrices
Uses Software
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Exact solution of linear equations using p-adic expansions
- The final NETLIB-LP results
- Safe bounds in linear and mixed-integer linear programming
- Exact arithmetic at low cost. -- A case study in linear programming
- Fraction free Gaussian elimination for sparse matrices
- An algorithm to solve integer linear systems exactly using numerical methods
- Exact solutions to linear programming problems
- A proof of the Kepler conjecture
- Fast multiplication of large numbers
- Roundoff-Error-Free Algorithms for Solving Linear Systems via Cholesky and LU Factorizations
- Iterative Refinement for Linear Programming
- On the Minimum FLOPs Problem in the Sparse Cholesky Factorization
- Solving Very Sparse Rational Systems of Equations
- An Exact Rational Mixed-Integer Programming Solver
- Computing the Crosscap Number of a Knot Using Integer Programming and Normal Surfaces
- Direct Methods for Sparse Linear Systems
- Solving sparse linear equations over finite fields
- Sparse Partial Pivoting in Time Proportional to Arithmetic Operations
- Computing the Minimum Fill-In is NP-Complete
- Sparse Matrices in MATLAB: Design and Implementation
- Predicting Structure in Sparse Matrix Computations
- Computational Experience and the Explanatory Value of Condition Measures for Linear Optimization
- Solution of Dense Linear Systems via Roundoff-Error-Free Factorization Algorithms
- An Approximate Minimum Degree Ordering Algorithm
- Roundoff-Error-Free Basis Updates of LU Factorizations for the Efficient Validation of Optimality Certificates
- A column approximate minimum degree ordering algorithm
- Algorithm 836
- Systems of distinct representatives and linear algebra
- Sylvester's Identity and Multistep Integer-Preserving Gaussian Elimination
- Computational Solutions of Matrix Problems Over an Integral Domain
- A survey of direct methods for sparse linear systems