Counting floating point operations in an algorithm

[JesseJC]

Hey guys, another question regarding MatLab here. In this assignment, I need to create a function of 'k' to count the number of floating point operations in the algorithm that I've made.

Here is my code so far:
expAk = zeros(1000, 1000);

load('CA3matrix.mat');

times = zeros(15, 1);

for j = 10:10:150

tic;

for k = 0:j

expAk = expAk + (A^k)/(factorial(k));

end

times(j/10) = toc;

end

plot(10:10:150, times);

figure()

imagesc(real(expAk));

colormap gray

I've bolded my algorithm. So our instructor told us to load the file 'CA3matrix' and do sort of an exponential series on it. I am trying to understand how I can count the number of flops for all of the runs, could I do this by hand? Is there an easy function to use? Can I create my own function? Any input would be great, thanks!

 

[SteamKing]

Hey guys, another question regarding MatLab here. In this assignment, I need to create a function of 'k' to count the number of floating point operations in the algorithm that I've made.

Here is my code so far:
expAk = zeros(1000, 1000);

load('CA3matrix.mat');

times = zeros(15, 1);

for j = 10:10:150

tic;

for k = 0:j

expAk = expAk + (A^k)/(factorial(k));

end

times(j/10) = toc;

end

plot(10:10:150, times);

figure()

imagesc(real(expAk));

colormap gray

I've bolded my algorithm. So our instructor told us to load the file 'CA3matrix' and do sort of an exponential series on it. I am trying to understand how I can count the number of flops for all of the runs, could I do this by hand? Is there an easy function to use? Can I create my own function? Any input would be great, thanks!

When posting code like this, put the code between a pair of [#CODE] [#/CODE] tags (omitting the #) for better legibility. This will preserve any indenting or spacing which might further clarify your code.

Without knowing much about Matlab, it seems your code above makes calls to separate subroutines, like zeros ( ) or factorial ( ). Without knowing how many FP operations each of these calls takes to execute, it is difficult, if not impossible, to tabulate how many FP ops this routine as a whole will take to execute.

If you had a routine which consisted of straight code with no other subroutine calls, you could set up and initialize a FP Op counter, and after each statement is executed, increment this FP Op counter by the number of FP ops it took to calculate.

 

[eachus]

There are two interesting answers here. The first is that for small values of k, if A is an integer array, this may be an exact integer function. (Depends on the determinant of A.) Is MATLAB evaluating it that way? Second, if you are in a regime where the value is approximated by a floating point result, there are known shortcuts for evaluating A^k and k! Is Matlab using those shortcuts behind your back? If I was writing this in a procedural language, and instructed not to use a bignum package, the shortcuts are simple enough that I would use about a dozen lines of code to reduce the computation time from O(k^k) to O(k). I would also use a bignum package if A was an integer matrix. I guess your job is to find out how MATLAB does at optimizing the evaluation.

 

[JesseJC]

There are two interesting answers here. The first is that for small values of k, if A is an integer array, this may be an exact integer function. (Depends on the determinant of A.) Is MATLAB evaluating it that way? Second, if you are in a regime where the value is approximated by a floating point result, there are known shortcuts for evaluating A^k and k! Is Matlab using those shortcuts behind your back? If I was writing this in a procedural language, and instructed not to use a bignum package, the shortcuts are simple enough that I would use about a dozen lines of code to reduce the computation time from O(k^k) to O(k). I would also use a bignum package if A was an integer matrix. I guess your job is to find out how MATLAB does at optimizing the evaluation.

I believe MATLAB is evaluating it that way, so it may be pretty simple. I'm intrigued with the shortcuts for both A^k and k!, I'm entirely new to MatLab so I'm unsure of how to find these. It would be really nice to find out what they were, since running my program now takes around 10 minutes for k = 150.

 

[JesseJC]

When posting code like this, put the code between a pair of [#CODE] [#/CODE] tags (omitting the #) for better legibility. This will preserve any indenting or spacing which might further clarify your code.

Without knowing much about Matlab, it seems your code above makes calls to separate subroutines, like zeros ( ) or factorial ( ). Without knowing how many FP operations each of these calls takes to execute, it is difficult, if not impossible, to tabulate how many FP ops this routine as a whole will take to execute.

If you had a routine which consisted of straight code with no other subroutine calls, you could set up and initialize a FP Op counter, and after each statement is executed, increment this FP Op counter by the number of FP ops it took to calculate.

Any advice on avoiding the subroutines?

 

[SteamKing]

Any advice on avoiding the subroutines?

Well, subroutines like factorial ( ) can always be replaced with another loop. Without knowing what the subroutine zeros ( ) does exactly, it's harder to say.

Are you wanting to know the number of FLOPs your code takes just out of curiosity, or is it part of an assigned task?

 

[JesseJC]

Well, subroutines like factorial ( ) can always be replaced with another loop. Without knowing what the subroutine zeros ( ) does exactly, it's harder to say.

Are you wanting to know the number of FLOPs your code takes just out of curiosity, or is it part of an assigned task?

Here is an excerpt from the assignment:

"Run your algorithm for k = 10, 20, 30, . . . , 150 and use the tic and toc commands (recall the in-class demo TicToc.m) to plot the computational time versus k. How does the computational time appear to depend on k? Does this agree with what you would expect from counting the number of flops in your algorithm? Explain."

 

[Delta2]

I guess your teacher is interested in the number of flops executed by the k-loop that contains the bolded line of code.
Each execution of the bolded line does 1 addition+1 division + k-1 matrix multiplications (you don't tell us what matrix A is) and k-1 integer multiplications (for k!). So the number of flops for one execution of the bolded line (while we are at the value k) is (if $\alpha$ is the number of flops for 1 matrix multiplication of the matrix A):
$f(k)=2+(k-1)(\alpha+1)$

and the total number of flops is

$\sum\limits_{k=0}^{j}f(k)$.

 

[JesseJC]

I guess your teacher is interested in the number of flops executed by the k-loop that contains the bolded line of code.
Each execution of the bolded line does 1 addition+1 division + k-1 matrix multiplications (you don't tell us what matrix A is) and k-1 integer multiplications (for k!). So the number of flops for one execution of the bolded line (while we are at the value k) is (if $\alpha$ is the number of flops for 1 matrix multiplication of the matrix A):
$f(k)=2+(k-1)(\alpha+1)$

and the total number of flops is

$\sum\limits_{k=0}^{j}f(k)$.

A is a thousand-by-thousand matrix that was provided to us by our instructor for download. What you just told me, I think, confirmed what I was going to try and do. Thank you

 

[Delta2]

Ok, just did a mistake though, that 2 in the f(k) is actually $2*10^6$ !

 

[JesseJC]

Ok, just did a mistake though, that 2 in the f(k) is actually $2*10^6$ !

How would you suppose I go about counting the number of flops for a 1000x1000 matrix multiplication?

 

[JesseJC]

This assignment is a real doozy

 

[SteamKing]

How would you suppose I go about counting the number of flops for a 1000x1000 matrix multiplication?

The number of FLOPS for certain calculations can be determined a priori, given the structure of the calculation. Matrix multiplication is one of those calculations, since it involves forming a certain number of inner products for each entry in the product matrix.

This article explains how to calculate the number of FLOPS for a general matrix multiplication:

http://cavern.uark.edu/~arnold/4353/Flops.pdf

 

[JesseJC]

The number of FLOPS for certain calculations can be determined a priori, given the structure of the calculation. Matrix multiplication is one of those calculations, since it involves forming a certain number of inner products for each entry in the product matrix.

This article explains how to calculate the number of FLOPS for a general matrix multiplication:

http://cavern.uark.edu/~arnold/4353/Flops.pdf

Yes, I did a few small nxn matrices and came up with n + 1 flops, hopefully your link confirms it.

Edit: Great, I was wrong haha

 

[SteamKing]

Yes, I did a few small nxn matrices and came up with n + 1 flops, hopefully your link confirms it.

I'm not sure how you came up with that result, since you typically form one inner product for each entry in a fully-populated matrix multiplication. The number of FLOPS is generally on the order of n³, unless you have two matrices which are very sparse (each contain a lot of zeroes as entries).

 

[JesseJC]

I'm not sure how you came up with that result, since you typically form one inner product for each entry in a fully-populated matrix multiplication. The number of FLOPS is generally on the order of n³, unless you have two matrices which are very sparse (each contain a lot of zeroes as entries).

I jumped to conclusions too quickly, that's interesting that it's n^3, I don't think I could have ever gotten that through trying with pen and paper. You guys have been a great help

 

[SteamKing]

I jumped to conclusions too quickly, that's interesting that it's n^3, I don't think I could have ever gotten that through trying with pen and paper. You guys have been a great help

Be sure to double check this calculation against the paper I linked to. I could be off ...

 

[Delta2]

Just to say that in your problem n^3 is actually considered a constant (if I understand correctly the size of the matrix is considered constant and we are interested how the number of flops varies for different values of j), though a big one $10^9$..