zsteqr2.f File Reference

Go to the source code of this file.

Functions/Subroutines
subroutine	zsteqr2 (compz, n, d, e, z, ldz, nr, work, info)

Function/Subroutine Documentation

zsteqr2()

subroutine zsteqr2	(	character	compz,
		integer	n,
		double precision, dimension( * )	d,
		double precision, dimension( * )	e,
		complex*16, dimension( ldz, * )	z,
		integer	ldz,
		integer	nr,
		double precision, dimension( * )	work,
		integer	info )

Definition at line 1 of file zsteqr2.f.

*
*  -- 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 ..
      DOUBLE PRECISION   D( * ), E( * ), WORK( * )
      COMPLEX*16         Z( LDZ, * )
*     ..
*
*  Purpose
*  =======
*
*  ZSTEQR2 is a modified version of LAPACK routine ZSTEQR.
*  ZSTEQR2 computes all eigenvalues and, optionally, eigenvectors of a
*  symmetric tridiagonal matrix using the implicit QL or QR method.
*  ZSTEQR2 is modified from ZSTEQR to allow each ScaLAPACK process
*  running ZSTEQR2 to perform updates on a distributed matrix Q.
*  Proper usage of ZSTEQR2 can be gleaned from
*  examination of ScaLAPACK's *  PZHEEV.
*  ZSTEQR2 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 PZLASET or ZLASET prior
*                  to entering this subroutine.
*
*  N       (input) INTEGER
*          The order of the matrix.  N >= 0.
*
*  D       (input/output) DOUBLE PRECISION 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) DOUBLE PRECISION 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*16 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) DOUBLE PRECISION 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 ..
      DOUBLE PRECISION   ZERO, ONE, TWO, THREE, HALF
      parameter( zero = 0.0d0, one = 1.0d0, two = 2.0d0,
     $                   three = 3.0d0, half = 0.5d0 )
      COMPLEX*16         CONE
      parameter( cone = ( 1.0d0, 1.0d0 ) )
      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
      DOUBLE PRECISION   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
      DOUBLE PRECISION   DLAMCH, DLANST, DLAPY2
      EXTERNAL           lsame, dlamch, dlanst, dlapy2
*     ..
*     .. External Subroutines ..
      EXTERNAL           dlaev2, dlartg, dlascl, dsterf, xerbla, zlasr,
     $                   zswap
*     ..
*     .. 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( 'ZSTEQR2', -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 dsterf( 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 = dlamch( 'E' )
      eps2 = eps**2
      safmin = dlamch( '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
.GT.      IF( L1N )
     $   GOTO 220
.GT.      IF( L11 )
     $   E( L1-1 ) = ZERO
.LE.      IF( L1NM1 ) THEN
         DO 20 M = L1, NM1
            TST = ABS( E( M ) )
.EQ.            IF( TSTZERO )
     $         GOTO 30
.LE.            IF( TST( 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
.EQ.      IF( LENDL )
     $   GOTO 10
*
*     Scale submatrix in rows and columns L to LEND
*
      ANORM = DLANST( 'i', LEND-L+1, D( L ), E( L ) )
      ISCALE = 0
.EQ.      IF( ANORMZERO )
     $   GOTO 10
.GT.      IF( ANORMSSFMAX ) THEN
         ISCALE = 1
         CALL DLASCL( 'g', 0, 0, ANORM, SSFMAX, LEND-L+1, 1, D( L ), N,
     $                INFO )
         CALL DLASCL( 'g', 0, 0, ANORM, SSFMAX, LEND-L, 1, E( L ), N,
     $                INFO )
.LT.      ELSEIF( ANORMSSFMIN ) THEN
         ISCALE = 2
         CALL DLASCL( 'g', 0, 0, ANORM, SSFMIN, LEND-L+1, 1, D( L ), N,
     $                INFO )
         CALL DLASCL( 'g', 0, 0, ANORM, SSFMIN, LEND-L, 1, E( L ), N,
     $                INFO )
      ENDIF
*
*     Choose between QL and QR iteration
*
.LT.      IF( ABS( D( LEND ) )ABS( D( L ) ) ) THEN
         LEND = LSV
         L = LENDSV
      ENDIF
*
.GT.      IF( LENDL ) THEN
*
*        QL Iteration
*
*        Look for small subdiagonal element.
*
   40    CONTINUE
.NE.         IF( LLEND ) THEN
            LENDM1 = LEND - 1
            DO 50 M = L, LENDM1
               TST = ABS( E( M ) )**2
.LE.               IF( TST( EPS2*ABS( D( M ) ) )*ABS( D( M+1 ) )+
     $             SAFMIN )GOTO 60
   50       CONTINUE
         ENDIF
*
         M = LEND
*
   60    CONTINUE
.LT.         IF( MLEND )
     $      E( M ) = ZERO
         P = D( L )
.EQ.         IF( ML )
     $      GOTO 110
*
*        If remaining matrix is 2-by-2, use DLAE2 or DLAEV2
*        to compute its eigensystem.
*
.EQ.         IF( ML+1 ) THEN
            CALL DLAEV2( D( L ), E( L ), D( L+1 ), RT1, RT2, C, S )
            WORK( L ) = C
            WORK( N-1+L ) = S
            CALL ZLASR( '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 = dlapy2( 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 dlartg( 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 = dlapy2( 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.9d0*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.0d0*
     $       ( ( 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 dlartg( 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 zlasr( '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 DLAE2 or DLAEV2
*        to compute its eigensystem.
*
         IF( m.EQ.l-1 ) THEN
            CALL dlaev2( d( l-1 ), e( l-1 ), d( l ), rt1, rt2, c, s )
            work( m ) = c
            work( n-1+m ) = s
            CALL zlasr( '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 = dlapy2( 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 dlartg( 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 = dlapy2( 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.9d0*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.0d0*
     $       ( ( 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 dlartg( 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 zlasr( '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
         IF( l.GE.lend )
     $      GOTO 120
         GOTO 200
*
      ENDIF
*
*     Undo scaling if necessary
*
  200 CONTINUE
      IF( iscale.EQ.1 ) THEN
         CALL dlascl( 'G', 0, 0, ssfmax, anorm, lendsv-lsv+1, 1,
     $                d( lsv ), n, info )
         CALL dlascl( 'G', 0, 0, ssfmax, anorm, lendsv-lsv, 1, e( lsv ),
     $                n, info )
      ELSEIF( iscale.EQ.2 ) THEN
         CALL dlascl( 'G', 0, 0, ssfmin, anorm, lendsv-lsv+1, 1,
     $                d( lsv ), n, info )
         CALL dlascl( '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.
*
      IF( jtot.LT.nmaxit )
     $   GOTO 10
      DO 210 i = 1, n - 1
         IF( e( i ).NE.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
            IF( d( j ).LT.p ) THEN
               k = j
               p = d( j )
            ENDIF
  230    CONTINUE
         IF( k.NE.i ) THEN
            d( k ) = d( i )
            d( i ) = p
            CALL zswap( nr, z( 1, i ), 1, z( 1, k ), 1 )
         ENDIF
  240 CONTINUE
*
  250 CONTINUE
*     WRITE( *, FMT = * )'JTOT', JTOT
      RETURN
*
*     End of DSTEQR2
*