468,738 Members | 2,641 Online

# Fast Multiplication of Three n-x-n matrices 85
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 vpawizard
66 Try Strassen Algorithm for fast matrix multiplication
Nov 28 '06 #2