Counting floating point operations in an algorithm

In summary, the conversation discusses a question about creating a function in MatLab to count the number of floating point operations in an algorithm. The code provided includes calls to subroutines, making it difficult to accurately determine the number of FLOPs. The participants also discuss the possibility of using shortcuts for evaluating certain operations to optimize computation time. The conversation ends with the question of how to avoid using subroutines in the code.
  • #1
JesseJC
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!
 
Physics news on Phys.org
  • #2
JesseJC said:
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
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
eachus said:
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
SteamKing said:
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
JesseJC said:
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
SteamKing said:
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
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
Delta² said:
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
Ok, just did a mistake though, that 2 in the f(k) is actually ##2*10^6## !
 
  • #11
Delta² said:
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
This assignment is a real doozy
 
  • #13
JesseJC said:
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
SteamKing said:
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
JesseJC said:
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
SteamKing said:
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
JesseJC said:
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
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##..
 

What are floating point operations?

Floating point operations are mathematical operations, such as addition, subtraction, multiplication, and division, that are performed on floating point numbers. These numbers are represented in a computer by a decimal point and can have both whole numbers and fractions.

Why is it important to count floating point operations in an algorithm?

Counting floating point operations helps to determine the complexity and efficiency of an algorithm. By knowing the number of operations, we can compare different algorithms and choose the most efficient one for a specific task.

How do you count floating point operations in an algorithm?

To count floating point operations in an algorithm, we first need to identify the mathematical operations that are being performed. Then, we can count the number of times each operation is used and calculate the total number of operations.

Can counting floating point operations help improve the performance of an algorithm?

Yes, counting floating point operations can help improve the performance of an algorithm. By minimizing the number of operations, we can reduce the time and resources needed to execute the algorithm.

Are there any limitations to counting floating point operations in an algorithm?

Yes, there are some limitations to counting floating point operations in an algorithm. This method does not take into account other factors that may affect the performance of an algorithm, such as the data type used or the efficiency of the implementation.

Similar threads

  • Engineering and Comp Sci Homework Help
Replies
7
Views
876
  • Programming and Computer Science
Replies
30
Views
4K
Replies
9
Views
1K
  • Programming and Computer Science
Replies
5
Views
1K
  • Programming and Computer Science
Replies
2
Views
888
  • Engineering and Comp Sci Homework Help
Replies
1
Views
949
  • Advanced Physics Homework Help
Replies
1
Views
1K
  • Programming and Computer Science
Replies
13
Views
3K
  • MATLAB, Maple, Mathematica, LaTeX
Replies
2
Views
1K
  • Atomic and Condensed Matter
Replies
3
Views
844
Back
Top