February 2, 2014

Smolyak Interpolation

Last semester, Spencer and I dedicated some time (probably too much time in fact) to writing up a Python class that could handle Smolyak interpolation.  For those that are unfamiliar with what Smolyak interpolation is, it is a sparse grid collocation method that uses perpendicular polynomials for accurate interpolation between grid points.  It is slowly becoming a "frequently" used tool by computationally focused economists (even saw a student from Penn use it in his job market talk).  Krueger and Kubler had what I believe was the first paper in economics to use this method in 2004 and they have since written some papers jointly with Malin that use it.  Additionally, Judd, the Maliars, and Rafael Valero have written some papers on the method and they have a working paper that was very helpful in our exploration of the material.  It is useful for tackling high dimensional problems where one would quickly run into the curse of dimensionality.

For example, imagine a model where you have 5 state variables.  Even if you wanted to build a grid with just 5 grid points in each dimension you get a grid that is 5^5 (3125) points large.  The same problem can be approximated quite well with a Smolyak grid of 241 points.  It reduces the growth in states from exponential to polynomial.

Our code is hosted at this github repository and some pretty decent documentation (and basic intro to the mathematics of the method, examples, code documentation) can be found here.  We are by no means finished with this project and we have plans to add more functionality to the package (after we finish our first year), but at this point there is good working code that builds grids, interpolates, and even handles first derivatives.  We would love some feedback (bugs, useful suggestions, etc...) if anyone tests or uses the code.