Berry and Golub in [2] have shown the effectiveness of
the scheme proposed in [10] through an implementation on
the Cray Y-MP that
approximates singular values of a sparse matrix **A** from the
eigenvalues of the corresponding two-cyclic matrix **C** defined by
Equation (2). They also point out that the potential
asynchronous computation of orthogonal polynomials with the
iterations of an adaptive Chebyshev semi-iterative method allows
multiple processors to execute different sections of the algorithm in
parallel. Thus, there is more inherent scope for parallelism with this
scheme than with Lanczos algorithms. Also, the recurrence relations
defining the Chebyshev polynomials allow an accelerated construction
of the moments so that singular values can be approximated in a
few number of iterations.

The implementation proposed in [2] describes a scheme to approximate singular values only, i.e., singular vectors are not estimated. The tridiagonal Jacobi matrix is constructed to approximate, through its eigenvalues, the roots of the characteristic equation. Moreover, while recurrence relations may be used to accelerate the construction of modified moments from the Chebyshev iterates, there is no known scheme to obtain the converse result, i.e., to approximate the Chebyshev iterates (and thus the singular vectors) from the moments. The absence of singular vector (or eigenvector) approximations gives rise to problems such as the lack of an error estimate on the approximated singular value (or eigenvalue) and inefficient deflation schemes. Due to these problems, there has been no robust, complete implementation of this algorithm, in spite of its theoretical efficiency and suitability for parallel computers.

Michael W. Berry (berry@cs.utk.edu)

Sun May 19 11:34:27 EDT 1996