4 ms·

I'm really interested to know when we will be able to prove that we have the fastest algorithm for some matrix multiplication problem. Is there a theoretical lo

by ajkjk 4y ago

I'm really interested to know when we will be able to prove that we have the fastest algorithm for some matrix multiplication problem. Is there a theoretical lower bound? (well in this case, for 5x5, there's gonna be an actual lower bound. but for asymptotic cases..?) Is figuring out the theoretical lower bound some kind of undecidable/NP problem? what do we know about it?

ithinkso 4y ago
I think there is some educated-believe that it can be done in n^(2+epsilon) but not in n^2. No proof yet ofcourse
genpfault 4y ago
https://en.wikipedia.org/wiki/Computational_complexity_of_matrix_multiplication#Lower_bounds_for_%CF%89 https://en.wikipedia.org/wiki/Computational_complexity_of_ma...
imbusy111 4y ago
Obviously a lower bound is O(N*M), but it's not very useful. But I'm not aware of any tighter lower bound.
deleted 4y ago
[deleted]
deleted 4y ago
[deleted]
deleted 4y ago
[deleted]
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

by ajkjk 4y ago

ithinkso 4y ago

I think there is some educated-believe that it can be done in n^(2+epsilon) but not in n^2. No proof yet ofcourse

genpfault 4y ago

https://en.wikipedia.org/wiki/Computational_complexity_of_matrix_multiplication#Lower_bounds_for_%CF%89 https://en.wikipedia.org/wiki/Computational_complexity_of_ma...

imbusy111 4y ago

Obviously a lower bound is O(N*M), but it's not very useful. But I'm not aware of any tighter lower bound.

deleted 4y ago

[deleted]

deleted 4y ago

[deleted]

deleted 4y ago

[deleted]

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