[SciPy-dev] implement reorthogonalization method in gmres

[Pauli Virtanen]

ke, 2010-02-24 kello 23:43 +0100, nicky van foreest kirjoitti:
> I am not at all a specialist on this, but I recall that Numerical
> Recipes states that the Gram-Schmidt process gives terrible results,
> and should be avoided nearly always.

There's a balance here: more accurate methods tend to require more work,
and the orthogonalization is probably the most expensive part of GMRES.
So one should use a method that is good enough.

> Instead, singular value
> decomposition should be used. To avoid the problem below, would is be
> an idea to replace the GM algo by SVD?

One could also QR factorize using Householder transforms, which should
be more accurate than GS, and is probably less expensive than SVD; or
reorthogonalize.

But as far as I understand, this would not really improve the
performance of GMRES: as shown in the article I linked to (and also in
others), the quality of the orthogonalization is not expected to matter
for GMRES -- modified Gram-Schmid is good enough. The point is that
breakdown of orthogonality happens simultaneously with the solution
reaching its maximal accuracy, so it will not essentially affect
convergence or accuracy. I'd like to have a reference or a test case at
hand stating otherwise before changing things here.

As far as I understand, however, the situation with orthogonality is
different if you want to solve eigenvalue problems with Arnoldi stuff.
But that's in the domain of ARPACK, and I would trust without looking
that the ARPACK people know what they are doing.

Cheers,
Pauli