Block Parallel Algorithms For Solving The General Linear Model

The General Linear Model (GLM) is the parent model of econometrics. Simultaneous equations and seemingly unrelated regression equation (SURE) models, to name but a few, can be formulated as a GLM. The estimation of the GLM can be viewed as a Generalized Linear Least-Squares problem (GLLSP). The solution of the GLLSP has been considered extensively. Serial algorithms have been proposed and numerical libraries such as LAPACK and ScALAPACK provide routines for solving the GLLSP using the generalized QR decomposition. These routines are efficient only when the matrices in the GLLSP are fully dense. However, in most cases one of the matrices corresponds to the triangular Cholesky factor of the disturbance's variance-covariance matrix.Indeed, the efficient serial algorithm, which is based on Givens rotations, exploits the triangular structure of the matrix. A parallel version of the serial Givens algorithm has shown that only in a few, extreme cases can it outperform the straightforward Householder algorithm, which ignores the structure of the matrices.In this paper, we propose block-updating algorithms for solving the GLLSP when one of the matrices has a triangular structure. The algorithms use Householder transformations, which are found to be efficient with contemporary parallel computers. The theoretical computational complexity of the algorithms, which is useful in evaluating the performance of parallel implementations, is derived. Extensions of the algorithms to SURE models are discussed.