claed0.f

Go to the documentation of this file.

*> \brief \b CLAED0 used by CSTEDC. Computes all eigenvalues and corresponding eigenvectors of an unreduced symmetric tridiagonal matrix using the divide and conquer method.
*
*  =========== DOCUMENTATION ===========
*
* Online html documentation available at
*            http://www.netlib.org/lapack/explore-html/
*
*> \htmlonly
*> Download CLAED0 + dependencies
*> <a href="http://www.netlib.org/cgi-bin/netlibfiles.tgz?format=tgz&filename=/lapack/lapack_routine/claed0.f">
*> [TGZ]</a>
*> <a href="http://www.netlib.org/cgi-bin/netlibfiles.zip?format=zip&filename=/lapack/lapack_routine/claed0.f">
*> [ZIP]</a>
*> <a href="http://www.netlib.org/cgi-bin/netlibfiles.txt?format=txt&filename=/lapack/lapack_routine/claed0.f">
*> [TXT]</a>
*> \endhtmlonly
*
*  Definition:
*  ===========
*
*       SUBROUTINE CLAED0( QSIZ, N, D, E, Q, LDQ, QSTORE, LDQS, RWORK,
*                          IWORK, INFO )
*
*       .. Scalar Arguments ..
*       INTEGER            INFO, LDQ, LDQS, N, QSIZ
*       ..
*       .. Array Arguments ..
*       INTEGER            IWORK( * )
*       REAL               D( * ), E( * ), RWORK( * )
*       COMPLEX            Q( LDQ, * ), QSTORE( LDQS, * )
*       ..
*
*
*> \par Purpose:
*  =============
*>
*> \verbatim
*>
*> Using the divide and conquer method, CLAED0 computes all eigenvalues
*> of a symmetric tridiagonal matrix which is one diagonal block of
*> those from reducing a dense or band Hermitian matrix and
*> corresponding eigenvectors of the dense or band matrix.
*> \endverbatim
*
*  Arguments:
*  ==========
*
*> \param[in] QSIZ
*> \verbatim
*>          QSIZ is INTEGER
*>         The dimension of the unitary matrix used to reduce
*>         the full matrix to tridiagonal form.  QSIZ >= N if ICOMPQ = 1.
*> \endverbatim
*>
*> \param[in] N
*> \verbatim
*>          N is INTEGER
*>         The dimension of the symmetric tridiagonal matrix.  N >= 0.
*> \endverbatim
*>
*> \param[in,out] D
*> \verbatim
*>          D is REAL array, dimension (N)
*>         On entry, the diagonal elements of the tridiagonal matrix.
*>         On exit, the eigenvalues in ascending order.
*> \endverbatim
*>
*> \param[in,out] E
*> \verbatim
*>          E is REAL array, dimension (N-1)
*>         On entry, the off-diagonal elements of the tridiagonal matrix.
*>         On exit, E has been destroyed.
*> \endverbatim
*>
*> \param[in,out] Q
*> \verbatim
*>          Q is COMPLEX array, dimension (LDQ,N)
*>         On entry, Q must contain an QSIZ x N matrix whose columns
*>         unitarily orthonormal. It is a part of the unitary matrix
*>         that reduces the full dense Hermitian matrix to a
*>         (reducible) symmetric tridiagonal matrix.
*> \endverbatim
*>
*> \param[in] LDQ
*> \verbatim
*>          LDQ is INTEGER
*>         The leading dimension of the array Q.  LDQ >= max(1,N).
*> \endverbatim
*>
*> \param[out] IWORK
*> \verbatim
*>          IWORK is INTEGER array,
*>         the dimension of IWORK must be at least
*>                      6 + 6*N + 5*N*lg N
*>                      ( lg( N ) = smallest integer k
*>                                  such that 2^k >= N )
*> \endverbatim
*>
*> \param[out] RWORK
*> \verbatim
*>          RWORK is REAL array,
*>                               dimension (1 + 3*N + 2*N*lg N + 3*N**2)
*>                        ( lg( N ) = smallest integer k
*>                                    such that 2^k >= N )
*> \endverbatim
*>
*> \param[out] QSTORE
*> \verbatim
*>          QSTORE is COMPLEX array, dimension (LDQS, N)
*>         Used to store parts of
*>         the eigenvector matrix when the updating matrix multiplies
*>         take place.
*> \endverbatim
*>
*> \param[in] LDQS
*> \verbatim
*>          LDQS is INTEGER
*>         The leading dimension of the array QSTORE.
*>         LDQS >= max(1,N).
*> \endverbatim
*>
*> \param[out] INFO
*> \verbatim
*>          INFO is INTEGER
*>          = 0:  successful exit.
*>          < 0:  if INFO = -i, the i-th argument had an illegal value.
*>          > 0:  The algorithm failed to compute an eigenvalue while
*>                working on the submatrix lying in rows and columns
*>                INFO/(N+1) through mod(INFO,N+1).
*> \endverbatim
*
*  Authors:
*  ========
*
*> \author Univ. of Tennessee
*> \author Univ. of California Berkeley
*> \author Univ. of Colorado Denver
*> \author NAG Ltd.
*
*> \ingroup laed0
*
*  =====================================================================
      SUBROUTINE claed0( QSIZ, N, D, E, Q, LDQ, QSTORE, LDQS, RWORK,
     $                   IWORK, 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 ..
      INTEGER            INFO, LDQ, LDQS, N, QSIZ
*     ..
*     .. Array Arguments ..
      INTEGER            IWORK( * )
      REAL               D( * ), E( * ), RWORK( * )
      COMPLEX            Q( LDQ, * ), QSTORE( LDQS, * )
*     ..
*
*  =====================================================================
*
*  Warning:      N could be as big as QSIZ!
*
*     .. Parameters ..
      REAL               TWO
      parameter( two = 2.e+0 )
*     ..
*     .. Local Scalars ..
      INTEGER            CURLVL, CURPRB, CURR, I, IGIVCL, IGIVNM,
     $                   igivpt, indxq, iperm, iprmpt, iq, iqptr, iwrem,
     $                   j, k, lgn, ll, matsiz, msd2, smlsiz, smm1,
     $                   spm1, spm2, submat, subpbs, tlvls
      REAL               TEMP
*     ..
*     .. External Subroutines ..
      EXTERNAL           ccopy, clacrm, claed7, scopy, ssteqr, xerbla
*     ..
*     .. External Functions ..
      INTEGER            ILAENV
      EXTERNAL           ilaenv
*     ..
*     .. Intrinsic Functions ..
      INTRINSIC          abs, int, log, max, real
*     ..
*     .. Executable Statements ..
*
*     Test the input parameters.
*
      info = 0
*
*     IF( ICOMPQ .LT. 0 .OR. ICOMPQ .GT. 2 ) THEN
*        INFO = -1
*     ELSE IF( ( ICOMPQ .EQ. 1 ) .AND. ( QSIZ .LT. MAX( 0, N ) ) )
*    $        THEN
      IF( qsiz.LT.max( 0, n ) ) THEN
         info = -1
      ELSE IF( n.LT.0 ) THEN
         info = -2
      ELSE IF( ldq.LT.max( 1, n ) ) THEN
         info = -6
      ELSE IF( ldqs.LT.max( 1, n ) ) THEN
         info = -8
      END IF
      IF( info.NE.0 ) THEN
         CALL xerbla( 'CLAED0', -info )
         RETURN
      END IF
*
*     Quick return if possible
*
      IF( n.EQ.0 )
     $   RETURN
*
      smlsiz = ilaenv( 9, 'CLAED0', ' ', 0, 0, 0, 0 )
*
*     Determine the size and placement of the submatrices, and save in
*     the leading elements of IWORK.
*
      iwork( 1 ) = n
      subpbs = 1
      tlvls = 0
   10 CONTINUE
      IF( iwork( subpbs ).GT.smlsiz ) THEN
         DO 20 j = subpbs, 1, -1
            iwork( 2*j ) = ( iwork( j )+1 ) / 2
            iwork( 2*j-1 ) = iwork( j ) / 2
   20    CONTINUE
         tlvls = tlvls + 1
         subpbs = 2*subpbs
         GO TO 10
      END IF
      DO 30 j = 2, subpbs
         iwork( j ) = iwork( j ) + iwork( j-1 )
   30 CONTINUE
*
*     Divide the matrix into SUBPBS submatrices of size at most SMLSIZ+1
*     using rank-1 modifications (cuts).
*
      spm1 = subpbs - 1
      DO 40 i = 1, spm1
         submat = iwork( i ) + 1
         smm1 = submat - 1
         d( smm1 ) = d( smm1 ) - abs( e( smm1 ) )
         d( submat ) = d( submat ) - abs( e( smm1 ) )
   40 CONTINUE
*
      indxq = 4*n + 3
*
*     Set up workspaces for eigenvalues only/accumulate new vectors
*     routine
*
      temp = log( real( n ) ) / log( two )
      lgn = int( temp )
      IF( 2**lgn.LT.n )
     $   lgn = lgn + 1
      IF( 2**lgn.LT.n )
     $   lgn = lgn + 1
      iprmpt = indxq + n + 1
      iperm = iprmpt + n*lgn
      iqptr = iperm + n*lgn
      igivpt = iqptr + n + 2
      igivcl = igivpt + n*lgn
*
      igivnm = 1
      iq = igivnm + 2*n*lgn
      iwrem = iq + n**2 + 1
*     Initialize pointers
      DO 50 i = 0, subpbs
         iwork( iprmpt+i ) = 1
         iwork( igivpt+i ) = 1
   50 CONTINUE
      iwork( iqptr ) = 1
*
*     Solve each submatrix eigenproblem at the bottom of the divide and
*     conquer tree.
*
      curr = 0
      DO 70 i = 0, spm1
         IF( i.EQ.0 ) THEN
            submat = 1
            matsiz = iwork( 1 )
         ELSE
            submat = iwork( i ) + 1
            matsiz = iwork( i+1 ) - iwork( i )
         END IF
         ll = iq - 1 + iwork( iqptr+curr )
         CALL ssteqr( 'I', matsiz, d( submat ), e( submat ),
     $                rwork( ll ), matsiz, rwork, info )
         CALL clacrm( qsiz, matsiz, q( 1, submat ), ldq, rwork( ll ),
     $                matsiz, qstore( 1, submat ), ldqs,
     $                rwork( iwrem ) )
         iwork( iqptr+curr+1 ) = iwork( iqptr+curr ) + matsiz**2
         curr = curr + 1
         IF( info.GT.0 ) THEN
            info = submat*( n+1 ) + submat + matsiz - 1
            RETURN
         END IF
         k = 1
         DO 60 j = submat, iwork( i+1 )
            iwork( indxq+j ) = k
            k = k + 1
   60    CONTINUE
   70 CONTINUE
*
*     Successively merge eigensystems of adjacent submatrices
*     into eigensystem for the corresponding larger matrix.
*
*     while ( SUBPBS > 1 )
*
      curlvl = 1
   80 CONTINUE
      IF( subpbs.GT.1 ) THEN
         spm2 = subpbs - 2
         DO 90 i = 0, spm2, 2
            IF( i.EQ.0 ) THEN
               submat = 1
               matsiz = iwork( 2 )
               msd2 = iwork( 1 )
               curprb = 0
            ELSE
               submat = iwork( i ) + 1
               matsiz = iwork( i+2 ) - iwork( i )
               msd2 = matsiz / 2
               curprb = curprb + 1
            END IF
*
*     Merge lower order eigensystems (of size MSD2 and MATSIZ - MSD2)
*     into an eigensystem of size MATSIZ.  CLAED7 handles the case
*     when the eigenvectors of a full or band Hermitian matrix (which
*     was reduced to tridiagonal form) are desired.
*
*     I am free to use Q as a valuable working space until Loop 150.
*
            CALL claed7( matsiz, msd2, qsiz, tlvls, curlvl, curprb,
     $                   d( submat ), qstore( 1, submat ), ldqs,
     $                   e( submat+msd2-1 ), iwork( indxq+submat ),
     $                   rwork( iq ), iwork( iqptr ), iwork( iprmpt ),
     $                   iwork( iperm ), iwork( igivpt ),
     $                   iwork( igivcl ), rwork( igivnm ),
     $                   q( 1, submat ), rwork( iwrem ),
     $                   iwork( subpbs+1 ), info )
            IF( info.GT.0 ) THEN
               info = submat*( n+1 ) + submat + matsiz - 1
               RETURN
            END IF
            iwork( i / 2+1 ) = iwork( i+2 )
   90    CONTINUE
         subpbs = subpbs / 2
         curlvl = curlvl + 1
         GO TO 80
      END IF
*
*     end while
*
*     Re-merge the eigenvalues/vectors which were deflated at the final
*     merge step.
*
      DO 100 i = 1, n
         j = iwork( indxq+i )
         rwork( i ) = d( j )
         CALL ccopy( qsiz, qstore( 1, j ), 1, q( 1, i ), 1 )
  100 CONTINUE
      CALL scopy( n, rwork, 1, d, 1 )
*
      RETURN
*
*     End of CLAED0
*
      END