Google Answers Logo
View Question
 
Q: strassen's theorem ( Answered,   0 Comments )
Question  
Subject: strassen's theorem
Category: Computers > Algorithms
Asked by: nerd17-ga
List Price: $9.50
Posted: 30 Oct 2003 08:51 PST
Expires: 29 Nov 2003 08:51 PST
Question ID: 271148
How would you modify Strassen's theorem of multiplying (n x n)
matrices where n is a power of 2 to accomodate arbitrary choices of
(positive integers) n so that the algorithm still has a running time
of Theta(n^lg(7))?
Answer  
Subject: Re: strassen's theorem
Answered By: mathtalk-ga on 30 Oct 2003 10:07 PST
 
Hi, nerd17-ga:

If N is the least power of 2 greater than or equal to n, extend the (n
x n) matrices to (N x N) matrices by extending the diagonal with an
(N-n) by (N-n) identity block and elsewhere zeros.  The (N x N)
product of the extended matrics is then the corresponding extension of
the (n x n) product of the two original matrices, and (if one wishes
to be careful about it) introducing and removing the extra entries is
an O(n^2) operation.

Now the original Strassen algorithm handles the multiplication of two
(N x N) matrices in (according to Strassen's theorem) a running time
of Theta(N^lg(7)).

But n <= N < 2n, so:

n^lg(7) <= N^lg(7) < (2^lg(7))*(n^lg(7) = 7(n^lg(7))

Thus Theta(N^lg(7)) is the same as Theta(n^lg(7)) by virtue of this
pair of upper and lower bounds.  Because lg(7) > 2, the extra O(n^2)
operations involved in constructing those extensions doesn't change
the dominate term in the "running time".

Please let me know if any part of my answer requires further
clarification.

regards, mathtalk-ga

Request for Answer Clarification by nerd17-ga on 30 Oct 2003 11:36 PST
it's been a while and my matrix theory is quite hazy, so i apologize
if this sounds elementary, but when you say you have to extend the
diagonal with an (N-n) by (N-n) identity block and elsewhere zeros,
i'm not entirely sure what you mean... say you have the following 3 x
3 matrix:

a b c
d e f
g h i

are you saying to extend it like so:

a b c 0
d e f 0
g h i 0
0 0 0 0

or am i missing something (like a 1 at the bottom right)?

Clarification of Answer by mathtalk-ga on 30 Oct 2003 12:25 PST
Hi, nerd17-ga:

I was thinking about putting 1's on the diagonal, but now I think your
suggestion will work just as well and is simpler (since one adds only
zeros).

Suppose we want to multiply:

a b c       r s t
d e f  and  u v w
g h i       x y z

Then one may "border" each with zeros:

a b c 0
d e f 0
g h i 0
0 0 0 0 

  and

r s t 0
u v w 0
x y z 0
0 0 0 0

The product of these bordered-with-zeros matrices works out to be the
same as bordering with zeros the product of the original matrices. 
One way to think about this is to write the matrix multiplication in
block form.

Let A,B be the original matrices, and let these be "bordered" with
blocks of arbitrary (but compatible) dimensions:

A 0  and  B 0
0 0       0 0

Now "block multipication" (which is used extensively in the proof of
Strassen's theorem) says we can write the extended product like this:

(AB+00) (A0+00)
(0B+00) (00+00)

which of course simplifies to:

AB  0
 0  0

[I've omitted the dirty details of showing you that all the dimensions
of these blocks, the nxn, the (N-n)xn, the nx(N-n), and the
(N-n)x(N-n), all match up just as they need to in order for the
resulting formula to make sense.  Left to the reader!]

In some contexts there might be an advantage to using 1's on the
diagonal (it would preserve the singularity/nonsingularity of the
matrix), but we're doing multiplication here (not "division"), so the
zeros are a good idea.

regards, mathtalk-ga

Clarification of Answer by mathtalk-ga on 31 Oct 2003 06:51 PST
By contrast, if we use 1's on the diagonal as I originally suggested,
then:

A 0         B 0         AB  0
0 I  times  0 I  equals  0  I

Either way, one easily recovers the original (n x n) product AB from
the product of the "extended" (N x N) matrices, and the computational
complexity is the same.

regards, mathtalk-ga
Comments  
There are no comments at this time.

Important Disclaimer: Answers and comments provided on Google Answers are general information, and are not intended to substitute for informed professional medical, psychiatric, psychological, tax, legal, investment, accounting, or other professional advice. Google does not endorse, and expressly disclaims liability for any product, manufacturer, distributor, service or service provider mentioned or any opinion expressed in answers or comments. Please read carefully the Google Answers Terms of Service.

If you feel that you have found inappropriate content, please let us know by emailing us at answers-support@google.com with the question ID listed above. Thank you.
Search Google Answers for
Google Answers  


Google Home - Answers FAQ - Terms of Service - Privacy Policy