Parallel Algorithms for Linear Models

by Kontoghiorghes, Erricos John

• ISBN13: 9780792377207
• ISBN10: 0792377206
• Format: Hardcover
• Copyright: 1999-12-01
• Publisher: Kluwer Academic Pub

Summary

Parallel Algorithms for Linear Models provides a complete and detailed account of the design, analysis and implementation of parallel algorithms for solving large-scale linear models. It investigates and presents efficient, numerically stable algorithms for computing the least-squares estimators and other quantities of interest on massively parallel systems. The monograph is in two parts. The first part consists of four chapters and deals with the computational aspects for solving linear models that have applicability in diverse areas. The remaining two chapters form the second part, which concentrates on numerical and computational methods for solving various problems associated with seemingly unrelated regression equations (SURE) and simultaneous equations models. The practical issues of the parallel algorithms and the theoretical aspects of the numerical methods will be of interest to a broad range of researchers working in the areas of numerical and computational methods in statistics and econometrics, parallel numerical algorithms, parallel computing and numerical linear algebra. The aim of this monograph is to promote research in the interface of econometrics, computational statistics, numerical linear algebra and parallelism.

Table of Contents

List of Figures	ix
List of Tables	xi
List of Algorithms	xiii
Preface	xv
Linear Models and Qr Decomposition	1	(38)
Introduction	1	(1)
Linear model specification	1	(9)
The ordinary linear model	2	(5)
The general linear model	7	(3)
Forming the QR decomposition	10	(7)
The Householder method	11	(2)
The Givens rotation method	13	(3)
The Gram-Schmidt orthogonalization method	16	(1)
Data parallel algorithms for computing the QR decomposition	17	(6)
Data parallelism and the MasPar SIMD system	17	(2)
The Householder method	19	(2)
The Gram-Schmidt method	21	(1)
The Givens roatation method	22	(1)
Computational results	23	(1)
QRD of large and skinny matrices	23	(6)
The CPP GAMMA SIMD system	24	(1)
The Householder QRD algorithm	25	(2)
QRD of skinny matrices	27	(2)
QRD of a set of matrices	29	(10)
Equal size matrices	29	(5)
Matrices with different number of columns	34	(5)
Olm Not of Full Rank	39	(18)
Introduction	39	(1)
The QLD of the coefficient matrix	40	(3)
SIMD implementation	41	(2)
Triangularizing the lower trapezoid	43	(6)
The Householder method	43	(3)
The Givens method	46	(3)
Computing the orthogonal matrices	49	(5)
Discussion	54	(3)
Updating and Downdating the Olm	57	(48)
Introduction	57	(1)
Adding observations	58	(32)
The hybrid Householder algorithm	60	(7)
The Bitonic and Greedy Givens sequences	67	(8)
Updating with a block lower-triangular matrix	75	(7)
QRD of structured banded matrices	82	(5)
Recursive and linearly constrained least-squares	87	(3)
Adding exogenous varibales	90	(2)
Deleting observations	92	(7)
Parallel strategies	94	(5)
Deleting exogenous variables	99	(6)
The General Linear Model	105	(12)
Introduction	105	(3)
Parallel algorithms	108	(3)
Implementation and performance analysis	111	(6)
Sure Models	117	(30)
Introduction	117	(4)
The generalized linear least squares method	121	(2)
Triangular SURE models	123	(6)
Implementation aspects	127	(2)
Covariance restrictions	129	(18)
The QLD of the block bi-diagonal matrix	133	(5)
Parallel strategies	138	(2)
Common exogenous variables	140	(7)
Simultaneous Equations Models	147	(16)
Generalized linear least squares	149	(5)
Estimating the disturbance covariance matrix	151	(1)
Redundancies	152	(1)
Inconsistencies	153	(1)
Modifying the SEM	154	(3)
Linear Equality Constraints	157	(3)
Basis of the null space and direct elimination methods	158	(2)
Computational Strategies	160	(3)
References	163	(14)
Author Index	177	(2)
Subject Index	179