Volume 31, pp. 68-85, 2008.

A robust and efficient parallel SVD solver based on restarted Lanczos bidiagonalization

Vicente Hernández, José E. Román, and Andrés Tomás

Abstract

Lanczos bidiagonalization is a competitive method for computing a partial singular value decomposition of a large sparse matrix, that is, when only a subset of the singular values and corresponding singular vectors are required. However, a straightforward implementation of the algorithm has the problem of loss of orthogonality between computed Lanczos vectors, and some reorthogonalization technique must be applied. Also, an effective restarting strategy must be used to prevent excessive growth of the cost of reorthogonalization per iteration. On the other hand, if the method is to be implemented on a distributed-memory parallel computer, then additional precautions are required so that parallel efficiency is maintained as the number of processors increases. In this paper, we present a Lanczos bidiagonalization procedure implemented in SLEPc, a software library for the solution of large, sparse eigenvalue problems on parallel computers. The solver is numerically robust and scales well up to hundreds of processors.

Full Text (PDF) [195 KB], BibTeX

Key words

Partial singular value decomposition, Lanczos bidiagonalization, thick restart, parallel computing.

AMS subject classifications

65F15, 15A18, 65F50.

< Back