Category: Knowledge Building

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.

[Todo: formulas to be done in Latex.]

[Last update: 2016-01-05]

In the next few posts, I would like to talk about five courses that I took in 2015Fall semester, including Data mining, Machine learning, Mathematical Optimization, Electrical Power Systems and Algorithms. This is going to be a summary of what I learnt during the semester (and also a preparation for my coming exams), which could be interesting and challenging for me.

The first topic of this series is from the course Data mining – Learning from Large Data Sets [Prof. Krause, 263-5200-00L]. This post is going to cover three lectures of the course (Lecture 11,12,13). The relative codes are going to be published on Github.