Atlas Mathematical Conference Abstracts || Conferences | Abstracts | for Organizers | About AMCA

5th IMACS Conference on Iterative Methods in Scientific Computing
May 28-31, 2001
Foundation for Research and Technology - Hellas (FORTH)
Heraklion, Crete, Greece

Organizers
Apostolos Hadjidimos, Elias Houstis, Emmanuel Vavalis

View Abstracts
Conference Homepage

An insight into the loss of orthogonality in the Modified Gram-Schmidt Algorithm
by
Julian Langou
CERFACS
Coauthors: Luc Girard (CERFACS), Serge Gratton (CNES)

An insight into the loss of Orthogonality in the Modified Gram-Schmidt Algorithm.

An insight into the loss of Orthogonality in the Modified Gram-Schmidt Algorithm.

L. Giraud, S. Gratton and J. Langou

We consider the Modified Gram-Schmidt orthogonalization applied to a matrix \varGamma in Rem×n with rank n <= m and singular values \sigma1 >= ... >= \sigman > 0. This corresponds to a QR factorization : \varGamma = VR where R in Ren×n is triangular and V in Rem×n has orthonormal columns in exact arithmetic. We study this algorithm in finite precision computation when the matrix \varGamma has a numerical rank defeciency k, that is \sigman-i+1/\sigma1 ~ u, i=1, ... , k, u being the machine precision. This subject has already been dealt with success by A. Björck in 1963 [], then continued by A. Björck and C. Paige in 1992 []. They give useful bounds in term of norms. We extend their results to provide bounds on singular values. In order to make it more clear, we present our results in term of numerical rank. We show that if,
Rank(\varGamma)=n-k,
then
0 <= Rank(I-VTV) <= k
and
existsE so that ì
ï
ï
í
ï
ï
î
0 <= Rank(E) <= k
Q=V-E,
QTQ=I,
\varGamma = QR.
These results say that in finite precision computation, V looses orthogonality in just a few directions that are given by E, we can also control the magnitude in each of these directions by the associated singular values of \varGamma.
Based on these results, we have developped some applications. The one that we present here is a reorthogonalization process of V. We have designed an algorithm that computes Q from V by exploiting the low rank k of the matrix E. The advantage of this approach is that we can monitor the orthogonality of V characterized by ||I-VTV||2. In general, the cost of our reorthogonalization is less than 2mn2 flops ( i.e. a MGS run).
Finally, we present an algorithm in exact arithmetic to model the loss of orthogonality in V. The procedure is as follows : we run MGS as usual but instead of stopping when encountering a breakdown, we introduce a vector and continue the MGS process. The vectors introduced at the breakdowns can be any vectors in Rem. We explain the foundation of this model, analyse properties of the set of vectors generated and correlate this model to existing results or experiments. Our algorithm has the advantage to be simple and expressed in exact arithmetic. From the theoretical point of view, it gives enlight to results on Least Squares problems and permits to developp new theory. For example, historically, it is using this model that the first results have been showed.

Date received: February 28, 2001

Copyright © 2001 by the author(s). The author(s) of this document and the organizers of the conference have granted their consent to include this abstract in Atlas Mathematical Conference Abstracts. Document # cagm-24.