3
$\begingroup$

I have a ~4.12 Tb structured relatively-sparse matrix dataset (about 8% of the matrix entries are non-zero) that i want to apply an LU decomposition, however, given the size of it, loading it in memory and using the usual BLAS or Eigen routines is out of the question.

Is there some unix/linux library that i can use to do LU decomposition on a memory-mapped matrix dataset?

I found out that R has a package for memory-mapped matrices (http://www.bigmemory.org) but i'm not expert in R, and i apologize in advance if this can be answered by installing it and trying it out, i wanted to ask before i embarked in learning a new programming environment if this would really solve the problem.

Thanks!

$\endgroup$
  • $\begingroup$ Can you explain why you want to do an LU factorization? Large, sparse matrices that arrise in PDE simulation problems, for example, are usually not factored, instead we use iterative methods to solve the underlying linear systems approximately. Would something similar be appropriate for your problem? $\endgroup$ – Bill Barth May 5 '13 at 14:12
  • $\begingroup$ anything that can allow me to solve linear systems encoded in a huge, memory-mapped dataset would be good enough i think $\endgroup$ – lurscher May 5 '13 at 15:29
  • $\begingroup$ Does it have to be memory-mapped? This seems like a prime candidate for parallel computing. $\endgroup$ – Bill Barth May 5 '13 at 17:10
  • 1
    $\begingroup$ It is also dangerous to consider 8% "sparse" in the usual sense. $\endgroup$ – Jack Poulson May 5 '13 at 18:51
  • 1
    $\begingroup$ Where does this problem come from, what properties does the matrix have, and how do you intend to use the result? $\endgroup$ – Jed Brown May 6 '13 at 4:03
7
$\begingroup$

I don't know of any libraries that are still in use today but the keyword in literature searches you will be looking for is "out of memory solver" or "out of core solver" -- linear solvers (and LU decompositions) that work on matrices stored on disk (or tape, at the time) were quite popular in the 1960s, 70s and 80s when memory was expensive and small.

That said, 4TB is even today an incredibly large size. For sparse matrices, LU decompositions are typically much denser, so you have to expect that any LU decomposition would run into the tens or hundreds of TB -- a size where you will likely find that dealing with it is impractical simply because of the time it takes to do I/O.

Your better bet is certainly to employ iterative solvers for linear systems. You can get 4TB into memory on 2-3000 cores on a cluster today. That's a significant, but not an infeasible size. Libraries like PETSc and Trilinos will happily do this for you. Depending on the properties of the matrix and the preconditioner you want to use, you may again need a (small) multiple of the memory and then a corresponding multiple of cores.

$\endgroup$
  • 1
    $\begingroup$ was able to find a really nice approximation with block iterative hybrid algorithm, based on this scheme: spectrum.library.concordia.ca/2484/1/MM18429.pdf and recursive block-wise iterative inversion, and it only took a week of CPU time in a single Xeon machine! $\endgroup$ – lurscher May 22 '13 at 6:24

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.