Iterative solvers for non-symmetric matrices

[JordiManyer]

We will eventually run into non-symmetric matrices. It would be good to have a solver for this cases.

The most common are GMRES (Krylov method similar to CG but for non-symmetric problems) and AMG.
Both can be complicated to implement in an efficient way:

For GMRES, the main problem is the least squares problem that needs to be solved at each loop iteration. For this reason, most people build and dynamically update a QR factorization when finding the orthogonal basis for the Krylov space. This can be done efficiently using Householder transformations.

For AMG, the problem is how to create an efficient sparse interpolator (i.e the transformation between the different fine and coarse levels). Rugge-Steuben is the all-purpose standard interpolator, but it can be tricky to implement in a sparse way. For simple geometries, and taking advantage of the mesh structure, simpler interpolatros can be obtained. After this, the actual solver is very easy to implement and test.

All in all, here are my initial thoughts:

• If we decide on a specific mesh, AMG can be made quite efficient by building a mesh-specific interpolator. For general meshes, I would probably prefer GMRES.
• When parallelizing the code, GMRES will suffer minimal changes whereas AMG will require a lot of work (specifically on the interpolator).
• AMG can be later used as a preconditioner (one of the best) for GMRES and CG if we ever need to.

So in conclusion I would start working towards GMRES as a priority and then try to go towards. Both could be nice to have, but neither are a real priority, since I doubt we find non-symmetric matrices in quite a while.

GMRES Solver

• Basic structure (re-use from CG)
• Implement Householder transformations
• Implement QR solver
• Implement GMRES loop (with restart)

AMG Solver

• Basic structure
• Implement general iterator class. Implement Jacobi and test separately.
• Implement interpolator for FEM.
• Implement AMG Level class.
• Put everything together and test.

[JordiManyer]

2e54233

GMRES: Basic structure + Householder transformations.
AMG: Basic structure + iterators. Jacobi iterator now works as a 1-level solver.