Daniel306/stat440 — pull request #2 by kousu (2014-03-20 07:24:17+00:00)
Title: Sync #1: Timings

I've been prototyping the algorithm Lysy gave us in NIW.R. I've got an automatic timing+marginals plotter
(_The marginals make me suspicious that I've done something wrong, but that might just be numerical instability_). The last commit in this PR also logs the timings I'm getting:
```
Starting test runs
------------------
Beginning rNIW.extremelynaive ...
Runtime for rNIW.extremelynaive :
user system elapsed
12.566 0.013 12.611

Beginning rNIW.naive ...
Runtime for rNIW.naive :
user system elapsed
8.743 0.000 8.758

Beginning rNIW.snappy1 ...
Runtime for rNIW.snappy1 :
user system elapsed
5.340 0.007 5.357

Beginning rNIW.snappy2 ...
Runtime for rNIW.snappy2 :
user system elapsed
4.214 0.000 4.225

Beginning rNIW.snappy3 ...
Runtime for rNIW.snappy3 :
user system elapsed
4.076 0.003 4.090
```

So, so far there's a factor-2 speed up.

Mind you, this code isn't baremetal code, but some of the heavy lifting is: [rWishart](http://svn.r-project.org/R/trunk/src/library/stats/src/rWishart.c) and [backsolve](http://svn.r-project.org/R/trunk/src/main/array.c). The heavy lifting that is not in this PR (because I don't know how to do it yet--it might require learning [Matrix](http://cran.r-project.org/web/packages/Matrix/index.html))

Also, to orient our heads, I've been writing up the math in extreme detail in a LyX file. And my math matches precisely what I'm seeing here: only a constant speed up at most (in fact, a factor 2 speed up makes a lot of sense: I believe that despite the slew of code differences, the utterly dominant time difference between `rNIW.naive` and `rNIW.snappy3` is that instead of using generic `solve()` with `O(d^3)` I use `backsolve()` which, across a matrix instead of just a vector, takes `O(d(d+1)/2)*d ~= O(d^3/2)`.)