PARALLEL GIVENS SEQUENCES FOR SOLVING THE GENERAL LINEAR MODEL ON A EREW PRAM∗

∗This work is in part supported by the Swiss National Foundation Grant 21-54109.98

Abstract

Parallel Givens sequences for solving the General Linear Model (GLM) are developed and analyzed. The block updating GLM estimation problem is also considered. The solution of the GLM employs as a main computational device the Generalized QR Decomposition, where one of the two matrices is initially upper triangular. The proposed Givens sequences efficiently exploit the initial triangular structure of the matrix and special properties of the solution method. The complexity analysis of the sequences is based on a Exclusive Read-Exclusive Write (EREW) Parallel Random Access Machine (PRAM) model with limited parallelism. Furthermore, the number of operations performed by a Givens rotation is determined by the size of the vectors used in the rotation. With these assumptions one conclusion drawn is that a sequence which applies the smallest number of compound disjoint Givens rotations to solve the GLM estimation problem does not necessarily have the lowest computational complexity. The various Givens sequences and their computational complexity analyses will be useful when addressing the solution of other similar factorization problems.

Keywords:

• General linear model
• QR decomposition
• Givens rotations
• Parallel algorithms
• EREW PRAM

Notes

∗This work is in part supported by the Swiss National Foundation Grant 21-54109.98

†Tel.: [phone]. Fax: [phone]. E-mail: [email protected].