# Preconditioner for dense matrix “with diagonal predominance”

For a CFD panel-based potential method, I'm trying to reduce the time to solve the linear system. The matrix has the larger values on the diagonal, since the influence of a panel on itself is maximum, and that the panel's influence on other panels decreases at least as the inverse of their distance. The matrix has no reason to be diagonally dominant however.

GMRES converges nicely, perhaps due to the diagonal having the larger values. IS there a preconditioner that would make it even faster?

Thanks,

• You could try a Gauss-Seidel preconditioner (use only the upper (or lower) triangular part of the matrix). If the matrix is sparse you could try algebraic multigrid. PyAMG in python is great; I like their Ruge-Steuben solver. Another possibility is to use Hierarchical matrices. H2lib in C is good for that. Though, the setup costs for H matrices is large, so if it already converges fast with GMRES there may not be much additional benefit there. – Nick Alger Mar 8 '17 at 20:15
• Are you using any preconditioner at the moment? It probably wouldn't hurt to try something simple like Jacobi if you haven't already tried that. If the influence decays sufficiently quickly as a function of distance, perhaps you could construct a sparse matrix approx. of your dense matrix and use an approx. of its inverse as a preconditioner. For example, maybe you could construct an approximation of your original matrix where the influence between anything more than 2 panels away is set to 0, get an incomplete LU factorization of this approximation, and then use this as a preconditioner. – nukeguy Mar 8 '17 at 20:49
• OK, thanks I'll experiment a bit and post back. – techwinder Mar 9 '17 at 18:00

In case it may be of help to others, here's the result of the testing on a 30x30 influence matrix.It was made using non-restarted GMRES. GMRES without preconditioner (red curve) converges in 13 iterations, with a sudden convergence at iteration 12.

GMRES with symmetric Gauss-Seidel (dashed curve) converges more smoothly, but in a little more iterations.

The ILU preconditioners are incomplete LU factorizations of the matrix, where only a band of variable width below and above the diagonal has been kept, i.e. Abs(i-j)

Bandwidth 2, black curve : smooth convergence, in roughly the same number of iterations as the non-preconditioned GMRES

Bandwidth 5 and 10 are the yellow and green curves : convergence increases with the bandwith.

The curves with icons are ILU with bandwidth 10, where the preconditiong is only applied on one side.

All in all, the ILU applied on the left and right sides seem to be the most promising preconditioners. It remains to be tested at full scale for large matrices.