Fast Linear Programming through Transprecision Computing on Small and Sparse Data
summary
Analyzes ~500,000 simplex tableaux from Polly PPCG and HayStack and finds >99% of coefficients <9 bits, medians of 18 columns and 84% sparsity, with rare values up to 127 bits. Builds a C++ transprecision simplex (template-instantiated precisions, 16-bit vectorized pivots, transprecision dispatcher) plus a Prime GCD Algorithm using prime-factor bitvectors and a new small-sparsity format. Core pivot latency drops from ~60 to ~15 cycles, coalesce sees 3.2x mean speedup and 6.7x on sum-of-times versus GMP.
AI-written summary · about
chapters (14)
- 0:00Start
- 0:15A Fast Cache Model
- 1:25Integer Sets
- 2:31Integer Set Operations
- 3:07Simplex at the Heart of Integer Set Arithmetic
- 3:45Simplex: A Sequence of Pivot Steps minimize cx
- 4:21Pivot - Row Operations over a (Dense) Matrix
- 5:16Characteristics Of Simplex Tableaux in Compilers
- 8:10Heterogeneity of SIMD Instruction Sets (AVX-512)
- 9:05Keeping Coefficients Small: Normalization
- 9:44Prime GCD for SIMD & Small Numbers
- 10:48Evaluation
- 11:56Fast Coalesce with Transprecision Simplex
- 12:35Conclusion
related talks
14mFast and Efficient Bit-Level Precision Tuning
14mFPL: Fast Presburger Arithmetic through Transprecision
44mScalable Algorithmic Primitives for Data Science
05mLightning Talk: Simple Compile Time Dynamic Programming
42mLearning What Works Best When
19mGeneralSparse: Bridging the Gap in SpMM for Pruned Large Language Model Inference..
58mPortable floating-point calculations
20mStatic Posterior Inference of Bayesian Probabilistic Programming via Polynomial Solving