As far as I know, most direct methods for solving linear systems of equations have time copmlexity $O(n^3)$ (where $n$ is the number of variables), with the few methods being faster having huge constants, which make them only useful for very large matrices.
(Though, the best known bound I've found is $O(n^{2.373})$)

As every system of linear equations is also a system of linear inequalities, the formulation as linear program is one possibility, at least if one is satisfied with finding any possible solution.

My question now is:
How do solvers for linear programs fare against the regular methods of solving systems of linear equations? Are there cases in which they are better?

  • 4
    $\begingroup$ If LP solvers were better, you’d already be using them to solve linear equations. $\endgroup$ – Yuval Filmus Apr 11 at 5:26
  • $\begingroup$ Are you interested in theoretical bounds or in practical algorithms? Is it enough for you to find an approximate solution? $\endgroup$ – Yuval Filmus Apr 11 at 5:27
  • $\begingroup$ Are you interested in dense systems or in sparse systems? $\endgroup$ – Yuval Filmus Apr 11 at 5:27
  • $\begingroup$ @YuvalFilmus Dense systems. The practical complexity is mainly important to me if there are aspects that theoretical analysis hides (e.g. big constants) or if no theoretical analysis is known (Simplex method). Approximate solutions are interesting as well, though they'd have to be matched against the corresponding canonical method for approximating a solution of a system of equations. $\endgroup$ – Sudix Apr 11 at 5:48

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.