Timing the Singular Value Decomposition

A separate input file drives the timing codes for the Singular Value Decomposition (SVD). The input file specifies

• pairs of parameter values (M, N) specifying the matrix row dimension M and the matrix column dimension N
• pairs of parameter values (NB, LDA) specifying the block size NB and the leading dimension LDA
• the test matrix types
• the routines or sequences of routines from LAPACK or LINPACK to be timed.

A goal of this timing code is to determine the values of NB which maximize the speed of the block algorithms.

The number and size of the input values are limited by certain program maximums which are defined in PARAMETER statements in the main timing program:

569#569

The computations that may be timed for the REAL version are

1. SGEBRD (LAPACK reduction to bidiagonal form)
2. SBDSQR (LAPACK computation of singular values only of a bidiagonal matrix)
3. SBDSQR(L) (LAPACK computation of the singular values and left singular vectors of a bidiagonal matrix)
4. SBDSQR(R) (LAPACK computation of the singular values and right singular vectors of a bidiagonal matrix)
5. SBDSQR(B) (LAPACK computation of the singular values and right and left singular vectors of a bidiagonal matrix)
6. SBDSQR(V) (LAPACK computation of the singular values and multiply square matrix of dimension min(M,N) by transpose of left singular vectors)
7. LAPSVD (LAPACK singular values only of a dense matrix, using SGEBRD and SBDSQR)
8. LAPSVD(l) (LAPACK singular values and min(M,N) left singular vectors of a dense matrix, using SGEBRD, SORGBR and SBDSQR(L))
9. LAPSVD(L) (LAPACK singular values and M left singular vectors of a dense matrix, using SGEBRD, SORGBR and SBDSQR(L))
10. LAPSVD(R) (LAPACK singular values and N right singular vectors of a dense matrix, using SGEBRD, SORGBR and SBDSQR(R))
11. LAPSVD(B) (LAPACK singular values, min(M,N) left singular vectors, and N right singular vectors of a dense matrix, using SGEBRD, SORGBR and SBDSQR(B))
12. SBDSDC(B) (LAPACK singular values and left and right singular vectors; assume original matrix min(M,N) by min(M,N))
13. SGESDD(B) (LAPACK singular values and min(M,N) left singular vectors and N right singular vectors if 570#570, singular values and M left singular vectors and min(M,N) right singular vectors otherwise.)
14. LINSVD (LINPACK singular values only of a dense matrix using SSVDC, to be compared to LAPSVD)
15. LINSVD(l) (LINPACK singular values and min(M,N) left singular vectors of a dense matrix using SSVDC, to be compared to LAPSVD(l))
16. LINSVD(L) (LINPACK singular values and M left singular vectors of a dense matrix using SSVDC, to be compared to LAPSVD(L))
17. LINSVD(R) (LINPACK singular values and N right singular vectors of a dense matrix using SSVDC, to be compared to LAPSVD(R))
18. LINSVD(B) (LINPACK singular values, min(M,N) left singular vectors and N right singular vectors of a dense matrix using SSVDC, to be compared to LAPSVD(B)).

Five different matrix types are provided for timing the singular value decomposition routines. Matrix types 1-3 are of the form 489#489, where 132#132 and 245#245 are orthogonal or unitary, and 282#282 is diagonal with entries

• evenly spaced entries from 1 down to 9#9 with random signs (matrix type 1),
• geometrically spaced entries from 1 down to 9#9 with random signs (matrix type 2), or
• ``clustered'' entries 557#557 with random signs (matrix type 3).

Matrix type 4 has in each entry a random number drawn from 571#571. Matrix type 5 is a nearly bidiagonal matrix, where the upper bidiagonal entries are 572#572 and the nonbidiagonal entries are 573#573, where 574#574 is a uniform random number drawn from 575#575 (a different 574#574 for each entry).

An annotated example of an input file for timing the REAL singular value decomposition routines is shown below.

SVD:  Data file for timing Singular Value Decomposition routines
7                               Number of values of M and N
10 10 20 20 20 40 40            Values of M (row dimension)
10 20 10 20 40 20 40            Values of N (column dimension)
1                               Number of values of parameters
1                               Values of NB (blocksize)
81                              Values of LDA (leading dimension)
0.05                            Minimum time in seconds
4                               Number of matrix types
1 2 3 4
SBD    T T T T T T T T T T T T T T T T T T

The first line of the input file must contain the characters SVD in columns 1-3. Lines 2-9 are read using list-directed input and specify the following values:

576#576

If 0 577#577, then line 9 specifies NTYPES integer values which are the numbers of the matrix types to be used. The remaining lines specify a path name and the specific computations to be timed. For the SVD, the path names for the four data types are SBD, DBD, CBD, and ZBD. The (optional) characters after the path name indicate the computations to be timed, as in the input file for the nonsymmetric eigenvalue problem.