via the great marcoscan
The new bulletin of the AMS is you with a not so simple paper about matrices multiplication.
Ok maybe the two or three of you who’s reading this blog will problably know the standard algorithm to multiply two matrices let say A and B are 2×2 matrices in R you need to compute 8 multiplication two find the result matrix. Ok that was not so difficult, in fact for a nxn matrix you will need n^3 multiplication to computer the result. The hard part for a pc in term of complexity is the product so if whe minimize the product it is possible to minimize the cost of elaboration by a computer. In 1969 Strassen proced that with a tricky observation it is possible to computer the product of a 2×2 matrices with only 7 product.It seems not a big result but this with appropriate generalization could lead to compute the product of a 2^k x 2^k matrices with 7^k multiplications in place of (2^k)^3 standard multiplication. This means that for a 32×32 matrix (k=5) this will lead to 7^5=16807 multiplications instead of 32^3=32768, which is as least the half.
I have to try a python test to verify that is at least the half in terms of times. In fact I haven’t finish the paper but one simple question arise: is it possible to find an algorithm for a 2×2 matrices multiplications that use only 6 multiplications?
ok I partecipate with lot of plajure at beppe grillo’s on-line referendum
The DARPA (the one wich will build skynet) has put on-line a 23 toughest math problem list.
Some are really difficult and young mathematicians are facing with this here’s the link