dlaein.f

Go to the documentation of this file.

*> \brief \b DLAEIN computes a specified right or left eigenvector of an upper Hessenberg matrix by inverse iteration.
*
*  =========== DOCUMENTATION ===========
*
* Online html documentation available at
*            http://www.netlib.org/lapack/explore-html/
*
*> Download DLAEIN + dependencies
*> <a href="http://www.netlib.org/cgi-bin/netlibfiles.tgz?format=tgz&filename=/lapack/lapack_routine/dlaein.f">
*> [TGZ]</a>
*> <a href="http://www.netlib.org/cgi-bin/netlibfiles.zip?format=zip&filename=/lapack/lapack_routine/dlaein.f">
*> [ZIP]</a>
*> <a href="http://www.netlib.org/cgi-bin/netlibfiles.txt?format=txt&filename=/lapack/lapack_routine/dlaein.f">
*> [TXT]</a>
*
*  Definition:
*  ===========
*
*       SUBROUTINE DLAEIN( RIGHTV, NOINIT, N, H, LDH, WR, WI, VR, VI, B,
*                          LDB, WORK, EPS3, SMLNUM, BIGNUM, INFO )
*
*       .. Scalar Arguments ..
*       LOGICAL            NOINIT, RIGHTV
*       INTEGER            INFO, LDB, LDH, N
*       DOUBLE PRECISION   BIGNUM, EPS3, SMLNUM, WI, WR
*       ..
*       .. Array Arguments ..
*       DOUBLE PRECISION   B( LDB, * ), H( LDH, * ), VI( * ), VR( * ),
*      $                   WORK( * )
*       ..
*
*
*> \par Purpose:
*  =============
*>
*> \verbatim
*>
*> DLAEIN uses inverse iteration to find a right or left eigenvector
*> corresponding to the eigenvalue (WR,WI) of a real upper Hessenberg
*> matrix H.
*> \endverbatim
*
*  Arguments:
*  ==========
*
*> \param[in] RIGHTV
*> \verbatim
*>          RIGHTV is LOGICAL
*>          = .TRUE. : compute right eigenvector;
*>          = .FALSE.: compute left eigenvector.
*> \endverbatim
*>
*> \param[in] NOINIT
*> \verbatim
*>          NOINIT is LOGICAL
*>          = .TRUE. : no initial vector supplied in (VR,VI).
*>          = .FALSE.: initial vector supplied in (VR,VI).
*> \endverbatim
*>
*> \param[in] N
*> \verbatim
*>          N is INTEGER
*>          The order of the matrix H.  N >= 0.
*> \endverbatim
*>
*> \param[in] H
*> \verbatim
*>          H is DOUBLE PRECISION array, dimension (LDH,N)
*>          The upper Hessenberg matrix H.
*> \endverbatim
*>
*> \param[in] LDH
*> \verbatim
*>          LDH is INTEGER
*>          The leading dimension of the array H.  LDH >= max(1,N).
*> \endverbatim
*>
*> \param[in] WR
*> \verbatim
*>          WR is DOUBLE PRECISION
*> \endverbatim
*>
*> \param[in] WI
*> \verbatim
*>          WI is DOUBLE PRECISION
*>          The real and imaginary parts of the eigenvalue of H whose
*>          corresponding right or left eigenvector is to be computed.
*> \endverbatim
*>
*> \param[in,out] VR
*> \verbatim
*>          VR is DOUBLE PRECISION array, dimension (N)
*> \endverbatim
*>
*> \param[in,out] VI
*> \verbatim
*>          VI is DOUBLE PRECISION array, dimension (N)
*>          On entry, if NOINIT = .FALSE. and WI = 0.0, VR must contain
*>          a real starting vector for inverse iteration using the real
*>          eigenvalue WR; if NOINIT = .FALSE. and WI.ne.0.0, VR and VI
*>          must contain the real and imaginary parts of a complex
*>          starting vector for inverse iteration using the complex
*>          eigenvalue (WR,WI); otherwise VR and VI need not be set.
*>          On exit, if WI = 0.0 (real eigenvalue), VR contains the
*>          computed real eigenvector; if WI.ne.0.0 (complex eigenvalue),
*>          VR and VI contain the real and imaginary parts of the
*>          computed complex eigenvector. The eigenvector is normalized
*>          so that the component of largest magnitude has magnitude 1;
*>          here the magnitude of a complex number (x,y) is taken to be
*>          |x| + |y|.
*>          VI is not referenced if WI = 0.0.
*> \endverbatim
*>
*> \param[out] B
*> \verbatim
*>          B is DOUBLE PRECISION array, dimension (LDB,N)
*> \endverbatim
*>
*> \param[in] LDB
*> \verbatim
*>          LDB is INTEGER
*>          The leading dimension of the array B.  LDB >= N+1.
*> \endverbatim
*>
*> \param[out] WORK
*> \verbatim
*>          WORK is DOUBLE PRECISION array, dimension (N)
*> \endverbatim
*>
*> \param[in] EPS3
*> \verbatim
*>          EPS3 is DOUBLE PRECISION
*>          A small machine-dependent value which is used to perturb
*>          close eigenvalues, and to replace zero pivots.
*> \endverbatim
*>
*> \param[in] SMLNUM
*> \verbatim
*>          SMLNUM is DOUBLE PRECISION
*>          A machine-dependent value close to the underflow threshold.
*> \endverbatim
*>
*> \param[in] BIGNUM
*> \verbatim
*>          BIGNUM is DOUBLE PRECISION
*>          A machine-dependent value close to the overflow threshold.
*> \endverbatim
*>
*> \param[out] INFO
*> \verbatim
*>          INFO is INTEGER
*>          = 0:  successful exit
*>          = 1:  inverse iteration did not converge; VR is set to the
*>                last iterate, and so is VI if WI.ne.0.0.
*> \endverbatim
*
*  Authors:
*  ========
*
*> \author Univ. of Tennessee
*> \author Univ. of California Berkeley
*> \author Univ. of Colorado Denver
*> \author NAG Ltd.
*
*> \ingroup laein
*
*  =====================================================================
      SUBROUTINE dlaein( RIGHTV, NOINIT, N, H, LDH, WR, WI, VR, VI,
     $                   B,
     $                   LDB, WORK, EPS3, SMLNUM, BIGNUM, INFO )
*
*  -- LAPACK auxiliary routine --
*  -- LAPACK is a software package provided by Univ. of Tennessee,    --
*  -- Univ. of California Berkeley, Univ. of Colorado Denver and NAG Ltd..--
*
*     .. Scalar Arguments ..
      LOGICAL            NOINIT, RIGHTV
      INTEGER            INFO, LDB, LDH, N
      DOUBLE PRECISION   BIGNUM, EPS3, SMLNUM, WI, WR
*     ..
*     .. Array Arguments ..
      DOUBLE PRECISION   B( LDB, * ), H( LDH, * ), VI( * ), VR( * ),
     $                   WORK( * )
*     ..
*
*  =====================================================================
*
*     .. Parameters ..
      DOUBLE PRECISION   ZERO, ONE, TENTH
      PARAMETER          ( ZERO = 0.0d+0, one = 1.0d+0, tenth = 1.0d-1 )
*     ..
*     .. Local Scalars ..
      CHARACTER          NORMIN, TRANS
      INTEGER            I, I1, I2, I3, IERR, ITS, J
      DOUBLE PRECISION   ABSBII, ABSBJJ, EI, EJ, GROWTO, NORM, NRMSML,
     $                   rec, rootn, scale, temp, vcrit, vmax, vnorm, w,
     $                   w1, x, xi, xr, y
*     ..
*     .. External Functions ..
      INTEGER            IDAMAX
      DOUBLE PRECISION   DASUM, DLAPY2, DNRM2
      EXTERNAL           idamax, dasum, dlapy2, dnrm2
*     ..
*     .. External Subroutines ..
      EXTERNAL           dladiv, dlatrs, dscal
*     ..
*     .. Intrinsic Functions ..
      INTRINSIC          abs, dble, max, sqrt
*     ..
*     .. Executable Statements ..
*
      info = 0
*
*     GROWTO is the threshold used in the acceptance test for an
*     eigenvector.
*
      rootn = sqrt( dble( n ) )
      growto = tenth / rootn
      nrmsml = max( one, eps3*rootn )*smlnum
*
*     Form B = H - (WR,WI)*I (except that the subdiagonal elements and
*     the imaginary parts of the diagonal elements are not stored).
*
      DO 20 j = 1, n
         DO 10 i = 1, j - 1
            b( i, j ) = h( i, j )
   10    CONTINUE
         b( j, j ) = h( j, j ) - wr
   20 CONTINUE
*
      IF( wi.EQ.zero ) THEN
*
*        Real eigenvalue.
*
         IF( noinit ) THEN
*
*           Set initial vector.
*
            DO 30 i = 1, n
               vr( i ) = eps3
   30       CONTINUE
         ELSE
*
*           Scale supplied initial vector.
*
            vnorm = dnrm2( n, vr, 1 )
            CALL dscal( n, ( eps3*rootn ) / max( vnorm, nrmsml ), vr,
     $                  1 )
         END IF
*
         IF( rightv ) THEN
*
*           LU decomposition with partial pivoting of B, replacing zero
*           pivots by EPS3.
*
            DO 60 i = 1, n - 1
               ei = h( i+1, i )
               IF( abs( b( i, i ) ).LT.abs( ei ) ) THEN
*
*                 Interchange rows and eliminate.
*
                  x = b( i, i ) / ei
                  b( i, i ) = ei
                  DO 40 j = i + 1, n
                     temp = b( i+1, j )
                     b( i+1, j ) = b( i, j ) - x*temp
                     b( i, j ) = temp
   40             CONTINUE
               ELSE
*
*                 Eliminate without interchange.
*
                  IF( b( i, i ).EQ.zero )
     $               b( i, i ) = eps3
                  x = ei / b( i, i )
                  IF( x.NE.zero ) THEN
                     DO 50 j = i + 1, n
                        b( i+1, j ) = b( i+1, j ) - x*b( i, j )
   50                CONTINUE
                  END IF
               END IF
   60       CONTINUE
            IF( b( n, n ).EQ.zero )
     $         b( n, n ) = eps3
*
            trans = 'N'
*
         ELSE
*
*           UL decomposition with partial pivoting of B, replacing zero
*           pivots by EPS3.
*
            DO 90 j = n, 2, -1
               ej = h( j, j-1 )
               IF( abs( b( j, j ) ).LT.abs( ej ) ) THEN
*
*                 Interchange columns and eliminate.
*
                  x = b( j, j ) / ej
                  b( j, j ) = ej
                  DO 70 i = 1, j - 1
                     temp = b( i, j-1 )
                     b( i, j-1 ) = b( i, j ) - x*temp
                     b( i, j ) = temp
   70             CONTINUE
               ELSE
*
*                 Eliminate without interchange.
*
                  IF( b( j, j ).EQ.zero )
     $               b( j, j ) = eps3
                  x = ej / b( j, j )
                  IF( x.NE.zero ) THEN
                     DO 80 i = 1, j - 1
                        b( i, j-1 ) = b( i, j-1 ) - x*b( i, j )
   80                CONTINUE
                  END IF
               END IF
   90       CONTINUE
            IF( b( 1, 1 ).EQ.zero )
     $         b( 1, 1 ) = eps3
*
            trans = 'T'
*
         END IF
*
         normin = 'N'
         DO 110 its = 1, n
*
*           Solve U*x = scale*v for a right eigenvector
*             or U**T*x = scale*v for a left eigenvector,
*           overwriting x on v.
*
            CALL dlatrs( 'Upper', trans, 'Nonunit', normin, n, b,
     $                   ldb,
     $                   vr, scale, work, ierr )
            normin = 'Y'
*
*           Test for sufficient growth in the norm of v.
*
            vnorm = dasum( n, vr, 1 )
            IF( vnorm.GE.growto*scale )
     $         GO TO 120
*
*           Choose new orthogonal starting vector and try again.
*
            temp = eps3 / ( rootn+one )
            vr( 1 ) = eps3
            DO 100 i = 2, n
               vr( i ) = temp
  100       CONTINUE
            vr( n-its+1 ) = vr( n-its+1 ) - eps3*rootn
  110    CONTINUE
*
*        Failure to find eigenvector in N iterations.
*
         info = 1
*
  120    CONTINUE
*
*        Normalize eigenvector.
*
         i = idamax( n, vr, 1 )
         CALL dscal( n, one / abs( vr( i ) ), vr, 1 )
      ELSE
*
*        Complex eigenvalue.
*
         IF( noinit ) THEN
*
*           Set initial vector.
*
            DO 130 i = 1, n
               vr( i ) = eps3
               vi( i ) = zero
  130       CONTINUE
         ELSE
*
*           Scale supplied initial vector.
*
            norm = dlapy2( dnrm2( n, vr, 1 ),
     $                     dnrm2( n, vi, 1 ) )
            rec = ( eps3*rootn ) / max( norm, nrmsml )
            CALL dscal( n, rec, vr, 1 )
            CALL dscal( n, rec, vi, 1 )
         END IF
*
         IF( rightv ) THEN
*
*           LU decomposition with partial pivoting of B, replacing zero
*           pivots by EPS3.
*
*           The imaginary part of the (i,j)-th element of U is stored in
*           B(j+1,i).
*
            b( 2, 1 ) = -wi
            DO 140 i = 2, n
               b( i+1, 1 ) = zero
  140       CONTINUE
*
            DO 170 i = 1, n - 1
               absbii = dlapy2( b( i, i ), b( i+1, i ) )
               ei = h( i+1, i )
               IF( absbii.LT.abs( ei ) ) THEN
*
*                 Interchange rows and eliminate.
*
                  xr = b( i, i ) / ei
                  xi = b( i+1, i ) / ei
                  b( i, i ) = ei
                  b( i+1, i ) = zero
                  DO 150 j = i + 1, n
                     temp = b( i+1, j )
                     b( i+1, j ) = b( i, j ) - xr*temp
                     b( j+1, i+1 ) = b( j+1, i ) - xi*temp
                     b( i, j ) = temp
                     b( j+1, i ) = zero
  150             CONTINUE
                  b( i+2, i ) = -wi
                  b( i+1, i+1 ) = b( i+1, i+1 ) - xi*wi
                  b( i+2, i+1 ) = b( i+2, i+1 ) + xr*wi
               ELSE
*
*                 Eliminate without interchanging rows.
*
                  IF( absbii.EQ.zero ) THEN
                     b( i, i ) = eps3
                     b( i+1, i ) = zero
                     absbii = eps3
                  END IF
                  ei = ( ei / absbii ) / absbii
                  xr = b( i, i )*ei
                  xi = -b( i+1, i )*ei
                  DO 160 j = i + 1, n
                     b( i+1, j ) = b( i+1, j ) - xr*b( i, j ) +
     $                             xi*b( j+1, i )
                     b( j+1, i+1 ) = -xr*b( j+1, i ) - xi*b( i, j )
  160             CONTINUE
                  b( i+2, i+1 ) = b( i+2, i+1 ) - wi
               END IF
*
*              Compute 1-norm of offdiagonal elements of i-th row.
*
               work( i ) = dasum( n-i, b( i, i+1 ), ldb ) +
     $                     dasum( n-i, b( i+2, i ), 1 )
  170       CONTINUE
            IF( b( n, n ).EQ.zero .AND. b( n+1, n ).EQ.zero )
     $         b( n, n ) = eps3
            work( n ) = zero
*
            i1 = n
            i2 = 1
            i3 = -1
         ELSE
*
*           UL decomposition with partial pivoting of conjg(B),
*           replacing zero pivots by EPS3.
*
*           The imaginary part of the (i,j)-th element of U is stored in
*           B(j+1,i).
*
            b( n+1, n ) = wi
            DO 180 j = 1, n - 1
               b( n+1, j ) = zero
  180       CONTINUE
*
            DO 210 j = n, 2, -1
               ej = h( j, j-1 )
               absbjj = dlapy2( b( j, j ), b( j+1, j ) )
               IF( absbjj.LT.abs( ej ) ) THEN
*
*                 Interchange columns and eliminate
*
                  xr = b( j, j ) / ej
                  xi = b( j+1, j ) / ej
                  b( j, j ) = ej
                  b( j+1, j ) = zero
                  DO 190 i = 1, j - 1
                     temp = b( i, j-1 )
                     b( i, j-1 ) = b( i, j ) - xr*temp
                     b( j, i ) = b( j+1, i ) - xi*temp
                     b( i, j ) = temp
                     b( j+1, i ) = zero
  190             CONTINUE
                  b( j+1, j-1 ) = wi
                  b( j-1, j-1 ) = b( j-1, j-1 ) + xi*wi
                  b( j, j-1 ) = b( j, j-1 ) - xr*wi
               ELSE
*
*                 Eliminate without interchange.
*
                  IF( absbjj.EQ.zero ) THEN
                     b( j, j ) = eps3
                     b( j+1, j ) = zero
                     absbjj = eps3
                  END IF
                  ej = ( ej / absbjj ) / absbjj
                  xr = b( j, j )*ej
                  xi = -b( j+1, j )*ej
                  DO 200 i = 1, j - 1
                     b( i, j-1 ) = b( i, j-1 ) - xr*b( i, j ) +
     $                             xi*b( j+1, i )
                     b( j, i ) = -xr*b( j+1, i ) - xi*b( i, j )
  200             CONTINUE
                  b( j, j-1 ) = b( j, j-1 ) + wi
               END IF
*
*              Compute 1-norm of offdiagonal elements of j-th column.
*
               work( j ) = dasum( j-1, b( 1, j ), 1 ) +
     $                     dasum( j-1, b( j+1, 1 ), ldb )
  210       CONTINUE
            IF( b( 1, 1 ).EQ.zero .AND. b( 2, 1 ).EQ.zero )
     $         b( 1, 1 ) = eps3
            work( 1 ) = zero
*
            i1 = 1
            i2 = n
            i3 = 1
         END IF
*
         DO 270 its = 1, n
            scale = one
            vmax = one
            vcrit = bignum
*
*           Solve U*(xr,xi) = scale*(vr,vi) for a right eigenvector,
*             or U**T*(xr,xi) = scale*(vr,vi) for a left eigenvector,
*           overwriting (xr,xi) on (vr,vi).
*
            DO 250 i = i1, i2, i3
*
               IF( work( i ).GT.vcrit ) THEN
                  rec = one / vmax
                  CALL dscal( n, rec, vr, 1 )
                  CALL dscal( n, rec, vi, 1 )
                  scale = scale*rec
                  vmax = one
                  vcrit = bignum
               END IF
*
               xr = vr( i )
               xi = vi( i )
               IF( rightv ) THEN
                  DO 220 j = i + 1, n
                     xr = xr - b( i, j )*vr( j ) + b( j+1, i )*vi( j )
                     xi = xi - b( i, j )*vi( j ) - b( j+1, i )*vr( j )
  220             CONTINUE
               ELSE
                  DO 230 j = 1, i - 1
                     xr = xr - b( j, i )*vr( j ) + b( i+1, j )*vi( j )
                     xi = xi - b( j, i )*vi( j ) - b( i+1, j )*vr( j )
  230             CONTINUE
               END IF
*
               w = abs( b( i, i ) ) + abs( b( i+1, i ) )
               IF( w.GT.smlnum ) THEN
                  IF( w.LT.one ) THEN
                     w1 = abs( xr ) + abs( xi )
                     IF( w1.GT.w*bignum ) THEN
                        rec = one / w1
                        CALL dscal( n, rec, vr, 1 )
                        CALL dscal( n, rec, vi, 1 )
                        xr = vr( i )
                        xi = vi( i )
                        scale = scale*rec
                        vmax = vmax*rec
                     END IF
                  END IF
*
*                 Divide by diagonal element of B.
*
                  CALL dladiv( xr, xi, b( i, i ), b( i+1, i ),
     $                         vr( i ),
     $                         vi( i ) )
                  vmax = max( abs( vr( i ) )+abs( vi( i ) ), vmax )
                  vcrit = bignum / vmax
               ELSE
                  DO 240 j = 1, n
                     vr( j ) = zero
                     vi( j ) = zero
  240             CONTINUE
                  vr( i ) = one
                  vi( i ) = one
                  scale = zero
                  vmax = one
                  vcrit = bignum
               END IF
  250       CONTINUE
*
*           Test for sufficient growth in the norm of (VR,VI).
*
            vnorm = dasum( n, vr, 1 ) + dasum( n, vi, 1 )
            IF( vnorm.GE.growto*scale )
     $         GO TO 280
*
*           Choose a new orthogonal starting vector and try again.
*
            y = eps3 / ( rootn+one )
            vr( 1 ) = eps3
            vi( 1 ) = zero
*
            DO 260 i = 2, n
               vr( i ) = y
               vi( i ) = zero
  260       CONTINUE
            vr( n-its+1 ) = vr( n-its+1 ) - eps3*rootn
  270    CONTINUE
*
*        Failure to find eigenvector in N iterations
*
         info = 1
*
  280    CONTINUE
*
*        Normalize eigenvector.
*
         vnorm = zero
         DO 290 i = 1, n
            vnorm = max( vnorm, abs( vr( i ) )+abs( vi( i ) ) )
  290    CONTINUE
         CALL dscal( n, one / vnorm, vr, 1 )
         CALL dscal( n, one / vnorm, vi, 1 )
*
      END IF
*
      RETURN
*
*     End of DLAEIN
*
      END