:: 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?



2 Responses to :: simple question arising from matrix multiplications

  1. Alexwebmaster says:

    Hello webmaster
    I would like to share with you a link to your site
    write me here preonrelt@mail.ru

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )


Connecting to %s

%d bloggers like this: