GSoC’13 – Implement estimators of large-scale sparse Gaussian densities

I have submitted the proposal (it can be found here). I’m having a much clearer view of the tasks that has to be done. I’ll be working on two other entrance issues before the official coding day begins, namely the graph coloring issue and the elliptic curve functions issue.

In my understanding, the whole work can be summarized as the following –

  1. use greedy graph coloring of the precision matrix (power of precision matrix?) for finding a set of probing vectors, \{v_{j}\} (task for the project includes integrating an existing library. I checked out a few libraries and seems like Joe Culberson’s Graph Coloring code is a really good candidate. Its written in C and provides two greedy methods for vertex coloring. More tests for our specific need has to be done)
  2. for each probing vector, we need to compute v^{T}log(Q)v, Q being the precision matrix, log(Q) is the matrix-logarithm
  3. for computing log(Q) v in the above expression, Cauchy’s integral formula (coming from complex analysis) for matrix function is used, which can be discretized, giving a rational approximation of log(Q) v, which involves solving N different systems of linear equation. Solving these systems involves invoking a preconditioned CG solver (in the project, we’ll  be integrating this from an existing library)
  4. the systems have complex coefficients (coming from conformal mapping needed for the quadrature rule of the above integration) which is given by an existing algorithm in Hale et. al. The precision of this approximation is defined by a theorem, which depends on the extremal eigenvalues. We can calculate the number N for desired accuracy using this theorem. The algorithm (for finding complex integration weights and shifts) needs Jacobi elliptic curve functions (in Driscoll’s SC-toolbox ellipkkp and ellipjc) and extremal eigenvalues. (task for the project is to integrate Krylstat’s implementation of this)
  5. combining everything for the expression of log-determinant involves writing a class which, which will combine all the subtasks. I had a discussion with Heiko on this. While initially we’ll use this to compute this on one computer, later plans include replacing this so that a OpenMPI program can run the subtasks on a cluster with low communication cost and speeded up execution. Will discuss about more details later on

The main paper describes several other techniques for handling special cases (like, when the matrix is ill-conditioned, etc). I’ll read up about these in more detail and update this page later.

One thought on “GSoC’13 – Implement estimators of large-scale sparse Gaussian densities

  1. Hi Rahul

    if interested, check out mathjax for typesetting the math in your blog, I use it for my webpage and its very easy to use. Just one line and then you can use LaTeX

Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s