Numerical algorithms for estimating least squares problems

The solution of least squares estimation problems is of great importance in the areas of numerical linear algebra, computational statistics and econometrics. The design and analysis of numerically stable and computationally efficient methods for solving such least squares problems is considered. The main computational tool used for the estimation of the least squares solutions is the QR decomposition, or the generalized QR decomposition. Specifically, emphasis is given to the design of sequential and parallel strategies for computing the main matrix factorizations which arise in the estimation procedures. The strategies are based on block-generalizations of the Givens sequences and efficiently exploit the structure of the matrices. An efficient minimum spanning tree algorithm is proposed for computing the QR decomposition of a set of matrices which have common columns. Heuristic strategies are also considered. Several computationally efficient sequential algorithms for block downdating of the least squares solutions are designed, implemented and analyzed. A parallel algorithm based on the best sequential approach for downdating the QR decomposition is also proposed. Within the context of block up-downdating, efficient serial and parallel algorithms for computing the estimators of the general linear and seemingly unrelated regression models after been updated with new observations are proposed. The algorithms are based on orthogonal factorizations and are rich in BLAS-3 computations. Experimental results which support the theoretical derived complexities of the new algorithms are presented. The comparison of the new algorithms with the corresponding LAPACK routines is also performed. The parallel algorithms utilize efficient load balanced distribution over the processors and are found to be scalable and efficient for large-scale least squares problems. It is expected that the proposed block-algorithms will facilitate the solution of computationally intensive statistical problems and the estimation of large scale linear models on serial and parallel computers.

Thèse de doctorat : Université de Neuchâtel, 2005 ; 1795