Applicability of combinatorial and support preconditioner

Question

There are several correspondences between matrices and graphs, e.g., each matrix is the adjacancy matrix of a weighted graph. The terms support preconditioner or combinatorial preconditioner refer to preconditioners which have been designed using graph theoretical tools that rely on these correspondences.

It certainly good to have another track of development besides, say, incomplete cholesky factorization or algebraic multigrid. But I wonder in which cases these preconditioners are superior to other usual preconditioners.

In recent paper, these preconditioners have been applied to finite element discretizations of scalar elliptic PDEs: Avron et al., Combinatorial preconditioners for scalar elliptic finite-elements problems. - As far as I understand, these preconditioners are outperformed by Incomplete Cholesky factorization, but on the other hand are very well-behaved in the presence of degenerated elements or very anisotropic coefficient tensors.

What are the applications where these preconditioners are most promising?

Answer 1

I have not kept up with this literature for a while, but I see these methods as not quite a genuine "another track of development". My recollection is the theory was that it invoked classic linear algebra at the end of the day and end up looking like incomplete factorization methods. That said if you have some ILU solver that you motivate with graph theory then more power to you, or if you find a useful implementation of a solver that invokes graph theory then by all means use it. I just don't see the area as a generically interesting source of algorithms that are more useful than what has come out of classic linear algebra communities.

And there is no comparison of these methods (and ILU) with AMG that explicitly exploit properties of individual discretizations of PDEs (eg, null spaces) and have solid theory, both abstract functional analysis type theory and linear algebra proofs of optimality. Note, AMG needs smoothers to actually solve the problem and ILU or support graph methods can be perfectly useful as smoothers.