Sunday, May 15, 2011

Slowly but surely they'll join our side of the Force...

Back in February 2009, Jack Dongarra, the father of LinPack/LAPACK, sent this request to the NA-Digest Mailing list:

Subject: Linear algebra software survey request
We are planning to update the survey of freely available software for the solution of linear algebra problems. The September 2006 version of the survey can be found at: The aim is to put in “one place” the source code that is freely available for solving problems in numerical linear algebra, specifically dense, sparse direct and iterative systems and sparse iterative eigenvalue problems. Please send me updates and corrections. I will post a note on the na-digest when the new list is available.

To which, I naively replied with:

Dear Dr. Dongarra,
In a recent NA-Digest you proposed to update the Linear algebra software survey. I was wondering how you were viewing the solvers currently being developed by the folks in the compressive sensing literature. As you know, the problems being solved are underdetermined linear problems and the solvers are nonlinear solvers. A set of examples/links to actual implementation (mostly in matlab) can be found here:
Would these solvers fit into the survey ?....

To which Jack kindly replied with:
Its a bit too far afield.

Fast forward two years later, what wasn't my surprise when I saw the following on my radar screen:

We show in this paper how linear algebra calculations can be enhanced by statistical techniques in the case of a square linear system Ax = b. We study a random transformation of A that enables us to avoid pivoting and then to reduce the amount of communication. Numerical experiments show that this randomization can be performed at a very aff ordable computational price while providing us with a satisfying accuracy when compared to partial pivoting. This random transformation called Partial Random Butter y Transformation (PRBT) is optimized in terms of data storage and ops count. We propose a solver where PRBT and the LU factorization with no pivoting take advantage of the latest generation of hybrid multicore/GPU machines and we compare its G op/s performance with a solver implemented in a current parallel library

So when are we starting Random Projection LAPACK or RP-LAPACK ?

No comments: