# ratqr.f

          SUBROUTINE RATQR (N, EPS1, D, E, E2, M, W, IND, BD, TYPE, IDEF,
         +   IERR)
    C***BEGIN PROLOGUE  RATQR
    C***PURPOSE  Compute the largest or smallest eigenvalues of a symmetric
    C            tridiagonal matrix using the rational QR method with Newton
    C            correction.
    C***LIBRARY   SLATEC (EISPACK)
    C***CATEGORY  D4A5, D4C2A
    C***TYPE      SINGLE PRECISION (RATQR-S)
    C***KEYWORDS  EIGENVALUES, EIGENVECTORS, EISPACK
    C***AUTHOR  Smith, B. T., et al.
    C***DESCRIPTION
    C
    C     This subroutine is a translation of the ALGOL procedure RATQR,
    C     NUM. MATH. 11, 264-272(1968) by REINSCH and BAUER.
    C     HANDBOOK FOR AUTO. COMP., VOL.II-LINEAR ALGEBRA, 257-265(1971).
    C
    C     This subroutine finds the algebraically smallest or largest
    C     eigenvalues of a SYMMETRIC TRIDIAGONAL matrix by the
    C     rational QR method with Newton corrections.
    C
    C     On Input
    C
    C        N is the order of the matrix.  N is an INTEGER variable.
    C
    C        EPS1 is a theoretical absolute error tolerance for the
    C          computed eigenvalues.  If the input EPS1 is non-positive, or
    C          indeed smaller than its default value, it is reset at each
    C          iteration to the respective default value, namely, the
    C          product of the relative machine precision and the magnitude
    C          of the current eigenvalue iterate.  The theoretical absolute
    C          error in the K-th eigenvalue is usually not greater than
    C          K times EPS1.  EPS1 is a REAL variable.
    C
    C        D contains the diagonal elements of the symmetric tridiagonal
    C          matrix.  D is a one-dimensional REAL array, dimensioned D(N).
    C
    C        E contains the subdiagonal elements of the symmetric
    C          tridiagonal matrix in its last N-1 positions.  E(1) is
    C          arbitrary.  E is a one-dimensional REAL array, dimensioned
    C          E(N).
    C
    C        E2 contains the squares of the corresponding elements of E in
    C          its last N-1 positions.  E2(1) is arbitrary.  E2 is a one-
    C          dimensional REAL array, dimensioned E2(N).
    C
    C        M is the number of eigenvalues to be found.  M is an INTEGER
    C          variable.
    C
    C        IDEF should be set to 1 if the input matrix is known to be
    C          positive definite, to -1 if the input matrix is known to
    C          be negative definite, and to 0 otherwise.  IDEF is an
    C          INTEGER variable.
    C
    C        TYPE should be set to .TRUE. if the smallest eigenvalues are
    C          to be found, and to .FALSE. if the largest eigenvalues are
    C          to be found.  TYPE is a LOGICAL variable.
    C
    C     On Output
    C
    C        EPS1 is unaltered unless it has been reset to its
    C          (last) default value.
    C
    C        D and E are unaltered (unless W overwrites D).
    C
    C        Elements of E2, corresponding to elements of E regarded as
    C          negligible, have been replaced by zero causing the matrix
    C          to split into a direct sum of submatrices.  E2(1) is set
    C          to 0.0e0 if the smallest eigenvalues have been found, and
    C          to 2.0e0 if the largest eigenvalues have been found.  E2
    C          is otherwise unaltered (unless overwritten by BD).
    C
    C        W contains the M algebraically smallest eigenvalues in
    C          ascending order, or the M largest eigenvalues in descending
    C          order.  If an error exit is made because of an incorrect
    C          specification of IDEF, no eigenvalues are found.  If the
    C          Newton iterates for a particular eigenvalue are not monotone,
    C          the best estimate obtained is returned and IERR is set.
    C          W is a one-dimensional REAL array, dimensioned W(N).  W need
    C          not be distinct from D.
    C
    C        IND contains in its first M positions the submatrix indices
    C          associated with the corresponding eigenvalues in W --
    C          1 for eigenvalues belonging to the first submatrix from
    C          the top, 2 for those belonging to the second submatrix, etc.
    C          IND is an one-dimensional INTEGER array, dimensioned IND(N).
    C
    C        BD contains refined bounds for the theoretical errors of the
    C          corresponding eigenvalues in W.  These bounds are usually
    C          within the tolerance specified by EPS1.  BD is a one-
    C          dimensional REAL array, dimensioned BD(N).  BD need not be
    C          distinct from E2.
    C
    C        IERR is an INTEGER flag set to
    C          Zero       for normal return,
    C          6*N+1      if  IDEF  is set to 1 and  TYPE  to .TRUE.
    C                     when the matrix is NOT positive definite, or
    C                     if  IDEF  is set to -1 and  TYPE  to .FALSE.
    C                     when the matrix is NOT negative definite,
    C                     no eigenvalues are computed, or
    C                     M is greater than N,
    C          5*N+K      if successive iterates to the K-th eigenvalue
    C                     are NOT monotone increasing, where K refers
    C                     to the last such occurrence.
    C
    C     Note that subroutine TRIDIB is generally faster and more
    C     accurate than RATQR if the eigenvalues are clustered.
    C
    C     Questions and comments should be directed to B. S. Garbow,
    C     APPLIED MATHEMATICS DIVISION, ARGONNE NATIONAL LABORATORY
    C     ------------------------------------------------------------------
    C
    C***REFERENCES  B. T. Smith, J. M. Boyle, J. J. Dongarra, B. S. Garbow,
    C                 Y. Ikebe, V. C. Klema and C. B. Moler, Matrix Eigen-
    C                 system Routines - EISPACK Guide, Springer-Verlag,
    C                 1976.
    C***ROUTINES CALLED  R1MACH
    C***REVISION HISTORY  (YYMMDD)
    C   760101  DATE WRITTEN
    C   890531  Changed all specific intrinsics to generic.  (WRB)
    C   890831  Modified array declarations.  (WRB)
    C   890831  REVISION DATE from Version 3.2
    C   891214  Prologue converted to Version 4.0 format.  (BAB)
    C   920501  Reformatted the REFERENCES section.  (WRB)
    C***END PROLOGUE  RATQR