NESC0534 EISPACK-3.

1. NAME OR DESIGNATION OF PROGRAM:  EISPACK-3.

3. DESCRIPTION OF PROBLEM OR FUNCTION

EISPACK3 is a collection of 75  FORTRAN subroutines, both single- and double-precision, that compute the eigenvalues and eigenvectors of nine classes of matrices. The package can determine the eigensystem of complex general, complex Hermitian, real general, real symmetric, real symmetric band, real symmetric tridiagonal, special real tridiagonal, generalized real, and generalized real symmetric matrices. In addition, there are two  routines which use the singular value decomposition to solve certain least squares problem. The individual subroutines are -

IDENTIFICATION   DESCRIPTION

BAKVEC       Back transform vectors of matrix formed by FIGI

BALANC       Balance a real general matrix

BALBAK       Back transform vectors of matrix formed by BALANC

BANDR        Reduce sym. band matrix to sym. tridiag. matrix

BANDV        Find some vectors of sym. band matrix

BISECT       Find some values of sym. tridiag. matrix

BQR          Find some values of sym. band matrix

CBABK2       Back transform vectors of matrix formed by CBAL

CBAL         Balance a complex general matrix

CDIV         Perform division of two complex quantities

CG           Driver subroutine for a complex general matrix

CH           Driver subroutine for a complex Hermitian matrix

CINVIT       Find some vectors of complex Hess. matrix

COMBAK       Back transform vectors of matrix formed by COMHES

COMHES       Reduce complex matrix to complex Hess. (elementary)

COMLR        Find all values of complex Hess. matrix (LR)

COMLR2       Find all values/vectors of cmplx Hess. matrix (LR)

CCMQR        Find all values of complex Hessenberg matrix (QR)

COMQR2       Find all values/vectors of cmplx Hess. matrix (QR)

CORTB        Back transform vectors of matrix formed by CORTH

CORTH        Reduce complex matrix to complex Hess. (unitary)

CSROOT       Find square root of complex quantity

ELMBAK       Back transform vectors of matrix formed by ELMHES

ELMHES       Reduce real matrix to real Hess. (elementary)

ELTRAN       Accumulate transformations from ELMHES (for HQR2)

EPSLON       Estimate unit roundoff relative to argument size

FIGI         Reduce nonsym. tridiag. matrix to sym. tridiag.

FIGI2        Reduce nonsym. tridiag. matrix to sym. tridiag.

HQR          Find all values of real Hess. matrix

HQR2         Find all values/vectors for real Hess. matrix

HTRIBK       Back transform vectors of matrix formed by HTRIDI

HTRIB3       Back transform vectors of matrix formed by HTRID3

HTRIDI       Reduce Hermitian matrix to sym. tridiag.

HTRID3       Reduce Hermitian packed matrix to sym. tridiag.

IMTQLV       Find all values of sym. tridiag. matrix

IMTQL1       Find all values of sym. tridiag. matrix

IMTQL2       Find all values/vectors of sym. tridiag. matrix

INVIT        Find some vectors of real Hess. matrix

MINFIT       Singular value decomposition & least squares soln.

ORTBAK       Back transform vectors of matrix formed by ORTHES

ORTHES       Reduce real matrix to real Hess. (orthogonal)

ORTRAN       Accumulate transformations from ORTHES (for HQR2)

PYTHAG       Find square root of sum of squares of two quantities

QZHES        Reduce real generalized matrix system

QZIT         Further reduce real generalized matrix system

QZVAL        Find all values of reduced real generalized system

QZVEC        Find all vectors of real generalized matrix system

RATQR        Find extreme values of sym. tridiag. matrix

REBAK        Back transform vectors of matrix formed by REDUC

REBAKB       Back transform vectors of matrix formed by REDUC2

REDUC        Reduce sym. generalized matrix system to standard

REDUC2       Reduce sym. generalized matrix system to standard

RG           Driver subroutine for a real general matrix

RGG          Driver subroutine for a real generalized system

RS           Driver subroutine for a real sym. matrix

RSB          Driver subroutine for a real sym. band matrix

RSG          Driver subroutine for real sym. generalized system

RSGAB        Driver subroutine for real sym. generalized system

RSGBA        Driver subroutine for real sym. generalized system

RSM          Driver subroutine for a real symmetric matrix

RSP          Driver subroutine for a real sym. packed matrix

RST          Driver subroutine for a real sym. tridiag. matrix

RT           Driver subroutine for a nonsym. tridiag. matrix

SVD          Singular value decomposition of rectangular matrix

TINVIT       Find some vectors of sym. tridiag. matrix

TQLRAT       Find all values of sym. tridiag. matrix

TQL1         Find all values of sym. tridiag. matrix

TQL2         Find all values/vectors of sym. tridiag. matrix

TRBAK1       Back transform vectors of matrix formed by TRED1

TRBAK3       Back transform vectors of matrix formed by TRED3

TRED1        Reduce sym. matrix to sym. tridiag. matrix

TRED2        Reduce sym. matrix to sym. tridiag. matrix

TRED3        Reduce sym. packed matrix to sym. tridiag. matrix

TRIDIB       Find some values of sym. tridiag. matrix

TSTURM       Find some values/vectors of sym. tridiag. matrix

4. METHOD OF SOLUTION

Almost all the algorithms used in EISPACK are based on similarity transformations. Similarity transformations based on orthogonal and unitary matrices are particularly attractive from a numerical point of view because they do not magnify any errors present in the input data or introduced during the computation. Most of the techniques employed are constructive realizations of variants of Schur's theorem, 'Any matrix can be triangularized by a unitary similarity transformation'. It is usually not possible to compute Schur's transformation with a finite number of rational arithmetic operations. Instead, the algorithms employ a potentially infinite sequence of similarity transformations in which the resultant matrix approaches an upper triangular matrix. The sequence is terminated when all of the subdiagonal elements of the resulting matrix are less than the roundoff errors involved in the computation. The diagonal elements are then the desired approximations to the eigenvalues of the original matrix and the corresponding eigenvectors can be calculated. Special algorithms deal with symmetric matrices. QR, LR, QL, rational QR, bisection QZ, and inverse iteration methods are used.

5. RESTRICTIONS ON THE COMPLEXITY OF THE PROBLEM:

6. TYPICAL RUNNING TIME

Running time varies and detailed information  appears in reference 2 and 3. The amount of time required to run the sample cases is small. On the IBM3033 NESC executed each of the  sample cases in from 2 to 10 CPU seconds.

7. UNUSUAL FEATURES OF THE PROGRAM

The IBM3090VF version is tailored  to take advantage of the machine's high-speed vector registers and cache.

8. RELATED AND AUXILIARY PROGRAMS

The subroutines are based mainly on the ALGOL procedures published by Wilkinson and Reinsch in Volume II of the Springer-Verlag Handbook series and the QZ algorithm of Moler and Stewart.

10. REFERENCES

- J.H. Wilkinson and C. Reinsch,
  Handbook for Automatic Computation, Volume II, Linear Algebra,
  Springer-Verlag,
  New York, Heidelberg, Berlin, 1971.
- B.T. Smith, J.M. Boyle, J.J. Dongarra, B.S. Garbow, Y. Ibeke,
  V.C. Klema, and C.B. Moler,
  Matrix Eigensystem Routines-EISPACK Guide,
  Lecture Notes in Computer Science, Volume 6 2nd Edition, G. Goos
  and J. Hartmanis, Springer-Verlag, New York, Heidelberg, Berlin,
  1976.
- B.S. Garbow, J.M. Boyle, J.J. Dongarra, and C.B. Moler,
  Matrix Eigensystem Routine-EISPACK Guide Extension,
  Lecture Notes in Computer Science, Volume 51, G. Goos and
J. Hartmanis, Springer-verlag, Berlin, Heidelberg, New York, 1977.  - C.B. Moler and G.W. Stewart,
  An Algorithm for Generalized Matrix Eigenvalue Problems,
  SIAM Journal of Numerical Analysis, Vol. 10, pp. 241-256, 1973.

- J.J. Dongarra and C.B. Moler:
  EISPACK-3 A Package for Solving Matrix Eigenvalue Problems.
  ANL/MCS-TM-12  Rev. April 1984
- J.J. Dongarra and B.S. Garbow:
  Instruction for Installation and Use of Release 2 of EISPACK.
  (April 1976)
- Notes - Eigensystem Package Path Chart (Release 2).
- Note on EISPACK Demonstration Output.
- J.J. Dongarra and C.B. Moler:
  EISPACK-3 A Package for Solving Matrix Eigenvalue Problems
  ANL/MCS-TM-12 (August 1983) Rev. (April 1984).
- A. Kaylor Cline and J. Meyering:
  Converting EISPACK to Run Efficiently on a Vector Processor
  (February 17, 1989).

11. MACHINE REQUIREMENTS

Vary according to usage. Previous releases of EISPACK used two machine-dependent parameters, RADIX and MACHEP.  In EISPACK3 the relative precision of floating-point arithmetic parameter, MACHEP, has either been eliminated or replaced by the EPSLON function, which returns an estimate of the roundoff unit  relative to the size of the argument. The parameter, RADIX, which specified the base of the machine floating-point representation in routines BALANC and CBAL has been replaced by the  constant, 16.

13. OPERATING SYSTEM UNDER WHICH PROGRAM IS EXECUTED:

14. OTHER PROGRAMMING OR OPERATING INFORMATION OR RESTRICTIONS

An
auxiliary routine is provided to help in extracting individual rou-  tines from the transmittal tape on non-IBM systems, and the UNIX script for testing on a UNIX system is included. The set of sample cases consists of drivers, data input subroutines, residual calcu- lation routines, and test data. Small changes may be required in the sample cases, e.g., to change the logical input and output unit or to include a PROGRAM statement. The FORTRAN 77 OPEN statement is used to associate the test data file with the appropriate logical unit number.

15. NAME AND ESTABLISHMENT OF AUTHOR

  MPLN     Burton S. Garbow
           Mathematics and Computer Science Division
           Argonne National Laboratory
           9700 South Cass Avenue
           Argonne, Illinois 60439

  3090     A.K. Cline and J. Meyering
           Pleasant Valley Software

File name	File description	Records
NESC0534_14.002	EISPACK-3 INFORMATION	55
NESC0534_14.004	EISPACK-3 INSTALLATION INSTRUCTIONS	201
NESC0534_14.005	EISPACK-3 SOURCE SINGLE PRECISION	11444
NESC0534_14.006	EISPACK-3 SOURCE DOUBLE PRECISION	11444
NESC0534_14.007	PROGRAM TO EXTRACT SUBROUTINES	133
NESC0534_14.008	SINGLE PRECISION TESTING ROUTINES (1/14)	657
NESC0534_14.009	SINGLE PRECISION TESTING ROUTINES (2/14)	391
NESC0534_14.010	SINGLE PRECISION TESTING ROUTINES (3/14)	450
NESC0534_14.011	SINGLE PRECISION TESTING ROUTINES (4/14)	433
NESC0534_14.012	SINGLE PRECISION TESTING ROUTINES (5/14)	443
NESC0534_14.013	SINGLE PRECISION TESTING ROUTINES (6/14)	394
NESC0534_14.014	SINGLE PRECISION TESTING ROUTINES (7/14)	586
NESC0534_14.015	SINGLE PRECISION TESTING ROUTINES (8/14)	414
NESC0534_14.016	SINGLE PRECISION TESTING ROUTINES (9/14)	319
NESC0534_14.017	SINGLE PRECISION TESTING ROUTINES (10/14)	460
NESC0534_14.018	SINGLE PRECISION TESTING ROUTINES (11/14	463
NESC0534_14.019	SINGLE PRECISION TESTING ROUTINES (12/14	462
NESC0534_14.020	SINGLE PRECISION TESTING ROUTINES (13/14	251
NESC0534_14.021	SINGLE PRECISION TESTING ROUTINES (14/14)	294
NESC0534_14.022	DOUBLE PRECISION TESTING ROUTINES (01/14)	657
NESC0534_14.023	DOUBLE PRECISION TESTING ROUTINES (02/14)	391
NESC0534_14.024	DOUBLE PRECISION TESTING ROUTINES (03/14)	450
NESC0534_14.025	DOUBLE PRECISION TESTING ROUTINES (04/14)	433
NESC0534_14.026	DOUBLE PRECISION TESTING ROUTINES (05/14)	443
NESC0534_14.027	DOUBLE PRECISION TESTING ROUTINES (06/14)	394
NESC0534_14.028	DOUBLE PRECISION TESTING ROUTINES (07/14)	586
NESC0534_14.029	DOUBLE PRECISION TESTING ROUTINES (08/14)	414
NESC0534_14.030	DOUBLE PRECISION TESTING ROUTINES (09/14)	319
NESC0534_14.031	DOUBLE PRECISION TESTING ROUTINES (10/14)	460
NESC0534_14.032	DOUBLE PRECISION TESTING ROUTINES (11/14)	463
NESC0534_14.033	DOUBLE PRECISION TESTING ROUTINES (12/14)	462
NESC0534_14.034	DOUBLE PRECISION TESTING ROUTINES (13/14)	251
NESC0534_14.035	DOUBLE PRECISION TESTING ROUTINES (14/14)	294
NESC0534_14.036	INPUT DATA FOR TESTING AIDES (01/20)	407
NESC0534_14.037	INPUT DATA FOR TESTING AIDES (02/20)	70
NESC0534_14.038	INPUT DATA FOR TESTING AIDES (03/20)	261
NESC0534_14.039	INPUT DATA FOR TESTING AIDES (04/20)	21
NESC0534_14.040	INPUT DATA FOR TESTING AIDES (05/20)	117
NESC0534_14.041	INPUT DATA FOR TESTING AIDES (06/20)	8
NESC0534_14.042	INPUT DATA FOR TESTING AIDES (07/20)	46
NESC0534_14.043	INPUT DATA FOR TESTING AIDES (08/20)	4
NESC0534_14.044	INPUT DATA FOR TESTING AIDES (09/20)	633
NESC0534_14.045	INPUT DATA FOR TESTING AIDES (10/20)	16
NESC0534_14.046	INPUT DATA FOR TESTING AIDES (11/20)	288
NESC0534_14.047	INPUT DATA FOR TESTING AIDES (12/20)	9
NESC0534_14.048	INPUT DATA FOR TESTING AIDES (13/20)	378
NESC0534_14.049	INPUT DATA FOR TESTING AIDES (14/20)	372
NESC0534_14.050	INPUT DATA FOR TESTING AIDES (15/20)	255
NESC0534_14.051	INPUT DATA FOR TESTING AIDES (16/20)	260
NESC0534_14.052	INPUT DATA FOR TESTING AIDES (17/20)	117
NESC0534_14.053	INPUT DATA FOR TESTING AIDES (18/20)	9
NESC0534_14.054	INPUT DATA FOR TESTING AIDES (19/20)	28
NESC0534_14.055	INPUT DATA FOR TESTING AIDES (20/20)	5
NESC0534_14.056	COMMENTS ON SINGLE PRECISION VERSION	4143
NESC0534_14.057	COMMENTS ON DOUBLE PRECISION VERSION	4143
NESC0534_14.058	UNIX SCRIPT	234

File name	File description	Records
NESC0534_15.001	Information file	82
NESC0534_15.002	Machine-readable documentation	190
NESC0534_15.003	EISPACK-3 single-precision FORTRAN	11713
NESC0534_15.004	EISPACK-3 double-precision FORTRAN	11208
NESC0534_15.005	Subroutine extraction program FORTRAN-77	133
NESC0534_15.006	RG single-precision sample driver (FTN77)	657
NESC0534_15.007	RS single-precision sample driver (FTN77)	391
NESC0534_15.008	RSB single-precision sample driver (FTN77)	450
NESC0534_15.009	RSP single-precision sample driver (FTN77)	433
NESC0534_15.010	RST single-precision sample driver (FTN77)	443
NESC0534_15.011	RT single-precision sample driver (FTN77)	394
NESC0534_15.012	CG single-precision sample driver (FTN77)	586
NESC0534_15.013	CH single-precision sample driver (FTN77)	414
NESC0534_15.014	RGG single-precision sample driver (FTN77)	319
NESC0534_15.015	RSG single-precision sample driver (FTN77)	460
NESC0534_15.016	RSGAB single-precision sample driver (FTN77)	463
NESC0534_15.017	RSGBA single-precision sample driver (FTN77)	462
NESC0534_15.018	RL single-precision sample driver (FTN77)	251
NESC0534_15.019	RBL single-precision sample driver (FTN77)	294
NESC0534_15.020	RG double-precision sample driver (FTN77)	657
NESC0534_15.021	RS double-precision sample driver (FTN77)	391
NESC0534_15.022	RSB double-precision sample driver (FTN77)	450
NESC0534_15.023	RSP double-precision sample driver (FTN77)	433
NESC0534_15.024	RST double-precision sample driver (FTN77)	443
NESC0534_15.025	RT double-precision sample driver (FTN77)	394
NESC0534_15.026	CG double-precision sample driver (FTN77)	586
NESC0534_15.027	CH double-precision sample driver (FTN77)	414
NESC0534_15.028	RGG double-precision sample driver (FTN77)	319
NESC0534_15.029	RSG double-precision sample driver (FTN77)	460
NESC0534_15.030	RSGAB double-precision sample driver(FTN77)	463
NESC0534_15.031	RSGBA double-precision sample driver(FTN77)	462
NESC0534_15.032	RL double-precision sample driver(FTN77)	251
NESC0534_15.033	RBL double-precision sample driver(FTN77)	294
NESC0534_15.034	RG Sample problem unit 1 data	407
NESC0534_15.035	RG Sample problem unit 5 data	70
NESC0534_15.036	RG RSP RSG RSGAB RSGBA s.p. unit 1 data	261
NESC0534_15.037	RG RSP RSG RSGAB RSGBA s.p. unit 5 data	21
NESC0534_15.038	RSB sample problem unit 1 data	117
NESC0534_15.039	RSB sample problem unit 5 data	8
NESC0534_15.040	RT sample problem unit 1 data	46
NESC0534_15.041	RT sample problem unit 5 data	4
NESC0534_15.042	CG sample problem unit 1 data	633
NESC0534_15.043	CG sample problem unit 5 data	16
NESC0534_15.044	CH sample problem unit 1 data	288
NESC0534_15.045	CH sample problem unit 5 data	9
NESC0534_15.046	RGG sample problem unit 1 data	378
NESC0534_15.047	RGG sample problem unit 2 data	372
NESC0534_15.048	RSG RSGAB RSGBA s.p. unit 2 data	255
NESC0534_15.049	RL sample problem unit 1 data	260
NESC0534_15.050	RBL sample problem unit 1 data	117
NESC0534_15.051	RBL sample problem unit 5 data	9
NESC0534_15.052	RST sample problem unit 1 data	28
NESC0534_15.053	RST sample problem unit 5 data	5
NESC0534_15.054	Comments from single-precision subroutines	4143
NESC0534_15.055	Comments from double-precision subroutines	4143
NESC0534_15.056	IBM VM/CMS EXEC compile and execute stream	195