dtgexc.f

*> \brief \b DTGEXC
*
*  =========== DOCUMENTATION ===========
*
* Online html documentation available at
*            http://www.netlib.org/lapack/explore-html/
*
*> \htmlonly
*> Download DTGEXC + dependencies
*> <a href="http://www.netlib.org/cgi-bin/netlibfiles.tgz?format=tgz&filename=/lapack/lapack_routine/dtgexc.f">
*> [TGZ]</a>
*> <a href="http://www.netlib.org/cgi-bin/netlibfiles.zip?format=zip&filename=/lapack/lapack_routine/dtgexc.f">
*> [ZIP]</a>
*> <a href="http://www.netlib.org/cgi-bin/netlibfiles.txt?format=txt&filename=/lapack/lapack_routine/dtgexc.f">
*> [TXT]</a>
*> \endhtmlonly
*
*  Definition:
*  ===========
*
*       SUBROUTINE DTGEXC( WANTQ, WANTZ, N, A, LDA, B, LDB, Q, LDQ, Z,
*                          LDZ, IFST, ILST, WORK, LWORK, INFO )
*
*       .. Scalar Arguments ..
*       LOGICAL            WANTQ, WANTZ
*       INTEGER            IFST, ILST, INFO, LDA, LDB, LDQ, LDZ, LWORK, N
*       ..
*       .. Array Arguments ..
*       DOUBLE PRECISION   A( LDA, * ), B( LDB, * ), Q( LDQ, * ),
*      $                   WORK( * ), Z( LDZ, * )
*       ..
*
*
*> \par Purpose:
*  =============
*>
*> \verbatim
*>
*> DTGEXC reorders the generalized real Schur decomposition of a real
*> matrix pair (A,B) using an orthogonal equivalence transformation
*>
*>                (A, B) = Q * (A, B) * Z**T,
*>
*> so that the diagonal block of (A, B) with row index IFST is moved
*> to row ILST.
*>
*> (A, B) must be in generalized real Schur canonical form (as returned
*> by DGGES), i.e. A is block upper triangular with 1-by-1 and 2-by-2
*> diagonal blocks. B is upper triangular.
*>
*> Optionally, the matrices Q and Z of generalized Schur vectors are
*> updated.
*>
*>        Q(in) * A(in) * Z(in)**T = Q(out) * A(out) * Z(out)**T
*>        Q(in) * B(in) * Z(in)**T = Q(out) * B(out) * Z(out)**T
*>
*> \endverbatim
*
*  Arguments:
*  ==========
*
*> \param[in] WANTQ
*> \verbatim
*>          WANTQ is LOGICAL
*>          .TRUE. : update the left transformation matrix Q;
*>          .FALSE.: do not update Q.
*> \endverbatim
*>
*> \param[in] WANTZ
*> \verbatim
*>          WANTZ is LOGICAL
*>          .TRUE. : update the right transformation matrix Z;
*>          .FALSE.: do not update Z.
*> \endverbatim
*>
*> \param[in] N
*> \verbatim
*>          N is INTEGER
*>          The order of the matrices A and B. N >= 0.
*> \endverbatim
*>
*> \param[in,out] A
*> \verbatim
*>          A is DOUBLE PRECISION array, dimension (LDA,N)
*>          On entry, the matrix A in generalized real Schur canonical
*>          form.
*>          On exit, the updated matrix A, again in generalized
*>          real Schur canonical form.
*> \endverbatim
*>
*> \param[in] LDA
*> \verbatim
*>          LDA is INTEGER
*>          The leading dimension of the array A. LDA >= max(1,N).
*> \endverbatim
*>
*> \param[in,out] B
*> \verbatim
*>          B is DOUBLE PRECISION array, dimension (LDB,N)
*>          On entry, the matrix B in generalized real Schur canonical
*>          form (A,B).
*>          On exit, the updated matrix B, again in generalized
*>          real Schur canonical form (A,B).
*> \endverbatim
*>
*> \param[in] LDB
*> \verbatim
*>          LDB is INTEGER
*>          The leading dimension of the array B. LDB >= max(1,N).
*> \endverbatim
*>
*> \param[in,out] Q
*> \verbatim
*>          Q is DOUBLE PRECISION array, dimension (LDQ,N)
*>          On entry, if WANTQ = .TRUE., the orthogonal matrix Q.
*>          On exit, the updated matrix Q.
*>          If WANTQ = .FALSE., Q is not referenced.
*> \endverbatim
*>
*> \param[in] LDQ
*> \verbatim
*>          LDQ is INTEGER
*>          The leading dimension of the array Q. LDQ >= 1.
*>          If WANTQ = .TRUE., LDQ >= N.
*> \endverbatim
*>
*> \param[in,out] Z
*> \verbatim
*>          Z is DOUBLE PRECISION array, dimension (LDZ,N)
*>          On entry, if WANTZ = .TRUE., the orthogonal matrix Z.
*>          On exit, the updated matrix Z.
*>          If WANTZ = .FALSE., Z is not referenced.
*> \endverbatim
*>
*> \param[in] LDZ
*> \verbatim
*>          LDZ is INTEGER
*>          The leading dimension of the array Z. LDZ >= 1.
*>          If WANTZ = .TRUE., LDZ >= N.
*> \endverbatim
*>
*> \param[in,out] IFST
*> \verbatim
*>          IFST is INTEGER
*> \endverbatim
*>
*> \param[in,out] ILST
*> \verbatim
*>          ILST is INTEGER
*>          Specify the reordering of the diagonal blocks of (A, B).
*>          The block with row index IFST is moved to row ILST, by a
*>          sequence of swapping between adjacent blocks.
*>          On exit, if IFST pointed on entry to the second row of
*>          a 2-by-2 block, it is changed to point to the first row;
*>          ILST always points to the first row of the block in its
*>          final position (which may differ from its input value by
*>          +1 or -1). 1 <= IFST, ILST <= N.
*> \endverbatim
*>
*> \param[out] WORK
*> \verbatim
*>          WORK is DOUBLE PRECISION array, dimension (MAX(1,LWORK))
*>          On exit, if INFO = 0, WORK(1) returns the optimal LWORK.
*> \endverbatim
*>
*> \param[in] LWORK
*> \verbatim
*>          LWORK is INTEGER
*>          The dimension of the array WORK.
*>          LWORK >= 1 when N <= 1, otherwise LWORK >= 4*N + 16.
*>
*>          If LWORK = -1, then a workspace query is assumed; the routine
*>          only calculates the optimal size of the WORK array, returns
*>          this value as the first entry of the WORK array, and no error
*>          message related to LWORK is issued by XERBLA.
*> \endverbatim
*>
*> \param[out] INFO
*> \verbatim
*>          INFO is INTEGER
*>           =0:  successful exit.
*>           <0:  if INFO = -i, the i-th argument had an illegal value.
*>           =1:  The transformed matrix pair (A, B) would be too far
*>                from generalized Schur form; the problem is ill-
*>                conditioned. (A, B) may have been partially reordered,
*>                and ILST points to the first row of the current
*>                position of the block being moved.
*> \endverbatim
*
*  Authors:
*  ========
*
*> \author Univ. of Tennessee
*> \author Univ. of California Berkeley
*> \author Univ. of Colorado Denver
*> \author NAG Ltd.
*
*> \ingroup tgexc
*
*> \par Contributors:
*  ==================
*>
*>     Bo Kagstrom and Peter Poromaa, Department of Computing Science,
*>     Umea University, S-901 87 Umea, Sweden.
*
*> \par References:
*  ================
*>
*> \verbatim
*>
*>  [1] B. Kagstrom; A Direct Method for Reordering Eigenvalues in the
*>      Generalized Real Schur Form of a Regular Matrix Pair (A, B), in
*>      M.S. Moonen et al (eds), Linear Algebra for Large Scale and
*>      Real-Time Applications, Kluwer Academic Publ. 1993, pp 195-218.
*> \endverbatim
*>
*  =====================================================================
      SUBROUTINE dtgexc( WANTQ, WANTZ, N, A, LDA, B, LDB, Q, LDQ, Z,
     $                   LDZ, IFST, ILST, WORK, LWORK, INFO )
*
*  -- LAPACK computational 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            WANTQ, WANTZ
      INTEGER            IFST, ILST, INFO, LDA, LDB, LDQ, LDZ, LWORK, N
*     ..
*     .. Array Arguments ..
      DOUBLE PRECISION   A( lda, * ), B( ldb, * ), Q( ldq, * ),
     $                   work( * ), z( ldz, * )
*     ..
*
*  =====================================================================
*
*     .. Parameters ..
      DOUBLE PRECISION   ZERO
      parameter( zero = 0.0d+0 )
*     ..
*     .. Local Scalars ..
      LOGICAL            LQUERY
      INTEGER            HERE, LWMIN, NBF, NBL, NBNEXT
*     ..
*     .. External Subroutines ..
      EXTERNAL           dtgex2, xerbla
*     ..
*     .. Intrinsic Functions ..
      INTRINSIC          max
*     ..
*     .. Executable Statements ..
*
*     Decode and test input arguments.
*
      info = 0
      lquery = ( lwork.EQ.-1 )
      IF( n.LT.0 ) THEN
         info = -3
      ELSE IF( lda.LT.max( 1, n ) ) THEN
         info = -5
      ELSE IF( ldb.LT.max( 1, n ) ) THEN
         info = -7
      ELSE IF( ldq.LT.1 .OR. wantq .AND. ( ldq.LT.max( 1, n ) ) ) THEN
         info = -9
      ELSE IF( ldz.LT.1 .OR. wantz .AND. ( ldz.LT.max( 1, n ) ) ) THEN
         info = -11
      ELSE IF( ifst.LT.1 .OR. ifst.GT.n ) THEN
         info = -12
      ELSE IF( ilst.LT.1 .OR. ilst.GT.n ) THEN
         info = -13
      END IF
*
      IF( info.EQ.0 ) THEN
         IF( n.LE.1 ) THEN
            lwmin = 1
         ELSE
            lwmin = 4*n + 16
         END IF
         work(1) = lwmin
*
         IF (lwork.LT.lwmin .AND. .NOT.lquery) THEN
            info = -15
         END IF
      END IF
*
      IF( info.NE.0 ) THEN
         CALL xerbla( 'DTGEXC', -info )
         RETURN
      ELSE IF( lquery ) THEN
         RETURN
      END IF
*
*     Quick return if possible
*
      IF( n.LE.1 )
     $   RETURN
*
*     Determine the first row of the specified block and find out
*     if it is 1-by-1 or 2-by-2.
*
      IF( ifst.GT.1 ) THEN
         IF( a( ifst, ifst-1 ).NE.zero )
     $      ifst = ifst - 1
      END IF
      nbf = 1
      IF( ifst.LT.n ) THEN
         IF( a( ifst+1, ifst ).NE.zero )
     $      nbf = 2
      END IF
*
*     Determine the first row of the final block
*     and find out if it is 1-by-1 or 2-by-2.
*
      IF( ilst.GT.1 ) THEN
         IF( a( ilst, ilst-1 ).NE.zero )
     $      ilst = ilst - 1
      END IF
      nbl = 1
      IF( ilst.LT.n ) THEN
         IF( a( ilst+1, ilst ).NE.zero )
     $      nbl = 2
      END IF
      IF( ifst.EQ.ilst )
     $   RETURN
*
      IF( ifst.LT.ilst ) THEN
*
*        Update ILST.
*
         IF( nbf.EQ.2 .AND. nbl.EQ.1 )
     $      ilst = ilst - 1
         IF( nbf.EQ.1 .AND. nbl.EQ.2 )
     $      ilst = ilst + 1
*
         here = ifst
*
   10    CONTINUE
*
*        Swap with next one below.
*
         IF( nbf.EQ.1 .OR. nbf.EQ.2 ) THEN
*
*           Current block either 1-by-1 or 2-by-2.
*
            nbnext = 1
            IF( here+nbf+1.LE.n ) THEN
               IF( a( here+nbf+1, here+nbf ).NE.zero )
     $            nbnext = 2
            END IF
            CALL dtgex2( wantq, wantz, n, a, lda, b, ldb, q, ldq, z,
     $                   ldz, here, nbf, nbnext, work, lwork, info )
            IF( info.NE.0 ) THEN
               ilst = here
               RETURN
            END IF
            here = here + nbnext
*
*           Test if 2-by-2 block breaks into two 1-by-1 blocks.
*
            IF( nbf.EQ.2 ) THEN
               IF( a( here+1, here ).EQ.zero )
     $            nbf = 3
            END IF
*
         ELSE
*
*           Current block consists of two 1-by-1 blocks, each of which
*           must be swapped individually.
*
            nbnext = 1
            IF( here+3.LE.n ) THEN
               IF( a( here+3, here+2 ).NE.zero )
     $            nbnext = 2
            END IF
            CALL dtgex2( wantq, wantz, n, a, lda, b, ldb, q, ldq, z,
     $                   ldz, here+1, 1, nbnext, work, lwork, info )
            IF( info.NE.0 ) THEN
               ilst = here
               RETURN
            END IF
            IF( nbnext.EQ.1 ) THEN
*
*              Swap two 1-by-1 blocks.
*
               CALL dtgex2( wantq, wantz, n, a, lda, b, ldb, q, ldq, z,
     $                      ldz, here, 1, 1, work, lwork, info )
               IF( info.NE.0 ) THEN
                  ilst = here
                  RETURN
               END IF
               here = here + 1
*
            ELSE
*
*              Recompute NBNEXT in case of 2-by-2 split.
*
               IF( a( here+2, here+1 ).EQ.zero )
     $            nbnext = 1
               IF( nbnext.EQ.2 ) THEN
*
*                 2-by-2 block did not split.
*
                  CALL dtgex2( wantq, wantz, n, a, lda, b, ldb, q, ldq,
     $                         z, ldz, here, 1, nbnext, work, lwork,
     $                         info )
                  IF( info.NE.0 ) THEN
                     ilst = here
                     RETURN
                  END IF
                  here = here + 2
               ELSE
*
*                 2-by-2 block did split.
*
                  CALL dtgex2( wantq, wantz, n, a, lda, b, ldb, q, ldq,
     $                         z, ldz, here, 1, 1, work, lwork, info )
                  IF( info.NE.0 ) THEN
                     ilst = here
                     RETURN
                  END IF
                  here = here + 1
                  CALL dtgex2( wantq, wantz, n, a, lda, b, ldb, q, ldq,
     $                         z, ldz, here, 1, 1, work, lwork, info )
                  IF( info.NE.0 ) THEN
                     ilst = here
                     RETURN
                  END IF
                  here = here + 1
               END IF
*
            END IF
         END IF
         IF( here.LT.ilst )
     $      GO TO 10
      ELSE
         here = ifst
*
   20    CONTINUE
*
*        Swap with next one below.
*
         IF( nbf.EQ.1 .OR. nbf.EQ.2 ) THEN
*
*           Current block either 1-by-1 or 2-by-2.
*
            nbnext = 1
            IF( here.GE.3 ) THEN
               IF( a( here-1, here-2 ).NE.zero )
     $            nbnext = 2
            END IF
            CALL dtgex2( wantq, wantz, n, a, lda, b, ldb, q, ldq, z,
     $                   ldz, here-nbnext, nbnext, nbf, work, lwork,
     $                   info )
            IF( info.NE.0 ) THEN
               ilst = here
               RETURN
            END IF
            here = here - nbnext
*
*           Test if 2-by-2 block breaks into two 1-by-1 blocks.
*
            IF( nbf.EQ.2 ) THEN
               IF( a( here+1, here ).EQ.zero )
     $            nbf = 3
            END IF
*
         ELSE
*
*           Current block consists of two 1-by-1 blocks, each of which
*           must be swapped individually.
*
            nbnext = 1
            IF( here.GE.3 ) THEN
               IF( a( here-1, here-2 ).NE.zero )
     $            nbnext = 2
            END IF
            CALL dtgex2( wantq, wantz, n, a, lda, b, ldb, q, ldq, z,
     $                   ldz, here-nbnext, nbnext, 1, work, lwork,
     $                   info )
            IF( info.NE.0 ) THEN
               ilst = here
               RETURN
            END IF
            IF( nbnext.EQ.1 ) THEN
*
*              Swap two 1-by-1 blocks.
*
               CALL dtgex2( wantq, wantz, n, a, lda, b, ldb, q, ldq, z,
     $                      ldz, here, nbnext, 1, work, lwork, info )
               IF( info.NE.0 ) THEN
                  ilst = here
                  RETURN
               END IF
               here = here - 1
            ELSE
*
*             Recompute NBNEXT in case of 2-by-2 split.
*
               IF( a( here, here-1 ).EQ.zero )
     $            nbnext = 1
               IF( nbnext.EQ.2 ) THEN
*
*                 2-by-2 block did not split.
*
                  CALL dtgex2( wantq, wantz, n, a, lda, b, ldb, q, ldq,
     $                         z, ldz, here-1, 2, 1, work, lwork, info )
                  IF( info.NE.0 ) THEN
                     ilst = here
                     RETURN
                  END IF
                  here = here - 2
               ELSE
*
*                 2-by-2 block did split.
*
                  CALL dtgex2( wantq, wantz, n, a, lda, b, ldb, q, ldq,
     $                         z, ldz, here, 1, 1, work, lwork, info )
                  IF( info.NE.0 ) THEN
                     ilst = here
                     RETURN
                  END IF
                  here = here - 1
                  CALL dtgex2( wantq, wantz, n, a, lda, b, ldb, q, ldq,
     $                         z, ldz, here, 1, 1, work, lwork, info )
                  IF( info.NE.0 ) THEN
                     ilst = here
                     RETURN
                  END IF
                  here = here - 1
               END IF
            END IF
         END IF
         IF( here.GT.ilst )
     $      GO TO 20
      END IF
      ilst = here
      work( 1 ) = lwmin
      RETURN
*
*     End of DTGEXC
*
      END