title :
-------
TMGS - A ``twice is enough'' reorthogonalization algorithm.

speaker : Julien Langou.
Conference : team meeting. 
Location : Institute of Computer Science, Prague, Czech Republic, 
Date : February 5, 2002. 

abstract :
----------
The Modified Gram-Schmidt (MGS) algorithm is a well-known orthogonalization
 method used in many linear algebra algorithms.
 It is a fast way to compute for instance a QR factorization.
 Even though this method is widely used, some theoretical questions on its
 behavior in finite precision arithmetic are still open.

It is well known that the set of computed vectors may loose orthogonality,
 however it is experimentally observed that this set has full rank.
 We propose a theorem that gives a theoretical explanation to this phenomenon.

If we combine this theorem with a well-known result from
 Bjorck, we can show that two sweeps of MGS are indeed enough to get a
 matrix whose columns are orthogonal up to machine precision.
 We recover the famous sentence of W. Kahan :  ``twice is enough.''

We can then generate an algorithm TMGS (Twice MGS) that gives a reliable
 QR factorization.