2 Replies - 3741 Views - Last Post: 05 August 2012 - 11:31 PM

#1 Manbearpig101  Icon User is offline

  • D.I.C Head
  • member icon

Reputation: 15
  • View blog
  • Posts: 62
  • Joined: 17-June 10

Matrix Multiplication

Posted 05 August 2012 - 03:31 PM

Currently I have two implementations of matrix multiplication algorithms, the standard Divide and Conquer approach, and Strassen's Algorithm. With both of these approaches, I partition the matrices into their submatrices with a function that takes O(n^2) time. Although there are only a constant amount of partitions, it still creates a large amount of overhead. What type of changes to the algorithms would I have to make, to allow for constant time partitioning?

Thanks.

Is This A Good Question/Topic? 0
  • +

Replies To: Matrix Multiplication

#2 Skydiver  Icon User is online

  • Code herder
  • member icon

Reputation: 3163
  • View blog
  • Posts: 9,554
  • Joined: 05-May 12

Re: Matrix Multiplication

Posted 05 August 2012 - 09:14 PM

Can you be a bit more explicit about "it still creates large amounts of overhead"?

I don't see the partitioning as particularly expensive if you make the matrices square matrices that are powers of 2. Each recursive level down is simply quartering the matrices.

I've only learned about Strassen's algorithm a few hours ago after you mentioned it. Never really learned about it in school. I can't really comment with in depth knowledge about the overhead for the operations needed to implement the algorithm.

If I were to implement it, though, as I was taking a quick skim over, I already noticed that M1-M7 don't need to co-exist all at the same time. So technically, I only pay the price of allocating space for M1 and keep recycling the space within that recursion level. Basically in pseudo code:
Compute M1 and store into M.
C11 += M
C22 += M
Compute M2 and store into M.
C21 += M
C22 -= M
Compute M3 and store into M.
C12 += M
C22 += M
Compute M4 and store into M.
C11 += M
C21 += M
Compute M5 and store into M.
C11 -= M
C12 += M
Compute M6 and store into M.
C22 += M
Compute M7 and store into M.
C11 += M 



If I was being really cheap, I'd just allocate space for M to be as big as the largest quadrant, and just keep using the same space as a scratch pad for each recursion level.

For "divide and conquer", the extra overheard I'm seeing is for the intermediate results of the products:
C11 = A11*B11 + A12*B21


I was thinking though, instead of the standard implementation where it would look like:
M1 = A11*B11
M2 = A12*B21
C11 = M1 + M2


That this could be changed into:
MultiplyAndAddSumInto(A11, B11, C11);
:
MultiplyAndAddSumInto(a[][], b[][], c[][])
{
    for(int i = 0; i < a.RowCounts; i++)
        for(int j = 0; j < b.ColumnCount; j++)
            for(int k = 0; k < a.ColumnCount; k++)
                c[i][j] += a[i][k] * b[k][j];
}


Basically get rid of intermediate arrays M1 and M2 and put the values directly into the target array.

Edit after:
And I completely forgot what I was going to write in the first place before I got sidetrack with these partial space optimizations. When partitioning A and B, there is no real need to create brand new smaller matrices and copying values out of them. It is possible to just remember the top left corner and size of a "child" matrix to be used by other operations. Yes the code maybe ugly, but since you're primary concern is efficiency, you'll save a lot of CPU time not allocation space copying stuff around and deallocating it.

This post has been edited by Skydiver: 05 August 2012 - 09:25 PM

Was This Post Helpful? 0
  • +
  • -

#3 Manbearpig101  Icon User is offline

  • D.I.C Head
  • member icon

Reputation: 15
  • View blog
  • Posts: 62
  • Joined: 17-June 10

Re: Matrix Multiplication

Posted 05 August 2012 - 11:31 PM

View PostSkydiver, on 05 August 2012 - 09:14 PM, said:

Can you be a bit more explicit about "it still creates large amounts of overhead"?

I don't see the partitioning as particularly expensive if you make the matrices square matrices that are powers of 2. Each recursive level down is simply quartering the matrices.

I've only learned about Strassen's algorithm a few hours ago after you mentioned it. Never really learned about it in school. I can't really comment with in depth knowledge about the overhead for the operations needed to implement the algorithm.

If I were to implement it, though, as I was taking a quick skim over, I already noticed that M1-M7 don't need to co-exist all at the same time. So technically, I only pay the price of allocating space for M1 and keep recycling the space within that recursion level. Basically in pseudo code:
Compute M1 and store into M.
C11 += M
C22 += M
Compute M2 and store into M.
C21 += M
C22 -= M
Compute M3 and store into M.
C12 += M
C22 += M
Compute M4 and store into M.
C11 += M
C21 += M
Compute M5 and store into M.
C11 -= M
C12 += M
Compute M6 and store into M.
C22 += M
Compute M7 and store into M.
C11 += M 



If I was being really cheap, I'd just allocate space for M to be as big as the largest quadrant, and just keep using the same space as a scratch pad for each recursion level.

For "divide and conquer", the extra overheard I'm seeing is for the intermediate results of the products:
C11 = A11*B11 + A12*B21


I was thinking though, instead of the standard implementation where it would look like:
M1 = A11*B11
M2 = A12*B21
C11 = M1 + M2


That this could be changed into:
MultiplyAndAddSumInto(A11, B11, C11);
:
MultiplyAndAddSumInto(a[][], b[][], c[][])
{
    for(int i = 0; i < a.RowCounts; i++)
        for(int j = 0; j < b.ColumnCount; j++)
            for(int k = 0; k < a.ColumnCount; k++)
                c[i][j] += a[i][k] * b[k][j];
}


Basically get rid of intermediate arrays M1 and M2 and put the values directly into the target array.

Edit after:
And I completely forgot what I was going to write in the first place before I got sidetrack with these partial space optimizations. When partitioning A and B, there is no real need to create brand new smaller matrices and copying values out of them. It is possible to just remember the top left corner and size of a "child" matrix to be used by other operations. Yes the code maybe ugly, but since you're primary concern is efficiency, you'll save a lot of CPU time not allocation space copying stuff around and deallocating it.



I wanted to do what you said in your edit, namely using indices and the sizes, but I'm not sure how I would actually do it. I'm just going to try and work this out by hand, thanks for the input!
Was This Post Helpful? 0
  • +
  • -

Page 1 of 1