The cost of 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/few 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})$. I assume this can be used to solve a linear system in $\mathcal{O}(N^{\log\_27})$. (?)


(The system has no special structure. 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.)


Thanks



Lower Bound on the Cost of Solving Linear System
Any $O(N^t)$ algorithm for matrix multiplication yields a corresponding $O(N^t)$ algorithm for matrix inversion. There are not any non-trivial lower bounds for matrix multiplication. It is believed that there exist $O(N^{2 + \epsilon})$ algorithms for any $\epsilon > 0$, but as far as I know there are not believed to be $O(N^2)$ algorithms.


