On Fri, Jan 15, 2010 at 8:05 PM, Philipp K. Janert <[email protected]> wrote:
> > > So, I am wondering whether people in the numerical > > > analysis community have started to think in this > > > direction and what they have come up with so far > > > (if anything). > > > > I don't think that the numerical analysis community has turned their > > attention much to map-reduce yet. > > One other major consumer of large, sparse matrix > operations are people dealing with partial differential > equations. Yes. And to the degree that large parallel relaxation methods would work for their solution, map-reduce would be a natural answer. Relaxation techniques are, of course, simply a power method in disguise. > And the Linear Programming/Optimization > people also have algorithmically non-trivial, large > problems, that might (just might) be amenable to M/R. > These techniques might work, but my guess is that it would require substantially different techniques than are currently used. There are a fair number of restatements of linear programming as some form of gradient descent, but these techniques can be very difficult to parallelize using map-reduce. The Pegasos algorithm for SVM is an example of a projection technique and SVM is essentially a form of constrained quadratic optimization. It is not clear how to parallelize the Pegasos algorithm. The SGD family are another example. L-1 regularized logistic regression can be restated as a linearly constrained optimization problem (was originally stated that way, actually), but the gradient descent algorithm currently used is inherently difficult to parallelize to any great degree. Both Pegasos and SGD can use multi-core machines and may be able to use GPU's well, but larger scale parallelism is really hard to do for either. Happily both algorithms are really, really fast on sequential machines. The future may involve just be solving a gazillion different gradient descent problems at the same time. > On the other hand, I would not expect physics > simulations to work well - the communication > overhead will kill you (it did not work very well on > the Cray, back in the day, and the problems have > not changed.) The problems haven't, but the techniques for some kinds of physics simulations have changed dramatically. Quasi-static electromagnetic propagation problems can be cast as approximately low rank matrix problems which can probably be handled using map-reduce derived decompositions. There has been some interesting work in facilitating n-body computations on map-reduce architectures: ftp://ftp.cs.washington.edu/tr/2009/06/UW-CSE-09-06-01.PDF Remember also that hadoop isn't the only map-reduce architecture around. There are now MPI-based implementations. The virtues of map-reduce still apply where-ever you need simple robust parallel architecture (if your algorithm fits). -- Ted Dunning, CTO DeepDyve
