Using fast matrix multiplication to find basic solutions

✍ Scribed by Peter A. Beling; Nimrod Megiddo

• Book ID: 104326461
• Publisher: Elsevier Science
• Year: 1998
• Tongue: English
• Weight: 679 KB
• Volume: 205
• Category: Article
• ISSN: 0304-3975
• DOI: 10.1016/s0304-3975(98)00003-6

✦ Synopsis

We consider the problem of finding a basic solution to a system of linear constraints (in standard form) given a non-basic solution to the system. We show that the known arithmetic complexity bounds for this problem admit considerable improvement. Our technique, which is similar in spirit to that used by Vaidya to find the best complexity bounds for linear programming, is based on reducing much of the computation involved to matrix multiplication. Consequently, our complexity bounds in their most general form are a function of the complexity of matrix multiplication. Using the best known algorithm for matrix multiplication, we achieve a running time of O(TTI'.'~~~) arithmetic operations for an m x n problem in standard form. Previously, the best bound was O(m2n) arithmetic operations.