next up previous
Next: Singular Vector Calculation Up: The CSI-MSVD Algorithm Previous: CSI-MSVD for the

3.3 Parallel Program Flow

  Unless otherwise stated, further references to CSI-MSVD in this paper reflect the use of 2-cyclic iteration matrices as defined in Equation (2). The three main steps that constitute the CSI-MSVD algorithm are:
  1. calculation of the CSI-iterate using Equations (26) and (27),  
  2. calculation of the new moments for the current iterate, and  
  3. updating the bidiagonal matrix and approximating the eigenvalues of the two-cyclic iteration matrix through the QR-iteration.  

  
Figure 2: A single pass of two-cyclic CSI-MSVD.

Figure 2 shows the dependencies involved in the steps of the above outlined procedure. The pipelined nature of the computation indicates that Steps 1, 2, and 3 described could be carried out concurrently. For example, the computation of the anti-diagonal elements (shown in the box labeled PHI in Figure 2) could be overlapped with the computation of the iterates and . Also, when the bidiagonal matrix has been updated with the elements and (the box labeled GAMMA) by using Equation (25), the approximation of eigenvalues through the bidiagonal-QR iteration could be done in parallel with the computation of the next anti-diagonal elements (, k+l=8 or k+l=10). Thus, the three functional components MATVEC, PHI, and GAMMA could be executed on three different processors. Information about the two-cyclic matrix M of Equation (2) is required only for the computations in MATVEC, so that the implementations of PHI and GAMMA is independent of the format used for storing the matrix.



Michael W. Berry (berry@cs.utk.edu)
Sun May 19 11:34:27 EDT 1996