Numerics of Gram-Schmidt orthogonalization

Kdy? 15.4.2010 13:00 - 14:00
Kde? ZČU / FAV / KMA / UL610 (učebna)

Miro Rozložník: Numerics of Gram-Schmidt orthogonalization


In this contribution we compare the numerical properties of the classical (CGS) and modified (MGS) Gram-Schmidt orthogonalization. The theory for the MGS algorithm is well-known thanks to results of Bj\"orck and Paige, who have shown that for a numerically nonsingular matrix $A$ the loss
of orthogonality in MGS occurs in a predictable way and it can be bounded by a term proportional to the condition number $\kappa(A)$ and to the roundoff unit $u$.

Generally accepted view for the CGS process is that due to rounding errors the orthogonality of computed vectors can be lost very quickly or may be even lost totally. The textbooks usually contain examples with progressive deterioration in the orthogonality without any bound relating it to the condition
number of initial vectors. We will show, however, that one can derive a bound for the loss of orthogonality  in the CGS algorithm. This  bound depends only quadratically on the condition number of the system. This result sounds very well with all examples used for demonstrating the unreliability of the CGS
process, what will be also illustrated on examples.

If we want to keep the computed orthogonality as close to the machine precision as possible, we need to use the Gram-Schmidt orthogonalization scheme with reorthogonalization. We will show that either for the CGS or MGS process with (one) reorthogonalzation the loss of orthogonality is preserved on the machine precision level. On the other hand, the price for it is
rather high, it is actually doubled in comparison to the standard CGS or MGS algorithm.

From a practical point of view, the CGS algorithm is a better candidate for parallel implementation than the MGS variant of the same algorithm and this aspect could not be overlooked in certain computing environments. Moreover, a new trend is emerging nowadays, several experiments are reporting that even if performing twice as much operations as MGS, the CGS algorithm with one (complete) reorthogonalization may be faster. This indicates that such results  to certain extent may lead to reinstating of

the CGS algorithm as a suitable alternative for parallel implementation of the Gram-Schmidt orthogonalization process.

Evropská unie, ESF, MŠMT, OP Vzdělávání pro konkurenceschopnost, ZČU


RSS kanál

Chcete mít stále aktuální přehled toho, co se chystá? Přidejte si náš kanál s přehledem chystaných událostí do Vaší RSS čtečky.