3 ms·

A lower bound of O(n^2 log n) has been known for quite some time. Good luck going any tighter than that... https://eccc.weizmann.ac.il/report/2002/012/download

by klyrs 4y ago

A lower bound of O(n^2 log n) has been known for quite some time. Good luck going any tighter than that... https://eccc.weizmann.ac.il/report/2002/012/download/ https://eccc.weizmann.ac.il/report/2002/012/download/ [pdf]

3j0hn 4y ago
This is a little bit apples and oranges, however. An asymptotic bound on the complexity doesn't say a lot about the number of multiplications needed for a fixed value of n=5 say. A lot of those complexity proofs say "for large enough n".
- klyrs 4y ago
  Not so! The 5x5 multiplication can be applied recursively to NxN matrices -- at the top level the "5x5 multiplication" carves the matrix into a 5x5 grid of "blocks" each of size approximately (N/5 x N/5). It's been a while since I've done this sort of complexity analysis, but I found some nice slides here explaining how to use the so-called Master Theorem for recursive algorithms: https://www.inf.ed.ac.uk/teaching/courses/ads/Lects/lecture3-4.pdf https://www.inf.ed.ac.uk/teaching/courses/ads/Lects/lecture3... [pdf]
  - 3j0hn 4y ago
    Oh yeah, great point. Like plugging numbers into the master theorem, if 5x5 could be done in 25 multiplications, say, it would imply multiplication in O(n^2), and even 45 multiplications would give a new asymptotically fast multiplication. I would have to dig out a textbook to figure out what an Omega(n^2 log n) lowerbound would imply for n=5. edit of course wikipedia links to a explicit lowerbound which is kind of useful for small cases. https://www.sciencedirect.com/science/article/pii/S0885064X02000079 https://www.sciencedirect.com/science/article/pii/S0885064X0... has it as 2*n*m+2*n-m-2 which is 53 for m=n=5, which is not super tight, but tight enough to say that no 5x5 formula is ever going to lead to an asymptotically faster MM algorithm.
henrydark 4y ago
that's for real and complex fields, and it's not exactly that. I don't think there's anything better than O(n^2) with no conditions
- klyrs 4y ago
  ah, excellent point
- temporalparts 4y ago
  simple proof that you can't get better than O(n^2) is that you need to produce an n x n matrix with O(n^2) distinct values, so you need at least O(n^2) just to print the result.
  - LinkLink 4y ago
    Not necessarily, assuming two nxn matrices are functionally defined as all 0's printing them takes O(n)
    - dmurray 4y ago
      The problem is defined to be over all (real-valued?) nxn matrices. It's fine if your method uses a representation other than the typical row- normal or column-normal form, but its performance is going to be measured over the worst case.
    - Someone 4y ago
      No, it doesn’t. You still need to produce n² zeroes for the result. If you multiply two n × n matrices, the result isn’t a vector; it’s a n × n matrix.
      - rrobukef 4y ago
        Any reasonable description of the matrix will do. The string "An n by n matrix of all zeroes." can be a good output if correctly defined.

by klyrs 4y ago

3j0hn 4y ago

This is a little bit apples and oranges, however. An asymptotic bound on the complexity doesn't say a lot about the number of multiplications needed for a fixed value of n=5 say. A lot of those complexity proofs say "for large enough n".

klyrs 4y ago
Not so! The 5x5 multiplication can be applied recursively to NxN matrices -- at the top level the "5x5 multiplication" carves the matrix into a 5x5 grid of "blocks" each of size approximately (N/5 x N/5). It's been a while since I've done this sort of complexity analysis, but I found some nice slides here explaining how to use the so-called Master Theorem for recursive algorithms: https://www.inf.ed.ac.uk/teaching/courses/ads/Lects/lecture3-4.pdf https://www.inf.ed.ac.uk/teaching/courses/ads/Lects/lecture3... [pdf]
- 3j0hn 4y ago
  Oh yeah, great point. Like plugging numbers into the master theorem, if 5x5 could be done in 25 multiplications, say, it would imply multiplication in O(n^2), and even 45 multiplications would give a new asymptotically fast multiplication. I would have to dig out a textbook to figure out what an Omega(n^2 log n) lowerbound would imply for n=5. edit of course wikipedia links to a explicit lowerbound which is kind of useful for small cases. https://www.sciencedirect.com/science/article/pii/S0885064X02000079 https://www.sciencedirect.com/science/article/pii/S0885064X0... has it as 2*n*m+2*n-m-2 which is 53 for m=n=5, which is not super tight, but tight enough to say that no 5x5 formula is ever going to lead to an asymptotically faster MM algorithm.

henrydark 4y ago

that's for real and complex fields, and it's not exactly that. I don't think there's anything better than O(n^2) with no conditions

klyrs 4y ago
ah, excellent point
temporalparts 4y ago
simple proof that you can't get better than O(n^2) is that you need to produce an n x n matrix with O(n^2) distinct values, so you need at least O(n^2) just to print the result.
- LinkLink 4y ago
  Not necessarily, assuming two nxn matrices are functionally defined as all 0's printing them takes O(n)
  - dmurray 4y ago
    The problem is defined to be over all (real-valued?) nxn matrices. It's fine if your method uses a representation other than the typical row- normal or column-normal form, but its performance is going to be measured over the worst case.
  - Someone 4y ago
    No, it doesn’t. You still need to produce n² zeroes for the result. If you multiply two n × n matrices, the result isn’t a vector; it’s a n × n matrix.
    - rrobukef 4y ago
      Any reasonable description of the matrix will do. The string "An n by n matrix of all zeroes." can be a good output if correctly defined.