468,738 Members | 2,641 Online
Bytes | Developer Community
New Post

Home Posts Topics Members FAQ

Post your question to a community of 468,738 developers. It's quick & easy.

Fast Multiplication of Three n-x-n matrices

emaghero
Does anybody know an algorithm for the fast multiplication of three n-x-n symmetric matrices?

I have an algorithm, which I'm not too pleased with, that does the job.

Does anybody know a faster method, or even how to improve my algorithm?

My algorithm takes three n-x-n symmetric matrices, A, B, C

It multiplies the first two in the usual way to give a matrix D = A*B.

It then calculates the product D*C and stores the result in A.

I am not happy with this as it takes far too long.

Can anybody speed it up?

The first function is the standard way in which matrix multiplication is performed
Expand|Select|Wrap|Line Numbers
  1. void Matrix_Multiply(double *mat_one,double *mat_two,double *mat_result,double &size)
  2. {
  3.     for(int i=0;i<(int)(size);i++){
  4.         for(int j=0;j<(int)(size);j++){
  5.             for(int k=0;k<(int)(size);k++){
  6.                 *(mat_result+(int)(i*size)+j)+=*(mat_one+(int)(i*size)+k)**(mat_two+(int)(k*size)+j);
  7.             }
  8.         }
  9.     }
  10. }
  11.  
The second function calls the first to perform two matrix multiplications and then stores the result
Expand|Select|Wrap|Line Numbers
  1. void Matrix_Triple_Product(double *mat_one,double *mat_two,double *mat_three,void (*g)(double *,double *,double *,double &),double &size)
  2. {
  3.     double *mat_temp=new(double [(int)(size)*(int)(size)]);//Array to hold the result of the first multiplication
  4.     for(int i=0;i<(int)(size);i++){
  5.         for(int j=0;j<(int)(size);j++){
  6.             *(mat_temp+(int)(i*size)+j)=0.0;
  7.         }
  8.     }
  9.     //Calculate the product of the first two matrices and store the result in mat_temp
  10.     g(mat_one,mat_two,mat_temp,size);
  11.     //Assign the second matrix to zero
  12.     for(int i=0;i<(int)(size);i++){
  13.         for(int j=0;j<(int)(size);j++){
  14.             *(mat_two+(int)(i*size)+j)=0.0;
  15.         }
  16.     }
  17.     //Calculate the product of mat_temp and the third matrix and store the result in the second matrix
  18.     g(mat_temp,mat_three,mat_two,size);
  19.  
  20.     cout<<"The matrix product has been computed and is stored in memory\n";
  21.  
  22.     delete[] mat_temp;
  23.  
  24. }
  25.  
Nov 23 '06 #1
1 4312
Try Strassen Algorithm for fast matrix multiplication
Nov 28 '06 #2

Post your reply

Sign in to post your reply or Sign up for a free account.

Similar topics

9 posts views Thread by Ralf Hildebrandt | last post: by
14 posts views Thread by amitnanda | last post: by
7 posts views Thread by VijaKhara | last post: by
3 posts views Thread by matheen | last post: by
3 posts views Thread by crazygrey | last post: by
1 post views Thread by glitchized | last post: by
1 post views Thread by Sozos | last post: by
By using this site, you agree to our Privacy Policy and Terms of Use.