Timing the Nonsymmetric Eigenproblem

A separate input file drives the timing codes for the nonsymmetric eigenproblem. The input file specifies

• N, the matrix size
• four-tuples of parameter values (NB, NS, MAXB, LDA) specifying the block size NB, the number of shifts NS, the matrix size MAXB less than which an unblocked routine is used, and the leading dimension LDA
• the test matrix types
• the routines or sequences of routines from LAPACK or EISPACK to be timed

The parameters NS and MAXB apply only to the QR iteration routine xHSEQR, and NB is used only by the block algorithms. A goal of this timing code is to determine the values of NB, NS and MAXB which maximize the speed of the codes.

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:

555#555

The computations that may be timed for the REAL version are

1. SGEHRD (LAPACK reduction to upper Hessenberg form)
2. SHSEQR(E) (LAPACK computation of eigenvalues only of a Hessenberg matrix)
3. SHSEQR(S) (LAPACK computation of the Schur form of a Hessenberg matrix)
4. SHSEQR(V) (LAPACK computation of the Schur form and Schur vectors of a Hessenberg matrix)
5. STREVC(L) (LAPACK computation of the the left eigenvectors of a matrix in Schur form)
6. STREVC(R) (LAPACK computation of the the right eigenvectors of a matrix in Schur form)
7. SHSEIN(L) (LAPACK computation of the the left eigenvectors of an upper Hessenberg matrix using inverse iteration)
8. SHSEIN(R) (LAPACK computation of the the right eigenvectors of an upper Hessenberg matrix using inverse iteration)
9. ORTHES (EISPACK reduction to upper Hessenberg form, to be compared to SGEHRD)
10. HQR (EISPACK computation of eigenvalues only of a Hessenberg matrix, to be compared to SHSEQR(E))
11. HQR2 (EISPACK computation of eigenvalues and eigenvectors of a Hessenberg matrix, to be compared to SHSEQR(V) plus STREVC(R))
12. INVIT (EISPACK computation of the right eigenvectors of an upper Hessenberg matrix using inverse iteration, to be compared to SHSEIN(R)).

Eight different matrix types are provided for timing the nonsymmetric eigenvalue routines. A variety of matrix types is allowed because the number of iterations to compute the eigenvalues, and hence the timing, can depend on the type of matrix whose eigendecomposition is desired. The matrices used for timing are of the form 128#128 where 98#98 is either orthogonal (for types 1-4) or random with condition number 556#556 (for types 5-8), where 9#9 is the machine roundoff error. The matrix 85#85 is upper triangular with random 124#124 entries in the strict upper triangle and has on its diagonal

• evenly spaced entries from 1 down to 9#9 with random signs (matrix types 1 and 5)
• geometrically spaced entries from 1 down to 9#9 with random signs (matrix types 2 and 6)
• ``clustered'' entries 557#557 with random signs (matrix types 3 and 7), or
• real or complex conjugate paired eigenvalues randomly chosen from the interval 558#558 (matrix types 4 or 8).

An annotated example of an input file for timing the REAL nonsymmetric eigenproblem routines is shown below.

NEP:  Data file for timing Nonsymmetric Eigenvalue Problem routines
4                               Number of values of N
10 20 30 40                     Values of N (dimension)
4                               Number of values of parameters
1   1   1   1                   Values of NB (blocksize)
2   4   6   2                   Values of NS (number of shifts)
12  12  12  50                  Values of MAXB (multishift crossover pt)
81  81  81  81                  Values of LDA (leading dimension)
0.05                            Minimum time in seconds
4                               Number of matrix types
1 3 4 6 
SHS    T T T T T T T T T T T T

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

559#559

If 0 560#560, then line 11 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 nonsymmetric eigenvalue problem, the path names for the four data types are SHS, DHS, CHS, and ZHS. A line to request all the routines in the REAL path has the form

SHS   T T T T T T T T T T T T

where the first 3 characters specify the path name, and up to 12 nonblank characters may appear in columns 4-80. If the 561#561 such character is `T' or `t', the 561#561 routine will be timed. If at least one but fewer than 12 nonblank characters are specified, the remaining routines will not be timed. If columns 4-80 are blank, all the routines will be timed, so the input line

SHS

is equivalent to the line above.

The output is in the form of a table which shows the absolute times in seconds, floating point operation counts, and megaflop rates for each routine over all relevant input parameters. For the blocked routines, the table has one line for each different value of NB, and for the SHSEQR routine, one line for each different combination of NS and MAXB as well.