MIT 18 310C - Strassen’s Fast Multiplication of Matrices Algorithm

Unformatted text preview:

25. Strassen’s Fast Multiplication of Matrices Algorithm, and Spreadsheet Matrix Multiplications 1. Introduction Suppose we want to multiply two n by n matrices, A and B. Their product, AB, will be an n by n matrix and will therefore have n2 elements. Each one of these elements is naturally expressed as the sum of n products, each of an element of A with one of B. Thus we have (AB)jk = Ss=1s=n AjsBsk, and the number of multiplications involved in producing the product in this way is n3. In fact, a matrix product of this kind can be obtained using a smaller number of operations, and we will describe how this can be done. We will also discuss some curious spreadsheet algorithms for manipulating matrices. Thus, if we produce the product AB in the usual manner on a spreadsheet with no additional work we can obtain AkB as well, for any k we choose. Also, with one easy instruction, whose entry is similar to applying the formula for computing the determinant of a 2 by 2 matrix (along with some copying), we can compute the determinant of any square matrix A of any size, and even obtain all the cofactors of the elements A, which is what you need to solve a set of n by n equations. 2. Fast Matrix Multiplication; Partitioning Matrices We will describe an algorithm (discovered by V.Strassen) and usually called “Strassen’s Algorithm) that allows us to multiply two n by n matrices A and B, with a number of multiplications (and additions) which is a small multiple of n(ln 7)/(ln 2), when n is of the form 2k. This is like 22.8 instead of 23 The algorithm is based upon three ideas. The first idea is that of “partitioning matrices” which in our context is: The multiplication of 4 by 4 matrices A and B is equivalent to the multiplication of a pair of 2 by 2 matrices whose elements are each 2 by 2 matrices. In a four by four matrix the indices on row or column range from 1 to 4 In a two by two matrix of two by two matrices there are also four indices on row or column but they are called 11, 12, 21 and 22, the first index here representing the index of one 2 by 2 matrix and the second of the other.Forming a matrix product is taking a dot product of row components of one with column components of the other. It does not matter in the slightest how you name the components; with either kind of index you multiply each row component of the first by the corresponding column component of the second. In one case this looks like aj1 * b1k + aj2 * b2k + aj3 * b3k + aj4 * b4k. while with the other names it looks like ajk,11 * b11,st + ajk.12 *b12,st + ajk,21 * b21,st + ajk,22 * b22,st . but who cares? The net result is the same. And as a matter of fact, given n by n matrices A and B for which n is factorable into r and s (n=r*s) you can similarly write them as r by r matrices whose components are each s by s matrices in the same general way without changing the definition of their matrix multiplication at all. Explicitly, in the 4 by 4 case, if we describe A and B as , and Then their matrix product is exactly the same as the product of the matrices and , where we have , , , and . and the same kind of thing for B. Now suppose we have matrices matrices whose dimensions are 2k by 2k. We can represent the indices either as integers from 1 to 2k or as k-tuples, each element of which is 1 or 2. (this is very much like using a binary representation of our indices except that we use 1 instead of 0 and 2 instead of 1 and the all 1’s index here corresponds to 1 while the all 0’s in binary corresponds to 0) And with the latter representation we can interpret matrix multiplication as the 2 by 2 product of 2k-1 by 2k-1 matrices each one of which is a 2 by 2 product of 2k-2 by 2k-2 matrices, and so on. The consequence we draw from this fact is: if we can multiply 2 by 2 matrices using only 7 multiplications instead of the usual 8, we can parlay that into multiplying 4 by 4 matrices using 7 multiplications of 2 by 2 matrices each of which requires 7 multiplications of numbers, for a total of 49 multiplications.Furthermore, by iterating this fact, we can multiply 2k by 2k matrices with 7k multiplications of numbers, so long as we can handle 2 by 2 matrices with 7 multiplications in a way that does not use commutativity. 3. Representing a Matrix Product as a Single Polynomial From now on then we will consider the problem of computing the 4 entries in the product of two 2 by 2 matrices. Explicitly, given 2 by 2 matrices with elements aij and bjk we want to compute the four combinations a11b11 + a12b21, a11b12 + a12b22, a21b11 + a22b21, and a21b12 + a22b22. The second idea here is that we will get a better grasp of the problem if we combine these four combinations into one entity. And we can do this by multiplying each one by an indeterminate (or variable) and adding them up. The result will be a polynomial, and our task will be both to compute this polynomial from the a’s and b’s using 7 multiplications, and to find the coefficients of our marker variables in the polynomial. And here is where we run into amazing luck. If we call our “variables” (or if you prefer “indeterminates”) zkj and multiply the combinations above by z11, z21, z12 and z22 respectively, our polynomial when written out is a11b11z11 + a12b21z11 + a11b12z21 + a12b22z21 + a21b11z12 + a22b21z12 + a21b12z22 + a22b22z22 which is Sj,s,k=12 ajsbskzkj. Our luck is the fact that this polynomial has quite a bit of symmetry. In particular, we can interchange the subscripts 1 and 2 everywhere, and this combination does not change. Which is to say that for each term (for example the first term) there is another which is its image under changing all the indices (here the last term). Second, we can permute the indices j s and k, replacing j by s, s by k and k by j, without changing this polynomial, and we can reverse this permutation. If we perform the first of these two permutations the first and last terms stay fixed, but the term a12b21z11 becomes a21b11z12 (j=1 s=2 k=1 becomes j=2 s=1 k=1) and so on. Thus there is a group of index changes that leave our polynomial unchanged, and this group has the following six elements: The identity; permute (j,s,k); permute (j,k,s); switch 1 and 2; switch 1 and 2 and permute (j,s,k); switch 1 and 2 and permute(j,k,s). The 8 terms in our polynomial form two orbits under the action of this group.One is the pair …


View Full Document

MIT 18 310C - Strassen’s Fast Multiplication of Matrices Algorithm

Download Strassen’s Fast Multiplication of Matrices Algorithm
Our administrator received your request to download this document. We will send you the file to your email shortly.
Loading Unlocking...
Login

Join to view Strassen’s Fast Multiplication of Matrices Algorithm and access 3M+ class-specific study document.

or
We will never post anything without your permission.
Don't have an account?
Sign Up

Join to view Strassen’s Fast Multiplication of Matrices Algorithm 2 2 and access 3M+ class-specific study document.

or

By creating an account you agree to our Privacy Policy and Terms Of Use

Already a member?