Volume 43, pp. 163-187, 2014-2015.

Block Gram-Schmidt downdating

Jesse L. Barlow

Abstract

Given positive integers $m$, $n$, and $p,$ where $m\ge n+p$ and $p\ll n$. A method is proposed to modify the QR decomposition of $X\in {\mathbb{R}}^{m\times n}$ to produce a QR decomposition of $X$ with $p$ rows deleted. The algorithm is based upon the classical block Gram-Schmidt method, requires an approximation of the norm of the inverse of a triangular matrix, has $\mathcal{O}(mnp)$ operations, and achieves an accuracy in the matrix 2-norm that is comparable to similar bounds for related procedures for $p=1$ in the vector 2-norm. Since the algorithm is based upon matrix-matrix operations, it is appropriate for modern cache oriented computer architectures.

Full Text (PDF) [270 KB], BibTeX

Key words

QR decomposition, singular value decomposition, orthogonality, downdating, matrix-matrix operations.

AMS subject classifications

65F25, 65F20, 65F35