Isoefficiency Analysis of CGLS Algorithm for Parallel Least Squares Problems

摘要

In this paper we study the parallelization of CGIS, a basic iterative method for large and sparse least squares problem whose main idea is to organize the computation of conjugate gradient method to normal equations. A performance model called isoefficiency concept is used to analyze the behavior of this method implemented on massively parallel distributed memory computers with two dimensional mesh communication scheme. Two different mappings of data to processors, namely simple stripe and cyclic stripe partitionings are compared by putting these communication times into the isoefficiency concenpt which models scalalbiltiy aspects. Theoretically, the cyclic stripe partitioning is shown to be asymptotically more scalable.