As most of us are aware the cost for solving a linear system ("exactly") with Gauss Elimination and other similar methods with a few right hand side and where the matrix has no structure is $\mathcal{O}(N^3)$ where $N$ is the system size.
I am wondering about the lower bound for solving a linear system. An obvious lower bound is $\mathcal{\Omega}(N^2)$ (since the information content is $\mathcal{O}(N^2)$). Are there better lower bounds other than $\mathcal{\Omega}(N^2)$ for solving the linear system? Is there a way to prove that the lower bound of $\mathcal{\Omega}(N^2)$ can never be hit for a matrix with no special structure? (assume that we are solving a system with only one right hand side).
Also are there other algorithm which solve these system "exactly" whose cost is less than $\mathcal{O}(N^3)$? I am aware of Strassen algorithm which perform matrix multiplications in $\mathcal{O}(N^{\log_27})$. Can this be used to solve a linear system in $\mathcal{O}(N^{\log_27})$?
(Note: The system has no special structure. Say the matrix is just made up of entries drawn out of a random number generator. I am not worried about the stability and other numerical intricacies of the method as of now. I would appreciate if someone could point to some work done in this regard.)
Best Answer
I assuming we are talking in terms of number of multiplications.
Since the de-facto algorithm for solving linear equations is Gaussian Elimination, let us only consider Gaussian Elimination.
Note that Gaussian Elimination can invert matrices in the same complexity as it solves linear equations.
It is well known that Matrix Inversion is as easy (or hard, if you will) as Matrix Multiplication (see this: http://www.lehigh.edu/~gi02/m242/08linstras.pdf)
The best known lower bound for Matrix multiplication, is apparently $\Omega(n^2)$, I believe.
I doubt you can find better lower bounds than that. In any case, the lower bounds you seek would very likely be same as the lower bounds for Matrix Multiplication.
Of course, that does not really answer your question exactly, but hope that helps.