diff libcruft/lapack/zhseqr.f @ 2329:30c606bec7a8

[project @ 1996-07-19 01:29:05 by jwe] Initial revision
author jwe
date Fri, 19 Jul 1996 01:29:55 +0000
parents
children 15cddaacbc2d
line wrap: on
line diff
new file mode 100644
--- /dev/null
+++ b/libcruft/lapack/zhseqr.f
@@ -0,0 +1,461 @@
+      SUBROUTINE ZHSEQR( JOB, COMPZ, N, ILO, IHI, H, LDH, W, Z, LDZ,
+     $                   WORK, LWORK, INFO )
+*
+*  -- LAPACK routine (version 2.0) --
+*     Univ. of Tennessee, Univ. of California Berkeley, NAG Ltd.,
+*     Courant Institute, Argonne National Lab, and Rice University
+*     September 30, 1994
+*
+*     .. Scalar Arguments ..
+      CHARACTER          COMPZ, JOB
+      INTEGER            IHI, ILO, INFO, LDH, LDZ, LWORK, N
+*     ..
+*     .. Array Arguments ..
+      COMPLEX*16         H( LDH, * ), W( * ), WORK( * ), Z( LDZ, * )
+*     ..
+*
+*  Purpose
+*  =======
+*
+*  ZHSEQR computes the eigenvalues of a complex upper Hessenberg
+*  matrix H, and, optionally, the matrices T and Z from the Schur
+*  decomposition H = Z T Z**H, where T is an upper triangular matrix
+*  (the Schur form), and Z is the unitary matrix of Schur vectors.
+*
+*  Optionally Z may be postmultiplied into an input unitary matrix Q,
+*  so that this routine can give the Schur factorization of a matrix A
+*  which has been reduced to the Hessenberg form H by the unitary
+*  matrix Q:  A = Q*H*Q**H = (QZ)*T*(QZ)**H.
+*
+*  Arguments
+*  =========
+*
+*  JOB     (input) CHARACTER*1
+*          = 'E': compute eigenvalues only;
+*          = 'S': compute eigenvalues and the Schur form T.
+*
+*  COMPZ   (input) CHARACTER*1
+*          = 'N': no Schur vectors are computed;
+*          = 'I': Z is initialized to the unit matrix and the matrix Z
+*                 of Schur vectors of H is returned;
+*          = 'V': Z must contain an unitary matrix Q on entry, and
+*                 the product Q*Z is returned.
+*
+*  N       (input) INTEGER
+*          The order of the matrix H.  N >= 0.
+*
+*  ILO     (input) INTEGER
+*  IHI     (input) INTEGER
+*          It is assumed that H is already upper triangular in rows
+*          and columns 1:ILO-1 and IHI+1:N. ILO and IHI are normally
+*          set by a previous call to ZGEBAL, and then passed to CGEHRD
+*          when the matrix output by ZGEBAL is reduced to Hessenberg
+*          form. Otherwise ILO and IHI should be set to 1 and N
+*          respectively.
+*          1 <= ILO <= IHI <= N, if N > 0; ILO=1 and IHI=0, if N=0.
+*
+*  H       (input/output) COMPLEX*16 array, dimension (LDH,N)
+*          On entry, the upper Hessenberg matrix H.
+*          On exit, if JOB = 'S', H contains the upper triangular matrix
+*          T from the Schur decomposition (the Schur form). If
+*          JOB = 'E', the contents of H are unspecified on exit.
+*
+*  LDH     (input) INTEGER
+*          The leading dimension of the array H. LDH >= max(1,N).
+*
+*  W       (output) COMPLEX*16 array, dimension (N)
+*          The computed eigenvalues. If JOB = 'S', the eigenvalues are
+*          stored in the same order as on the diagonal of the Schur form
+*          returned in H, with W(i) = H(i,i).
+*
+*  Z       (input/output) COMPLEX*16 array, dimension (LDZ,N)
+*          If COMPZ = 'N': Z is not referenced.
+*          If COMPZ = 'I': on entry, Z need not be set, and on exit, Z
+*          contains the unitary matrix Z of the Schur vectors of H.
+*          If COMPZ = 'V': on entry Z must contain an N-by-N matrix Q,
+*          which is assumed to be equal to the unit matrix except for
+*          the submatrix Z(ILO:IHI,ILO:IHI); on exit Z contains Q*Z.
+*          Normally Q is the unitary matrix generated by ZUNGHR after
+*          the call to ZGEHRD which formed the Hessenberg matrix H.
+*
+*  LDZ     (input) INTEGER
+*          The leading dimension of the array Z.
+*          LDZ >= max(1,N) if COMPZ = 'I' or 'V'; LDZ >= 1 otherwise.
+*
+*  WORK    (workspace) COMPLEX*16 array, dimension (N)
+*
+*  LWORK   (input) INTEGER
+*          This argument is currently redundant.
+*
+*  INFO    (output) INTEGER
+*          = 0:  successful exit
+*          < 0:  if INFO = -i, the i-th argument had an illegal value
+*          > 0:  if INFO = i, ZHSEQR failed to compute all the
+*                eigenvalues in a total of 30*(IHI-ILO+1) iterations;
+*                elements 1:ilo-1 and i+1:n of W contain those
+*                eigenvalues which have been successfully computed.
+*
+*  =====================================================================
+*
+*     .. Parameters ..
+      COMPLEX*16         ZERO, ONE
+      PARAMETER          ( ZERO = ( 0.0D+0, 0.0D+0 ),
+     $                   ONE = ( 1.0D+0, 0.0D+0 ) )
+      DOUBLE PRECISION   RZERO, RONE, CONST
+      PARAMETER          ( RZERO = 0.0D+0, RONE = 1.0D+0,
+     $                   CONST = 1.5D+0 )
+      INTEGER            NSMAX, LDS
+      PARAMETER          ( NSMAX = 15, LDS = NSMAX )
+*     ..
+*     .. Local Scalars ..
+      LOGICAL            INITZ, WANTT, WANTZ
+      INTEGER            I, I1, I2, IERR, II, ITEMP, ITN, ITS, J, K, L,
+     $                   MAXB, NH, NR, NS, NV
+      DOUBLE PRECISION   OVFL, RTEMP, SMLNUM, TST1, ULP, UNFL
+      COMPLEX*16         CDUM, TAU, TEMP
+*     ..
+*     .. Local Arrays ..
+      DOUBLE PRECISION   RWORK( 1 )
+      COMPLEX*16         S( LDS, NSMAX ), V( NSMAX+1 ), VV( NSMAX+1 )
+*     ..
+*     .. External Functions ..
+      LOGICAL            LSAME
+      INTEGER            ILAENV, IZAMAX
+      DOUBLE PRECISION   DLAMCH, DLAPY2, ZLANHS
+      EXTERNAL           LSAME, ILAENV, IZAMAX, DLAMCH, DLAPY2, ZLANHS
+*     ..
+*     .. External Subroutines ..
+      EXTERNAL           DLABAD, XERBLA, ZCOPY, ZDSCAL, ZGEMV, ZLACPY,
+     $                   ZLAHQR, ZLARFG, ZLARFX, ZLASET, ZSCAL
+*     ..
+*     .. Intrinsic Functions ..
+      INTRINSIC          ABS, DBLE, DCONJG, DIMAG, MAX, MIN
+*     ..
+*     .. Statement Functions ..
+      DOUBLE PRECISION   CABS1
+*     ..
+*     .. Statement Function definitions ..
+      CABS1( CDUM ) = ABS( DBLE( CDUM ) ) + ABS( DIMAG( CDUM ) )
+*     ..
+*     .. Executable Statements ..
+*
+*     Decode and test the input parameters
+*
+      WANTT = LSAME( JOB, 'S' )
+      INITZ = LSAME( COMPZ, 'I' )
+      WANTZ = INITZ .OR. LSAME( COMPZ, 'V' )
+*
+      INFO = 0
+      IF( .NOT.LSAME( JOB, 'E' ) .AND. .NOT.WANTT ) THEN
+         INFO = -1
+      ELSE IF( .NOT.LSAME( COMPZ, 'N' ) .AND. .NOT.WANTZ ) THEN
+         INFO = -2
+      ELSE IF( N.LT.0 ) THEN
+         INFO = -3
+      ELSE IF( ILO.LT.1 .OR. ILO.GT.MAX( 1, N ) ) THEN
+         INFO = -4
+      ELSE IF( IHI.LT.MIN( ILO, N ) .OR. IHI.GT.N ) THEN
+         INFO = -5
+      ELSE IF( LDH.LT.MAX( 1, N ) ) THEN
+         INFO = -7
+      ELSE IF( LDZ.LT.1 .OR. WANTZ .AND. LDZ.LT.MAX( 1, N ) ) THEN
+         INFO = -10
+      END IF
+      IF( INFO.NE.0 ) THEN
+         CALL XERBLA( 'ZHSEQR', -INFO )
+         RETURN
+      END IF
+*
+*     Initialize Z, if necessary
+*
+      IF( INITZ )
+     $   CALL ZLASET( 'Full', N, N, ZERO, ONE, Z, LDZ )
+*
+*     Store the eigenvalues isolated by ZGEBAL.
+*
+      DO 10 I = 1, ILO - 1
+         W( I ) = H( I, I )
+   10 CONTINUE
+      DO 20 I = IHI + 1, N
+         W( I ) = H( I, I )
+   20 CONTINUE
+*
+*     Quick return if possible.
+*
+      IF( N.EQ.0 )
+     $   RETURN
+      IF( ILO.EQ.IHI ) THEN
+         W( ILO ) = H( ILO, ILO )
+         RETURN
+      END IF
+*
+*     Set rows and columns ILO to IHI to zero below the first
+*     subdiagonal.
+*
+      DO 40 J = ILO, IHI - 2
+         DO 30 I = J + 2, N
+            H( I, J ) = ZERO
+   30    CONTINUE
+   40 CONTINUE
+      NH = IHI - ILO + 1
+*
+*     I1 and I2 are the indices of the first row and last column of H
+*     to which transformations must be applied. If eigenvalues only are
+*     being computed, I1 and I2 are re-set inside the main loop.
+*
+      IF( WANTT ) THEN
+         I1 = 1
+         I2 = N
+      ELSE
+         I1 = ILO
+         I2 = IHI
+      END IF
+*
+*     Ensure that the subdiagonal elements are real.
+*
+      DO 50 I = ILO + 1, IHI
+         TEMP = H( I, I-1 )
+         IF( DIMAG( TEMP ).NE.RZERO ) THEN
+            RTEMP = DLAPY2( DBLE( TEMP ), DIMAG( TEMP ) )
+            H( I, I-1 ) = RTEMP
+            TEMP = TEMP / RTEMP
+            IF( I2.GT.I )
+     $         CALL ZSCAL( I2-I, DCONJG( TEMP ), H( I, I+1 ), LDH )
+            CALL ZSCAL( I-I1, TEMP, H( I1, I ), 1 )
+            IF( I.LT.IHI )
+     $         H( I+1, I ) = TEMP*H( I+1, I )
+            IF( WANTZ )
+     $         CALL ZSCAL( NH, TEMP, Z( ILO, I ), 1 )
+         END IF
+   50 CONTINUE
+*
+*     Determine the order of the multi-shift QR algorithm to be used.
+*
+      NS = ILAENV( 4, 'ZHSEQR', JOB // COMPZ, N, ILO, IHI, -1 )
+      MAXB = ILAENV( 8, 'ZHSEQR', JOB // COMPZ, N, ILO, IHI, -1 )
+      IF( NS.LE.1 .OR. NS.GT.NH .OR. MAXB.GE.NH ) THEN
+*
+*        Use the standard double-shift algorithm
+*
+         CALL ZLAHQR( WANTT, WANTZ, N, ILO, IHI, H, LDH, W, ILO, IHI, Z,
+     $                LDZ, INFO )
+         RETURN
+      END IF
+      MAXB = MAX( 2, MAXB )
+      NS = MIN( NS, MAXB, NSMAX )
+*
+*     Now 1 < NS <= MAXB < NH.
+*
+*     Set machine-dependent constants for the stopping criterion.
+*     If norm(H) <= sqrt(OVFL), overflow should not occur.
+*
+      UNFL = DLAMCH( 'Safe minimum' )
+      OVFL = RONE / UNFL
+      CALL DLABAD( UNFL, OVFL )
+      ULP = DLAMCH( 'Precision' )
+      SMLNUM = UNFL*( NH / ULP )
+*
+*     ITN is the total number of multiple-shift QR iterations allowed.
+*
+      ITN = 30*NH
+*
+*     The main loop begins here. I is the loop index and decreases from
+*     IHI to ILO in steps of at most MAXB. Each iteration of the loop
+*     works with the active submatrix in rows and columns L to I.
+*     Eigenvalues I+1 to IHI have already converged. Either L = ILO, or
+*     H(L,L-1) is negligible so that the matrix splits.
+*
+      I = IHI
+   60 CONTINUE
+      IF( I.LT.ILO )
+     $   GO TO 180
+*
+*     Perform multiple-shift QR iterations on rows and columns ILO to I
+*     until a submatrix of order at most MAXB splits off at the bottom
+*     because a subdiagonal element has become negligible.
+*
+      L = ILO
+      DO 160 ITS = 0, ITN
+*
+*        Look for a single small subdiagonal element.
+*
+         DO 70 K = I, L + 1, -1
+            TST1 = CABS1( H( K-1, K-1 ) ) + CABS1( H( K, K ) )
+            IF( TST1.EQ.RZERO )
+     $         TST1 = ZLANHS( '1', I-L+1, H( L, L ), LDH, RWORK )
+            IF( ABS( DBLE( H( K, K-1 ) ) ).LE.MAX( ULP*TST1, SMLNUM ) )
+     $         GO TO 80
+   70    CONTINUE
+   80    CONTINUE
+         L = K
+         IF( L.GT.ILO ) THEN
+*
+*           H(L,L-1) is negligible.
+*
+            H( L, L-1 ) = ZERO
+         END IF
+*
+*        Exit from loop if a submatrix of order <= MAXB has split off.
+*
+         IF( L.GE.I-MAXB+1 )
+     $      GO TO 170
+*
+*        Now the active submatrix is in rows and columns L to I. If
+*        eigenvalues only are being computed, only the active submatrix
+*        need be transformed.
+*
+         IF( .NOT.WANTT ) THEN
+            I1 = L
+            I2 = I
+         END IF
+*
+         IF( ITS.EQ.20 .OR. ITS.EQ.30 ) THEN
+*
+*           Exceptional shifts.
+*
+            DO 90 II = I - NS + 1, I
+               W( II ) = CONST*( ABS( DBLE( H( II, II-1 ) ) )+
+     $                   ABS( DBLE( H( II, II ) ) ) )
+   90       CONTINUE
+         ELSE
+*
+*           Use eigenvalues of trailing submatrix of order NS as shifts.
+*
+            CALL ZLACPY( 'Full', NS, NS, H( I-NS+1, I-NS+1 ), LDH, S,
+     $                   LDS )
+            CALL ZLAHQR( .FALSE., .FALSE., NS, 1, NS, S, LDS,
+     $                   W( I-NS+1 ), 1, NS, Z, LDZ, IERR )
+            IF( IERR.GT.0 ) THEN
+*
+*              If ZLAHQR failed to compute all NS eigenvalues, use the
+*              unconverged diagonal elements as the remaining shifts.
+*
+               DO 100 II = 1, IERR
+                  W( I-NS+II ) = S( II, II )
+  100          CONTINUE
+            END IF
+         END IF
+*
+*        Form the first column of (G-w(1)) (G-w(2)) . . . (G-w(ns))
+*        where G is the Hessenberg submatrix H(L:I,L:I) and w is
+*        the vector of shifts (stored in W). The result is
+*        stored in the local array V.
+*
+         V( 1 ) = ONE
+         DO 110 II = 2, NS + 1
+            V( II ) = ZERO
+  110    CONTINUE
+         NV = 1
+         DO 130 J = I - NS + 1, I
+            CALL ZCOPY( NV+1, V, 1, VV, 1 )
+            CALL ZGEMV( 'No transpose', NV+1, NV, ONE, H( L, L ), LDH,
+     $                  VV, 1, -W( J ), V, 1 )
+            NV = NV + 1
+*
+*           Scale V(1:NV) so that max(abs(V(i))) = 1. If V is zero,
+*           reset it to the unit vector.
+*
+            ITEMP = IZAMAX( NV, V, 1 )
+            RTEMP = CABS1( V( ITEMP ) )
+            IF( RTEMP.EQ.RZERO ) THEN
+               V( 1 ) = ONE
+               DO 120 II = 2, NV
+                  V( II ) = ZERO
+  120          CONTINUE
+            ELSE
+               RTEMP = MAX( RTEMP, SMLNUM )
+               CALL ZDSCAL( NV, RONE / RTEMP, V, 1 )
+            END IF
+  130    CONTINUE
+*
+*        Multiple-shift QR step
+*
+         DO 150 K = L, I - 1
+*
+*           The first iteration of this loop determines a reflection G
+*           from the vector V and applies it from left and right to H,
+*           thus creating a nonzero bulge below the subdiagonal.
+*
+*           Each subsequent iteration determines a reflection G to
+*           restore the Hessenberg form in the (K-1)th column, and thus
+*           chases the bulge one step toward the bottom of the active
+*           submatrix. NR is the order of G.
+*
+            NR = MIN( NS+1, I-K+1 )
+            IF( K.GT.L )
+     $         CALL ZCOPY( NR, H( K, K-1 ), 1, V, 1 )
+            CALL ZLARFG( NR, V( 1 ), V( 2 ), 1, TAU )
+            IF( K.GT.L ) THEN
+               H( K, K-1 ) = V( 1 )
+               DO 140 II = K + 1, I
+                  H( II, K-1 ) = ZERO
+  140          CONTINUE
+            END IF
+            V( 1 ) = ONE
+*
+*           Apply G' from the left to transform the rows of the matrix
+*           in columns K to I2.
+*
+            CALL ZLARFX( 'Left', NR, I2-K+1, V, DCONJG( TAU ),
+     $                   H( K, K ), LDH, WORK )
+*
+*           Apply G from the right to transform the columns of the
+*           matrix in rows I1 to min(K+NR,I).
+*
+            CALL ZLARFX( 'Right', MIN( K+NR, I )-I1+1, NR, V, TAU,
+     $                   H( I1, K ), LDH, WORK )
+*
+            IF( WANTZ ) THEN
+*
+*              Accumulate transformations in the matrix Z
+*
+               CALL ZLARFX( 'Right', NH, NR, V, TAU, Z( ILO, K ), LDZ,
+     $                      WORK )
+            END IF
+  150    CONTINUE
+*
+*        Ensure that H(I,I-1) is real.
+*
+         TEMP = H( I, I-1 )
+         IF( DIMAG( TEMP ).NE.RZERO ) THEN
+            RTEMP = DLAPY2( DBLE( TEMP ), DIMAG( TEMP ) )
+            H( I, I-1 ) = RTEMP
+            TEMP = TEMP / RTEMP
+            IF( I2.GT.I )
+     $         CALL ZSCAL( I2-I, DCONJG( TEMP ), H( I, I+1 ), LDH )
+            CALL ZSCAL( I-I1, TEMP, H( I1, I ), 1 )
+            IF( WANTZ ) THEN
+               CALL ZSCAL( NH, TEMP, Z( ILO, I ), 1 )
+            END IF
+         END IF
+*
+  160 CONTINUE
+*
+*     Failure to converge in remaining number of iterations
+*
+      INFO = I
+      RETURN
+*
+  170 CONTINUE
+*
+*     A submatrix of order <= MAXB in rows and columns L to I has split
+*     off. Use the double-shift QR algorithm to handle it.
+*
+      CALL ZLAHQR( WANTT, WANTZ, N, L, I, H, LDH, W, ILO, IHI, Z, LDZ,
+     $             INFO )
+      IF( INFO.GT.0 )
+     $   RETURN
+*
+*     Decrement number of remaining iterations, and return to start of
+*     the main loop with a new value of I.
+*
+      ITN = ITN - ITS
+      I = L - 1
+      GO TO 60
+*
+  180 CONTINUE
+      RETURN
+*
+*     End of ZHSEQR
+*
+      END