Debian Codegraph @

Modules/ThirdParty/VNL/src/vxl/v3p/netlib/lapack/complex16/zlahqr.f

raw
1 SUBROUTINE ZLAHQR( WANTT, WANTZ, N, ILO, IHI, H, LDH, W, ILOZ,
2 $ IHIZ, Z, LDZ, INFO )
3 *
4 * -- LAPACK auxiliary routine (version 3.0) --
5 * Univ. of Tennessee, Univ. of California Berkeley, NAG Ltd.,
6 * Courant Institute, Argonne National Lab, and Rice University
7 * June 30, 1999
8 *
9 * .. Scalar Arguments ..
10 LOGICAL WANTT, WANTZ
11 INTEGER IHI, IHIZ, ILO, ILOZ, INFO, LDH, LDZ, N
12 * ..
13 * .. Array Arguments ..
14 COMPLEX*16 H( LDH, * ), W( * ), Z( LDZ, * )
15 * ..
16 *
17 * Purpose
18 * =======
19 *
20 * ZLAHQR is an auxiliary routine called by ZHSEQR to update the
21 * eigenvalues and Schur decomposition already computed by ZHSEQR, by
22 * dealing with the Hessenberg submatrix in rows and columns ILO to IHI.
23 *
24 * Arguments
25 * =========
26 *
27 * WANTT (input) LOGICAL
28 * = .TRUE. : the full Schur form T is required;
29 * = .FALSE.: only eigenvalues are required.
30 *
31 * WANTZ (input) LOGICAL
32 * = .TRUE. : the matrix of Schur vectors Z is required;
33 * = .FALSE.: Schur vectors are not required.
34 *
35 * N (input) INTEGER
36 * The order of the matrix H. N >= 0.
37 *
38 * ILO (input) INTEGER
39 * IHI (input) INTEGER
40 * It is assumed that H is already upper triangular in rows and
41 * columns IHI+1:N, and that H(ILO,ILO-1) = 0 (unless ILO = 1).
42 * ZLAHQR works primarily with the Hessenberg submatrix in rows
43 * and columns ILO to IHI, but applies transformations to all of
44 * H if WANTT is .TRUE..
45 * 1 <= ILO <= max(1,IHI); IHI <= N.
46 *
47 * H (input/output) COMPLEX*16 array, dimension (LDH,N)
48 * On entry, the upper Hessenberg matrix H.
49 * On exit, if WANTT is .TRUE., H is upper triangular in rows
50 * and columns ILO:IHI, with any 2-by-2 diagonal blocks in
51 * standard form. If WANTT is .FALSE., the contents of H are
52 * unspecified on exit.
53 *
54 * LDH (input) INTEGER
55 * The leading dimension of the array H. LDH >= max(1,N).
56 *
57 * W (output) COMPLEX*16 array, dimension (N)
58 * The computed eigenvalues ILO to IHI are stored in the
59 * corresponding elements of W. If WANTT is .TRUE., the
60 * eigenvalues are stored in the same order as on the diagonal
61 * of the Schur form returned in H, with W(i) = H(i,i).
62 *
63 * ILOZ (input) INTEGER
64 * IHIZ (input) INTEGER
65 * Specify the rows of Z to which transformations must be
66 * applied if WANTZ is .TRUE..
67 * 1 <= ILOZ <= ILO; IHI <= IHIZ <= N.
68 *
69 * Z (input/output) COMPLEX*16 array, dimension (LDZ,N)
70 * If WANTZ is .TRUE., on entry Z must contain the current
71 * matrix Z of transformations accumulated by ZHSEQR, and on
72 * exit Z has been updated; transformations are applied only to
73 * the submatrix Z(ILOZ:IHIZ,ILO:IHI).
74 * If WANTZ is .FALSE., Z is not referenced.
75 *
76 * LDZ (input) INTEGER
77 * The leading dimension of the array Z. LDZ >= max(1,N).
78 *
79 * INFO (output) INTEGER
80 * = 0: successful exit
81 * > 0: if INFO = i, ZLAHQR failed to compute all the
82 * eigenvalues ILO to IHI in a total of 30*(IHI-ILO+1)
83 * iterations; elements i+1:ihi of W contain those
84 * eigenvalues which have been successfully computed.
85 *
86 * =====================================================================
87 *
88 * .. Parameters ..
89 COMPLEX*16 ZERO, ONE
90 PARAMETER ( ZERO = ( 0.0D+0, 0.0D+0 ),
91 $ ONE = ( 1.0D+0, 0.0D+0 ) )
92 DOUBLE PRECISION RZERO, HALF
93 PARAMETER ( RZERO = 0.0D+0, HALF = 0.5D+0 )
94 DOUBLE PRECISION DAT1
95 PARAMETER ( DAT1 = 0.75D+0 )
96 * ..
97 * .. Local Scalars ..
98 INTEGER I, I1, I2, ITN, ITS, J, K, L, M, NH, NZ
99 DOUBLE PRECISION H10, H21, RTEMP, S, SMLNUM, T2, TST1, ULP
100 COMPLEX*16 CDUM, H11, H11S, H22, SUM, T, T1, TEMP, U, V2,
101 $ X, Y
102 * ..
103 * .. Local Arrays ..
104 DOUBLE PRECISION RWORK( 1 )
105 COMPLEX*16 V( 2 )
106 * ..
107 * .. External Functions ..
108 DOUBLE PRECISION DLAMCH, ZLANHS
109 COMPLEX*16 ZLADIV
110 EXTERNAL DLAMCH, ZLANHS, ZLADIV
111 * ..
112 * .. External Subroutines ..
113 EXTERNAL ZCOPY, ZLARFG, ZSCAL
114 * ..
115 * .. Intrinsic Functions ..
116 INTRINSIC ABS, DBLE, DCONJG, DIMAG, MAX, MIN, SQRT
117 * ..
118 * .. Statement Functions ..
119 DOUBLE PRECISION CABS1
120 * ..
121 * .. Statement Function definitions ..
122 CABS1( CDUM ) = ABS( DBLE( CDUM ) ) + ABS( DIMAG( CDUM ) )
123 * ..
124 * .. Executable Statements ..
125 *
126 INFO = 0
127 *
128 * Quick return if possible
129 *
130 IF( N.EQ.0 )
131 $ RETURN
132 IF( ILO.EQ.IHI ) THEN
133 W( ILO ) = H( ILO, ILO )
134 RETURN
135 END IF
136 *
137 NH = IHI - ILO + 1
138 NZ = IHIZ - ILOZ + 1
139 *
140 * Set machine-dependent constants for the stopping criterion.
141 * If norm(H) <= sqrt(OVFL), overflow should not occur.
142 *
143 ULP = DLAMCH( 'Precision' )
144 SMLNUM = DLAMCH( 'Safe minimum' ) / ULP
145 *
146 * I1 and I2 are the indices of the first row and last column of H
147 * to which transformations must be applied. If eigenvalues only are
148 * being computed, I1 and I2 are set inside the main loop.
149 *
150 IF( WANTT ) THEN
151 I1 = 1
152 I2 = N
153 END IF
154 *
155 * ITN is the total number of QR iterations allowed.
156 *
157 ITN = 30*NH
158 *
159 * The main loop begins here. I is the loop index and decreases from
160 * IHI to ILO in steps of 1. Each iteration of the loop works
161 * with the active submatrix in rows and columns L to I.
162 * Eigenvalues I+1 to IHI have already converged. Either L = ILO, or
163 * H(L,L-1) is negligible so that the matrix splits.
164 *
165 I = IHI
166 10 CONTINUE
167 IF( I.LT.ILO )
168 $ GO TO 130
169 *
170 * Perform QR iterations on rows and columns ILO to I until a
171 * submatrix of order 1 splits off at the bottom because a
172 * subdiagonal element has become negligible.
173 *
174 L = ILO
175 DO 110 ITS = 0, ITN
176 *
177 * Look for a single small subdiagonal element.
178 *
179 DO 20 K = I, L + 1, -1
180 TST1 = CABS1( H( K-1, K-1 ) ) + CABS1( H( K, K ) )
181 IF( TST1.EQ.RZERO )
182 $ TST1 = ZLANHS( '1', I-L+1, H( L, L ), LDH, RWORK )
183 IF( ABS( DBLE( H( K, K-1 ) ) ).LE.MAX( ULP*TST1, SMLNUM ) )
184 $ GO TO 30
185 20 CONTINUE
186 30 CONTINUE
187 L = K
188 IF( L.GT.ILO ) THEN
189 *
190 * H(L,L-1) is negligible
191 *
192 H( L, L-1 ) = ZERO
193 END IF
194 *
195 * Exit from loop if a submatrix of order 1 has split off.
196 *
197 IF( L.GE.I )
198 $ GO TO 120
199 *
200 * Now the active submatrix is in rows and columns L to I. If
201 * eigenvalues only are being computed, only the active submatrix
202 * need be transformed.
203 *
204 IF( .NOT.WANTT ) THEN
205 I1 = L
206 I2 = I
207 END IF
208 *
209 IF( ITS.EQ.10 .OR. ITS.EQ.20 ) THEN
210 *
211 * Exceptional shift.
212 *
213 S = DAT1*ABS( DBLE( H( I, I-1 ) ) )
214 T = S + H( I, I )
215 ELSE
216 *
217 * Wilkinson's shift.
218 *
219 T = H( I, I )
220 U = H( I-1, I )*DBLE( H( I, I-1 ) )
221 IF( U.NE.ZERO ) THEN
222 X = HALF*( H( I-1, I-1 )-T )
223 Y = SQRT( X*X+U )
224 IF( DBLE( X )*DBLE( Y )+DIMAG( X )*DIMAG( Y ).LT.RZERO )
225 $ Y = -Y
226 T = T - ZLADIV( U, ( X+Y ) )
227 END IF
228 END IF
229 *
230 * Look for two consecutive small subdiagonal elements.
231 *
232 DO 40 M = I - 1, L + 1, -1
233 *
234 * Determine the effect of starting the single-shift QR
235 * iteration at row M, and see if this would make H(M,M-1)
236 * negligible.
237 *
238 H11 = H( M, M )
239 H22 = H( M+1, M+1 )
240 H11S = H11 - T
241 H21 = H( M+1, M )
242 S = CABS1( H11S ) + ABS( H21 )
243 H11S = H11S / S
244 H21 = H21 / S
245 V( 1 ) = H11S
246 V( 2 ) = H21
247 H10 = H( M, M-1 )
248 TST1 = CABS1( H11S )*( CABS1( H11 )+CABS1( H22 ) )
249 IF( ABS( H10*H21 ).LE.ULP*TST1 )
250 $ GO TO 50
251 40 CONTINUE
252 H11 = H( L, L )
253 H22 = H( L+1, L+1 )
254 H11S = H11 - T
255 H21 = H( L+1, L )
256 S = CABS1( H11S ) + ABS( H21 )
257 H11S = H11S / S
258 H21 = H21 / S
259 V( 1 ) = H11S
260 V( 2 ) = H21
261 50 CONTINUE
262 *
263 * Single-shift QR step
264 *
265 DO 100 K = M, I - 1
266 *
267 * The first iteration of this loop determines a reflection G
268 * from the vector V and applies it from left and right to H,
269 * thus creating a nonzero bulge below the subdiagonal.
270 *
271 * Each subsequent iteration determines a reflection G to
272 * restore the Hessenberg form in the (K-1)th column, and thus
273 * chases the bulge one step toward the bottom of the active
274 * submatrix.
275 *
276 * V(2) is always real before the call to ZLARFG, and hence
277 * after the call T2 ( = T1*V(2) ) is also real.
278 *
279 IF( K.GT.M )
280 $ CALL ZCOPY( 2, H( K, K-1 ), 1, V, 1 )
281 CALL ZLARFG( 2, V( 1 ), V( 2 ), 1, T1 )
282 IF( K.GT.M ) THEN
283 H( K, K-1 ) = V( 1 )
284 H( K+1, K-1 ) = ZERO
285 END IF
286 V2 = V( 2 )
287 T2 = DBLE( T1*V2 )
288 *
289 * Apply G from the left to transform the rows of the matrix
290 * in columns K to I2.
291 *
292 DO 60 J = K, I2
293 SUM = DCONJG( T1 )*H( K, J ) + T2*H( K+1, J )
294 H( K, J ) = H( K, J ) - SUM
295 H( K+1, J ) = H( K+1, J ) - SUM*V2
296 60 CONTINUE
297 *
298 * Apply G from the right to transform the columns of the
299 * matrix in rows I1 to min(K+2,I).
300 *
301 DO 70 J = I1, MIN( K+2, I )
302 SUM = T1*H( J, K ) + T2*H( J, K+1 )
303 H( J, K ) = H( J, K ) - SUM
304 H( J, K+1 ) = H( J, K+1 ) - SUM*DCONJG( V2 )
305 70 CONTINUE
306 *
307 IF( WANTZ ) THEN
308 *
309 * Accumulate transformations in the matrix Z
310 *
311 DO 80 J = ILOZ, IHIZ
312 SUM = T1*Z( J, K ) + T2*Z( J, K+1 )
313 Z( J, K ) = Z( J, K ) - SUM
314 Z( J, K+1 ) = Z( J, K+1 ) - SUM*DCONJG( V2 )
315 80 CONTINUE
316 END IF
317 *
318 IF( K.EQ.M .AND. M.GT.L ) THEN
319 *
320 * If the QR step was started at row M > L because two
321 * consecutive small subdiagonals were found, then extra
322 * scaling must be performed to ensure that H(M,M-1) remains
323 * real.
324 *
325 TEMP = ONE - T1
326 TEMP = TEMP / ABS( TEMP )
327 H( M+1, M ) = H( M+1, M )*DCONJG( TEMP )
328 IF( M+2.LE.I )
329 $ H( M+2, M+1 ) = H( M+2, M+1 )*TEMP
330 DO 90 J = M, I
331 IF( J.NE.M+1 ) THEN
332 IF( I2.GT.J )
333 $ CALL ZSCAL( I2-J, TEMP, H( J, J+1 ), LDH )
334 CALL ZSCAL( J-I1, DCONJG( TEMP ), H( I1, J ), 1 )
335 IF( WANTZ ) THEN
336 CALL ZSCAL( NZ, DCONJG( TEMP ), Z( ILOZ, J ),
337 $ 1 )
338 END IF
339 END IF
340 90 CONTINUE
341 END IF
342 100 CONTINUE
343 *
344 * Ensure that H(I,I-1) is real.
345 *
346 TEMP = H( I, I-1 )
347 IF( DIMAG( TEMP ).NE.RZERO ) THEN
348 RTEMP = ABS( TEMP )
349 H( I, I-1 ) = RTEMP
350 TEMP = TEMP / RTEMP
351 IF( I2.GT.I )
352 $ CALL ZSCAL( I2-I, DCONJG( TEMP ), H( I, I+1 ), LDH )
353 CALL ZSCAL( I-I1, TEMP, H( I1, I ), 1 )
354 IF( WANTZ ) THEN
355 CALL ZSCAL( NZ, TEMP, Z( ILOZ, I ), 1 )
356 END IF
357 END IF
358 *
359 110 CONTINUE
360 *
361 * Failure to converge in remaining number of iterations
362 *
363 INFO = I
364 RETURN
365 *
366 120 CONTINUE
367 *
368 * H(I,I-1) is negligible: one eigenvalue has converged.
369 *
370 W( I ) = H( I, I )
371 *
372 * Decrement number of remaining iterations, and return to start of
373 * the main loop with new value of I.
374 *
375 ITN = ITN - ITS
376 I = L - 1
377 GO TO 10
378 *
379 130 CONTINUE
380 RETURN
381 *
382 * End of ZLAHQR
383 *
384 END