5 ms·

> In fact, you can show that solving a linear systems has to have O(n^3) as a lower bound Where did the author get this idea? It can be done more efficiently t

> In fact, you can show that solving a linear systems has to have O(n^3) as a lower bound Where did the author get this idea? It can be done more efficiently than that: https://mathoverflow.net/a/52557/40272 https://mathoverflow.net/a/52557/40272

danbruc 9y ago
I think you are misreading the answers; it states the well-known fact that matrix multiplication and inversion can be done is less than O(n³) but it does not say this about solving linear systems. If you read through the material referenced in the answers it seems that O(n³) is indeed a lower bound and actually hard to obtain in practice.
- tmyklebu 9y ago
  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. So no, the article is wrong.
  - danbruc 9y ago
    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.
    - tmyklebu 9y ago
      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.
  - ChrisRackauckas 9y ago
    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: http://theory.epfl.ch/vishnoi/CargeseLectures.pdf http://theory.epfl.ch/vishnoi/CargeseLectures.pdf 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).
    - tmyklebu 9y ago
      It looks like you also turned the rest of your post into a link. The best currently known exponent for square matrix multiplication is around 2.3728; Wikipedia's page on matrix multiplication has a reference.
      - ChrisRackauckas 9y ago
        >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.
        tmyklebu 9y ago
        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.

danbruc 9y ago

I think you are misreading the answers; it states the well-known fact that matrix multiplication and inversion can be done is less than O(n³) but it does not say this about solving linear systems. If you read through the material referenced in the answers it seems that O(n³) is indeed a lower bound and actually hard to obtain in practice.

tmyklebu 9y ago
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. So no, the article is wrong.
- danbruc 9y ago
  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.
  - tmyklebu 9y ago
    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.
- ChrisRackauckas 9y ago
  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: http://theory.epfl.ch/vishnoi/CargeseLectures.pdf http://theory.epfl.ch/vishnoi/CargeseLectures.pdf 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).
  - tmyklebu 9y ago
    It looks like you also turned the rest of your post into a link. The best currently known exponent for square matrix multiplication is around 2.3728; Wikipedia's page on matrix multiplication has a reference.
    - ChrisRackauckas 9y ago
      >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.
      - tmyklebu 9y ago
        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.