search

ginkgo-project / ginkgo

Numerical linear algebra software package
https://ginkgo-project.github.io/
BSD 3-Clause "New" or "Revised" License
386 stars 86 forks source link

Support for right & two-sided preconditioning #28

Open gflegar opened 6 years ago

gflegar commented 6 years ago

Ginkgo currently supports only left preconditioning.

However, it seems that some use-cases require right and two-sided preconditioning. We started this as an off-topic (or maybe vaguely-on-topic) discussion in thread #17 , so I'll collect related comments, and we can continue the discussion here.

[...] we have to decide between left preconditioning ( MAx = Mb ) Right preconditioning ( AMx =c, x = My) and mixed preconditioning. Matlab only supports left preconditioning (afaik), and the same holds for MAGMA-sparse (that I should know.) Is it valid to stick with that? I am not sure what Trilinos/SuperLU/PetSC does. I would appreciate input from the community. -- @hartwiganzt

Iterative solvers may

  • choose to accept left, right, or both (split) preconditioners.
  • have this option without overhead, if the solver implementation dispatches to different algorithms based on whether or not the (left,right,both) preconditioner(s) exist(s). [...]
    • Most users want right preconditioning because it preserves the residual norm (e.g., makes GMRES' "implicit" residual norm the same as its "explicit" residual norm norm(b-A*x, 2)).
  • However, some users want left preconditioning (optimization folks, for example -- I can fish around for details if you're interested).

-- @mhoemmen

I know some people who use left preconditioning and others who use right. Mathematically they give different results, so I think both options should be supported. However, split/both is much less common, so lower priority though it is the most general approach. -- @egboman (upvoted by @mhoemmen, @drittelhacker)

We talked a little bit about LSQR over the phone today. Matlab actually right-preconditions LSQR:

https://www.mathworks.com/help/matlab/ref/lsqr.html?s_tid=gn_loc_drop

That makes sense because LSQR solves a (constrained) least-squares problem. A "left preconditioner" would actually change the function to minimize. (That's true for GMRES as well, but GMRES aims to solve the linear system and a good solution to the linear system will minimize that function regardless. LSQR works even when there is no x such that Ax=b.)

Our users tend to prefer right preconditioners for GMRES etc. for this reason. However, it's not hard to make GMRES, etc. achieve the tolerance for the actual ("explicit") residual norm(b-A*x,2); first iterate until the "implicit residual" (the thing that GMRES computes from the little upper Hessenberg system) achieves the desired tolerance, than iterate some more until norm(b-A*x,2) does as well. Thus, it's not much different to use a left preconditioner.

-- @mhoemmen

[...] if we support both left and right, we can also support two-sided preconditioning without significant effort. -- @gflegar

mhoemmen commented 6 years ago

(commenting just to show interest in further discussion :) )