LAPACK: SRC/ssterf.f Source File

Go to the documentation of this file.
00001       SUBROUTINE SSTERF( N, D, E, INFO )
00002 *
00003 *  -- LAPACK routine (version 3.2) --
00004 *  -- LAPACK is a software package provided by Univ. of Tennessee,    --
00005 *  -- Univ. of California Berkeley, Univ. of Colorado Denver and NAG Ltd..--
00006 *     November 2006
00007 *
00008 *     .. Scalar Arguments ..
00009       INTEGER            INFO, N
00010 *     ..
00011 *     .. Array Arguments ..
00012       REAL               D( * ), E( * )
00013 *     ..
00014 *
00015 *  Purpose
00016 *  =======
00017 *
00018 *  SSTERF computes all eigenvalues of a symmetric tridiagonal matrix
00019 *  using the Pal-Walker-Kahan variant of the QL or QR algorithm.
00020 *
00021 *  Arguments
00022 *  =========
00023 *
00024 *  N       (input) INTEGER
00025 *          The order of the matrix.  N >= 0.
00026 *
00027 *  D       (input/output) REAL array, dimension (N)
00028 *          On entry, the n diagonal elements of the tridiagonal matrix.
00029 *          On exit, if INFO = 0, the eigenvalues in ascending order.
00030 *
00031 *  E       (input/output) REAL array, dimension (N-1)
00032 *          On entry, the (n-1) subdiagonal elements of the tridiagonal
00033 *          matrix.
00034 *          On exit, E has been destroyed.
00035 *
00036 *  INFO    (output) INTEGER
00037 *          = 0:  successful exit
00038 *          < 0:  if INFO = -i, the i-th argument had an illegal value
00039 *          > 0:  the algorithm failed to find all of the eigenvalues in
00040 *                a total of 30*N iterations; if INFO = i, then i
00041 *                elements of E have not converged to zero.
00042 *
00043 *  =====================================================================
00044 *
00045 *     .. Parameters ..
00046       REAL               ZERO, ONE, TWO, THREE
00047       PARAMETER          ( ZERO = 0.0E0, ONE = 1.0E0, TWO = 2.0E0,
00048      $                   THREE = 3.0E0 )
00049       INTEGER            MAXIT
00050       PARAMETER          ( MAXIT = 30 )
00051 *     ..
00052 *     .. Local Scalars ..
00053       INTEGER            I, ISCALE, JTOT, L, L1, LEND, LENDSV, LSV, M,
00054      $                   NMAXIT
00055       REAL               ALPHA, ANORM, BB, C, EPS, EPS2, GAMMA, OLDC,
00056      $                   OLDGAM, P, R, RT1, RT2, RTE, S, SAFMAX, SAFMIN,
00057      $                   SIGMA, SSFMAX, SSFMIN
00058 *     ..
00059 *     .. External Functions ..
00060       REAL               SLAMCH, SLANST, SLAPY2
00061       EXTERNAL           SLAMCH, SLANST, SLAPY2
00062 *     ..
00063 *     .. External Subroutines ..
00064       EXTERNAL           SLAE2, SLASCL, SLASRT, XERBLA
00065 *     ..
00066 *     .. Intrinsic Functions ..
00067       INTRINSIC          ABS, SIGN, SQRT
00068 *     ..
00069 *     .. Executable Statements ..
00070 *
00071 *     Test the input parameters.
00072 *
00073       INFO = 0
00074 *
00075 *     Quick return if possible
00076 *
00077       IF( N.LT.0 ) THEN
00078          INFO = -1
00079          CALL XERBLA( 'SSTERF', -INFO )
00080          RETURN
00081       END IF
00082       IF( N.LE.1 )
00083      $   RETURN
00084 *
00085 *     Determine the unit roundoff for this environment.
00086 *
00087       EPS = SLAMCH( 'E' )
00088       EPS2 = EPS**2
00089       SAFMIN = SLAMCH( 'S' )
00090       SAFMAX = ONE / SAFMIN
00091       SSFMAX = SQRT( SAFMAX ) / THREE
00092       SSFMIN = SQRT( SAFMIN ) / EPS2
00093 *
00094 *     Compute the eigenvalues of the tridiagonal matrix.
00095 *
00096       NMAXIT = N*MAXIT
00097       SIGMA = ZERO
00098       JTOT = 0
00099 *
00100 *     Determine where the matrix splits and choose QL or QR iteration
00101 *     for each block, according to whether top or bottom diagonal
00102 *     element is smaller.
00103 *
00104       L1 = 1
00105 *
00106    10 CONTINUE
00107       IF( L1.GT.N )
00108      $   GO TO 170
00109       IF( L1.GT.1 )
00110      $   E( L1-1 ) = ZERO
00111       DO 20 M = L1, N - 1
00112          IF( ABS( E( M ) ).LE.( SQRT( ABS( D( M ) ) )*
00113      $       SQRT( ABS( D( M+1 ) ) ) )*EPS ) THEN
00114             E( M ) = ZERO
00115             GO TO 30
00116          END IF
00117    20 CONTINUE
00118       M = N
00119 *
00120    30 CONTINUE
00121       L = L1
00122       LSV = L
00123       LEND = M
00124       LENDSV = LEND
00125       L1 = M + 1
00126       IF( LEND.EQ.L )
00127      $   GO TO 10
00128 *
00129 *     Scale submatrix in rows and columns L to LEND
00130 *
00131       ANORM = SLANST( 'I', LEND-L+1, D( L ), E( L ) )
00132       ISCALE = 0
00133       IF( ANORM.GT.SSFMAX ) THEN
00134          ISCALE = 1
00135          CALL SLASCL( 'G', 0, 0, ANORM, SSFMAX, LEND-L+1, 1, D( L ), N,
00136      $                INFO )
00137          CALL SLASCL( 'G', 0, 0, ANORM, SSFMAX, LEND-L, 1, E( L ), N,
00138      $                INFO )
00139       ELSE IF( ANORM.LT.SSFMIN ) THEN
00140          ISCALE = 2
00141          CALL SLASCL( 'G', 0, 0, ANORM, SSFMIN, LEND-L+1, 1, D( L ), N,
00142      $                INFO )
00143          CALL SLASCL( 'G', 0, 0, ANORM, SSFMIN, LEND-L, 1, E( L ), N,
00144      $                INFO )
00145       END IF
00146 *
00147       DO 40 I = L, LEND - 1
00148          E( I ) = E( I )**2
00149    40 CONTINUE
00150 *
00151 *     Choose between QL and QR iteration
00152 *
00153       IF( ABS( D( LEND ) ).LT.ABS( D( L ) ) ) THEN
00154          LEND = LSV
00155          L = LENDSV
00156       END IF
00157 *
00158       IF( LEND.GE.L ) THEN
00159 *
00160 *        QL Iteration
00161 *
00162 *        Look for small subdiagonal element.
00163 *
00164    50    CONTINUE
00165          IF( L.NE.LEND ) THEN
00166             DO 60 M = L, LEND - 1
00167                IF( ABS( E( M ) ).LE.EPS2*ABS( D( M )*D( M+1 ) ) )
00168      $            GO TO 70
00169    60       CONTINUE
00170          END IF
00171          M = LEND
00172 *
00173    70    CONTINUE
00174          IF( M.LT.LEND )
00175      $      E( M ) = ZERO
00176          P = D( L )
00177          IF( M.EQ.L )
00178      $      GO TO 90
00179 *
00180 *        If remaining matrix is 2 by 2, use SLAE2 to compute its
00181 *        eigenvalues.
00182 *
00183          IF( M.EQ.L+1 ) THEN
00184             RTE = SQRT( E( L ) )
00185             CALL SLAE2( D( L ), RTE, D( L+1 ), RT1, RT2 )
00186             D( L ) = RT1
00187             D( L+1 ) = RT2
00188             E( L ) = ZERO
00189             L = L + 2
00190             IF( L.LE.LEND )
00191      $         GO TO 50
00192             GO TO 150
00193          END IF
00194 *
00195          IF( JTOT.EQ.NMAXIT )
00196      $      GO TO 150
00197          JTOT = JTOT + 1
00198 *
00199 *        Form shift.
00200 *
00201          RTE = SQRT( E( L ) )
00202          SIGMA = ( D( L+1 )-P ) / ( TWO*RTE )
00203          R = SLAPY2( SIGMA, ONE )
00204          SIGMA = P - ( RTE / ( SIGMA+SIGN( R, SIGMA ) ) )
00205 *
00206          C = ONE
00207          S = ZERO
00208          GAMMA = D( M ) - SIGMA
00209          P = GAMMA*GAMMA
00210 *
00211 *        Inner loop
00212 *
00213          DO 80 I = M - 1, L, -1
00214             BB = E( I )
00215             R = P + BB
00216             IF( I.NE.M-1 )
00217      $         E( I+1 ) = S*R
00218             OLDC = C
00219             C = P / R
00220             S = BB / R
00221             OLDGAM = GAMMA
00222             ALPHA = D( I )
00223             GAMMA = C*( ALPHA-SIGMA ) - S*OLDGAM
00224             D( I+1 ) = OLDGAM + ( ALPHA-GAMMA )
00225             IF( C.NE.ZERO ) THEN
00226                P = ( GAMMA*GAMMA ) / C
00227             ELSE
00228                P = OLDC*BB
00229             END IF
00230    80    CONTINUE
00231 *
00232          E( L ) = S*P
00233          D( L ) = SIGMA + GAMMA
00234          GO TO 50
00235 *
00236 *        Eigenvalue found.
00237 *
00238    90    CONTINUE
00239          D( L ) = P
00240 *
00241          L = L + 1
00242          IF( L.LE.LEND )
00243      $      GO TO 50
00244          GO TO 150
00245 *
00246       ELSE
00247 *
00248 *        QR Iteration
00249 *
00250 *        Look for small superdiagonal element.
00251 *
00252   100    CONTINUE
00253          DO 110 M = L, LEND + 1, -1
00254             IF( ABS( E( M-1 ) ).LE.EPS2*ABS( D( M )*D( M-1 ) ) )
00255      $         GO TO 120
00256   110    CONTINUE
00257          M = LEND
00258 *
00259   120    CONTINUE
00260          IF( M.GT.LEND )
00261      $      E( M-1 ) = ZERO
00262          P = D( L )
00263          IF( M.EQ.L )
00264      $      GO TO 140
00265 *
00266 *        If remaining matrix is 2 by 2, use SLAE2 to compute its
00267 *        eigenvalues.
00268 *
00269          IF( M.EQ.L-1 ) THEN
00270             RTE = SQRT( E( L-1 ) )
00271             CALL SLAE2( D( L ), RTE, D( L-1 ), RT1, RT2 )
00272             D( L ) = RT1
00273             D( L-1 ) = RT2
00274             E( L-1 ) = ZERO
00275             L = L - 2
00276             IF( L.GE.LEND )
00277      $         GO TO 100
00278             GO TO 150
00279          END IF
00280 *
00281          IF( JTOT.EQ.NMAXIT )
00282      $      GO TO 150
00283          JTOT = JTOT + 1
00284 *
00285 *        Form shift.
00286 *
00287          RTE = SQRT( E( L-1 ) )
00288          SIGMA = ( D( L-1 )-P ) / ( TWO*RTE )
00289          R = SLAPY2( SIGMA, ONE )
00290          SIGMA = P - ( RTE / ( SIGMA+SIGN( R, SIGMA ) ) )
00291 *
00292          C = ONE
00293          S = ZERO
00294          GAMMA = D( M ) - SIGMA
00295          P = GAMMA*GAMMA
00296 *
00297 *        Inner loop
00298 *
00299          DO 130 I = M, L - 1
00300             BB = E( I )
00301             R = P + BB
00302             IF( I.NE.M )
00303      $         E( I-1 ) = S*R
00304             OLDC = C
00305             C = P / R
00306             S = BB / R
00307             OLDGAM = GAMMA
00308             ALPHA = D( I+1 )
00309             GAMMA = C*( ALPHA-SIGMA ) - S*OLDGAM
00310             D( I ) = OLDGAM + ( ALPHA-GAMMA )
00311             IF( C.NE.ZERO ) THEN
00312                P = ( GAMMA*GAMMA ) / C
00313             ELSE
00314                P = OLDC*BB
00315             END IF
00316   130    CONTINUE
00317 *
00318          E( L-1 ) = S*P
00319          D( L ) = SIGMA + GAMMA
00320          GO TO 100
00321 *
00322 *        Eigenvalue found.
00323 *
00324   140    CONTINUE
00325          D( L ) = P
00326 *
00327          L = L - 1
00328          IF( L.GE.LEND )
00329      $      GO TO 100
00330          GO TO 150
00331 *
00332       END IF
00333 *
00334 *     Undo scaling if necessary
00335 *
00336   150 CONTINUE
00337       IF( ISCALE.EQ.1 )
00338      $   CALL SLASCL( 'G', 0, 0, SSFMAX, ANORM, LENDSV-LSV+1, 1,
00339      $                D( LSV ), N, INFO )
00340       IF( ISCALE.EQ.2 )
00341      $   CALL SLASCL( 'G', 0, 0, SSFMIN, ANORM, LENDSV-LSV+1, 1,
00342      $                D( LSV ), N, INFO )
00343 *
00344 *     Check for no convergence to an eigenvalue after a total
00345 *     of N*MAXIT iterations.
00346 *
00347       IF( JTOT.LT.NMAXIT )
00348      $   GO TO 10
00349       DO 160 I = 1, N - 1
00350          IF( E( I ).NE.ZERO )
00351      $      INFO = INFO + 1
00352   160 CONTINUE
00353       GO TO 180
00354 *
00355 *     Sort eigenvalues in increasing order.
00356 *
00357   170 CONTINUE
00358       CALL SLASRT( 'I', N, D, INFO )
00359 *
00360   180 CONTINUE
00361       RETURN
00362 *
00363 *     End of SSTERF
00364 *
00365       END