Approximating Dominant Singular Triplets of Large Sparse Matrices via Modified Moments

Pafnuty L. Chebyshev (May 16 1821 - Dec 8 1894)

Sowmini Varadhan and
Michael W. Berry
Department of Computer Science
107 Ayres Hall
University of Tennessee
Knoxville, TN 37996-1301
varadhan@cs.utk.edu
berry@cs.utk.edu

Gene H. Golub,
Department of Computer Science,
Bldg. 460, Rm. 306
Stanford University
Stanford CA 94305
golub@cs.stanford.edu

To appear in Numerical Algorithms, 1996.

• Abstract
• 1. Introduction
  • 1.1 Singular Value Decomposition
  • 1.2 Related Eigenvalue Problems
  • 1.3 Candidate Methods for Sparse Matrices
  • 1.4 Orthogonal Polynomials and Modified Moments
  • 1.5 Focus and Organization
• 2. Derivation of CSI-MSVD Method
  • 2.1 Chebyshev Semi-Iterative Method
  • 2.2 Modified Moments and Orthogonal Polynomials
  • 2.3 Relation to the Eigenvalue Problem
  • 2.4 Modified Moments from the Chebyshev Semi-iterative Method
• 3. The CSI-MSVD Algorithm
  • 3.1 CSI-MSVD for Two-Cyclic Matrices
  • 3.2 CSI-MSVD for the Matrix A'A
  • 3.3 Parallel Program Flow
  • 3.4 Singular Vector Calculation
  • 3.5 Error Estimation for Singular Triplets
• 4. Computational Environments
  • 4.1 Performance Characterizations of CSI-MSVD
  • 4.2 Performance Evaluation of the Parallel Implementation
  • 4.3 Test Problems and Parameters
• 5. CSI-MSVD Performance Results
  • 5.1 Comparison with Lanczos Algorithm
  • 5.2 Preconditioner for Arnoldi's method
  • 5.3 Components of the Parallel Implementation
  • 5.4 Scalability
  • 5.5 Results of Cray T3D Implementation
• 6. Summary and Future Work
• References
• About this document ...

The first and second authors' research was supported by the National Science Foundation under grant Nos. NSF-ASC-92-03004 and NSF-ASC-94-11394.