Gaussian elimination
The best classical algorithm which produces the actual solution vector formula_9 is Gaussian elimination, which runs in formula_75 time.