Is it possible to solve Ax=b with mapreduce ?

I’m trying to solve some really large linear regression problems with the mldivide command. When I try to do the calculation with large variables the system RAM quickly goes up to 100% and Matlab starts to use the page file and it’s quite slow.

So I was wondering if it is possible to partition a calculation of the type x=A\b with mapreduce to tackle it in chunks instead. Does anyone know?

Answer 1

[Brendan Hamm]

You can do this if certain conditions hold fairly simply. In the case of a diagonally dominant matrix A you could write the Gauss-Seidel, Jacobi or Conjugate Gradient (symmetric positive definite only) methods. I imagine they would be very slow with so much read write from disk with iterative algorithms, but likely better than using paging. Then there is the obvious, buy more RAM for your machine if it is feasible.

[Peta]

To make sure I didn’t misunderstand you – are you suggesting that I try one of these iterative approaches through the mapreduce functionality? Or simply that I should switch to an iterative solver and not use mapreduce ?

[Brendan Hamm]

If RAM is an issue, then I am presuming that you cannot hold your matrix A and vector b in memory and SHOULD use mapreduce. If you can fit A and b in memory, then these iterative methods have very little "extra" data that needs to be stored in memory and you can proceed without mapreduce.

Hadoop Linear Equation

Conjugate Gradient

There are plenty more papers on this out there. I would recommend the Conjugate Gradient Method (if the stricter conditions are met).