The linear least-squares problem in statistics is usually solved by finding the Cholesky factor of the matrix of normal equations. In certain applications, one wants to solve several related problems formed by removing and/or adding data. In this case, the algorithm presented here uses the previous Cholesky factor in constructing the new factor. Adding new samples can be easily handled using the ordinary Householder matrices [1]. Removing data, however, can result in a reduction of the rank. This algorithm uses methods described by Stewart and Stewart [2], who show how the removal or down-dating can be done in a numerically stable manner using hyperbolic Householder transformations.

The authors describe their method as an “algorithm-by-blocks,” where a matrix is seen as a collection of submatrices. Each block becomes a unit of data and each computation with a block becomes a unit of computation. The implementation is coded in this style so that the code defines the organization of both the data and the computation. From this code, runtime software can analyze and schedule the computation for execution on a multi-processor platform. This runtime software has been developed as part of the FLAME project at the University of Texas. Details of this coding and analysis are reported in [3]. The algorithm-by-blocks has a slightly higher operation count than other implementations, and the authors show results from the tests on a multicore shared memory system. The threading of their routine is at the block level, and each block operation is done using a sequential version of the GotoBLAS2 library. The authors compare their implementation to a threaded implementation of the LAPACK QR routine.