CAM Seminar

March 6, 2019




Jesse L. Barlow, the University of Pennsylvania.


Title: BLOCK MODIFIED GRAM-SCHMIDT ALGORITHMS.

Abstract: New block modified Gram-Schmidt (BMGS) methods for the Q-R factorization of a full column rank matrix \( X \in \mathbb{R}^{m \times n} \), \(m \geq n\), are considered. Such methods factor \(X\) into \(Q \in \mathbb{R}^{m \times n}\) and an upper triangular \(R \in \mathbb{R}^{m \times n}\) such that $$X = QR$$ where, in exact arithmetic, \(Q\) is left orthogonal (i.e., \(Q^T\!~Q=I_n\)). Gram-Schmidt based algorithms play an important role in the implementation of Krylov space methods such as GMRES, Arnoldi, and Lanczos. To design such BMGS algorithms, we build upon the block Householder representation of Schreiber and Van Loan and an observation by Charles Sheffield analyzed by Paige about the relationship between modified Gram-Schmidt and Householder QR factorization. Our new BMGS algorithms exploit the Sheffield framework so that they share a similar relationship to Householder Q-R and thus have similar error analysis properties to modified Gram-Schmidt.

The last BMGS algorithm developed is based entirely upon matrix multiplications and the ''tall, skinny'' Q-R (TSQR) factorization---two operations that have been studied extensively for cache-based architectures and distributed architectures. It is shown that if the TSQR part of the BMGS algorithm satisfies error analysis properties connected to the Sheffield structure, then so does the entire BMGS algorithm. Thus a new criteria for when a BMGS algorithm has similar error analysis properties to MGS is proposed.





CAM Seminar Spring 2019