LAPACK 3.3.0

zlaqr2.f

Go to the documentation of this file.
00001       SUBROUTINE ZLAQR2( WANTT, WANTZ, N, KTOP, KBOT, NW, H, LDH, ILOZ,
00002      $                   IHIZ, Z, LDZ, NS, ND, SH, V, LDV, NH, T, LDT,
00003      $                   NV, WV, LDWV, WORK, LWORK )
00004 *
00005 *  -- LAPACK auxiliary routine (version 3.2.1)                        --
00006 *     Univ. of Tennessee, Univ. of California Berkeley, Univ. of Colorado Denver and NAG Ltd..
00007 *  -- April 2009                                                      --
00008 *
00009 *     .. Scalar Arguments ..
00010       INTEGER            IHIZ, ILOZ, KBOT, KTOP, LDH, LDT, LDV, LDWV,
00011      $                   LDZ, LWORK, N, ND, NH, NS, NV, NW
00012       LOGICAL            WANTT, WANTZ
00013 *     ..
00014 *     .. Array Arguments ..
00015       COMPLEX*16         H( LDH, * ), SH( * ), T( LDT, * ), V( LDV, * ),
00016      $                   WORK( * ), WV( LDWV, * ), Z( LDZ, * )
00017 *     ..
00018 *
00019 *     This subroutine is identical to ZLAQR3 except that it avoids
00020 *     recursion by calling ZLAHQR instead of ZLAQR4.
00021 *
00022 *
00023 *     ******************************************************************
00024 *     Aggressive early deflation:
00025 *
00026 *     This subroutine accepts as input an upper Hessenberg matrix
00027 *     H and performs an unitary similarity transformation
00028 *     designed to detect and deflate fully converged eigenvalues from
00029 *     a trailing principal submatrix.  On output H has been over-
00030 *     written by a new Hessenberg matrix that is a perturbation of
00031 *     an unitary similarity transformation of H.  It is to be
00032 *     hoped that the final version of H has many zero subdiagonal
00033 *     entries.
00034 *
00035 *     ******************************************************************
00036 *     WANTT   (input) LOGICAL
00037 *          If .TRUE., then the Hessenberg matrix H is fully updated
00038 *          so that the triangular Schur factor may be
00039 *          computed (in cooperation with the calling subroutine).
00040 *          If .FALSE., then only enough of H is updated to preserve
00041 *          the eigenvalues.
00042 *
00043 *     WANTZ   (input) LOGICAL
00044 *          If .TRUE., then the unitary matrix Z is updated so
00045 *          so that the unitary Schur factor may be computed
00046 *          (in cooperation with the calling subroutine).
00047 *          If .FALSE., then Z is not referenced.
00048 *
00049 *     N       (input) INTEGER
00050 *          The order of the matrix H and (if WANTZ is .TRUE.) the
00051 *          order of the unitary matrix Z.
00052 *
00053 *     KTOP    (input) INTEGER
00054 *          It is assumed that either KTOP = 1 or H(KTOP,KTOP-1)=0.
00055 *          KBOT and KTOP together determine an isolated block
00056 *          along the diagonal of the Hessenberg matrix.
00057 *
00058 *     KBOT    (input) INTEGER
00059 *          It is assumed without a check that either
00060 *          KBOT = N or H(KBOT+1,KBOT)=0.  KBOT and KTOP together
00061 *          determine an isolated block along the diagonal of the
00062 *          Hessenberg matrix.
00063 *
00064 *     NW      (input) INTEGER
00065 *          Deflation window size.  1 .LE. NW .LE. (KBOT-KTOP+1).
00066 *
00067 *     H       (input/output) COMPLEX*16 array, dimension (LDH,N)
00068 *          On input the initial N-by-N section of H stores the
00069 *          Hessenberg matrix undergoing aggressive early deflation.
00070 *          On output H has been transformed by a unitary
00071 *          similarity transformation, perturbed, and the returned
00072 *          to Hessenberg form that (it is to be hoped) has some
00073 *          zero subdiagonal entries.
00074 *
00075 *     LDH     (input) integer
00076 *          Leading dimension of H just as declared in the calling
00077 *          subroutine.  N .LE. LDH
00078 *
00079 *     ILOZ    (input) INTEGER
00080 *     IHIZ    (input) INTEGER
00081 *          Specify the rows of Z to which transformations must be
00082 *          applied if WANTZ is .TRUE.. 1 .LE. ILOZ .LE. IHIZ .LE. N.
00083 *
00084 *     Z       (input/output) COMPLEX*16 array, dimension (LDZ,N)
00085 *          IF WANTZ is .TRUE., then on output, the unitary
00086 *          similarity transformation mentioned above has been
00087 *          accumulated into Z(ILOZ:IHIZ,ILO:IHI) from the right.
00088 *          If WANTZ is .FALSE., then Z is unreferenced.
00089 *
00090 *     LDZ     (input) integer
00091 *          The leading dimension of Z just as declared in the
00092 *          calling subroutine.  1 .LE. LDZ.
00093 *
00094 *     NS      (output) integer
00095 *          The number of unconverged (ie approximate) eigenvalues
00096 *          returned in SR and SI that may be used as shifts by the
00097 *          calling subroutine.
00098 *
00099 *     ND      (output) integer
00100 *          The number of converged eigenvalues uncovered by this
00101 *          subroutine.
00102 *
00103 *     SH      (output) COMPLEX*16 array, dimension KBOT
00104 *          On output, approximate eigenvalues that may
00105 *          be used for shifts are stored in SH(KBOT-ND-NS+1)
00106 *          through SR(KBOT-ND).  Converged eigenvalues are
00107 *          stored in SH(KBOT-ND+1) through SH(KBOT).
00108 *
00109 *     V       (workspace) COMPLEX*16 array, dimension (LDV,NW)
00110 *          An NW-by-NW work array.
00111 *
00112 *     LDV     (input) integer scalar
00113 *          The leading dimension of V just as declared in the
00114 *          calling subroutine.  NW .LE. LDV
00115 *
00116 *     NH      (input) integer scalar
00117 *          The number of columns of T.  NH.GE.NW.
00118 *
00119 *     T       (workspace) COMPLEX*16 array, dimension (LDT,NW)
00120 *
00121 *     LDT     (input) integer
00122 *          The leading dimension of T just as declared in the
00123 *          calling subroutine.  NW .LE. LDT
00124 *
00125 *     NV      (input) integer
00126 *          The number of rows of work array WV available for
00127 *          workspace.  NV.GE.NW.
00128 *
00129 *     WV      (workspace) COMPLEX*16 array, dimension (LDWV,NW)
00130 *
00131 *     LDWV    (input) integer
00132 *          The leading dimension of W just as declared in the
00133 *          calling subroutine.  NW .LE. LDV
00134 *
00135 *     WORK    (workspace) COMPLEX*16 array, dimension LWORK.
00136 *          On exit, WORK(1) is set to an estimate of the optimal value
00137 *          of LWORK for the given values of N, NW, KTOP and KBOT.
00138 *
00139 *     LWORK   (input) integer
00140 *          The dimension of the work array WORK.  LWORK = 2*NW
00141 *          suffices, but greater efficiency may result from larger
00142 *          values of LWORK.
00143 *
00144 *          If LWORK = -1, then a workspace query is assumed; ZLAQR2
00145 *          only estimates the optimal workspace size for the given
00146 *          values of N, NW, KTOP and KBOT.  The estimate is returned
00147 *          in WORK(1).  No error message related to LWORK is issued
00148 *          by XERBLA.  Neither H nor Z are accessed.
00149 *
00150 *     ================================================================
00151 *     Based on contributions by
00152 *        Karen Braman and Ralph Byers, Department of Mathematics,
00153 *        University of Kansas, USA
00154 *
00155 *     ================================================================
00156 *     .. Parameters ..
00157       COMPLEX*16         ZERO, ONE
00158       PARAMETER          ( ZERO = ( 0.0d0, 0.0d0 ),
00159      $                   ONE = ( 1.0d0, 0.0d0 ) )
00160       DOUBLE PRECISION   RZERO, RONE
00161       PARAMETER          ( RZERO = 0.0d0, RONE = 1.0d0 )
00162 *     ..
00163 *     .. Local Scalars ..
00164       COMPLEX*16         BETA, CDUM, S, TAU
00165       DOUBLE PRECISION   FOO, SAFMAX, SAFMIN, SMLNUM, ULP
00166       INTEGER            I, IFST, ILST, INFO, INFQR, J, JW, KCOL, KLN,
00167      $                   KNT, KROW, KWTOP, LTOP, LWK1, LWK2, LWKOPT
00168 *     ..
00169 *     .. External Functions ..
00170       DOUBLE PRECISION   DLAMCH
00171       EXTERNAL           DLAMCH
00172 *     ..
00173 *     .. External Subroutines ..
00174       EXTERNAL           DLABAD, ZCOPY, ZGEHRD, ZGEMM, ZLACPY, ZLAHQR,
00175      $                   ZLARF, ZLARFG, ZLASET, ZTREXC, ZUNMHR
00176 *     ..
00177 *     .. Intrinsic Functions ..
00178       INTRINSIC          ABS, DBLE, DCMPLX, DCONJG, DIMAG, INT, MAX, MIN
00179 *     ..
00180 *     .. Statement Functions ..
00181       DOUBLE PRECISION   CABS1
00182 *     ..
00183 *     .. Statement Function definitions ..
00184       CABS1( CDUM ) = ABS( DBLE( CDUM ) ) + ABS( DIMAG( CDUM ) )
00185 *     ..
00186 *     .. Executable Statements ..
00187 *
00188 *     ==== Estimate optimal workspace. ====
00189 *
00190       JW = MIN( NW, KBOT-KTOP+1 )
00191       IF( JW.LE.2 ) THEN
00192          LWKOPT = 1
00193       ELSE
00194 *
00195 *        ==== Workspace query call to ZGEHRD ====
00196 *
00197          CALL ZGEHRD( JW, 1, JW-1, T, LDT, WORK, WORK, -1, INFO )
00198          LWK1 = INT( WORK( 1 ) )
00199 *
00200 *        ==== Workspace query call to ZUNMHR ====
00201 *
00202          CALL ZUNMHR( 'R', 'N', JW, JW, 1, JW-1, T, LDT, WORK, V, LDV,
00203      $                WORK, -1, INFO )
00204          LWK2 = INT( WORK( 1 ) )
00205 *
00206 *        ==== Optimal workspace ====
00207 *
00208          LWKOPT = JW + MAX( LWK1, LWK2 )
00209       END IF
00210 *
00211 *     ==== Quick return in case of workspace query. ====
00212 *
00213       IF( LWORK.EQ.-1 ) THEN
00214          WORK( 1 ) = DCMPLX( LWKOPT, 0 )
00215          RETURN
00216       END IF
00217 *
00218 *     ==== Nothing to do ...
00219 *     ... for an empty active block ... ====
00220       NS = 0
00221       ND = 0
00222       WORK( 1 ) = ONE
00223       IF( KTOP.GT.KBOT )
00224      $   RETURN
00225 *     ... nor for an empty deflation window. ====
00226       IF( NW.LT.1 )
00227      $   RETURN
00228 *
00229 *     ==== Machine constants ====
00230 *
00231       SAFMIN = DLAMCH( 'SAFE MINIMUM' )
00232       SAFMAX = RONE / SAFMIN
00233       CALL DLABAD( SAFMIN, SAFMAX )
00234       ULP = DLAMCH( 'PRECISION' )
00235       SMLNUM = SAFMIN*( DBLE( N ) / ULP )
00236 *
00237 *     ==== Setup deflation window ====
00238 *
00239       JW = MIN( NW, KBOT-KTOP+1 )
00240       KWTOP = KBOT - JW + 1
00241       IF( KWTOP.EQ.KTOP ) THEN
00242          S = ZERO
00243       ELSE
00244          S = H( KWTOP, KWTOP-1 )
00245       END IF
00246 *
00247       IF( KBOT.EQ.KWTOP ) THEN
00248 *
00249 *        ==== 1-by-1 deflation window: not much to do ====
00250 *
00251          SH( KWTOP ) = H( KWTOP, KWTOP )
00252          NS = 1
00253          ND = 0
00254          IF( CABS1( S ).LE.MAX( SMLNUM, ULP*CABS1( H( KWTOP,
00255      $       KWTOP ) ) ) ) THEN
00256             NS = 0
00257             ND = 1
00258             IF( KWTOP.GT.KTOP )
00259      $         H( KWTOP, KWTOP-1 ) = ZERO
00260          END IF
00261          WORK( 1 ) = ONE
00262          RETURN
00263       END IF
00264 *
00265 *     ==== Convert to spike-triangular form.  (In case of a
00266 *     .    rare QR failure, this routine continues to do
00267 *     .    aggressive early deflation using that part of
00268 *     .    the deflation window that converged using INFQR
00269 *     .    here and there to keep track.) ====
00270 *
00271       CALL ZLACPY( 'U', JW, JW, H( KWTOP, KWTOP ), LDH, T, LDT )
00272       CALL ZCOPY( JW-1, H( KWTOP+1, KWTOP ), LDH+1, T( 2, 1 ), LDT+1 )
00273 *
00274       CALL ZLASET( 'A', JW, JW, ZERO, ONE, V, LDV )
00275       CALL ZLAHQR( .true., .true., JW, 1, JW, T, LDT, SH( KWTOP ), 1,
00276      $             JW, V, LDV, INFQR )
00277 *
00278 *     ==== Deflation detection loop ====
00279 *
00280       NS = JW
00281       ILST = INFQR + 1
00282       DO 10 KNT = INFQR + 1, JW
00283 *
00284 *        ==== Small spike tip deflation test ====
00285 *
00286          FOO = CABS1( T( NS, NS ) )
00287          IF( FOO.EQ.RZERO )
00288      $      FOO = CABS1( S )
00289          IF( CABS1( S )*CABS1( V( 1, NS ) ).LE.MAX( SMLNUM, ULP*FOO ) )
00290      $        THEN
00291 *
00292 *           ==== One more converged eigenvalue ====
00293 *
00294             NS = NS - 1
00295          ELSE
00296 *
00297 *           ==== One undeflatable eigenvalue.  Move it up out of the
00298 *           .    way.   (ZTREXC can not fail in this case.) ====
00299 *
00300             IFST = NS
00301             CALL ZTREXC( 'V', JW, T, LDT, V, LDV, IFST, ILST, INFO )
00302             ILST = ILST + 1
00303          END IF
00304    10 CONTINUE
00305 *
00306 *        ==== Return to Hessenberg form ====
00307 *
00308       IF( NS.EQ.0 )
00309      $   S = ZERO
00310 *
00311       IF( NS.LT.JW ) THEN
00312 *
00313 *        ==== sorting the diagonal of T improves accuracy for
00314 *        .    graded matrices.  ====
00315 *
00316          DO 30 I = INFQR + 1, NS
00317             IFST = I
00318             DO 20 J = I + 1, NS
00319                IF( CABS1( T( J, J ) ).GT.CABS1( T( IFST, IFST ) ) )
00320      $            IFST = J
00321    20       CONTINUE
00322             ILST = I
00323             IF( IFST.NE.ILST )
00324      $         CALL ZTREXC( 'V', JW, T, LDT, V, LDV, IFST, ILST, INFO )
00325    30    CONTINUE
00326       END IF
00327 *
00328 *     ==== Restore shift/eigenvalue array from T ====
00329 *
00330       DO 40 I = INFQR + 1, JW
00331          SH( KWTOP+I-1 ) = T( I, I )
00332    40 CONTINUE
00333 *
00334 *
00335       IF( NS.LT.JW .OR. S.EQ.ZERO ) THEN
00336          IF( NS.GT.1 .AND. S.NE.ZERO ) THEN
00337 *
00338 *           ==== Reflect spike back into lower triangle ====
00339 *
00340             CALL ZCOPY( NS, V, LDV, WORK, 1 )
00341             DO 50 I = 1, NS
00342                WORK( I ) = DCONJG( WORK( I ) )
00343    50       CONTINUE
00344             BETA = WORK( 1 )
00345             CALL ZLARFG( NS, BETA, WORK( 2 ), 1, TAU )
00346             WORK( 1 ) = ONE
00347 *
00348             CALL ZLASET( 'L', JW-2, JW-2, ZERO, ZERO, T( 3, 1 ), LDT )
00349 *
00350             CALL ZLARF( 'L', NS, JW, WORK, 1, DCONJG( TAU ), T, LDT,
00351      $                  WORK( JW+1 ) )
00352             CALL ZLARF( 'R', NS, NS, WORK, 1, TAU, T, LDT,
00353      $                  WORK( JW+1 ) )
00354             CALL ZLARF( 'R', JW, NS, WORK, 1, TAU, V, LDV,
00355      $                  WORK( JW+1 ) )
00356 *
00357             CALL ZGEHRD( JW, 1, NS, T, LDT, WORK, WORK( JW+1 ),
00358      $                   LWORK-JW, INFO )
00359          END IF
00360 *
00361 *        ==== Copy updated reduced window into place ====
00362 *
00363          IF( KWTOP.GT.1 )
00364      $      H( KWTOP, KWTOP-1 ) = S*DCONJG( V( 1, 1 ) )
00365          CALL ZLACPY( 'U', JW, JW, T, LDT, H( KWTOP, KWTOP ), LDH )
00366          CALL ZCOPY( JW-1, T( 2, 1 ), LDT+1, H( KWTOP+1, KWTOP ),
00367      $               LDH+1 )
00368 *
00369 *        ==== Accumulate orthogonal matrix in order update
00370 *        .    H and Z, if requested.  ====
00371 *
00372          IF( NS.GT.1 .AND. S.NE.ZERO )
00373      $      CALL ZUNMHR( 'R', 'N', JW, NS, 1, NS, T, LDT, WORK, V, LDV,
00374      $                   WORK( JW+1 ), LWORK-JW, INFO )
00375 *
00376 *        ==== Update vertical slab in H ====
00377 *
00378          IF( WANTT ) THEN
00379             LTOP = 1
00380          ELSE
00381             LTOP = KTOP
00382          END IF
00383          DO 60 KROW = LTOP, KWTOP - 1, NV
00384             KLN = MIN( NV, KWTOP-KROW )
00385             CALL ZGEMM( 'N', 'N', KLN, JW, JW, ONE, H( KROW, KWTOP ),
00386      $                  LDH, V, LDV, ZERO, WV, LDWV )
00387             CALL ZLACPY( 'A', KLN, JW, WV, LDWV, H( KROW, KWTOP ), LDH )
00388    60    CONTINUE
00389 *
00390 *        ==== Update horizontal slab in H ====
00391 *
00392          IF( WANTT ) THEN
00393             DO 70 KCOL = KBOT + 1, N, NH
00394                KLN = MIN( NH, N-KCOL+1 )
00395                CALL ZGEMM( 'C', 'N', JW, KLN, JW, ONE, V, LDV,
00396      $                     H( KWTOP, KCOL ), LDH, ZERO, T, LDT )
00397                CALL ZLACPY( 'A', JW, KLN, T, LDT, H( KWTOP, KCOL ),
00398      $                      LDH )
00399    70       CONTINUE
00400          END IF
00401 *
00402 *        ==== Update vertical slab in Z ====
00403 *
00404          IF( WANTZ ) THEN
00405             DO 80 KROW = ILOZ, IHIZ, NV
00406                KLN = MIN( NV, IHIZ-KROW+1 )
00407                CALL ZGEMM( 'N', 'N', KLN, JW, JW, ONE, Z( KROW, KWTOP ),
00408      $                     LDZ, V, LDV, ZERO, WV, LDWV )
00409                CALL ZLACPY( 'A', KLN, JW, WV, LDWV, Z( KROW, KWTOP ),
00410      $                      LDZ )
00411    80       CONTINUE
00412          END IF
00413       END IF
00414 *
00415 *     ==== Return the number of deflations ... ====
00416 *
00417       ND = JW - NS
00418 *
00419 *     ==== ... and the number of shifts. (Subtracting
00420 *     .    INFQR from the spike length takes care
00421 *     .    of the case of a rare QR failure while
00422 *     .    calculating eigenvalues of the deflation
00423 *     .    window.)  ====
00424 *
00425       NS = NS - INFQR
00426 *
00427 *      ==== Return optimal workspace. ====
00428 *
00429       WORK( 1 ) = DCMPLX( LWKOPT, 0 )
00430 *
00431 *     ==== End of ZLAQR2 ====
00432 *
00433       END
 All Files Functions