dlaqr3.f

*> \brief \b DLAQR3 performs the orthogonal similarity transformation of a Hessenberg matrix to detect and deflate fully converged eigenvalues from a trailing principal submatrix (aggressive early deflation).
*
*  =========== DOCUMENTATION ===========
*
* Online html documentation available at
*            http://www.netlib.org/lapack/explore-html/
*
*> \htmlonly
*> Download DLAQR3 + dependencies
*> <a href="http://www.netlib.org/cgi-bin/netlibfiles.tgz?format=tgz&filename=/lapack/lapack_routine/dlaqr3.f">
*> [TGZ]</a>
*> <a href="http://www.netlib.org/cgi-bin/netlibfiles.zip?format=zip&filename=/lapack/lapack_routine/dlaqr3.f">
*> [ZIP]</a>
*> <a href="http://www.netlib.org/cgi-bin/netlibfiles.txt?format=txt&filename=/lapack/lapack_routine/dlaqr3.f">
*> [TXT]</a>
*> \endhtmlonly
*
*  Definition:
*  ===========
*
*       SUBROUTINE DLAQR3( WANTT, WANTZ, N, KTOP, KBOT, NW, H, LDH, ILOZ,
*                          IHIZ, Z, LDZ, NS, ND, SR, SI, V, LDV, NH, T,
*                          LDT, NV, WV, LDWV, WORK, LWORK )
*
*       .. Scalar Arguments ..
*       INTEGER            IHIZ, ILOZ, KBOT, KTOP, LDH, LDT, LDV, LDWV,
*      $                   LDZ, LWORK, N, ND, NH, NS, NV, NW
*       LOGICAL            WANTT, WANTZ
*       ..
*       .. Array Arguments ..
*       DOUBLE PRECISION   H( LDH, * ), SI( * ), SR( * ), T( LDT, * ),
*      $                   V( LDV, * ), WORK( * ), WV( LDWV, * ),
*      $                   Z( LDZ, * )
*       ..
*
*
*> \par Purpose:
*  =============
*>
*> \verbatim
*>
*>    Aggressive early deflation:
*>
*>    DLAQR3 accepts as input an upper Hessenberg matrix
*>    H and performs an orthogonal similarity transformation
*>    designed to detect and deflate fully converged eigenvalues from
*>    a trailing principal submatrix.  On output H has been over-
*>    written by a new Hessenberg matrix that is a perturbation of
*>    an orthogonal similarity transformation of H.  It is to be
*>    hoped that the final version of H has many zero subdiagonal
*>    entries.
*> \endverbatim
*
*  Arguments:
*  ==========
*
*> \param[in] WANTT
*> \verbatim
*>          WANTT is LOGICAL
*>          If .TRUE., then the Hessenberg matrix H is fully updated
*>          so that the quasi-triangular Schur factor may be
*>          computed (in cooperation with the calling subroutine).
*>          If .FALSE., then only enough of H is updated to preserve
*>          the eigenvalues.
*> \endverbatim
*>
*> \param[in] WANTZ
*> \verbatim
*>          WANTZ is LOGICAL
*>          If .TRUE., then the orthogonal matrix Z is updated so
*>          so that the orthogonal Schur factor may be computed
*>          (in cooperation with the calling subroutine).
*>          If .FALSE., then Z is not referenced.
*> \endverbatim
*>
*> \param[in] N
*> \verbatim
*>          N is INTEGER
*>          The order of the matrix H and (if WANTZ is .TRUE.) the
*>          order of the orthogonal matrix Z.
*> \endverbatim
*>
*> \param[in] KTOP
*> \verbatim
*>          KTOP is INTEGER
*>          It is assumed that either KTOP = 1 or H(KTOP,KTOP-1)=0.
*>          KBOT and KTOP together determine an isolated block
*>          along the diagonal of the Hessenberg matrix.
*> \endverbatim
*>
*> \param[in] KBOT
*> \verbatim
*>          KBOT is INTEGER
*>          It is assumed without a check that either
*>          KBOT = N or H(KBOT+1,KBOT)=0.  KBOT and KTOP together
*>          determine an isolated block along the diagonal of the
*>          Hessenberg matrix.
*> \endverbatim
*>
*> \param[in] NW
*> \verbatim
*>          NW is INTEGER
*>          Deflation window size.  1 <= NW <= (KBOT-KTOP+1).
*> \endverbatim
*>
*> \param[in,out] H
*> \verbatim
*>          H is DOUBLE PRECISION array, dimension (LDH,N)
*>          On input the initial N-by-N section of H stores the
*>          Hessenberg matrix undergoing aggressive early deflation.
*>          On output H has been transformed by an orthogonal
*>          similarity transformation, perturbed, and the returned
*>          to Hessenberg form that (it is to be hoped) has some
*>          zero subdiagonal entries.
*> \endverbatim
*>
*> \param[in] LDH
*> \verbatim
*>          LDH is INTEGER
*>          Leading dimension of H just as declared in the calling
*>          subroutine.  N <= LDH
*> \endverbatim
*>
*> \param[in] ILOZ
*> \verbatim
*>          ILOZ is INTEGER
*> \endverbatim
*>
*> \param[in] IHIZ
*> \verbatim
*>          IHIZ is INTEGER
*>          Specify the rows of Z to which transformations must be
*>          applied if WANTZ is .TRUE.. 1 <= ILOZ <= IHIZ <= N.
*> \endverbatim
*>
*> \param[in,out] Z
*> \verbatim
*>          Z is DOUBLE PRECISION array, dimension (LDZ,N)
*>          IF WANTZ is .TRUE., then on output, the orthogonal
*>          similarity transformation mentioned above has been
*>          accumulated into Z(ILOZ:IHIZ,ILOZ:IHIZ) from the right.
*>          If WANTZ is .FALSE., then Z is unreferenced.
*> \endverbatim
*>
*> \param[in] LDZ
*> \verbatim
*>          LDZ is INTEGER
*>          The leading dimension of Z just as declared in the
*>          calling subroutine.  1 <= LDZ.
*> \endverbatim
*>
*> \param[out] NS
*> \verbatim
*>          NS is INTEGER
*>          The number of unconverged (ie approximate) eigenvalues
*>          returned in SR and SI that may be used as shifts by the
*>          calling subroutine.
*> \endverbatim
*>
*> \param[out] ND
*> \verbatim
*>          ND is INTEGER
*>          The number of converged eigenvalues uncovered by this
*>          subroutine.
*> \endverbatim
*>
*> \param[out] SR
*> \verbatim
*>          SR is DOUBLE PRECISION array, dimension (KBOT)
*> \endverbatim
*>
*> \param[out] SI
*> \verbatim
*>          SI is DOUBLE PRECISION array, dimension (KBOT)
*>          On output, the real and imaginary parts of approximate
*>          eigenvalues that may be used for shifts are stored in
*>          SR(KBOT-ND-NS+1) through SR(KBOT-ND) and
*>          SI(KBOT-ND-NS+1) through SI(KBOT-ND), respectively.
*>          The real and imaginary parts of converged eigenvalues
*>          are stored in SR(KBOT-ND+1) through SR(KBOT) and
*>          SI(KBOT-ND+1) through SI(KBOT), respectively.
*> \endverbatim
*>
*> \param[out] V
*> \verbatim
*>          V is DOUBLE PRECISION array, dimension (LDV,NW)
*>          An NW-by-NW work array.
*> \endverbatim
*>
*> \param[in] LDV
*> \verbatim
*>          LDV is INTEGER
*>          The leading dimension of V just as declared in the
*>          calling subroutine.  NW <= LDV
*> \endverbatim
*>
*> \param[in] NH
*> \verbatim
*>          NH is INTEGER
*>          The number of columns of T.  NH >= NW.
*> \endverbatim
*>
*> \param[out] T
*> \verbatim
*>          T is DOUBLE PRECISION array, dimension (LDT,NW)
*> \endverbatim
*>
*> \param[in] LDT
*> \verbatim
*>          LDT is INTEGER
*>          The leading dimension of T just as declared in the
*>          calling subroutine.  NW <= LDT
*> \endverbatim
*>
*> \param[in] NV
*> \verbatim
*>          NV is INTEGER
*>          The number of rows of work array WV available for
*>          workspace.  NV >= NW.
*> \endverbatim
*>
*> \param[out] WV
*> \verbatim
*>          WV is DOUBLE PRECISION array, dimension (LDWV,NW)
*> \endverbatim
*>
*> \param[in] LDWV
*> \verbatim
*>          LDWV is INTEGER
*>          The leading dimension of W just as declared in the
*>          calling subroutine.  NW <= LDV
*> \endverbatim
*>
*> \param[out] WORK
*> \verbatim
*>          WORK is DOUBLE PRECISION array, dimension (LWORK)
*>          On exit, WORK(1) is set to an estimate of the optimal value
*>          of LWORK for the given values of N, NW, KTOP and KBOT.
*> \endverbatim
*>
*> \param[in] LWORK
*> \verbatim
*>          LWORK is INTEGER
*>          The dimension of the work array WORK.  LWORK = 2*NW
*>          suffices, but greater efficiency may result from larger
*>          values of LWORK.
*>
*>          If LWORK = -1, then a workspace query is assumed; DLAQR3
*>          only estimates the optimal workspace size for the given
*>          values of N, NW, KTOP and KBOT.  The estimate is returned
*>          in WORK(1).  No error message related to LWORK is issued
*>          by XERBLA.  Neither H nor Z are accessed.
*> \endverbatim
*
*  Authors:
*  ========
*
*> \author Univ. of Tennessee
*> \author Univ. of California Berkeley
*> \author Univ. of Colorado Denver
*> \author NAG Ltd.
*
*> \ingroup laqr3
*
*> \par Contributors:
*  ==================
*>
*>       Karen Braman and Ralph Byers, Department of Mathematics,
*>       University of Kansas, USA
*>
*  =====================================================================
      SUBROUTINE dlaqr3( WANTT, WANTZ, N, KTOP, KBOT, NW, H, LDH, ILOZ,
     $                   IHIZ, Z, LDZ, NS, ND, SR, SI, V, LDV, NH, T,
     $                   LDT, NV, WV, LDWV, WORK, LWORK )
*
*  -- 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 ..
      INTEGER            IHIZ, ILOZ, KBOT, KTOP, LDH, LDT, LDV, LDWV,
     $                   ldz, lwork, n, nd, nh, ns, nv, nw
      LOGICAL            WANTT, WANTZ
*     ..
*     .. Array Arguments ..
      DOUBLE PRECISION   H( ldh, * ), SI( * ), SR( * ), T( ldt, * ),
     $                   v( ldv, * ), work( * ), wv( ldwv, * ),
     $                   z( ldz, * )
*     ..
*
*  ================================================================
*     .. Parameters ..
      DOUBLE PRECISION   ZERO, ONE
      parameter( zero = 0.0d0, one = 1.0d0 )
*     ..
*     .. Local Scalars ..
      DOUBLE PRECISION   AA, BB, BETA, CC, CS, DD, EVI, EVK, FOO, S,
     $                   safmax, safmin, smlnum, sn, tau, ulp
      INTEGER            I, IFST, ILST, INFO, INFQR, J, JW, K, KCOL,
     $                   kend, kln, krow, kwtop, ltop, lwk1, lwk2, lwk3,
     $                   lwkopt, nmin
      LOGICAL            BULGE, SORTED
*     ..
*     .. External Functions ..
      DOUBLE PRECISION   DLAMCH
      INTEGER            ILAENV
      EXTERNAL           dlamch, ilaenv
*     ..
*     .. External Subroutines ..
      EXTERNAL           dcopy, dgehrd, dgemm, dlabad, dlacpy, dlahqr,
     $                   dlanv2, dlaqr4, dlarf, dlarfg, dlaset, dormhr,
     $                   dtrexc
*     ..
*     .. Intrinsic Functions ..
      INTRINSIC          abs, dble, int, max, min, sqrt
*     ..
*     .. Executable Statements ..
*
*     ==== Estimate optimal workspace. ====
*
      jw = min( nw, kbot-ktop+1 )
      IF( jw.LE.2 ) THEN
         lwkopt = 1
      ELSE
*
*        ==== Workspace query call to DGEHRD ====
*
         CALL dgehrd( jw, 1, jw-1, t, ldt, work, work, -1, info )
         lwk1 = int( work( 1 ) )
*
*        ==== Workspace query call to DORMHR ====
*
         CALL dormhr( 'R', 'N', jw, jw, 1, jw-1, t, ldt, work, v, ldv,
     $                work, -1, info )
         lwk2 = int( work( 1 ) )
*
*        ==== Workspace query call to DLAQR4 ====
*
         CALL dlaqr4( .true., .true., jw, 1, jw, t, ldt, sr, si, 1, jw,
     $                v, ldv, work, -1, infqr )
         lwk3 = int( work( 1 ) )
*
*        ==== Optimal workspace ====
*
         lwkopt = max( jw+max( lwk1, lwk2 ), lwk3 )
      END IF
*
*     ==== Quick return in case of workspace query. ====
*
      IF( lwork.EQ.-1 ) THEN
         work( 1 ) = dble( lwkopt )
         RETURN
      END IF
*
*     ==== Nothing to do ...
*     ... for an empty active block ... ====
      ns = 0
      nd = 0
      work( 1 ) = one
      IF( ktop.GT.kbot )
     $   RETURN
*     ... nor for an empty deflation window. ====
      IF( nw.LT.1 )
     $   RETURN
*
*     ==== Machine constants ====
*
      safmin = dlamch( 'SAFE MINIMUM' )
      safmax = one / safmin
      CALL dlabad( safmin, safmax )
      ulp = dlamch( 'PRECISION' )
      smlnum = safmin*( dble( n ) / ulp )
*
*     ==== Setup deflation window ====
*
      jw = min( nw, kbot-ktop+1 )
      kwtop = kbot - jw + 1
      IF( kwtop.EQ.ktop ) THEN
         s = zero
      ELSE
         s = h( kwtop, kwtop-1 )
      END IF
*
      IF( kbot.EQ.kwtop ) THEN
*
*        ==== 1-by-1 deflation window: not much to do ====
*
         sr( kwtop ) = h( kwtop, kwtop )
         si( kwtop ) = zero
         ns = 1
         nd = 0
         IF( abs( s ).LE.max( smlnum, ulp*abs( h( kwtop, kwtop ) ) ) )
     $        THEN
            ns = 0
            nd = 1
            IF( kwtop.GT.ktop )
     $         h( kwtop, kwtop-1 ) = zero
         END IF
         work( 1 ) = one
         RETURN
      END IF
*
*     ==== Convert to spike-triangular form.  (In case of a
*     .    rare QR failure, this routine continues to do
*     .    aggressive early deflation using that part of
*     .    the deflation window that converged using INFQR
*     .    here and there to keep track.) ====
*
      CALL dlacpy( 'U', jw, jw, h( kwtop, kwtop ), ldh, t, ldt )
      CALL dcopy( jw-1, h( kwtop+1, kwtop ), ldh+1, t( 2, 1 ), ldt+1 )
*
      CALL dlaset( 'A', jw, jw, zero, one, v, ldv )
      nmin = ilaenv( 12, 'DLAQR3', 'SV', jw, 1, jw, lwork )
      IF( jw.GT.nmin ) THEN
         CALL dlaqr4( .true., .true., jw, 1, jw, t, ldt, sr( kwtop ),
     $                si( kwtop ), 1, jw, v, ldv, work, lwork, infqr )
      ELSE
         CALL dlahqr( .true., .true., jw, 1, jw, t, ldt, sr( kwtop ),
     $                si( kwtop ), 1, jw, v, ldv, infqr )
      END IF
*
*     ==== DTREXC needs a clean margin near the diagonal ====
*
      DO 10 j = 1, jw - 3
         t( j+2, j ) = zero
         t( j+3, j ) = zero
   10 CONTINUE
      IF( jw.GT.2 )
     $   t( jw, jw-2 ) = zero
*
*     ==== Deflation detection loop ====
*
      ns = jw
      ilst = infqr + 1
   20 CONTINUE
      IF( ilst.LE.ns ) THEN
         IF( ns.EQ.1 ) THEN
            bulge = .false.
         ELSE
            bulge = t( ns, ns-1 ).NE.zero
         END IF
*
*        ==== Small spike tip test for deflation ====
*
         IF( .NOT. bulge ) THEN
*
*           ==== Real eigenvalue ====
*
            foo = abs( t( ns, ns ) )
            IF( foo.EQ.zero )
     $         foo = abs( s )
            IF( abs( s*v( 1, ns ) ).LE.max( smlnum, ulp*foo ) ) THEN
*
*              ==== Deflatable ====
*
               ns = ns - 1
            ELSE
*
*              ==== Undeflatable.   Move it up out of the way.
*              .    (DTREXC can not fail in this case.) ====
*
               ifst = ns
               CALL dtrexc( 'V', jw, t, ldt, v, ldv, ifst, ilst, work,
     $                      info )
               ilst = ilst + 1
            END IF
         ELSE
*
*           ==== Complex conjugate pair ====
*
            foo = abs( t( ns, ns ) ) + sqrt( abs( t( ns, ns-1 ) ) )*
     $            sqrt( abs( t( ns-1, ns ) ) )
            IF( foo.EQ.zero )
     $         foo = abs( s )
            IF( max( abs( s*v( 1, ns ) ), abs( s*v( 1, ns-1 ) ) ).LE.
     $          max( smlnum, ulp*foo ) ) THEN
*
*              ==== Deflatable ====
*
               ns = ns - 2
            ELSE
*
*              ==== Undeflatable. Move them up out of the way.
*              .    Fortunately, DTREXC does the right thing with
*              .    ILST in case of a rare exchange failure. ====
*
               ifst = ns
               CALL dtrexc( 'V', jw, t, ldt, v, ldv, ifst, ilst, work,
     $                      info )
               ilst = ilst + 2
            END IF
         END IF
*
*        ==== End deflation detection loop ====
*
         GO TO 20
      END IF
*
*        ==== Return to Hessenberg form ====
*
      IF( ns.EQ.0 )
     $   s = zero
*
      IF( ns.LT.jw ) THEN
*
*        ==== sorting diagonal blocks of T improves accuracy for
*        .    graded matrices.  Bubble sort deals well with
*        .    exchange failures. ====
*
         sorted = .false.
         i = ns + 1
   30    CONTINUE
         IF( sorted )
     $      GO TO 50
         sorted = .true.
*
         kend = i - 1
         i = infqr + 1
         IF( i.EQ.ns ) THEN
            k = i + 1
         ELSE IF( t( i+1, i ).EQ.zero ) THEN
            k = i + 1
         ELSE
            k = i + 2
         END IF
   40    CONTINUE
         IF( k.LE.kend ) THEN
            IF( k.EQ.i+1 ) THEN
               evi = abs( t( i, i ) )
            ELSE
               evi = abs( t( i, i ) ) + sqrt( abs( t( i+1, i ) ) )*
     $               sqrt( abs( t( i, i+1 ) ) )
            END IF
*
            IF( k.EQ.kend ) THEN
               evk = abs( t( k, k ) )
            ELSE IF( t( k+1, k ).EQ.zero ) THEN
               evk = abs( t( k, k ) )
            ELSE
               evk = abs( t( k, k ) ) + sqrt( abs( t( k+1, k ) ) )*
     $               sqrt( abs( t( k, k+1 ) ) )
            END IF
*
            IF( evi.GE.evk ) THEN
               i = k
            ELSE
               sorted = .false.
               ifst = i
               ilst = k
               CALL dtrexc( 'V', jw, t, ldt, v, ldv, ifst, ilst, work,
     $                      info )
               IF( info.EQ.0 ) THEN
                  i = ilst
               ELSE
                  i = k
               END IF
            END IF
            IF( i.EQ.kend ) THEN
               k = i + 1
            ELSE IF( t( i+1, i ).EQ.zero ) THEN
               k = i + 1
            ELSE
               k = i + 2
            END IF
            GO TO 40
         END IF
         GO TO 30
   50    CONTINUE
      END IF
*
*     ==== Restore shift/eigenvalue array from T ====
*
      i = jw
   60 CONTINUE
      IF( i.GE.infqr+1 ) THEN
         IF( i.EQ.infqr+1 ) THEN
            sr( kwtop+i-1 ) = t( i, i )
            si( kwtop+i-1 ) = zero
            i = i - 1
         ELSE IF( t( i, i-1 ).EQ.zero ) THEN
            sr( kwtop+i-1 ) = t( i, i )
            si( kwtop+i-1 ) = zero
            i = i - 1
         ELSE
            aa = t( i-1, i-1 )
            cc = t( i, i-1 )
            bb = t( i-1, i )
            dd = t( i, i )
            CALL dlanv2( aa, bb, cc, dd, sr( kwtop+i-2 ),
     $                   si( kwtop+i-2 ), sr( kwtop+i-1 ),
     $                   si( kwtop+i-1 ), cs, sn )
            i = i - 2
         END IF
         GO TO 60
      END IF
*
      IF( ns.LT.jw .OR. s.EQ.zero ) THEN
         IF( ns.GT.1 .AND. s.NE.zero ) THEN
*
*           ==== Reflect spike back into lower triangle ====
*
            CALL dcopy( ns, v, ldv, work, 1 )
            beta = work( 1 )
            CALL dlarfg( ns, beta, work( 2 ), 1, tau )
            work( 1 ) = one
*
            CALL dlaset( 'L', jw-2, jw-2, zero, zero, t( 3, 1 ), ldt )
*
            CALL dlarf( 'L', ns, jw, work, 1, tau, t, ldt,
     $                  work( jw+1 ) )
            CALL dlarf( 'R', ns, ns, work, 1, tau, t, ldt,
     $                  work( jw+1 ) )
            CALL dlarf( 'R', jw, ns, work, 1, tau, v, ldv,
     $                  work( jw+1 ) )
*
            CALL dgehrd( jw, 1, ns, t, ldt, work, work( jw+1 ),
     $                   lwork-jw, info )
         END IF
*
*        ==== Copy updated reduced window into place ====
*
         IF( kwtop.GT.1 )
     $      h( kwtop, kwtop-1 ) = s*v( 1, 1 )
         CALL dlacpy( 'U', jw, jw, t, ldt, h( kwtop, kwtop ), ldh )
         CALL dcopy( jw-1, t( 2, 1 ), ldt+1, h( kwtop+1, kwtop ),
     $               ldh+1 )
*
*        ==== Accumulate orthogonal matrix in order update
*        .    H and Z, if requested.  ====
*
         IF( ns.GT.1 .AND. s.NE.zero )
     $      CALL dormhr( 'R', 'N', jw, ns, 1, ns, t, ldt, work, v, ldv,
     $                   work( jw+1 ), lwork-jw, info )
*
*        ==== Update vertical slab in H ====
*
         IF( wantt ) THEN
            ltop = 1
         ELSE
            ltop = ktop
         END IF
         DO 70 krow = ltop, kwtop - 1, nv
            kln = min( nv, kwtop-krow )
            CALL dgemm( 'N', 'N', kln, jw, jw, one, h( krow, kwtop ),
     $                  ldh, v, ldv, zero, wv, ldwv )
            CALL dlacpy( 'A', kln, jw, wv, ldwv, h( krow, kwtop ), ldh )
   70    CONTINUE
*
*        ==== Update horizontal slab in H ====
*
         IF( wantt ) THEN
            DO 80 kcol = kbot + 1, n, nh
               kln = min( nh, n-kcol+1 )
               CALL dgemm( 'C', 'N', jw, kln, jw, one, v, ldv,
     $                     h( kwtop, kcol ), ldh, zero, t, ldt )
               CALL dlacpy( 'A', jw, kln, t, ldt, h( kwtop, kcol ),
     $                      ldh )
   80       CONTINUE
         END IF
*
*        ==== Update vertical slab in Z ====
*
         IF( wantz ) THEN
            DO 90 krow = iloz, ihiz, nv
               kln = min( nv, ihiz-krow+1 )
               CALL dgemm( 'N', 'N', kln, jw, jw, one, z( krow, kwtop ),
     $                     ldz, v, ldv, zero, wv, ldwv )
               CALL dlacpy( 'A', kln, jw, wv, ldwv, z( krow, kwtop ),
     $                      ldz )
   90       CONTINUE
         END IF
      END IF
*
*     ==== Return the number of deflations ... ====
*
      nd = jw - ns
*
*     ==== ... and the number of shifts. (Subtracting
*     .    INFQR from the spike length takes care
*     .    of the case of a rare QR failure while
*     .    calculating eigenvalues of the deflation
*     .    window.)  ====
*
      ns = ns - infqr
*
*      ==== Return optimal workspace. ====
*
      work( 1 ) = dble( lwkopt )
*
*     ==== End of DLAQR3 ====
*
      END