How to Write Fast Numerical Code 263-2300 (ETH, CS)
Prof. Markus Püschel
https://www.inf.ethz.ch/personal/markusp/teaching/263-2300-ETH-spring16/course.html
//As a quick review before HW1
Lecture 0
Skip.
Lecture 1
O-notation…. Asymptotic analysis…//Skip
- Is asymptotic analysis still valid given this?
All algorithms are O(n^3) when counting flops.
>Memory accesses into account? OK
>vectorization/parallelization into account? More parameters needed. E.g. O(n^3/p) on p processors(parallelization)
In sum, Asymptotic analysis has its limitations, constants matters. E.g. 10000000000n is likely worse than n^2.
- Cost analysis for Numerical Problems
Goal: determine exact “cost” of an algorithm
cost = number of relevant operations
C(n) = (adds(n), mults(n)) or (adds(n), mults(n), divs(n)) or flops(n)
Here we focus on floating points operations.