Orthogonal decomposition of dense and sparse matrices on multiprocessors
Eleanor Chu · 1988
In this thesis we propose a number of new parallel algorithms for performing orthogonal decomposition of dense and sparse square or rectangular matrices. Our target machines are shared-memory multiprocessors and local-memory hypercube multiprocessors. For dense matrices, we propose an algorithm for shared-memory multiprocessors, and several algorithms for the hypercube multiprocessors. For sparse matrices, the algorithm we propose is specific to hypercubes. The paradigms we use in developing these parallel algorithms include divide-and-conquer, changing the order of computation, asynchronous computation and redundant computation. The algorithms designed for the hypercubes take further advantage of various topological properties of the network. We provide arithmetic and communication complexity analyses or implementations for each algorithm to indicate their expected performance. In particular, our analyses show that the parallel algorithms we propose for QR decomposition of dense (square or rectangular) matrices have lower synchronization cost or lower communication cost than other known schemes. These results are supported by numerical experiments.