3 ms·

Looks like a description of simplex (and/or montecarlo) method for solving linear equations. Or did I get it wrong?

alanbernstein 6y ago
I believe the simplex method is for solving optimization problems, not linear systems?
vitus 6y ago
1. Simplex is used to solve linear programs, which are inequalities (not equations). While it's true that your solution will typically be on one of the vertices of your polytope, that just means that some (not necessarily all) of your constraints are hard constraints. 2. The worst-case time complexity of Simplex is exponential.
- c-smile 6y ago
  AFAIR first step of simplex method is to convert system of inequalities to system of equalities by adding weak variables and making tableau (matrix) of those. And then incrementally solve that. And usually simplex is considered as having polynomial complexity - close to their estimations.
  - eru 6y ago
    Simplex uses solving systems of linear equations as a building block. Most variants of simplex have exponential runtime on worst case input. (But they do well in practice.) Recently, some variants of simplex with polynomial runtime have been found. Solving linear equations was always known to 'only' take polynomial amounts of time at most. But the question is whether that's n^3 or n^2 or something better..
  - vitus 6y ago
    (I'd be interested to see an average-case running-time analysis of Simplex that yields O(n^2.332) additions/multiplications, where n is the number of variables. Or even O(n^3). Because that's what's claimed here.) That's mostly correct. You end up with a system of equalities for _a subset_ of your points, which yields a single vertex. Ultimately with a linear program, you're trying to optimize an objective function, max w'x s.t. Ax <= b, x >= 0 (in canonical form). The x >= 0 constraint makes this nontrivial to translate from a linear equation Ax = b. If you magically knew the sign of each component of the solution, you'd be able to perform a simple variable substitution, but you generally don't, at least not without solving the system of equations. (And yes, you need that constraint, or else your LP is unbounded, and your solution ends up with a negative infinity in it.)
jl2718 6y ago
Krylov subspace methods. Use a random seed to find an approximate diagonalization.

I believe the simplex method is for solving optimization problems, not linear systems?

1. Simplex is used to solve linear programs, which are inequalities (not equations). While it's true that your solution will typically be on one of the vertices of your polytope, that just means that some (not necessarily all) of your constraints are hard constraints. 2. The worst-case time complexity of Simplex is exponential.

c-smile 6y ago
AFAIR first step of simplex method is to convert system of inequalities to system of equalities by adding weak variables and making tableau (matrix) of those. And then incrementally solve that. And usually simplex is considered as having polynomial complexity - close to their estimations.
- eru 6y ago
  Simplex uses solving systems of linear equations as a building block. Most variants of simplex have exponential runtime on worst case input. (But they do well in practice.) Recently, some variants of simplex with polynomial runtime have been found. Solving linear equations was always known to 'only' take polynomial amounts of time at most. But the question is whether that's n^3 or n^2 or something better..
- vitus 6y ago
  (I'd be interested to see an average-case running-time analysis of Simplex that yields O(n^2.332) additions/multiplications, where n is the number of variables. Or even O(n^3). Because that's what's claimed here.) That's mostly correct. You end up with a system of equalities for _a subset_ of your points, which yields a single vertex. Ultimately with a linear program, you're trying to optimize an objective function, max w'x s.t. Ax <= b, x >= 0 (in canonical form). The x >= 0 constraint makes this nontrivial to translate from a linear equation Ax = b. If you magically knew the sign of each component of the solution, you'd be able to perform a simple variable substitution, but you generally don't, at least not without solving the system of equations. (And yes, you need that constraint, or else your LP is unbounded, and your solution ends up with a negative infinity in it.)

jl2718 6y ago

Krylov subspace methods. Use a random seed to find an approximate diagonalization.