:: simple question arising from matrix multiplications

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?

zerocold

Advertisements

Like this:

LikeLoading...

Related

This entry was posted on Tuesday, October 14th, 2008 at 8:44 pm and is filed under Uncategorized. You can follow any responses to this entry through the RSS 2.0 feed.
You can leave a response, or trackback from your own site.

2 Responses to :: simple question arising from matrix multiplications

Hello webmaster

I would like to share with you a link to your site

write me here preonrelt@mail.ru