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

3.1 CSI-MSVD for Two-Cyclic Matrices

Let M be in the form of a weakly cyclic matrix of index 2, defined in Equation (2). Partition the Chebyshev iterate into the vector and the vector , and the vector b from Equations (4) into the vector and the vector so that

Equation (11) can be re-written as

 

 

   

  
Figure 1: Updating the Chebyshev iterate.

The elements of successive iterates generated by Equations (26) and (27) are related by the dependency shown in Figure (1), so that choosing when forces . If denotes the iterate, then

 

Thus, at each step, only one of the Equations (26) and (27) needs to be computed, reducing the number of computations by a factor of two. Also, this new iteration requires only one initial vector approximation to as opposed to the two approximations ( and ) required for the general case.

The simplifications provided by Equation (28) also reduce the number of computations involved in the calculation of the coefficients of the Jacobi matrix in Equation (17). From Equations (28) and (22), it follows that , with , so that . It can be shown by induction that

 

which forces for all k. Hence, the only unknown quantities in the Jacobi matrix are the elements of the sub-diagonal, .

As demonstrated in [12], the eigenvalues of the Jacobi matrix are the same as the singular values of the matrix

 

The QR-iteration for bidiagonal matrices [7] may be applied to the matrix to obtain its singular values, thus approximating the singular values of the original matrix A.



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



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