Fast Algorithms for Separable Linear Programs
Sally Dong, Gramoz Goranci, Lawrence Li, Sushant Sachdeva, Guanghao Ye · Society for Industrial and Applied Mathematics eBooks · 2024
In numerical linear algebra, considerable effort has been devoted to obtaining faster algorithms for linear systems whose underlying matrices exhibit structural properties. A prominent success story is the method of generalized nested dissection [Lipton-Rose-Tarjan’79] for separable matrices. On the other hand, the majority of recent developments in the design of efficient linear program (LP) solvers have not leveraged the ideas underlying these faster linear system solvers nor exploited the separable structure of the constraint matrix.