New Algorithms

[KlausC]

Is it valid to consider the results of this paper from 2011: Inner-Iteration Krylov Subspace Methods for Least Squares Problems?

Especially the algorithm called there "BAGMRES-NRSOR" seems to show outstanding performance.

See also the current 2022 article: GMRES methods for tomographic reconstruction with an unmatched back projector

[amontoison]

Hi @KlausC !
The results of the first paper are not great.
CG and GMRES should be only used to solve generic symmetric and square systems.
For least squares problems LSQR and LSMR are recommended, more stable and less expensive.
They also compared with very specific preconditioners (nobody use a RIF preconditioner...).

BAGMRES-NRSOR is juste GMRES with a right preconditioner N for information.
You just need to model the preconditioner and you have a "BAGMRES-NRSOR".
I can help you to implement it if it's your issue.

I will read the other paper tonight :)

[KlausC]

I am not yet convinced, that BA-GMRES is just GMRES with an appropriate conditioner.
Here Ax - b is replaced by B * (Ax - b) to become square, where B is close to A'.

I am not sure, how BA-GMRES would compare to LSQR or LSMR. Would be interesting to find out.

I also found that one useful. Preconditioned GMRES methods with incomplete Givens orthogonalization method for large sparse least-squares problems

When I find the time I will make a PR to prove the concept.

[dpo]

I am not yet convinced, that BA-GMRES is just GMRES with an appropriate conditioner.
Here Ax - b is replaced by B * (Ax - b) to become square, where B is close to A'.

Right. If A is rectangular, that isn't called preconditioning.

[amontoison]

@KlausC
I discussed with Ken Hayami today (ICIAM 2023).
BA-GMRES is just GMRES applied on BAx = Bb.
AB-GMRES is GMRES applied on ABx = b.

You just need to model AB or BA by forming explicitly the matrices or implementing linear operators that perform AB * v or BA * v.

When B=A', BA-GMRES is equivalent to MINRES on the normal equations or LSMR. You can see it as MINRES with full reorthogonalization (stable but very expensive).
We have similar result for AB-GMRES.

With the current implementation of GMRES in Krylov.jl we can already do AB-GMRES and BA-GMRES.
Do you want that I add an example or more documentation about it?

[KlausC]

Thanks, that would be fine.