Do black-box preconditioners for matrix-free methods exist?

Question

Jacobian-Free Newton-Krylov (JFNK) methods, and Krylov methods in general, can be very useful because they don't require explicit storage or construction of a matrix, only the results of matrix-vector products. If you do actually form the sparse system, there's many preconditioners out there for you.

What is available for true matrix-free methods? Googling turns up some references to "matrix estimation" and some other things indicating that it is possible. How do these methods generally work? How do they compare to traditional preconditioners? Are physics-based matrix-free preconditioners the way to go? Are there any openly available methods in the wild, say in PETSc or some other package?

Answer 1

Maybe not a preconditioning strategy in the traditional sense, but deflation could be useful in this case. In gmres(A) for instance, you can use the eigenpairs of the hessenberg projection H to form ritz vectors that are good estimates for eigenvectors of A. You use that to deflate your residual upon a restart, and give speedups over traditional restarted gmres. [The harmonic ritz values can be used to find small eigenvalues of A and deflate them out, which is more useful IMO than deflating out large eigenvalues of A]. I think deflated variants exist for all kinds of krylov solvers (CG, etc), but I am most familiar with the concept in the context of restarted gmres.

You could google for GMRES-DR for more info, I also ran across a matlab implementation of GCRODR written by someone at Sandia, shouldn't be hard to find it again.

Answer 2

It's going to be heavily dependent on your problem.

Since you mention fluid dynamics, you might look into BFBt approximate commutators which have been very effective for fluid dynamics problems with constraints such as incompresible Navier-Stokes,

http://epubs.siam.org/doi/abs/10.1137/040608817