CSE Colloquia: An Overview of Numerical Issues in Gram-Schmidt Orthogonalization

Abstract:
Gram-Schmidt algorithms factor a full column rank matrix X ∈ R^{m x n}, m ≥ n, into Q ∈ R^{m x n} and upper triangular R ∈ R^{m x n} such that X = QR and, in exact arithmetic, Q is left orthogonal, i.e, Q^T Q = I_n. Two versions are typically taught in undergraduate numerical analysis classes: classical Gram-Schmidt (CGS) and modified Gram-Schmidt (MGS). However, there are significant numerical issues with both algorithms. The most common applications for them are the implementation of iterative methods for solving large systems of linear equations and for problems where the decomposition in X = QR must be modified. These are applications where explicit representation of Q is necessary.

Even though the algorithms were first published in the 19th century, there are still issues surrounding these algorithms in modern computation. CGS is typically taught as an algorithm based upon matrix-vector operations whereas MGS is taught based upon only vector operations. That tends to make MGS the slower of the two algorithms, but MGS has much better numerical properties. Moreover, CGS requires reorthogonalization to be stable. It is shown how both algorithms can be generalized to become based upon matrix multiplication like operations making them more efficient on caching-based architectures and how their numerical properties can be maintained in these newer versions of the algorithms.

Bio:
Jesse L. Barlow is Professor Emeritus of Computer Science and Engineering at Pennsylvania State University. He was hired at Penn State after finishing his Ph.D. at Northwestern University in 1981. He has spent sabbaticals at New York University, the University of Manchester, City University of New York, and the University of California at Berkeley.
His work is primarily in numerical linear algebra with an emphasis on least squares and eigenvalue computations. In recent years, he has also worked on computational aspects of image processing.