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.
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?
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.
Comments
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.
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?
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.