# Speeding up calculations with lookup tables and Lagrangian interpolation

## Lookup Tables with Lagrangian Interpolation¶

One of my students wanted to speed up the calculation of exp(x) in a simulation. There are a few ways to do this, but a lookup table is often a huge win in situations like this. The basic idea is that, for an expensive function like exp(x), you pre-calculate exp(x) for a bunch of values that cover the range in which you're interested. You then look things up in the table at runtime. If the exact value you want isn't in the table, you use a cheap interpolation function. By tweaking the density of your pre-calculated values and the sophistication of your interpolation function, you can get results that are quite close to exact calculations for a fraction of the run-time cost.

Sadly for me, I didn't know a bunch about which interpolation functions to use, so I asked Andy Simmonett. I wrote the Python bits below, but the general explanation is direct from him, with some light modifications. He's a QM/MM guy, so some of what is written below should be taken in the context of molecular simulations.

# Evolution of a Learning Goal

I just got back from the Lilly Conference on College Teaching. The first workshop I went to was on course design. One chunk of this was on learning goals. This came in the second half of the workshop, after we’d talked quite a bit about learning factors, etc. I chose to work on my 200-level Biophysics class, where I thought I had decent goals already. One of the ones I particularly liked was

Use simple physical models to provide quantitative insight into biological systems.

# Making IPython Notebooks for the matplotlib examples

matplotlib comes with tons of fantastic examples. I’m not as familiar with matplotlib as I probably should be, so I often find myself wanting to tinker a bit, but needing to refer to those examples. Since matplotlib comes with such wonderful documentation, I though it would be great to just turn those docs into IPython Notebooks for easy tinkering. That’s probably biting off a bit more than I want to chew at the moment, considering that the matplotlib docs are fairly involved and written in reStructuredText instead of markdown (what the IPython Notebook uses).

Luckily, the IPython Notebook format is so mind-bendingly sane that I didn’t even need to read any documentation to understand it. So, instead, I wrote a bit of code that gobbles up matplotlib example scripts and spits out IPython Notebooks. The whole notebook is JSON, but I only want simple things, so I hardcode everything except for the cells. (After Daniel’s comment below, I started to write my own JSONEncoder. Then, I realized that I was right about the “it’s all JSON” thing and rewrote the notebook class). I have a little IPyNB class that knows how to add cells to itself and spit out the results as strings and files:

# Histograms and kernel density estimation KDE 2

## Why histograms¶

As we all know, Histograms are an extremely common way to make sense of discrete data. Whether we mean to or not, when we're using histograms, we're usually doing some form of density estimation. That is, although we only have a few discrete data points, we'd really pretend that we have some sort of continuous distribution, and we'd really like to know what that distribution is. For instance, I was recently grading an exam and trying to figure out what the underlying distribution of grades looked like, whether I should curve the exam, and, if so, how I should curve it.

I'll poke at this in an IPython Notebook; if you're doing this in a different environments, you may wish to uncomment out the commented lines so that your namespace is properly polluted.

In [1]:
from __future__ import division
%pylab inline


Populating the interactive namespace from numpy and matplotlib


# Drum head normal modes, with movies

We’re working our way through Boas in my Mathematical Physics class, and we’ve come to the point in the PDE chapter where every good Physics student figures out what the normal modes of a circular drum head ought to look like. Punchline:

# March Madness, Monte Carlo Style!

I’m teaching Thermal Physics this term, so obviously I rearranged the syllabus so that we could all run Monte Carlo simulations for March Madness!

Quick summary for the class is at the end

# The basics

We started off writing an energy function and figuring out how to play a simple 8-team bracket (side-note: IPython notebooks were great for this purpose! We were able to record our class sessions and post them online, along with a “Scientific Cookbook”). This version of Thermal Physics doesn’t have a programming prerequisite, so the coding parts of the assignments stopped with running and analyzing 8-team brackets.

We then spent a chunk of class time comparing our simulations with the 2-state paramagnets we’d seen in Schroeder’s text (we covered section 8.2 a bit out of sequence). In that context, it was clear what a Monte Carlo move was. We convinced ourselves that we could do something similar in bracket space, but that we couldn’t just flip a single game (we also had to consider flipping the games that depended on that game). The coding for that part was definitely beyond the scope of this class, but I hacked up an ugly version for us to use.

# Getting a working Python install, part 2

With the new laptop (side note: the 13″ MacBook Pro is a really nice machine. The screen certainly has enough pixels for real work, unlike previous 13″ machines. The only thing missing is a GPU.), it’s time to re-install. Since my last post, I’ve been convinced to upgrade to Python 2.7. Anthony Bak has recently gone through the same thing, so here’s my version of his set of notes on how to do this:

- ActiveState, the EPD, etc. are great, but don’t seem to play nicely with a few external packages.
- CMake causes lots of trouble, but there doesn’t seem to be a good alternative. I’m not sure why the macports version can’t be made to “just work”.

0) Fully uninstall macports (http://guide.macports.org/#installing.macports.uninstalling). Follow the full set of directions.

Then, go through your .bashrc/.bash_profile and collect all of the macports-related changes (they’ll all have /opt in them). Stick them at the end so that you can combine them with whatever macports does to your init files during the rest of the install.

1) Set /opt/local/etc/macports/variants.conf to contain

+python27 +py27 -python26 -py26 -universal +bash_completion

You’ll have to make the file and the directories, assuming you followed step 0.

2) Install the latest and greatest macports, using the package install and the easy options (http://guide.macports.org/#installing.macports). The rest of this guide was done with MacPorts-2.0.4-10.7-Lion.dmg.

3) Open a new shell so that your path is correct and run

sudo su # port requires superuser privs
port selfupdate
port install coreutils python27
port select –set python python27
port install cmake boost mercurial cairo eigen py27-cython py27-numpy py27-scipy py27-wxpython-devel py27-matplotlib py27-pil

Note that we aren’t installing py27-wxpython because it requires
universal builds (which will mess up some other choices) so we use

4) Edit .bash_profile

export PATH=/opt/local/libexec/gnubin:/opt/local/bin:/opt/local/sbin:$PATH export MANPATH=/opt/local/share/man:$MANPATH
export PYTHONPATH=\$PYTHONPATH:/opt/local/lib/python2.7/site-packages:./

Also in there

export LDFLAGS=’-L/opt/local/lib’
export CPPFLAGS=’-I/opt/local/include’
export LD_LIBRARY_PATH=/opt/local/lib
export LD_INCLUDE_PATH=/opt/local/include

5) Now we handle cgal.

port extract cgal

Apply this patch:

http://cgal-discuss.949826.n4.nabble.com/PATCH-prevent-Qt-s-moc-from-choking-on-BOOST-JOIN-td4081602.html

The files are in

/opt/local/var/macports/build/_opt_local_var_macports_sources_rsync.macports.org_release_tarballs_ports_gis_cgal/cgal/work/CGAL-3.9/include/CGAL/Qt.

and the patch is tiny enough that it’s faster to just do it by hand.

port build cgal
port install cgal

—–

6) Download the openbable source distribution (latest is 2.3.1) . We’ll be installing by hand.

cd openbable-2.3.1
mkdir build
cd build
cmake -DCMAKE_INSTALL_PREFIX=/opt/local/ -DPYTHON_BINDINGS=YES ../

Edit CMakeCache.txt to fix all the python paths. Use
/opt/local/Library/Frameworks/Python.framework/Versions/2.7

So, in emacs, a straightforward search and replace for /Library/Frameworks/Python.framework/ –> /opt/local/Library/Frameworks/Python.framework/ should work, but I had some trouble if I didn’t specify the specific version, so
/Library/Frameworks/Python.framework/ –> /opt/local/Library/Frameworks/Python.framework/Versions/2.7/

make
make install

and even that never really worked for me. I also had to change a couple of instances of /usr/local/lib/python… to point to opt. And then the install failed. It installed all of the ob tools, but not the python .so. So, I copied it over by hand, and that seems to work.

So far, I am unable to get Mayavi installed from source. It works with the EPD, so I actually have two Python installations at the moment, sadly enough.

7) Install Dionysus(http://www.mrzv.org/software/dionysus/get-build-install.html). You have to tell it where the CGAL cmake files are.

cd Dionysus
mkdir build
cd build
cmake ../

Now edit the CMakeCache.txt file. Fix the python headers/path and
change the cgal dir (and maybe the same for boost).

CGAL_DIR:PATH=/opt/local/lib/cmake

make
cd bindings/python
mv lib_dionysus.dylib /opt/local/lib/
mv dionysus /opt/local/Library/Frameworks/Python.framework/Versions/2.7/lib/python2.7/site-packages/
cd /opt/local/Library/Frameworks/Python.framework/Versions/2.7/lib/python2.7/site-packages/dionysus
rm _dionysus.so
ln -s /opt/local/lib/lib_dionysus.dylib _dionysus.so

http://math.stanford.edu/~muellner/fastcluster.html

sudo su python setup.py install

Install Mapper
TODO

Install sharedmem

hg clone https://bitbucket.org/cleemesser/numpy-sharedmem
cd numpy-sharedmem
sudo python setup.py install

When you have time (on my machine graph-tool takes many hours and uses
>4GB durring the build phase):

port install py27-scikits-learn py27-scikits-statsmodels py27-networkx
py27-graph-tool

# Getting a sensible Python install on my Mac

I recently had to get Python + things I like up and running on my Mac from scratch. That’s a significantly harder task than you might guess, so one of the main reasons I’m posting this is for my own benefit (I’ll have to do this all again in February when I give my current laptop back to NIH and buy one of my own). There’s a decent chance this will be useful for others, though. A significant amount of experience and gnashing of teeth has told me

1) ActiveState is awesome, but not everything works perfectly with it.
2) Ditto for Python 2.7.
3) Never mix macports and fink.

So, here’s my setup for a working python2.6 system that happens to meet my current needs: