5.3 Components of the Parallel Implementation

The major functional components of CSI-MSVD (refer to Figure 2) are

• MATVEC(i) - Assuming the matrix has been partitioned across p processors, this indicates the i-th process participating in matrix-vector multiplication for the Chebyshev semi-iterative method defined by Equation (11). Processes MATVEC(i), , are enrolled in a logical dynamic PVM group, MATVEC.
• PHI - The process that updates the array defined in Equation (24).
• GAMMA - The process that performs the bidiagonal QR-iteration to approximate the singular values of the current bidiagonal matrix in Equation (30).
• MAIN - The driver program that initializes parameters for CSI-MSVD and keeps track of deflation.

The processes MATVEC, PHI and GAMMA are pipelined so that MATVEC initiates the pipeline by sending moments to PHI. PHI then updates the bidiagonal matrix, and GAMMA, the third process in the pipeline, performs the QR-iteration with the updated bidiagonal matrix. As noted in Section 5.1, due to the accelerated computation of moments and the simplifications possible for the two-cyclic iteration (Section 3.1), the order of the matrix defined by Equation (24) and the bidiagonal matrix are independent of the problem size in practice. Hence, the computational workload in PHI and GAMMA may not be large enough to necessitate the parallelization of these components.

The load on processors involved in the MATVEC group, on the other hand, is dependent on the size of the input sparse matrix. It is quite possible that a single processor may not be able to satisfy the memory requirements of some large input matrices. Even if the matrix could be accommodated in a single processor's memory, it is desirable to partition a large matrix across multiple processors to exploit the distributed computation of the Chebyshev iteration [22].