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.

  • 4
    $\begingroup$ Fast matrix multiplication algorithms translate to fast matrix inversion methods with the same exponent. $\endgroup$
    – Robert Israel
    May 22, 2020 at 3:54
  • $\begingroup$ To followup @RobertIsrael's comment:This leads to $n^{2.376}$. Unfortunately, as Wikipedia says, "it is of little practical use." $\endgroup$ May 22, 2020 at 11:45
  • $\begingroup$ @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. $\endgroup$
    – Inershya
    May 22, 2020 at 12:02
  • $\begingroup$ $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. $\endgroup$
    – Robert Israel
    May 22, 2020 at 13:44
  • 2
    $\begingroup$ 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. $\endgroup$
    – S. Carnahan
    May 24, 2020 at 22:44


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.