2
$\begingroup$

Someone point me in the right direction. I'm looking to do some heavy-duty manipulation of some really large and often very sparse matrices. Naturally, this problem overlaps programming heavily (I will probably ask a similar question on StackOverflow), but since I'm on a math site I'm interested in finding a family of algorithms that are suitable for this. Or more generally I'm interested in anything that gets me closer to the goal.

So, the goal: I will want to do several different manipulations of giant matrices. These matrices will be much, much larger than the RAM of any single machine and will therefore likely be spread to several different machines. The matrices will often be sparse. I will want to perform all of the common matrix operations: multiplication, transpose, inverse, pseudo-inverse, SVD, Eigenvalue Decomposition, etc. Probably key among my concerns is that since the matrices will very likely be spread among several machines, I will want to minimize information sharing, because network latency is probably my biggest enemy. I'm concerned that map-reduce (a la Hadoop) is not the right option because it's focus is upon streaming large amounts of data between machines. This book provides a great intro to map-reduce from an algorithmic perspective. And lots of matrix operations are akin to giant JOIN operations which are known to be slow or map-reduce.

So... where should I go?

$\endgroup$
3
  • $\begingroup$ Try this en.wikipedia.org/wiki/Matrix-free_methods $\endgroup$ Commented Sep 3, 2013 at 1:11
  • 1
    $\begingroup$ You should probably avoid, at all costs, inverting your giant matrices. The inverse of a sparse matrix is generally not sparse. Similarly, an eigenvector of a sparse matrix is generally not sparse: it may be OK to compute a few of them, but you don't want to try a complete eigenvalue decomposition. $\endgroup$ Commented Sep 3, 2013 at 1:35
  • $\begingroup$ @RobertIsrael Good point! I'm hypothesizing about what I would like to do with the matrices and I'm not quite thinking it through. So sure.. I'd like to find the first eigenvector and thus solve for the eigenvector centrality of all nodes in a graph. For SVD, I only need the first 150 vectors for rank-reduction. And rather than inverse, I will solve the matrix for a particular solution. And when I do a pseudo inverse, it will be with skinny matrices. That sounds more reasonable, right? $\endgroup$ Commented Sep 3, 2013 at 1:54

1 Answer 1

1
$\begingroup$

I think that you should not try to reinvent the wheel and try to use one of the two following big libraries:

  • Trilinos, in particular at the sparse matrix packages (Epetra, Tpetra,...), linear solver packages (Amesos, Belos,...) and the eigen solver package (Anasazi).
  • PETSc which as similar features.

Both libraries are widely used in computational science and well suited for calculations with large distributed matrices.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .