# Computational complexity in linear solvers

I have recently been trying out methods of coding for solving systems of linear equations on Python. Of course, I first used the inbuilt function $$\mathit{inv}$$ under certain if-conditions to obtain the solution, if unique. I also tried the LU decomposition method, and the Gaussian Elimination Method, neither of which proved very efficient either. I have not tried the QR method, but found an article online that suggested that it would be less efficient than the LU one, which makes it uninteresting to me.

I am trying to find resources about the most efficient complexity achieved on this problem, hopefully of O($$n^{r}$$), where $$r < 3$$. In fact, I would like a complete (or even less-than-complete) list of all improvements made in this area, and the most efficient solution currently available. Links to the code itself will be helpful, but are not necessary. I am more interested in the technique used, rather than the program itself, so links to the papers that illustrate the method and prove complexity of said method are what I am looking for here.

• Fast matrix multiplication algorithms translate to fast matrix inversion methods with the same exponent.
– Robert Israel
May 22, 2020 at 3:54
• To followup @RobertIsrael's comment:This leads to $n^{2.376}$. Unfortunately, as Wikipedia says, "it is of little practical use." May 22, 2020 at 11:45
• @joseph-orourke That is indeed unfortunate. Do you know of any literature that attempts to bound r non-trivially from below? Perhaps 2.376 is not the best possible exponent, in other words, theoretically, and may be significantly faster in growth than the lowest possible value of r.
– Inershya
May 22, 2020 at 12:02
• $2.376$ is certainly not the best possible. The Wikipedia page lists $2.373$ for "Optimized CW-like algorithms". The conjecture (see the paper of Cohn, Kleinberg, Szegedy and Umans) is that the optimal exponent is $2$. It certainly can't be less than $2$ because you have to look at all the matrix elements.
– Robert Israel
May 22, 2020 at 13:44
• If someone were to establish a lower bound that was strictly greater than 2, that would be huge news. On the other hand, if you are lucky, your matrix may be sparse or naturally factor as a product of sparse matrices, making such bounds somewhat irrelevant.
– S. Carnahan
May 24, 2020 at 22:44