next up previous
Next: Focus and Organization Up: Introduction Previous: Candidate Methods for

1.4 Orthogonal Polynomials and Modified Moments

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