Dynamic Linear Algebra
summary
Describes algorithms that maintain changing matrices to update graph and optimization answers faster, with concrete bounds: a matrix multiplication time deterministic LP solver and an LP solver running in nd + d^3 time (so nearly linear when n >> d), simplex iterations dropping from O(n^2) to O(n^1.5) each, and nearly-linear algorithms for discrete optimal transport, L1 regression when n ≥ d^1.5, min-cost flow and matching under similar density assumptions. All methods rely on handling updates as low-rank change or low-rank approximations.
AI-written summary · about