![]() | Only 14 pages are availabe for public view |
Abstract The general problem considered In this dissertation, is the efficient solution of the large least squares problems associated with linear systems of algebraic equations in which the coefficient matrix is expressed as the Kronecker product of two rectangular, real and dense matrices. Both the full rank and the rank deficient cases are trealed. An efficient method of solution based on QR factorizations of the original matrices is developed. The method utilizes the ”commutatively property” of Kronecker product to obtain better computational load balancing when implemented on a distributed memory computer. A parallel solution algorithm for the full rank case has been developed and implemented on a distributed memory computer using ScaLAP ACK linear algebra routines. A similar approach based on rank-revealing Q R (RRQR) factorization of the original matrices has been developed for the rank deficient case. RRQR factorizations are utilized to determine the numerical ranks of the original matrices and the numerical rank of their Kronecker product. The upper triangular matrices resulting from the RRQR factorizations are truncated to obtain upper trapezoidal matrices. A complete orthogonal decomposition is then performed on each of the upper trapezoidal matrices. These decompositions are used to obtain a complete orthogonal decomposition analogous to the Cholesky factorization of the least squares coefficient matrix which is expressed as the Kronecker product without explicitly forming the normal equation. A parallel algorithm based on the complete orthogonal decompositions has been developed for implementation on distributed memory computers. The parallel algorithms are presented, and timing results from test runs on an Intel ipsc/860 computer are show. |