You can compute the inverse of a matrix A in asymptotically the same amount of time as you can multiply two matrices. You can also Cholesky factorise in that amount of time, and compute T^(-1) A where T is (upper or lower) triangular in that amount of time. You invert by A^(-1) = (A^T A)^(-1) A^T, the latter computed by Cholesky and two triangular solves. You Cholesky and do triangular solves by divide-and-conquer.
Yes, I made a mistake. Gaussian elimination is O(n^3), but there are general algorithms which are as fast (or slow, depending on how you look at it) as the current complexity bound for matrix multiplication which is O(n^{2.737}). Not the end of the world, I corrected the article. Reference:
Still, the point stands that you'd never want to actually solve a large system "the generic way" unless you really have to (i.e. you cannot identify a structure for which you have a faster algorithm).
>However, the constant coefficient hidden by the Big O notation is so large that these algorithms are only worthwhile for matrices that are too large to handle on present-day computers.
No wonder I never heard about these. I updated it for correctness (and fixed the link, ugh) but yeah, these are details I'd hope to not dwell on in the post since for all intents and purposes you'd still never want to do the worst fallback unless you have to.
Yep. (Largely) irrelevant in practice. But the gap between what we can do and what lower bounds we can prove is very large indeed for many matrix operations.
I am not an expert but I think you are right and I misread it myself. After reading it again Gaussian elimination seems to be somewhat worse than O(n³) but other algorithms are as fast as fast matrix multiplication.
The details people are talking about in that MathOverflow thread concern the precision needed to represent the numbers that crop up during Gaussian elimination. (They get huge, and if you are counting bit or word operations, then Gaussian elimination is indeed terribly slow.) The post author is using a less detailed model in which he counts arithmetic operations. In this model, matrix multiplication and matrix inversion have the same asymptotic complexity.
So no, the article is wrong.