Matrices multiplication algorithm

[j.gohel]

I have just started learning Algorithms.

And i have got stucked at on point.
Actually in the book which i am referring there is an exercise of
multiplying 2 matrices i.e one matrix is (m by n) length and another matrix is (n by p) length

Algorithm :

for(variable i := 1 to m) {
for(variable j := 1 to p) {
for(variable k := 1 to n) {
... here the resultant matrix is built
}
}
}


Now the first question was to find out the time complexity which is as follows:
Starting from top,
the first outermost loop will execute m times,
the second outermost loop will execute m*p times, and the innermost loop will execute m*p*n times.

The second question is : Under what conditions is it profitable to interchange the two outermost loops?
I am stuck at this question.
As far as execution time is considered, interchanging the loops won't make any difference, as per me.
So if i am correct then is there anything else which can make the algorithm efficient by interchanging the two outermost loops ?

Hope i will get my problem's solution.

Thanks in advance.

[msg555]

You are correct in thinking that changing the outermost loops alone wouldn't do anything. The only real case I can think of is when p is 0 (which seems silly). Perhaps there is some sort of optimization where you could cut the loop early by swapping the iteration order.

[j.gohel]

Perhaps there is some sort of optimization where you could cut the loop early by swapping the iteration order.

Sorry but didn't get you.

Thanks.

[pm_kirkham]

Depending on the representation of your matrices, you get better cache performance (by orders of magnitude for large matrices) depending on whether you iterate over the rows or columns. Since the default representation of multidimensional arrays in C is the opposite to that of Fortran, many ports of older algorithms get the rows and columns 'the wrong way'.

For simple multiplication, you need to iterate one matrix in row order and the other in column order, so you may want to iterate whichever is more contiguous in the second loop, though I'd have to go through the math to be sure. Some systems, where memory is cheap, store transpose as well as default representation, to make the memory accesses contiguous for both matrix.

[answer]

I think when P < M swap the 2 outer most loops order. Since it takes time to compare if the iterating variable has reached its destination.


for(variable i := 1 to m) { // is is compared to m, m times
for(variable j := 1 to p) { // j is compared to p p*m times
for(variable k := 1 to n) {
... here the resultant matrix is built
}
}
}


Total comparisons with respect to outer loops = p*m + m

Comparisons = p*m + m
if swapped
Comparisons' = p*m + p
Comparisons - Comparisons' = m - p = D

So if P > M then D < 0 Comparisons is faster.
if P < M then D > 0 & Comparisons' is faster

So for least amount of comparing (ie is i == m?) the outer most loop has to be smaller than the inner most loop.

This is the best I can think of.

I remember timing a binary search on 100 000 values. And comparing variables does have a significant impact on the time it takes with such large values. Though its not too significant and I don't think anyone will care.