Matrix Multiplication

[myk45]

Hello.

For 2D matrix multiplication, i tried a new method, which uses only 2 for loops.
(im basically using a 1D array to access the elements).

Here is the code:

// Mutiplication.cpp : Defines the entry point for the console application.
//

#include <stdio.h>


int main(void)
{
	int a[] = {2, 2, 1, 2};
	int b[] = {2, 2, 2, 1, 1, 1};
	int ans[10] = {0, 0, 0, 0, 0, 0, 0, 0, 0, 0};

	int NoOfColsMat2 = 3; // Number of columns in Matrix2 
	int noOfColsMat1 = 2; // Number of rows in Matrix1 
	int m = -(noOfColsMat1), k = 0; // m and k are used as indices

	for (int p = 0; p < NoOfColsMat2 * noOfColsMat1; p++) {
		k =  p % noOfColsMat1;
		m = ((p % NoOfColsMat2) == 0) ? (m += noOfColsMat1) : (m);

		for (int j = 0; j < noOfColsMat1; j++) {
			ans[p] = ans[p] + (a[m] * b[k]);
			k += NoOfColsMat2;
			m++;
		}
		//Reduce m
		m -= noOfColsMat1;
	}

	for (int i = 0; i < NoOfColsMat2 * noOfColsMat1; i++) {
		printf(i % NoOfColsMat2 ? "" : "\n");
		printf("%d   ", ans[i]);	
	}

	getchar();
	return 0;
}

[B]So basically,
{2, 2, 1, 2} is :
2 2 
1 2 

and 

{2, 2, 2, 1, 1, 1} is :
2 2 2 
1 1 1[/B]

Can anyone please tell me how i can analyze this against the brute force method(of having 2D arrays and 3 for loops).

Thanks in advance.

[drkybelk]

What kind of analysis do you want? You know that you will need 3 loops for arbitrary matrices (unless you use the fast algorithm, which saves on the loops in favour of caching some values and re-ordering the calculations). If you have constant matrix-dimensions then you can hardcode away the loops but that doesn't make your program any faster as you still have to do the same amount of multiplications. If your algorithm genuinely only has two loops then your algorith is wrong, i.e it does not work for arbitrary matrices. Diagonal matrices or other special matrices can be multiplied with less than three loops, but not arbitrary ones.

[myk45]

Thanks for the reply.

You know that you will need 3 loops for arbitrary matrices (unless you use the fast algorithm, which saves on the loops in favour of caching some values and re-ordering the calculations)

Well what i mean to say is, cant this method be used for any 2D matrix multiplication? Since the only thing we need to be sure in Matrix multiplication is

Number of columns in Matrix1 = No of rows in Matrix2;

Well i just used this principle to carry out the calcuation.
i tried another example(actually i needed this in some other task). Here is the link:

........................
http://ideone.com/vIy5P
........................

[arkoenig]

Count the number of floating-point additions and floating-point multiplications in both methods. I'll bet you find that they're the same.

[myk45]

@arkoenig

Yeah! so removing the loop did not help! The number still remains the same.