Maximum Consensus Floating Point Solutions for Infeasible Low-Dimensional Linear(…)
summary
Claims an algorithm that finds a maximum consensus floating point solution for infeasible low-dimensional linear programs with billions of constraints and few variables, using geometric duality to compute a convex hull as IR in 2D to extract a superset V of violated constraints. Method: identify a feasible basis from X, add slack and unitary variables for V, move complementarity penalties into the objective, and solve iteratively. Applied to RLibm LPs, it fixes many timed-out cases, yields correct-rounding improvements and up to ~100x speedups (most infeasible instances solved within ~20 minutes), with remaining violations handled as hard-coded special cases.
AI-written summary · about
chapters (12)
- 0:00Correct rounding in math libraries
- 1:27Correct rounding for transcendental functions
- 3:14Infeasible linear programs in math libraries
- 4:58Maximum consensus solutions for infeasible systems
- 6:31Computational geometry duality for constraints
- 9:43Dual space transformation for analysis
- 11:06Convex hull for optimization
- 12:31Maximum consensus feasible solutions
- 13:36Linear programming with slack variables
- 15:42Iterative solving and convergence
- 16:26Experimental results and performance
- 16:47Q&A
related talks
28mA Unified Approach for Reverse Data Management Problems
01h 24mIntroduction to Constraint Logic Programming
24mWhen Less Is More: Consequence-Finding in a Weak Theory of Arithmetic
30mExact Completeness of LP Hierarchies for Linear Codes
57mQuery Optimization and Evaluation 1: Output Size Bounds and Information Theory
41mIntroduction to Constraint Programming
01h 02mThe Complexity of Dynamic Least-Squares Regression
36mOptimizing Relational Programs II