Roundoff-Error-Free Basis Updates of LU Factorizations for the Efficient Validation of Optimality Certificates

DOI10.1137/16M1089630zbMath1373.65018WikidataQ114074327 ScholiaQ114074327MaRDI QIDQ5358295

Adolfo R. Escobedo, Erick Moreno-Centeno

Publication date: 20 September 2017

Published in: SIAM Journal on Matrix Analysis and Applications (Search for Journal in Brave)

zbMATH Keywords

algorithmnumerical examplesLU factorizationroundoff errorsCholesky factorizationsexact mathematical programmingmatrix factorization updates

Mathematics Subject Classification ID

Numerical mathematical programming methods (65K05) Mixed integer programming (90C11) Linear programming (90C05) Roundoff error (65G50) Direct numerical methods for linear systems and matrix inversion (65F05)

Related Items (3)

Roundoff-Error-Free Basis Updates of LU Factorizations for the Efficient Validation of Optimality Certificates ⋮ 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

• gmp
• SoPlex
• QSopt_ex
• QSopt-Exact

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• A hybrid branch-and-bound approach for exact rational mixed-integer programming
• Distributed matrix-free solution of large sparse linear systems over finite fields
• Exact solution of linear equations using p-adic expansions
• A fast LU update for linear programming
• The final NETLIB-LP results
• Safe bounds in linear and mixed-integer linear programming
• Maintaining LU factors of a general sparse matrix
• 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
• Roundoff-Error-Free Algorithms for Solving Linear Systems via Cholesky and LU Factorizations
• Iterative Refinement for Linear Programming
• Solving sparse rational linear systems
• Solving Very Sparse Rational Systems of Equations
• An Exact Rational Mixed-Integer Programming Solver
• An Algorithm-by-Blocks for SuperMatrix Band Cholesky Factorization
• Solving sparse linear equations over finite fields
• A sparsity-exploiting variant of the Bartels—Golub decomposition for linear programming bases
• Updated triangular factors of the basis to maintain sparsity in the product form simplex method
• Roundoff-Error-Free Basis Updates of LU Factorizations for the Efficient Validation of Optimality Certificates
• Systems of distinct representatives and linear algebra
• The simplex method of linear programming using LU decomposition
• 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 Basis Updates of LU Factorizations for the Efficient Validation of Optimality Certificates