csteqr2.f

Go to the documentation of this file.

      SUBROUTINE csteqr2( COMPZ, N, D, E, Z, LDZ, NR, WORK, INFO )
*
*  -- ScaLAPACK routine (version 1.7) --
*     Univ. of Tennessee, Univ. of California Berkeley, NAG Ltd.,
*     Courant Institute, Argonne National Lab, and Rice University
*     November 15, 1997
*
*     .. Scalar Arguments ..
      CHARACTER          COMPZ
      INTEGER            INFO, LDZ, N, NR
*     ..
*     .. Array Arguments ..
      REAL               D( * ), E( * ), WORK( * )
      COMPLEX            Z( LDZ, * )
*     ..
*
*  Purpose
*  =======
*
*  CSTEQR2 is a modified version of LAPACK routine CSTEQR.
*  CSTEQR2 computes all eigenvalues and, optionally, eigenvectors of a
*  symmetric tridiagonal matrix using the implicit QL or QR method.
*  CSTEQR2 is modified from CSTEQR to allow each ScaLAPACK process
*  running CSTEQR2 to perform updates on a distributed matrix Q.
*  Proper usage of CSTEQR2 can be gleaned from
*  examination of ScaLAPACK's *  PCHEEV.
*  CSTEQR2 incorporates changes attributed to Greg Henry.
*
*  Arguments
*  =========
*
*  COMPZ   (input) CHARACTER*1
*          = 'N':  Compute eigenvalues only.
*          = 'I':  Compute eigenvalues and eigenvectors of the
*                  tridiagonal matrix.  Z must be initialized to the
*                  identity matrix by PCLASET or CLASET prior
*                  to entering this subroutine.
*
*  N       (input) INTEGER
*          The order of the matrix.  N >= 0.
*
*  D       (input/output) REAL array, dimension (N)
*          On entry, the diagonal elements of the tridiagonal matrix.
*          On exit, if INFO = 0, the eigenvalues in ascending order.
*
*  E       (input/output) REAL array, dimension (N-1)
*          On entry, the (n-1) subdiagonal elements of the tridiagonal
*          matrix.
*          On exit, E has been destroyed.
*
*  Z       (local input/local output) COMPLEX array, global
*          dimension (N, N), local dimension (LDZ, NR).
*          On entry, if  COMPZ = 'V', then Z contains the orthogonal
*          matrix used in the reduction to tridiagonal form.
*          On exit, if INFO = 0, then if  COMPZ = 'V', Z contains the
*          orthonormal eigenvectors of the original symmetric matrix,
*          and if COMPZ = 'I', Z contains the orthonormal eigenvectors
*          of the symmetric tridiagonal matrix.
*          If COMPZ = 'N', then Z is not referenced.
*
*  LDZ     (input) INTEGER
*          The leading dimension of the array Z.  LDZ >= 1, and if
*          eigenvectors are desired, then  LDZ >= max(1,N).
*
*  NR      (input) INTEGER
*          NR = MAX(1, NUMROC( N, NB, MYPROW, 0, NPROCS ) ).
*          If COMPZ = 'N', then NR is not referenced.
*
*  WORK    (workspace) REAL array, dimension (max(1,2*N-2))
*          If COMPZ = 'N', then WORK is not referenced.
*
*  INFO    (output) INTEGER
*          = 0:  successful exit
*          < 0:  if INFO = -i, the i-th argument had an illegal value
*          > 0:  the algorithm has failed to find all the eigenvalues in
*                a total of 30*N iterations; if INFO = i, then i
*                elements of E have not converged to zero; on exit, D
*                and E contain the elements of a symmetric tridiagonal
*                matrix which is orthogonally similar to the original
*                matrix.
*
*  =====================================================================
*
*     .. Parameters ..
      REAL               ZERO, ONE, TWO, THREE, HALF
      parameter( zero = 0.0e0, one = 1.0e0, two = 2.0e0,
     $                   three = 3.0e0, half = 0.5e0 )
      COMPLEX            CONE
      parameter( cone = ( 1.0e0, 1.0e0 ) )
      INTEGER            MAXIT, NMAXLOOK
      parameter( maxit = 30, nmaxlook = 15 )
*     ..
*     .. Local Scalars ..
      INTEGER            I, ICOMPZ, II, ILAST, ISCALE, J, JTOT, K, L,
     $                   L1, LEND, LENDM1, LENDP1, LENDSV, LM1, LSV, M,
     $                   MM, MM1, NLOOK, NM1, NMAXIT
      REAL               ANORM, B, C, EPS, EPS2, F, G, GP, OLDEL, OLDGP,
     $                   OLDRP, P, R, RP, RT1, RT2, S, SAFMAX, SAFMIN,
     $                   SSFMAX, SSFMIN, TST, TST1
*     ..
*     .. External Functions ..
      LOGICAL            LSAME
      REAL               SLAMCH, SLANST, SLAPY2
      EXTERNAL           lsame, slamch, slanst, slapy2
*     ..
*     .. External Subroutines ..
      EXTERNAL           clasr, cswap, slaev2, slartg, slascl, ssterf,
     $                   xerbla
*     ..
*     .. Intrinsic Functions ..
      INTRINSIC          abs, max, sign, sqrt
*     ..
*     .. Executable Statements ..
*
*     Test the input parameters.
*
      ilast = 0
      info = 0
*
      IF( lsame( compz, 'N' ) ) THEN
         icompz = 0
      ELSEIF( lsame( compz, 'I' ) ) THEN
         icompz = 1
      ELSE
         icompz = -1
      ENDIF
      IF( icompz.LT.0 ) THEN
         info = -1
      ELSEIF( n.LT.0 ) THEN
         info = -2
      ELSEIF( icompz.GT.0 .AND. ldz.LT.max( 1, nr ) ) THEN
         info = -6
      ENDIF
      IF( info.NE.0 ) THEN
         CALL xerbla( 'CSTEQR2', -info )
         RETURN
      ENDIF
*
*     Quick return if possible
*
      IF( n.EQ.0 )
     $   RETURN
*
*     If eigenvectors aren't not desired, this is faster
*
      IF( icompz.EQ.0 ) THEN
         CALL ssterf( n, d, e, info )
         RETURN
      ENDIF
*
      IF( n.EQ.1 ) THEN
         z( 1, 1 ) = cone
         RETURN
      ENDIF
*
*     Determine the unit roundoff and over/underflow thresholds.
*
      eps = slamch( 'E' )
      eps2 = eps**2
      safmin = slamch( 'S' )
      safmax = one / safmin
      ssfmax = sqrt( safmax ) / three
      ssfmin = sqrt( safmin ) / eps2
*
*     Compute the eigenvalues and eigenvectors of the tridiagonal
*     matrix.
*
      nmaxit = n*maxit
      jtot = 0
*
*     Determine where the matrix splits and choose QL or QR iteration
*     for each block, according to whether top or bottom diagonal
*     element is smaller.
*
      l1 = 1
      nm1 = n - 1
*
   10 CONTINUE
      IF( l1.GT.n )
     $   GOTO 220
      IF( l1.GT.1 )
     $   e( l1-1 ) = zero
      IF( l1.LE.nm1 ) THEN
         DO 20 m = l1, nm1
            tst = abs( e( m ) )
            IF( tst.EQ.zero )
     $         GOTO 30
            IF( tst.LE.( sqrt( abs( d( m ) ) )*sqrt( abs( d( m+
     $          1 ) ) ) )*eps ) THEN
               e( m ) = zero
               GOTO 30
            ENDIF
   20    CONTINUE
      ENDIF
      m = n
*
   30 CONTINUE
      l = l1
      lsv = l
      lend = m
      lendsv = lend
      l1 = m + 1
      IF( lend.EQ.l )
     $   GOTO 10
*
*     Scale submatrix in rows and columns L to LEND
*
      anorm = slanst( 'I', lend-l+1, d( l ), e( l ) )
      iscale = 0
      IF( anorm.EQ.zero )
     $   GOTO 10
      IF( anorm.GT.ssfmax ) THEN
         iscale = 1
         CALL slascl( 'G', 0, 0, anorm, ssfmax, lend-l+1, 1, d( l ), n,
     $                info )
         CALL slascl( 'G', 0, 0, anorm, ssfmax, lend-l, 1, e( l ), n,
     $                info )
      ELSEIF( anorm.LT.ssfmin ) THEN
         iscale = 2
         CALL slascl( 'G', 0, 0, anorm, ssfmin, lend-l+1, 1, d( l ), n,
     $                info )
         CALL slascl( 'G', 0, 0, anorm, ssfmin, lend-l, 1, e( l ), n,
     $                info )
      ENDIF
*
*     Choose between QL and QR iteration
*
      IF( abs( d( lend ) ).LT.abs( d( l ) ) ) THEN
         lend = lsv
         l = lendsv
      ENDIF
*
      IF( lend.GT.l ) THEN
*
*        QL Iteration
*
*        Look for small subdiagonal element.
*
   40    CONTINUE
         IF( l.NE.lend ) THEN
            lendm1 = lend - 1
            DO 50 m = l, lendm1
               tst = abs( e( m ) )**2
               IF( tst.LE.( eps2*abs( d( m ) ) )*abs( d( m+1 ) )+
     $             safmin )GOTO 60
   50       CONTINUE
         ENDIF
*
         m = lend
*
   60    CONTINUE
         IF( m.LT.lend )
     $      e( m ) = zero
         p = d( l )
         IF( m.EQ.l )
     $      GOTO 110
*
*        If remaining matrix is 2-by-2, use SLAE2 or SLAEV2
*        to compute its eigensystem.
*
         IF( m.EQ.l+1 ) THEN
            CALL slaev2( d( l ), e( l ), d( l+1 ), rt1, rt2, c, s )
            work( l ) = c
            work( n-1+l ) = s
            CALL clasr( 'R', 'V', 'B', nr, 2, work( l ), work( n-1+l ),
     $                  z( 1, l ), ldz )
            d( l ) = rt1
            d( l+1 ) = rt2
            e( l ) = zero
            l = l + 2
            IF( l.LE.lend )
     $         GOTO 40
            GOTO 200
         ENDIF
*
         IF( jtot.EQ.nmaxit )
     $      GOTO 200
         jtot = jtot + 1
*
*        Form shift.
*
         g = ( d( l+1 )-p ) / ( two*e( l ) )
         r = slapy2( g, one )
         g = d( m ) - p + ( e( l ) / ( g+sign( r, g ) ) )
*
         IF( icompz.EQ.0 ) THEN
*           Do not do a lookahead!
            GOTO 90
         ENDIF
*
         oldel = abs( e( l ) )
         gp = g
         rp = r
         tst = abs( e( l ) )**2
         tst = tst / ( ( eps2*abs( d( l ) ) )*abs( d( l+1 ) )+safmin )
*
         nlook = 1
         IF( ( tst.GT.one ) .AND. ( nlook.LE.nmaxlook ) ) THEN
   70       CONTINUE
*
*           This is the lookahead loop, going until we have
*           convergence or too many steps have been taken.
*
            s = one
            c = one
            p = zero
            mm1 = m - 1
            DO 80 i = mm1, l, -1
               f = s*e( i )
               b = c*e( i )
               CALL slartg( gp, f, c, s, rp )
               gp = d( i+1 ) - p
               rp = ( d( i )-gp )*s + two*c*b
               p = s*rp
               IF( i.NE.l )
     $            gp = c*rp - b
   80       CONTINUE
            oldgp = gp
            oldrp = rp
*           Find GP & RP for the next iteration
            IF( abs( c*oldrp-b ).GT.safmin ) THEN
               gp = ( ( oldgp+p )-( d( l )-p ) ) / ( two*( c*oldrp-b ) )
            ELSE
*
*           Goto put in by G. Henry to fix ALPHA problem
*
               GOTO 90
*              GP = ( ( OLDGP+P )-( D( L )-P ) ) /
*    $              ( TWO*( C*OLDRP-B )+SAFMIN )
            ENDIF
            rp = slapy2( gp, one )
            gp = d( m ) - ( d( l )-p ) +
     $           ( ( c*oldrp-b ) / ( gp+sign( rp, gp ) ) )
            tst1 = tst
            tst = abs( c*oldrp-b )**2
            tst = tst / ( ( eps2*abs( d( l )-p ) )*abs( oldgp+p )+
     $            safmin )
*           Make sure that we are making progress
            IF( abs( c*oldrp-b ).GT.0.9e0*oldel ) THEN
               IF( abs( c*oldrp-b ).GT.oldel ) THEN
                  gp = g
                  rp = r
               ENDIF
               tst = half
            ELSE
               oldel = abs( c*oldrp-b )
            ENDIF
            nlook = nlook + 1
            IF( ( tst.GT.one ) .AND. ( nlook.LE.nmaxlook ) )
     $         GOTO 70
         ENDIF
*
         IF( ( tst.LE.one ) .AND. ( tst.NE.half ) .AND.
     $       ( abs( p ).LT.eps*abs( d( l ) ) ) .AND.
     $       ( ilast.EQ.l ) .AND. ( abs( e( l ) )**2.LE.10000.0e0*
     $       ( ( eps2*abs( d( l ) ) )*abs( d( l+1 ) )+safmin ) ) ) THEN
*
*           Skip the current step: the subdiagonal info is just noise.
*
            m = l
            e( m ) = zero
            p = d( l )
            jtot = jtot - 1
            GOTO 110
         ENDIF
         g = gp
         r = rp
*
*        Lookahead over
*
   90    CONTINUE
*
         s = one
         c = one
         p = zero
*
*        Inner loop
*
         mm1 = m - 1
         DO 100 i = mm1, l, -1
            f = s*e( i )
            b = c*e( i )
            CALL slartg( g, f, c, s, r )
            IF( i.NE.m-1 )
     $         e( i+1 ) = r
            g = d( i+1 ) - p
            r = ( d( i )-g )*s + two*c*b
            p = s*r
            d( i+1 ) = g + p
            g = c*r - b
*
*           If eigenvectors are desired, then save rotations.
*
            work( i ) = c
            work( n-1+i ) = -s
*
  100    CONTINUE
*
*        If eigenvectors are desired, then apply saved rotations.
*
         mm = m - l + 1
         CALL clasr( 'R', 'V', 'B', nr, mm, work( l ), work( n-1+l ),
     $               z( 1, l ), ldz )
*
         d( l ) = d( l ) - p
         e( l ) = g
         ilast = l
         GOTO 40
*
*        Eigenvalue found.
*
  110    CONTINUE
         d( l ) = p
*
         l = l + 1
         IF( l.LE.lend )
     $      GOTO 40
         GOTO 200
*
      ELSE
*
*        QR Iteration
*
*        Look for small superdiagonal element.
*
  120    CONTINUE
         IF( l.NE.lend ) THEN
            lendp1 = lend + 1
            DO 130 m = l, lendp1, -1
               tst = abs( e( m-1 ) )**2
               IF( tst.LE.( eps2*abs( d( m ) ) )*abs( d( m-1 ) )+
     $             safmin )GOTO 140
  130       CONTINUE
         ENDIF
*
         m = lend
*
  140    CONTINUE
         IF( m.GT.lend )
     $      e( m-1 ) = zero
         p = d( l )
         IF( m.EQ.l )
     $      GOTO 190
*
*        If remaining matrix is 2-by-2, use SLAE2 or SLAEV2
*        to compute its eigensystem.
*
         IF( m.EQ.l-1 ) THEN
            CALL slaev2( d( l-1 ), e( l-1 ), d( l ), rt1, rt2, c, s )
            work( m ) = c
            work( n-1+m ) = s
            CALL clasr( 'R', 'V', 'F', nr, 2, work( m ), work( n-1+m ),
     $                  z( 1, l-1 ), ldz )
            d( l-1 ) = rt1
            d( l ) = rt2
            e( l-1 ) = zero
            l = l - 2
            IF( l.GE.lend )
     $         GOTO 120
            GOTO 200
         ENDIF
*
         IF( jtot.EQ.nmaxit )
     $      GOTO 200
         jtot = jtot + 1
*
*        Form shift.
*
         g = ( d( l-1 )-p ) / ( two*e( l-1 ) )
         r = slapy2( g, one )
         g = d( m ) - p + ( e( l-1 ) / ( g+sign( r, g ) ) )
*
         IF( icompz.EQ.0 ) THEN
*           Do not do a lookahead!
            GOTO 170
         ENDIF
*
         oldel = abs( e( l-1 ) )
         gp = g
         rp = r
         tst = abs( e( l-1 ) )**2
         tst = tst / ( ( eps2*abs( d( l ) ) )*abs( d( l-1 ) )+safmin )
         nlook = 1
         IF( ( tst.GT.one ) .AND. ( nlook.LE.nmaxlook ) ) THEN
  150       CONTINUE
*
*           This is the lookahead loop, going until we have
*           convergence or too many steps have been taken.
*
            s = one
            c = one
            p = zero
*
*        Inner loop
*
            lm1 = l - 1
            DO 160 i = m, lm1
               f = s*e( i )
               b = c*e( i )
               CALL slartg( gp, f, c, s, rp )
               gp = d( i ) - p
               rp = ( d( i+1 )-gp )*s + two*c*b
               p = s*rp
               IF( i.LT.lm1 )
     $            gp = c*rp - b
  160       CONTINUE
            oldgp = gp
            oldrp = rp
*           Find GP & RP for the next iteration
            IF( abs( c*oldrp-b ).GT.safmin ) THEN
               gp = ( ( oldgp+p )-( d( l )-p ) ) / ( two*( c*oldrp-b ) )
            ELSE
*
*           Goto put in by G. Henry to fix ALPHA problem
*
               GOTO 170
*              GP = ( ( OLDGP+P )-( D( L )-P ) ) /
*    $              ( TWO*( C*OLDRP-B )+SAFMIN )
            ENDIF
            rp = slapy2( gp, one )
            gp = d( m ) - ( d( l )-p ) +
     $           ( ( c*oldrp-b ) / ( gp+sign( rp, gp ) ) )
            tst1 = tst
            tst = abs( ( c*oldrp-b ) )**2
            tst = tst / ( ( eps2*abs( d( l )-p ) )*abs( oldgp+p )+
     $            safmin )
*           Make sure that we are making progress
            IF( abs( c*oldrp-b ).GT.0.9e0*oldel ) THEN
               IF( abs( c*oldrp-b ).GT.oldel ) THEN
                  gp = g
                  rp = r
               ENDIF
               tst = half
            ELSE
               oldel = abs( c*oldrp-b )
            ENDIF
            nlook = nlook + 1
            IF( ( tst.GT.one ) .AND. ( nlook.LE.nmaxlook ) )
     $         GOTO 150
         ENDIF
         IF( ( tst.LE.one ) .AND. ( tst.NE.half ) .AND.
     $       ( abs( p ).LT.eps*abs( d( l ) ) ) .AND.
     $       ( ilast.EQ.l ) .AND. ( abs( e( l-1 ) )**2.LE.10000.0e0*
     $       ( ( eps2*abs( d( l-1 ) ) )*abs( d( l ) )+safmin ) ) ) THEN
*
*           Skip the current step: the subdiagonal info is just noise.
*
            m = l
            e( m-1 ) = zero
            p = d( l )
            jtot = jtot - 1
            GOTO 190
         ENDIF
*
         g = gp
         r = rp
*
*        Lookahead over
*
  170    CONTINUE
*
         s = one
         c = one
         p = zero
         DO 180 i = m, lm1
            f = s*e( i )
            b = c*e( i )
            CALL slartg( g, f, c, s, r )
            IF( i.NE.m )
     $         e( i-1 ) = r
            g = d( i ) - p
            r = ( d( i+1 )-g )*s + two*c*b
            p = s*r
            d( i ) = g + p
            g = c*r - b
*
*           If eigenvectors are desired, then save rotations.
*
            work( i ) = c
            work( n-1+i ) = s
*
  180    CONTINUE
*
*        If eigenvectors are desired, then apply saved rotations.
*
         mm = l - m + 1
         CALL clasr( 'R', 'v', 'f', NR, MM, WORK( M ), WORK( N-1+M ),
     $               Z( 1, M ), LDZ )
*
         D( L ) = D( L ) - P
         E( LM1 ) = G
         ILAST = L
         GOTO 120
*
*        Eigenvalue found.
*
  190    CONTINUE
         D( L ) = P
*
         L = L - 1
.GE.         IF( LLEND )
     $      GOTO 120
         GOTO 200
*
      ENDIF
*
*     Undo scaling if necessary
*
  200 CONTINUE
.EQ.      IF( ISCALE1 ) THEN
         CALL SLASCL( 'g', 0, 0, SSFMAX, ANORM, LENDSV-LSV+1, 1,
     $                D( LSV ), N, INFO )
         CALL SLASCL( 'g', 0, 0, SSFMAX, ANORM, LENDSV-LSV, 1, E( LSV ),
     $                N, INFO )
.EQ.      ELSEIF( ISCALE2 ) THEN
         CALL SLASCL( 'g', 0, 0, SSFMIN, ANORM, LENDSV-LSV+1, 1,
     $                D( LSV ), N, INFO )
         CALL SLASCL( 'g', 0, 0, SSFMIN, ANORM, LENDSV-LSV, 1, E( LSV ),
     $                N, INFO )
      ENDIF
*
*     Check for no convergence to an eigenvalue after a total
*     of N*MAXIT iterations.
*
.LT.      IF( JTOTNMAXIT )
     $   GOTO 10
      DO 210 I = 1, N - 1
.NE.         IF( E( I )ZERO )
     $      INFO = INFO + 1
  210 CONTINUE
      GOTO 250
*
*     Order eigenvalues and eigenvectors.
*
  220 CONTINUE
*
*        Use Selection Sort to minimize swaps of eigenvectors
*
      DO 240 II = 2, N
         I = II - 1
         K = I
         P = D( I )
         DO 230 J = II, N
.LT.            IF( D( J )P ) THEN
               K = J
               P = D( J )
            ENDIF
  230    CONTINUE
.NE.         IF( KI ) THEN
            D( K ) = D( I )
            D( I ) = P
            CALL CSWAP( NR, Z( 1, I ), 1, Z( 1, K ), 1 )
         ENDIF
  240 CONTINUE
*
  250 CONTINUE
*     WRITE( *, FMT = * )'JTOT', JTOT
      RETURN
*
*     End of SSTEQR2
*
      END