1. Limited time only! Sign up for a free 30min personal tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Counting floating point operations in an algorithm

  1. Jun 8, 2016 #1
    • 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!
     
  2. jcsd
  3. Jun 8, 2016 #2

    SteamKing

    User Avatar
    Staff Emeritus
    Science Advisor
    Homework Helper

    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.
     
  4. Jun 8, 2016 #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.
     
  5. Jun 8, 2016 #4
    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.
     
  6. Jun 8, 2016 #5
    Any advice on avoiding the subroutines?
     
  7. Jun 8, 2016 #6

    SteamKing

    User Avatar
    Staff Emeritus
    Science Advisor
    Homework Helper

    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?
     
  8. Jun 8, 2016 #7
    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."
     
  9. Jun 8, 2016 #8

    Delta²

    User Avatar
    Gold Member

    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)##.
     
  10. Jun 8, 2016 #9
    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
     
  11. Jun 8, 2016 #10

    Delta²

    User Avatar
    Gold Member

    Ok, just did a mistake though, that 2 in the f(k) is actually ##2*10^6## !!!
     
  12. Jun 8, 2016 #11
    How would you suppose I go about counting the number of flops for a 1000x1000 matrix multiplication?
     
  13. Jun 8, 2016 #12
    This assignment is a real doozy
     
  14. Jun 8, 2016 #13

    SteamKing

    User Avatar
    Staff Emeritus
    Science Advisor
    Homework Helper

    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
     
  15. Jun 8, 2016 #14
    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
     
  16. Jun 8, 2016 #15

    SteamKing

    User Avatar
    Staff Emeritus
    Science Advisor
    Homework Helper

    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).
     
  17. Jun 8, 2016 #16
    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
     
  18. Jun 8, 2016 #17

    SteamKing

    User Avatar
    Staff Emeritus
    Science Advisor
    Homework Helper

    Be sure to double check this calculation against the paper I linked to. I could be off ...
     
  19. Jun 8, 2016 #18

    Delta²

    User Avatar
    Gold Member

    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##..
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?
Draft saved Draft deleted



Similar Discussions: Counting floating point operations in an algorithm
  1. Floating point format (Replies: 1)

Loading...