Timeline for What is the fastest algorithm to establish whether a linear system in $\mathbb{R}$ has a solution?
Current License: CC BY-SA 4.0
5 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Jan 21, 2019 at 13:20 | comment | added | Pseudonym♦ | Yes. See Bunch & Hopcroft, "Triangular Factorization and Inversion by Fast Matrix Multiplication". apps.dtic.mil/dtic/tr/fulltext/u2/754790.pdf Essentially, if two matrices of order $n$ can be multiplied in $M(n) = \Omega(n^2)$ time, then triangular factorisation, inversion, and determinant calculation can be performed in $O(M(n))$ time. | |
| Jan 18, 2019 at 14:37 | comment | added | Gio | Thanks for your answer. I'm also curious about what @j_random_hacker asked. Is there any reference for this claim? | |
| Jan 17, 2019 at 17:07 | vote | accept | Gio | ||
| Jan 17, 2019 at 13:33 | comment | added | j_random_hacker | Does "As far as we know" mean that someone has given a reduction from matrix multiplication to determining whether it has a solution? Or is it just a commonly held "feeling"? | |
| Jan 17, 2019 at 7:16 | history | answered | Pseudonym♦ | CC BY-SA 4.0 |