Counting floating point operations in an algorithm

  • Thread starter JesseJC
  • Start date
  • #1
49
0
Moved from a technical forum, so homework template missing
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!
 

Answers and Replies

  • #2
SteamKing
Staff Emeritus
Science Advisor
Homework Helper
12,796
1,668
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.
 
  • Like
Likes JesseJC
  • #3
136
19
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.
 
  • Like
Likes JesseJC
  • #4
49
0
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.
 
  • #5
49
0
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?
 
  • #6
SteamKing
Staff Emeritus
Science Advisor
Homework Helper
12,796
1,668
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?
 
  • #7
49
0
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."
 
  • #8
Delta2
Homework Helper
Insights Author
Gold Member
3,572
1,380
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)##.
 
  • Like
Likes JesseJC
  • #9
49
0
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
 
  • #10
Delta2
Homework Helper
Insights Author
Gold Member
3,572
1,380
Ok, just did a mistake though, that 2 in the f(k) is actually ##2*10^6## !!!
 
  • #11
49
0
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?
 
  • #12
49
0
This assignment is a real doozy
 
  • #13
SteamKing
Staff Emeritus
Science Advisor
Homework Helper
12,796
1,668
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
 
  • #14
49
0
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
 
  • #15
SteamKing
Staff Emeritus
Science Advisor
Homework Helper
12,796
1,668
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 n3, unless you have two matrices which are very sparse (each contain a lot of zeroes as entries).
 
  • Like
Likes JesseJC
  • #16
49
0
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 n3, 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
 
  • #17
SteamKing
Staff Emeritus
Science Advisor
Homework Helper
12,796
1,668
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 ...
 
  • #18
Delta2
Homework Helper
Insights Author
Gold Member
3,572
1,380
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##..
 

Related Threads on Counting floating point operations in an algorithm

  • Last Post
Replies
1
Views
3K
  • Last Post
Replies
10
Views
4K
  • Last Post
Replies
4
Views
1K
  • Last Post
Replies
20
Views
4K
  • Last Post
Replies
14
Views
2K
  • Last Post
Replies
5
Views
5K
  • Last Post
Replies
13
Views
2K
  • Last Post
Replies
10
Views
2K
  • Last Post
Replies
2
Views
1K
Replies
5
Views
9K
Top