# The fastest way to multiply 2D matrices

I read in the article about the machine learning interview, there is a question:

"To multiply 2 matrices with the shape 10000x10000. How to speed up the calculation?"

The candidate said: "Multi-thread", but the interviewer told that there was another way to do that, the mathematics way.

Can someone give me a solution? Is it related to "eigenvalue"?

• I don't know what "the interviewer" could possibly mean, but I think it is not possible to answer this question without access to the article and interview. Oct 28, 2020 at 5:22
• @JackozeeHakkiuz I believe he wants another way except for the normal way, multiply row with column and sum to get one element, and so on, we will need to do $10^{10}$ calculations, is there any better way? Oct 28, 2020 at 6:02
• What do you mean by the "dot product" of two matrices? Oct 28, 2020 at 6:15
• @littleO I mean like this, should I change it to "multiply"? Oct 28, 2020 at 7:15
• They could mean using something like the Strassen algorithm to multiply faster than the naive $O(n^3)$ method. Oct 28, 2020 at 7:46

The question was not fair, because if you don't know the answer it is hard to guess. Most probably, the interviewer was referring to the fast(er) multiplication method of Strassen and similar. https://en.wikipedia.org/wiki/Strassen_algorithm#:~:text=In%20linear%20algebra%2C%20the%20Strassen,algorithms%20for%20extremely%20large%20matrices.

The basic idea is that if you decompose both matrices each in four blocks, you can perform the product in 7 block multiplies instead of the expected 8. And by applying this principle recursively, you break the $$O(n^3)$$ barrier.

But I fail to see how this belongs to machine learning.

• thank you for that information, I also see the author mention to something else even faster. In machine learning, the features normally are presented as vectors, then multiply it with a weight matrix, so linear algebra knowledge is really important in this field. Oct 28, 2020 at 12:06
• @Toby: understanding linear algebra is indeed useful. How it is implemented is secondary (and in any case readily available in freeware).
– user65203
Oct 28, 2020 at 12:48
• Yes, but I think in this case, the interviewer just wants to check the knowledge of linear algebra of the candidate. For further information, this question is from the interview for a PhD position. Oct 28, 2020 at 12:58
• @Toby: ah, that's different. The interviewer could have asked the proof then ;-)
– user65203
Oct 28, 2020 at 13:00
• might be worth mentioning: some of the faster (i.e. best $O(\cdot)$ bound) known multiplication methods are "galactic algorithms", i.e. the implicit constant hidden in the $O(\cdot)$ notation is so large that the algorithm can't be used in practice, even in machine learning Oct 29, 2020 at 6:32