Accession Number:

ADA229501

Title:

Solving Least Squares Problems on Distributed Memory Machines

Descriptive Note:

Technical rept.

Corporate Author:

PENNSYLVANIA STATE UNIV UNIVERSITY PARK APPLIED RESEARCH LAB

Personal Author(s):

Report Date:

1990-12-01

Pagination or Media Count:

99.0

Abstract:

We consider solving unconstrained least squares and equality constrained least squares problems on distributed memory multi-processors. First, we examine some issues related to matrix computations in general, on such architectures. We then describe three different algorithms to compute an orthogonal factorization of a matrix on a multi-processor, which are well suited for dense matrices. As for sparse matrices, efficient solution of problems involving large, sparse matrices on distributed memory multi-processors calls for the use of static data structures. Often, at the same time, it is critical to detect the rank of a matrix during the factorization to accurate results. We describe a rank detection strategy, using an incremental condition estimator, that computes a factorization using pre-determined static data structure. We present experimental evidence to show that the accuracy of the rank detection algorithm is comparable to the column pivoting and another recent procedure by Bischof. We further demonstrate that the algorithm is quite suitable for parallel sparse matrix factorizations, by showing good speed-ups on a hypercube with up to 128 processors. We use this algorithm to detect the rank of the constraint matrix in solving the equality constrained least squares problem. We use the weighting approach to solve the equality constrained least square problem, with two iterations of modified deferred correction technique, to improve the accuracy of the original solution. KR

Subject Categories:

  • Numerical Mathematics
  • Computer Hardware

Distribution Statement:

APPROVED FOR PUBLIC RELEASE