Roundoff-Error-Free Algorithms for Solving Linear Systems via Cholesky and LU Factorizations

DOI10.1287/ijoc.2015.0653zbMath1337.65025OpenAlexW2209734631WikidataQ114058191 ScholiaQ114058191MaRDI QIDQ2802247

Adolfo R. Escobedo, Erick Moreno-Centeno

Publication date: 25 April 2016

Published in: INFORMS Journal on Computing (Search for Journal in Brave)

Full work available at URL: https://semanticscholar.org/paper/30d7b1ce78a453fd91e9c1c8451528ae55e6e98c

zbMATH Keywords

computational complexityCholesky factorizationLU factorizationroundoff errorsexact algorithmsmatrix factorizationsexact mathematical programmingsolving linear systems

Mathematics Subject Classification ID

Roundoff error (65G50) Complexity and performance of numerical algorithms (65Y20) Direct numerical methods for linear systems and matrix inversion (65F05)

Related Items (6)

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 ⋮ Roundoff-Error-Free Basis Updates of LU Factorizations for the Efficient Validation of Optimality Certificates ⋮ Exact QR factorizations of rectangular matrices ⋮ Linear programming using limited-precision oracles ⋮ Exact Solution of Sparse Linear Systems via Left-Looking Roundoff-Error-Free LU Factorization in Time Proportional to Arithmetic Work

Uses Software

• QSopt_ex
• QSopt-Exact

Cites Work

• Unnamed Item
• Unnamed Item
• Distributed matrix-free solution of large sparse linear systems over finite fields
• Exact solution of linear equations using p-adic expansions
• The final NETLIB-LP results
• Safe bounds in linear and mixed-integer 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
• Fast multiplication of large numbers
• How Tight is Hadamard's Bound?
• Solving sparse rational linear systems
• Solving Very Sparse Rational Systems of Equations
• Rational solutions of singular linear systems
• Solving sparse linear equations over finite fields
• Analysis of Algorithms, A Case Study: Determinants of Matrices with Polynomial Entries
• Note sur les $Q$-matrices d’Edmonds
• Improving the accuracy of linear programming solvers with iterative refinement
• 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

This page was built for publication: Roundoff-Error-Free Algorithms for Solving Linear Systems via Cholesky and LU Factorizations