1
$\begingroup$

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.

Improve this question
$\endgroup$
6
  • 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$
    – Joseph O'Rourke
    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

0

Reset to default

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.