Ordinary linear model estimation on a massively parallel SIMD computer

Efficient algorithms for estimating the coefficient parameters of the ordin ary linear model on a massively parallel SIMD computer are presented. The n umerical stability of the algorithms is ensured by using orthogonal transfo rmations in the form of Householder reflections and Givens plane rotations to compute the complete orthogonal decomposition of the coefficient matrix, Algorithms for reconstructing the orthogonal matrices involved in the deco mpositions are also designed, implemented and analyzed, The implementation of all algorithms on the targeted SIR ID array processor is considered in d etail. Timing models for predicting the execution time of the implementatio ns are derived using regression modelling methods. The timing models also p rovide an insight into how the algorithms interact with the parallel comput er, The predetermined factors used in the regression fits are derived from the number of memory layers involved in the factorization process of the ma trices. Experimental results show the high accuracy and predictive power of the timing models. (C) 1999 John Wiley & Sons, Ltd.