About cookies on this site Our websites require some cookies to function properly (required). In addition, other cookies may be used with your consent to analyze site usage, improve the user experience and for advertising. For more information, please review your options. By visiting our website, you agree to our processing of information as described in IBM’sprivacy statement. To provide a smooth navigation, your cookie preferences will be shared across the IBM web domains listed here.
Publication
Theoretical Computer Science
Paper
Using fast matrix multiplication to find basic solutions
Abstract
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(m1.594n) arithmetic operations for an m × n problem in standard form. Previously, the best bound was O(m2n) arithmetic operations. © 1998 - Elsevier Science B.V. All rights reserved.