001:       SUBROUTINE SSTERF( N, D, E, INFO )
002: *
003: *  -- LAPACK routine (version 3.2) --
004: *  -- LAPACK is a software package provided by Univ. of Tennessee,    --
005: *  -- Univ. of California Berkeley, Univ. of Colorado Denver and NAG Ltd..--
006: *     November 2006
007: *
008: *     .. Scalar Arguments ..
009:       INTEGER            INFO, N
010: *     ..
011: *     .. Array Arguments ..
012:       REAL               D( * ), E( * )
013: *     ..
014: *
015: *  Purpose
016: *  =======
017: *
018: *  SSTERF computes all eigenvalues of a symmetric tridiagonal matrix
019: *  using the Pal-Walker-Kahan variant of the QL or QR algorithm.
020: *
021: *  Arguments
022: *  =========
023: *
024: *  N       (input) INTEGER
025: *          The order of the matrix.  N >= 0.
026: *
027: *  D       (input/output) REAL array, dimension (N)
028: *          On entry, the n diagonal elements of the tridiagonal matrix.
029: *          On exit, if INFO = 0, the eigenvalues in ascending order.
030: *
031: *  E       (input/output) REAL array, dimension (N-1)
032: *          On entry, the (n-1) subdiagonal elements of the tridiagonal
033: *          matrix.
034: *          On exit, E has been destroyed.
035: *
036: *  INFO    (output) INTEGER
037: *          = 0:  successful exit
038: *          < 0:  if INFO = -i, the i-th argument had an illegal value
039: *          > 0:  the algorithm failed to find all of the eigenvalues in
040: *                a total of 30*N iterations; if INFO = i, then i
041: *                elements of E have not converged to zero.
042: *
043: *  =====================================================================
044: *
045: *     .. Parameters ..
046:       REAL               ZERO, ONE, TWO, THREE
047:       PARAMETER          ( ZERO = 0.0E0, ONE = 1.0E0, TWO = 2.0E0,
048:      $                   THREE = 3.0E0 )
049:       INTEGER            MAXIT
050:       PARAMETER          ( MAXIT = 30 )
051: *     ..
052: *     .. Local Scalars ..
053:       INTEGER            I, ISCALE, JTOT, L, L1, LEND, LENDSV, LSV, M,
054:      $                   NMAXIT
055:       REAL               ALPHA, ANORM, BB, C, EPS, EPS2, GAMMA, OLDC,
056:      $                   OLDGAM, P, R, RT1, RT2, RTE, S, SAFMAX, SAFMIN,
057:      $                   SIGMA, SSFMAX, SSFMIN
058: *     ..
059: *     .. External Functions ..
060:       REAL               SLAMCH, SLANST, SLAPY2
061:       EXTERNAL           SLAMCH, SLANST, SLAPY2
062: *     ..
063: *     .. External Subroutines ..
064:       EXTERNAL           SLAE2, SLASCL, SLASRT, XERBLA
065: *     ..
066: *     .. Intrinsic Functions ..
067:       INTRINSIC          ABS, SIGN, SQRT
068: *     ..
069: *     .. Executable Statements ..
070: *
071: *     Test the input parameters.
072: *
073:       INFO = 0
074: *
075: *     Quick return if possible
076: *
077:       IF( N.LT.0 ) THEN
078:          INFO = -1
079:          CALL XERBLA( 'SSTERF', -INFO )
080:          RETURN
081:       END IF
082:       IF( N.LE.1 )
083:      $   RETURN
084: *
085: *     Determine the unit roundoff for this environment.
086: *
087:       EPS = SLAMCH( 'E' )
088:       EPS2 = EPS**2
089:       SAFMIN = SLAMCH( 'S' )
090:       SAFMAX = ONE / SAFMIN
091:       SSFMAX = SQRT( SAFMAX ) / THREE
092:       SSFMIN = SQRT( SAFMIN ) / EPS2
093: *
094: *     Compute the eigenvalues of the tridiagonal matrix.
095: *
096:       NMAXIT = N*MAXIT
097:       SIGMA = ZERO
098:       JTOT = 0
099: *
100: *     Determine where the matrix splits and choose QL or QR iteration
101: *     for each block, according to whether top or bottom diagonal
102: *     element is smaller.
103: *
104:       L1 = 1
105: *
106:    10 CONTINUE
107:       IF( L1.GT.N )
108:      $   GO TO 170
109:       IF( L1.GT.1 )
110:      $   E( L1-1 ) = ZERO
111:       DO 20 M = L1, N - 1
112:          IF( ABS( E( M ) ).LE.( SQRT( ABS( D( M ) ) )*
113:      $       SQRT( ABS( D( M+1 ) ) ) )*EPS ) THEN
114:             E( M ) = ZERO
115:             GO TO 30
116:          END IF
117:    20 CONTINUE
118:       M = N
119: *
120:    30 CONTINUE
121:       L = L1
122:       LSV = L
123:       LEND = M
124:       LENDSV = LEND
125:       L1 = M + 1
126:       IF( LEND.EQ.L )
127:      $   GO TO 10
128: *
129: *     Scale submatrix in rows and columns L to LEND
130: *
131:       ANORM = SLANST( 'I', LEND-L+1, D( L ), E( L ) )
132:       ISCALE = 0
133:       IF( ANORM.GT.SSFMAX ) THEN
134:          ISCALE = 1
135:          CALL SLASCL( 'G', 0, 0, ANORM, SSFMAX, LEND-L+1, 1, D( L ), N,
136:      $                INFO )
137:          CALL SLASCL( 'G', 0, 0, ANORM, SSFMAX, LEND-L, 1, E( L ), N,
138:      $                INFO )
139:       ELSE IF( ANORM.LT.SSFMIN ) THEN
140:          ISCALE = 2
141:          CALL SLASCL( 'G', 0, 0, ANORM, SSFMIN, LEND-L+1, 1, D( L ), N,
142:      $                INFO )
143:          CALL SLASCL( 'G', 0, 0, ANORM, SSFMIN, LEND-L, 1, E( L ), N,
144:      $                INFO )
145:       END IF
146: *
147:       DO 40 I = L, LEND - 1
148:          E( I ) = E( I )**2
149:    40 CONTINUE
150: *
151: *     Choose between QL and QR iteration
152: *
153:       IF( ABS( D( LEND ) ).LT.ABS( D( L ) ) ) THEN
154:          LEND = LSV
155:          L = LENDSV
156:       END IF
157: *
158:       IF( LEND.GE.L ) THEN
159: *
160: *        QL Iteration
161: *
162: *        Look for small subdiagonal element.
163: *
164:    50    CONTINUE
165:          IF( L.NE.LEND ) THEN
166:             DO 60 M = L, LEND - 1
167:                IF( ABS( E( M ) ).LE.EPS2*ABS( D( M )*D( M+1 ) ) )
168:      $            GO TO 70
169:    60       CONTINUE
170:          END IF
171:          M = LEND
172: *
173:    70    CONTINUE
174:          IF( M.LT.LEND )
175:      $      E( M ) = ZERO
176:          P = D( L )
177:          IF( M.EQ.L )
178:      $      GO TO 90
179: *
180: *        If remaining matrix is 2 by 2, use SLAE2 to compute its
181: *        eigenvalues.
182: *
183:          IF( M.EQ.L+1 ) THEN
184:             RTE = SQRT( E( L ) )
185:             CALL SLAE2( D( L ), RTE, D( L+1 ), RT1, RT2 )
186:             D( L ) = RT1
187:             D( L+1 ) = RT2
188:             E( L ) = ZERO
189:             L = L + 2
190:             IF( L.LE.LEND )
191:      $         GO TO 50
192:             GO TO 150
193:          END IF
194: *
195:          IF( JTOT.EQ.NMAXIT )
196:      $      GO TO 150
197:          JTOT = JTOT + 1
198: *
199: *        Form shift.
200: *
201:          RTE = SQRT( E( L ) )
202:          SIGMA = ( D( L+1 )-P ) / ( TWO*RTE )
203:          R = SLAPY2( SIGMA, ONE )
204:          SIGMA = P - ( RTE / ( SIGMA+SIGN( R, SIGMA ) ) )
205: *
206:          C = ONE
207:          S = ZERO
208:          GAMMA = D( M ) - SIGMA
209:          P = GAMMA*GAMMA
210: *
211: *        Inner loop
212: *
213:          DO 80 I = M - 1, L, -1
214:             BB = E( I )
215:             R = P + BB
216:             IF( I.NE.M-1 )
217:      $         E( I+1 ) = S*R
218:             OLDC = C
219:             C = P / R
220:             S = BB / R
221:             OLDGAM = GAMMA
222:             ALPHA = D( I )
223:             GAMMA = C*( ALPHA-SIGMA ) - S*OLDGAM
224:             D( I+1 ) = OLDGAM + ( ALPHA-GAMMA )
225:             IF( C.NE.ZERO ) THEN
226:                P = ( GAMMA*GAMMA ) / C
227:             ELSE
228:                P = OLDC*BB
229:             END IF
230:    80    CONTINUE
231: *
232:          E( L ) = S*P
233:          D( L ) = SIGMA + GAMMA
234:          GO TO 50
235: *
236: *        Eigenvalue found.
237: *
238:    90    CONTINUE
239:          D( L ) = P
240: *
241:          L = L + 1
242:          IF( L.LE.LEND )
243:      $      GO TO 50
244:          GO TO 150
245: *
246:       ELSE
247: *
248: *        QR Iteration
249: *
250: *        Look for small superdiagonal element.
251: *
252:   100    CONTINUE
253:          DO 110 M = L, LEND + 1, -1
254:             IF( ABS( E( M-1 ) ).LE.EPS2*ABS( D( M )*D( M-1 ) ) )
255:      $         GO TO 120
256:   110    CONTINUE
257:          M = LEND
258: *
259:   120    CONTINUE
260:          IF( M.GT.LEND )
261:      $      E( M-1 ) = ZERO
262:          P = D( L )
263:          IF( M.EQ.L )
264:      $      GO TO 140
265: *
266: *        If remaining matrix is 2 by 2, use SLAE2 to compute its
267: *        eigenvalues.
268: *
269:          IF( M.EQ.L-1 ) THEN
270:             RTE = SQRT( E( L-1 ) )
271:             CALL SLAE2( D( L ), RTE, D( L-1 ), RT1, RT2 )
272:             D( L ) = RT1
273:             D( L-1 ) = RT2
274:             E( L-1 ) = ZERO
275:             L = L - 2
276:             IF( L.GE.LEND )
277:      $         GO TO 100
278:             GO TO 150
279:          END IF
280: *
281:          IF( JTOT.EQ.NMAXIT )
282:      $      GO TO 150
283:          JTOT = JTOT + 1
284: *
285: *        Form shift.
286: *
287:          RTE = SQRT( E( L-1 ) )
288:          SIGMA = ( D( L-1 )-P ) / ( TWO*RTE )
289:          R = SLAPY2( SIGMA, ONE )
290:          SIGMA = P - ( RTE / ( SIGMA+SIGN( R, SIGMA ) ) )
291: *
292:          C = ONE
293:          S = ZERO
294:          GAMMA = D( M ) - SIGMA
295:          P = GAMMA*GAMMA
296: *
297: *        Inner loop
298: *
299:          DO 130 I = M, L - 1
300:             BB = E( I )
301:             R = P + BB
302:             IF( I.NE.M )
303:      $         E( I-1 ) = S*R
304:             OLDC = C
305:             C = P / R
306:             S = BB / R
307:             OLDGAM = GAMMA
308:             ALPHA = D( I+1 )
309:             GAMMA = C*( ALPHA-SIGMA ) - S*OLDGAM
310:             D( I ) = OLDGAM + ( ALPHA-GAMMA )
311:             IF( C.NE.ZERO ) THEN
312:                P = ( GAMMA*GAMMA ) / C
313:             ELSE
314:                P = OLDC*BB
315:             END IF
316:   130    CONTINUE
317: *
318:          E( L-1 ) = S*P
319:          D( L ) = SIGMA + GAMMA
320:          GO TO 100
321: *
322: *        Eigenvalue found.
323: *
324:   140    CONTINUE
325:          D( L ) = P
326: *
327:          L = L - 1
328:          IF( L.GE.LEND )
329:      $      GO TO 100
330:          GO TO 150
331: *
332:       END IF
333: *
334: *     Undo scaling if necessary
335: *
336:   150 CONTINUE
337:       IF( ISCALE.EQ.1 )
338:      $   CALL SLASCL( 'G', 0, 0, SSFMAX, ANORM, LENDSV-LSV+1, 1,
339:      $                D( LSV ), N, INFO )
340:       IF( ISCALE.EQ.2 )
341:      $   CALL SLASCL( 'G', 0, 0, SSFMIN, ANORM, LENDSV-LSV+1, 1,
342:      $                D( LSV ), N, INFO )
343: *
344: *     Check for no convergence to an eigenvalue after a total
345: *     of N*MAXIT iterations.
346: *
347:       IF( JTOT.LT.NMAXIT )
348:      $   GO TO 10
349:       DO 160 I = 1, N - 1
350:          IF( E( I ).NE.ZERO )
351:      $      INFO = INFO + 1
352:   160 CONTINUE
353:       GO TO 180
354: *
355: *     Sort eigenvalues in increasing order.
356: *
357:   170 CONTINUE
358:       CALL SLASRT( 'I', N, D, INFO )
359: *
360:   180 CONTINUE
361:       RETURN
362: *
363: *     End of SSTERF
364: *
365:       END
366: