Annotation of rpl/lapack/lapack/dstedc.f, revision 1.8

1.8     ! bertrand    1: *> \brief \b DSTEBZ
        !             2: *
        !             3: *  =========== DOCUMENTATION ===========
        !             4: *
        !             5: * Online html documentation available at 
        !             6: *            http://www.netlib.org/lapack/explore-html/ 
        !             7: *
        !             8: *> \htmlonly
        !             9: *> Download DSTEDC + dependencies 
        !            10: *> <a href="http://www.netlib.org/cgi-bin/netlibfiles.tgz?format=tgz&filename=/lapack/lapack_routine/dstedc.f"> 
        !            11: *> [TGZ]</a> 
        !            12: *> <a href="http://www.netlib.org/cgi-bin/netlibfiles.zip?format=zip&filename=/lapack/lapack_routine/dstedc.f"> 
        !            13: *> [ZIP]</a> 
        !            14: *> <a href="http://www.netlib.org/cgi-bin/netlibfiles.txt?format=txt&filename=/lapack/lapack_routine/dstedc.f"> 
        !            15: *> [TXT]</a>
        !            16: *> \endhtmlonly 
        !            17: *
        !            18: *  Definition:
        !            19: *  ===========
        !            20: *
        !            21: *       SUBROUTINE DSTEDC( COMPZ, N, D, E, Z, LDZ, WORK, LWORK, IWORK,
        !            22: *                          LIWORK, INFO )
        !            23: * 
        !            24: *       .. Scalar Arguments ..
        !            25: *       CHARACTER          COMPZ
        !            26: *       INTEGER            INFO, LDZ, LIWORK, LWORK, N
        !            27: *       ..
        !            28: *       .. Array Arguments ..
        !            29: *       INTEGER            IWORK( * )
        !            30: *       DOUBLE PRECISION   D( * ), E( * ), WORK( * ), Z( LDZ, * )
        !            31: *       ..
        !            32: *  
        !            33: *
        !            34: *> \par Purpose:
        !            35: *  =============
        !            36: *>
        !            37: *> \verbatim
        !            38: *>
        !            39: *> DSTEDC computes all eigenvalues and, optionally, eigenvectors of a
        !            40: *> symmetric tridiagonal matrix using the divide and conquer method.
        !            41: *> The eigenvectors of a full or band real symmetric matrix can also be
        !            42: *> found if DSYTRD or DSPTRD or DSBTRD has been used to reduce this
        !            43: *> matrix to tridiagonal form.
        !            44: *>
        !            45: *> This code makes very mild assumptions about floating point
        !            46: *> arithmetic. It will work on machines with a guard digit in
        !            47: *> add/subtract, or on those binary machines without guard digits
        !            48: *> which subtract like the Cray X-MP, Cray Y-MP, Cray C-90, or Cray-2.
        !            49: *> It could conceivably fail on hexadecimal or decimal machines
        !            50: *> without guard digits, but we know of none.  See DLAED3 for details.
        !            51: *> \endverbatim
        !            52: *
        !            53: *  Arguments:
        !            54: *  ==========
        !            55: *
        !            56: *> \param[in] COMPZ
        !            57: *> \verbatim
        !            58: *>          COMPZ is CHARACTER*1
        !            59: *>          = 'N':  Compute eigenvalues only.
        !            60: *>          = 'I':  Compute eigenvectors of tridiagonal matrix also.
        !            61: *>          = 'V':  Compute eigenvectors of original dense symmetric
        !            62: *>                  matrix also.  On entry, Z contains the orthogonal
        !            63: *>                  matrix used to reduce the original matrix to
        !            64: *>                  tridiagonal form.
        !            65: *> \endverbatim
        !            66: *>
        !            67: *> \param[in] N
        !            68: *> \verbatim
        !            69: *>          N is INTEGER
        !            70: *>          The dimension of the symmetric tridiagonal matrix.  N >= 0.
        !            71: *> \endverbatim
        !            72: *>
        !            73: *> \param[in,out] D
        !            74: *> \verbatim
        !            75: *>          D is DOUBLE PRECISION array, dimension (N)
        !            76: *>          On entry, the diagonal elements of the tridiagonal matrix.
        !            77: *>          On exit, if INFO = 0, the eigenvalues in ascending order.
        !            78: *> \endverbatim
        !            79: *>
        !            80: *> \param[in,out] E
        !            81: *> \verbatim
        !            82: *>          E is DOUBLE PRECISION array, dimension (N-1)
        !            83: *>          On entry, the subdiagonal elements of the tridiagonal matrix.
        !            84: *>          On exit, E has been destroyed.
        !            85: *> \endverbatim
        !            86: *>
        !            87: *> \param[in,out] Z
        !            88: *> \verbatim
        !            89: *>          Z is DOUBLE PRECISION array, dimension (LDZ,N)
        !            90: *>          On entry, if COMPZ = 'V', then Z contains the orthogonal
        !            91: *>          matrix used in the reduction to tridiagonal form.
        !            92: *>          On exit, if INFO = 0, then if COMPZ = 'V', Z contains the
        !            93: *>          orthonormal eigenvectors of the original symmetric matrix,
        !            94: *>          and if COMPZ = 'I', Z contains the orthonormal eigenvectors
        !            95: *>          of the symmetric tridiagonal matrix.
        !            96: *>          If  COMPZ = 'N', then Z is not referenced.
        !            97: *> \endverbatim
        !            98: *>
        !            99: *> \param[in] LDZ
        !           100: *> \verbatim
        !           101: *>          LDZ is INTEGER
        !           102: *>          The leading dimension of the array Z.  LDZ >= 1.
        !           103: *>          If eigenvectors are desired, then LDZ >= max(1,N).
        !           104: *> \endverbatim
        !           105: *>
        !           106: *> \param[out] WORK
        !           107: *> \verbatim
        !           108: *>          WORK is DOUBLE PRECISION array,
        !           109: *>                                         dimension (LWORK)
        !           110: *>          On exit, if INFO = 0, WORK(1) returns the optimal LWORK.
        !           111: *> \endverbatim
        !           112: *>
        !           113: *> \param[in] LWORK
        !           114: *> \verbatim
        !           115: *>          LWORK is INTEGER
        !           116: *>          The dimension of the array WORK.
        !           117: *>          If COMPZ = 'N' or N <= 1 then LWORK must be at least 1.
        !           118: *>          If COMPZ = 'V' and N > 1 then LWORK must be at least
        !           119: *>                         ( 1 + 3*N + 2*N*lg N + 4*N**2 ),
        !           120: *>                         where lg( N ) = smallest integer k such
        !           121: *>                         that 2**k >= N.
        !           122: *>          If COMPZ = 'I' and N > 1 then LWORK must be at least
        !           123: *>                         ( 1 + 4*N + N**2 ).
        !           124: *>          Note that for COMPZ = 'I' or 'V', then if N is less than or
        !           125: *>          equal to the minimum divide size, usually 25, then LWORK need
        !           126: *>          only be max(1,2*(N-1)).
        !           127: *>
        !           128: *>          If LWORK = -1, then a workspace query is assumed; the routine
        !           129: *>          only calculates the optimal size of the WORK array, returns
        !           130: *>          this value as the first entry of the WORK array, and no error
        !           131: *>          message related to LWORK is issued by XERBLA.
        !           132: *> \endverbatim
        !           133: *>
        !           134: *> \param[out] IWORK
        !           135: *> \verbatim
        !           136: *>          IWORK is INTEGER array, dimension (MAX(1,LIWORK))
        !           137: *>          On exit, if INFO = 0, IWORK(1) returns the optimal LIWORK.
        !           138: *> \endverbatim
        !           139: *>
        !           140: *> \param[in] LIWORK
        !           141: *> \verbatim
        !           142: *>          LIWORK is INTEGER
        !           143: *>          The dimension of the array IWORK.
        !           144: *>          If COMPZ = 'N' or N <= 1 then LIWORK must be at least 1.
        !           145: *>          If COMPZ = 'V' and N > 1 then LIWORK must be at least
        !           146: *>                         ( 6 + 6*N + 5*N*lg N ).
        !           147: *>          If COMPZ = 'I' and N > 1 then LIWORK must be at least
        !           148: *>                         ( 3 + 5*N ).
        !           149: *>          Note that for COMPZ = 'I' or 'V', then if N is less than or
        !           150: *>          equal to the minimum divide size, usually 25, then LIWORK
        !           151: *>          need only be 1.
        !           152: *>
        !           153: *>          If LIWORK = -1, then a workspace query is assumed; the
        !           154: *>          routine only calculates the optimal size of the IWORK array,
        !           155: *>          returns this value as the first entry of the IWORK array, and
        !           156: *>          no error message related to LIWORK is issued by XERBLA.
        !           157: *> \endverbatim
        !           158: *>
        !           159: *> \param[out] INFO
        !           160: *> \verbatim
        !           161: *>          INFO is INTEGER
        !           162: *>          = 0:  successful exit.
        !           163: *>          < 0:  if INFO = -i, the i-th argument had an illegal value.
        !           164: *>          > 0:  The algorithm failed to compute an eigenvalue while
        !           165: *>                working on the submatrix lying in rows and columns
        !           166: *>                INFO/(N+1) through mod(INFO,N+1).
        !           167: *> \endverbatim
        !           168: *
        !           169: *  Authors:
        !           170: *  ========
        !           171: *
        !           172: *> \author Univ. of Tennessee 
        !           173: *> \author Univ. of California Berkeley 
        !           174: *> \author Univ. of Colorado Denver 
        !           175: *> \author NAG Ltd. 
        !           176: *
        !           177: *> \date November 2011
        !           178: *
        !           179: *> \ingroup auxOTHERcomputational
        !           180: *
        !           181: *> \par Contributors:
        !           182: *  ==================
        !           183: *>
        !           184: *> Jeff Rutter, Computer Science Division, University of California
        !           185: *> at Berkeley, USA \n
        !           186: *>  Modified by Francoise Tisseur, University of Tennessee
        !           187: *>
        !           188: *  =====================================================================
1.1       bertrand  189:       SUBROUTINE DSTEDC( COMPZ, N, D, E, Z, LDZ, WORK, LWORK, IWORK,
                    190:      $                   LIWORK, INFO )
                    191: *
1.8     ! bertrand  192: *  -- LAPACK computational routine (version 3.4.0) --
1.1       bertrand  193: *  -- LAPACK is a software package provided by Univ. of Tennessee,    --
                    194: *  -- Univ. of California Berkeley, Univ. of Colorado Denver and NAG Ltd..--
1.8     ! bertrand  195: *     November 2011
1.1       bertrand  196: *
                    197: *     .. Scalar Arguments ..
                    198:       CHARACTER          COMPZ
                    199:       INTEGER            INFO, LDZ, LIWORK, LWORK, N
                    200: *     ..
                    201: *     .. Array Arguments ..
                    202:       INTEGER            IWORK( * )
                    203:       DOUBLE PRECISION   D( * ), E( * ), WORK( * ), Z( LDZ, * )
                    204: *     ..
                    205: *
                    206: *  =====================================================================
                    207: *
                    208: *     .. Parameters ..
                    209:       DOUBLE PRECISION   ZERO, ONE, TWO
                    210:       PARAMETER          ( ZERO = 0.0D0, ONE = 1.0D0, TWO = 2.0D0 )
                    211: *     ..
                    212: *     .. Local Scalars ..
                    213:       LOGICAL            LQUERY
                    214:       INTEGER            FINISH, I, ICOMPZ, II, J, K, LGN, LIWMIN,
                    215:      $                   LWMIN, M, SMLSIZ, START, STOREZ, STRTRW
                    216:       DOUBLE PRECISION   EPS, ORGNRM, P, TINY
                    217: *     ..
                    218: *     .. External Functions ..
                    219:       LOGICAL            LSAME
                    220:       INTEGER            ILAENV
                    221:       DOUBLE PRECISION   DLAMCH, DLANST
                    222:       EXTERNAL           LSAME, ILAENV, DLAMCH, DLANST
                    223: *     ..
                    224: *     .. External Subroutines ..
                    225:       EXTERNAL           DGEMM, DLACPY, DLAED0, DLASCL, DLASET, DLASRT,
                    226:      $                   DSTEQR, DSTERF, DSWAP, XERBLA
                    227: *     ..
                    228: *     .. Intrinsic Functions ..
                    229:       INTRINSIC          ABS, DBLE, INT, LOG, MAX, MOD, SQRT
                    230: *     ..
                    231: *     .. Executable Statements ..
                    232: *
                    233: *     Test the input parameters.
                    234: *
                    235:       INFO = 0
                    236:       LQUERY = ( LWORK.EQ.-1 .OR. LIWORK.EQ.-1 )
                    237: *
                    238:       IF( LSAME( COMPZ, 'N' ) ) THEN
                    239:          ICOMPZ = 0
                    240:       ELSE IF( LSAME( COMPZ, 'V' ) ) THEN
                    241:          ICOMPZ = 1
                    242:       ELSE IF( LSAME( COMPZ, 'I' ) ) THEN
                    243:          ICOMPZ = 2
                    244:       ELSE
                    245:          ICOMPZ = -1
                    246:       END IF
                    247:       IF( ICOMPZ.LT.0 ) THEN
                    248:          INFO = -1
                    249:       ELSE IF( N.LT.0 ) THEN
                    250:          INFO = -2
                    251:       ELSE IF( ( LDZ.LT.1 ) .OR.
                    252:      $         ( ICOMPZ.GT.0 .AND. LDZ.LT.MAX( 1, N ) ) ) THEN
                    253:          INFO = -6
                    254:       END IF
                    255: *
                    256:       IF( INFO.EQ.0 ) THEN
                    257: *
                    258: *        Compute the workspace requirements
                    259: *
                    260:          SMLSIZ = ILAENV( 9, 'DSTEDC', ' ', 0, 0, 0, 0 )
                    261:          IF( N.LE.1 .OR. ICOMPZ.EQ.0 ) THEN
                    262:             LIWMIN = 1
                    263:             LWMIN = 1
                    264:          ELSE IF( N.LE.SMLSIZ ) THEN
                    265:             LIWMIN = 1
                    266:             LWMIN = 2*( N - 1 )
                    267:          ELSE
                    268:             LGN = INT( LOG( DBLE( N ) )/LOG( TWO ) )
                    269:             IF( 2**LGN.LT.N )
                    270:      $         LGN = LGN + 1
                    271:             IF( 2**LGN.LT.N )
                    272:      $         LGN = LGN + 1
                    273:             IF( ICOMPZ.EQ.1 ) THEN
1.8     ! bertrand  274:                LWMIN = 1 + 3*N + 2*N*LGN + 4*N**2
1.1       bertrand  275:                LIWMIN = 6 + 6*N + 5*N*LGN
                    276:             ELSE IF( ICOMPZ.EQ.2 ) THEN
                    277:                LWMIN = 1 + 4*N + N**2
                    278:                LIWMIN = 3 + 5*N
                    279:             END IF
                    280:          END IF
                    281:          WORK( 1 ) = LWMIN
                    282:          IWORK( 1 ) = LIWMIN
                    283: *
                    284:          IF( LWORK.LT.LWMIN .AND. .NOT. LQUERY ) THEN
                    285:             INFO = -8
                    286:          ELSE IF( LIWORK.LT.LIWMIN .AND. .NOT. LQUERY ) THEN
                    287:             INFO = -10
                    288:          END IF
                    289:       END IF
                    290: *
                    291:       IF( INFO.NE.0 ) THEN
                    292:          CALL XERBLA( 'DSTEDC', -INFO )
                    293:          RETURN
                    294:       ELSE IF (LQUERY) THEN
                    295:          RETURN
                    296:       END IF
                    297: *
                    298: *     Quick return if possible
                    299: *
                    300:       IF( N.EQ.0 )
                    301:      $   RETURN
                    302:       IF( N.EQ.1 ) THEN
                    303:          IF( ICOMPZ.NE.0 )
                    304:      $      Z( 1, 1 ) = ONE
                    305:          RETURN
                    306:       END IF
                    307: *
                    308: *     If the following conditional clause is removed, then the routine
                    309: *     will use the Divide and Conquer routine to compute only the
                    310: *     eigenvalues, which requires (3N + 3N**2) real workspace and
                    311: *     (2 + 5N + 2N lg(N)) integer workspace.
                    312: *     Since on many architectures DSTERF is much faster than any other
                    313: *     algorithm for finding eigenvalues only, it is used here
                    314: *     as the default. If the conditional clause is removed, then
                    315: *     information on the size of workspace needs to be changed.
                    316: *
                    317: *     If COMPZ = 'N', use DSTERF to compute the eigenvalues.
                    318: *
                    319:       IF( ICOMPZ.EQ.0 ) THEN
                    320:          CALL DSTERF( N, D, E, INFO )
                    321:          GO TO 50
                    322:       END IF
                    323: *
                    324: *     If N is smaller than the minimum divide size (SMLSIZ+1), then
                    325: *     solve the problem with another solver.
                    326: *
                    327:       IF( N.LE.SMLSIZ ) THEN
                    328: *
                    329:          CALL DSTEQR( COMPZ, N, D, E, Z, LDZ, WORK, INFO )
                    330: *
                    331:       ELSE
                    332: *
                    333: *        If COMPZ = 'V', the Z matrix must be stored elsewhere for later
                    334: *        use.
                    335: *
                    336:          IF( ICOMPZ.EQ.1 ) THEN
                    337:             STOREZ = 1 + N*N
                    338:          ELSE
                    339:             STOREZ = 1
                    340:          END IF
                    341: *
                    342:          IF( ICOMPZ.EQ.2 ) THEN
                    343:             CALL DLASET( 'Full', N, N, ZERO, ONE, Z, LDZ )
                    344:          END IF
                    345: *
                    346: *        Scale.
                    347: *
                    348:          ORGNRM = DLANST( 'M', N, D, E )
                    349:          IF( ORGNRM.EQ.ZERO )
                    350:      $      GO TO 50
                    351: *
                    352:          EPS = DLAMCH( 'Epsilon' )
                    353: *
                    354:          START = 1
                    355: *
                    356: *        while ( START <= N )
                    357: *
                    358:    10    CONTINUE
                    359:          IF( START.LE.N ) THEN
                    360: *
                    361: *           Let FINISH be the position of the next subdiagonal entry
                    362: *           such that E( FINISH ) <= TINY or FINISH = N if no such
                    363: *           subdiagonal exists.  The matrix identified by the elements
                    364: *           between START and FINISH constitutes an independent
                    365: *           sub-problem.
                    366: *
                    367:             FINISH = START
                    368:    20       CONTINUE
                    369:             IF( FINISH.LT.N ) THEN
                    370:                TINY = EPS*SQRT( ABS( D( FINISH ) ) )*
                    371:      $                    SQRT( ABS( D( FINISH+1 ) ) )
                    372:                IF( ABS( E( FINISH ) ).GT.TINY ) THEN
                    373:                   FINISH = FINISH + 1
                    374:                   GO TO 20
                    375:                END IF
                    376:             END IF
                    377: *
                    378: *           (Sub) Problem determined.  Compute its size and solve it.
                    379: *
                    380:             M = FINISH - START + 1
                    381:             IF( M.EQ.1 ) THEN
                    382:                START = FINISH + 1
                    383:                GO TO 10
                    384:             END IF
                    385:             IF( M.GT.SMLSIZ ) THEN
                    386: *
                    387: *              Scale.
                    388: *
                    389:                ORGNRM = DLANST( 'M', M, D( START ), E( START ) )
                    390:                CALL DLASCL( 'G', 0, 0, ORGNRM, ONE, M, 1, D( START ), M,
                    391:      $                      INFO )
                    392:                CALL DLASCL( 'G', 0, 0, ORGNRM, ONE, M-1, 1, E( START ),
                    393:      $                      M-1, INFO )
                    394: *
                    395:                IF( ICOMPZ.EQ.1 ) THEN
                    396:                   STRTRW = 1
                    397:                ELSE
                    398:                   STRTRW = START
                    399:                END IF
                    400:                CALL DLAED0( ICOMPZ, N, M, D( START ), E( START ),
                    401:      $                      Z( STRTRW, START ), LDZ, WORK( 1 ), N,
                    402:      $                      WORK( STOREZ ), IWORK, INFO )
                    403:                IF( INFO.NE.0 ) THEN
                    404:                   INFO = ( INFO / ( M+1 )+START-1 )*( N+1 ) +
                    405:      $                   MOD( INFO, ( M+1 ) ) + START - 1
                    406:                   GO TO 50
                    407:                END IF
                    408: *
                    409: *              Scale back.
                    410: *
                    411:                CALL DLASCL( 'G', 0, 0, ONE, ORGNRM, M, 1, D( START ), M,
                    412:      $                      INFO )
                    413: *
                    414:             ELSE
                    415:                IF( ICOMPZ.EQ.1 ) THEN
                    416: *
                    417: *                 Since QR won't update a Z matrix which is larger than
                    418: *                 the length of D, we must solve the sub-problem in a
                    419: *                 workspace and then multiply back into Z.
                    420: *
                    421:                   CALL DSTEQR( 'I', M, D( START ), E( START ), WORK, M,
                    422:      $                         WORK( M*M+1 ), INFO )
                    423:                   CALL DLACPY( 'A', N, M, Z( 1, START ), LDZ,
                    424:      $                         WORK( STOREZ ), N )
                    425:                   CALL DGEMM( 'N', 'N', N, M, M, ONE,
                    426:      $                        WORK( STOREZ ), N, WORK, M, ZERO,
                    427:      $                        Z( 1, START ), LDZ )
                    428:                ELSE IF( ICOMPZ.EQ.2 ) THEN
                    429:                   CALL DSTEQR( 'I', M, D( START ), E( START ),
                    430:      $                         Z( START, START ), LDZ, WORK, INFO )
                    431:                ELSE
                    432:                   CALL DSTERF( M, D( START ), E( START ), INFO )
                    433:                END IF
                    434:                IF( INFO.NE.0 ) THEN
                    435:                   INFO = START*( N+1 ) + FINISH
                    436:                   GO TO 50
                    437:                END IF
                    438:             END IF
                    439: *
                    440:             START = FINISH + 1
                    441:             GO TO 10
                    442:          END IF
                    443: *
                    444: *        endwhile
                    445: *
                    446: *        If the problem split any number of times, then the eigenvalues
                    447: *        will not be properly ordered.  Here we permute the eigenvalues
                    448: *        (and the associated eigenvectors) into ascending order.
                    449: *
                    450:          IF( M.NE.N ) THEN
                    451:             IF( ICOMPZ.EQ.0 ) THEN
                    452: *
                    453: *              Use Quick Sort
                    454: *
                    455:                CALL DLASRT( 'I', N, D, INFO )
                    456: *
                    457:             ELSE
                    458: *
                    459: *              Use Selection Sort to minimize swaps of eigenvectors
                    460: *
                    461:                DO 40 II = 2, N
                    462:                   I = II - 1
                    463:                   K = I
                    464:                   P = D( I )
                    465:                   DO 30 J = II, N
                    466:                      IF( D( J ).LT.P ) THEN
                    467:                         K = J
                    468:                         P = D( J )
                    469:                      END IF
                    470:    30             CONTINUE
                    471:                   IF( K.NE.I ) THEN
                    472:                      D( K ) = D( I )
                    473:                      D( I ) = P
                    474:                      CALL DSWAP( N, Z( 1, I ), 1, Z( 1, K ), 1 )
                    475:                   END IF
                    476:    40          CONTINUE
                    477:             END IF
                    478:          END IF
                    479:       END IF
                    480: *
                    481:    50 CONTINUE
                    482:       WORK( 1 ) = LWMIN
                    483:       IWORK( 1 ) = LIWMIN
                    484: *
                    485:       RETURN
                    486: *
                    487: *     End of DSTEDC
                    488: *
                    489:       END

CVSweb interface <joel.bertrand@systella.fr>