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