Roundoff-error-free algorithms for solving linear systems via Cholesky and LU factorizations

DOI10.1287/IJOC.2015.0653MaRDI QIDQ2802247zbMATH OpenOpenAlexWikidataFDO

Authors 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 factorizationexact algorithmsmatrix factorizationsLU factorizationroundoff errorsexact mathematical programmingsolving linear systems

Mathematics Subject Classification ID

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

Recommendations

• Roundoff-Error-Free Basis Updates of LU Factorizations for the Efficient Validation of Optimality Certificates
• Exact solution of sparse linear systems via left-looking roundoff-error-free Lu factorization in time proportional to arithmetic work
• Exactly solving sparse rational linear systems via roundoff-error-free Cholesky factorizations
• Forward roundoff error analysis of the LU and Cholesky factorizations
• Solution of dense linear systems via roundoff-error-free factorization algorithms. Theoretical connections and computational comparisons

Cites work

• scientific article; zbMATH DE number 1253960 (Why is no real title available?)
• scientific article; zbMATH DE number 2079347 (Why is no real title available?)
• An algorithm to solve integer linear systems exactly using numerical methods
• Analysis of Algorithms, A Case Study: Determinants of Matrices with Polynomial Entries
• Computational Solutions of Matrix Problems Over an Integral Domain
• Distributed matrix-free solution of large sparse linear systems over finite fields
• Exact solution of linear equations using p-adic expansions
• Exact solutions to linear programming problems
• Fast multiplication of large numbers
• Fraction free Gaussian elimination for sparse matrices
• How Tight is Hadamard's Bound?
• Improving the accuracy of linear programming solvers with iterative refinement
• Note sur les $Q$-matrices d’Edmonds
• Rational solutions of singular linear systems
• Safe bounds in linear and mixed-integer linear programming
• Solving sparse linear equations over finite fields
• Solving sparse rational linear systems
• Solving very sparse rational systems of equations
• Sylvester's Identity and Multistep Integer-Preserving Gaussian Elimination
• Systems of distinct representatives and linear algebra
• The final NETLIB-LP results

Cited in

(7)

• Roundoff-Error-Free Basis Updates of LU Factorizations for the Efficient Validation of Optimality Certificates
• Algorithm 1021: SPEX Left LU, Exactly Solving Sparse Linear Systems via a Sparse Left-looking Integer-preserving LU Factorization
• Exact Matrix Factorization Updates for Nonlinear Programming
• Exact QR factorizations of rectangular matrices
• Exactly solving sparse rational linear systems via roundoff-error-free Cholesky factorizations
• Solution of dense linear systems via roundoff-error-free factorization algorithms. Theoretical connections and computational comparisons
• Exact solution of sparse linear systems via left-looking roundoff-error-free Lu factorization in time proportional to arithmetic work

Describes a project that uses

Uses Software

• QSopt_ex
• QSopt-Exact

This page was built for publication: Roundoff-error-free algorithms for solving linear systems via Cholesky and LU factorizations

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2802247)