ABSTRACT
Abstract . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 118 4.1 Introduction. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 118
4.1.1 Basics . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 118 4.1.2 Sensitivity of the Smallest Singular Value . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 120 4.1.3 Distance to Singularity — Pseudospectrum . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 122
4.2 Jacobi Methods for Dense Matrices . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 123 4.2.1 Two-Sided Jacobi Scheme [2JAC] . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 123 4.2.2 One-Sided Jacobi Scheme [1JAC] . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 127 4.2.3 Algorithm [QJAC] . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 130 4.2.4 Block-Jacobi Algorithms . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 132
4.3 Methods for Large and Sparse Matrices . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 133 4.3.1 Sparse Storages and Linear Systems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 133 4.3.2 Subspace Iteration [SISVD] . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 134 4.3.3 Lanczos Methods . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 136
4.3.3.1 The Single-Vector Lanczos Method [LASVD] . . . . . . . . . . . . . . . . . . . . . . . . 136 4.3.3.2 The Block Lanczos Method [BLSVD] . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 138
4.3.4 The Trace Minimization Method [TRSVD] . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 140 4.3.4.1 Polynomial Acceleration Techniques for [TRSVD] . . . . . . . . . . . . . . . . . . . 142 4.3.4.2 Shifting Strategy for [TRSVD] . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 143
4.3.5 Refinement of Left Singular Vectors . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 144 4.3.6 The Davidson Methods . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 147
4.3.6.1 General Framework of the Methods . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 147 4.3.6.2 How Do the Davidson Methods Differ? . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 149 4.3.6.3 Application to the Computation of the Smallest Singular Value . . . . . . . 151
4.4 Parallel Computation for Sparse Matrices . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 152 4.4.1 Parallel Sparse Matrix-Vector Multiplications . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 152 4.4.2 A Parallel Scheme for Basis Orthogonalization . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 154 4.4.3 Computing the Smallest Singular Value on Several Processors . . . . . . . . . . . . . . . . . 156
4.5 Application: Parallel Computation of a Pseudospectrum . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 157 4.5.1 Parallel Path-Following Algorithm Using Triangles . . . . . . . . . . . . . . . . . . . . . . . . . . . 157 4.5.2 Speedup and Efficiency . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 158 4.5.3 Test Problems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 159
References . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 160
The goal of the survey is to review the state-of-the-art of computing the singular value decomposition (SVD) of dense and sparse matrices, with some emphasis on those schemes that are suitable for parallel computing platforms. For dense matrices, we present those schemes that yield the complete decomposition, whereas for sparse matrices we describe schemes that yield only the extremal singular triplets. Special attention is devoted to the computation of the smallest singular values which are normally the most difficult to evaluate but which provide a measure of the distance to singularity of the matrix under consideration. Also, we conclude with the presentation of a parallel method for computing pseudospectra, which depends on computing the smallest singular values.
