News for hackers. Stuff that matters.
Re:CMU Researchers Break Speed Barrier In Solving Important ... by jedbrown on Saturday October 23, 2010 @10:28AM (#1823530)
Funny that they don't mention multigrid which is O(n) and very reliable for M-matrices (more general than SDD, which is a rarely used term in the multigrid literature). It's hard to take this seriously if they don't demonstrate that the constants are good enough to beat the various multigrids for this problem. Also note that most physical problems which lack optimal sparsity are also not M-matrices, and indeed lack H-ellipticity (necessary and sufficient condition for the existence of a pointwise smoother), even though they are often still SPD.
Re:CMU Researchers Break Speed Barrier In Solving Important ... by wtallis on Saturday October 23, 2010 @09:38PM (#1824915)
Wouldn't this method at least have the advantage of being a drop-in replacement, where multigrid methods require a bit more work to integrate in to your solver?
Re:CMU Researchers Break Speed Barrier In Solving Important ... by jedbrown on Sunday October 24, 2010 @03:46AM (#1825583)
Algebraic multigrid is usually called in the same way as a direct solver. For example, there are three distributed-memory parallel algebraic multigrid packages (and a bunch of other methods, direct and iterative) that may be used as runtime options with PETSc's same Solve call.