Debian Codegraph @

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

raw
1 SUBROUTINE ZHSEQR( JOB, COMPZ, N, ILO, IHI, H, LDH, W, Z, LDZ,
2 $ WORK, LWORK, INFO )
3 *
4 * -- LAPACK 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 CHARACTER COMPZ, JOB
11 INTEGER IHI, ILO, INFO, LDH, LDZ, LWORK, N
12 * ..
13 * .. Array Arguments ..
14 COMPLEX*16 H( LDH, * ), W( * ), WORK( * ), Z( LDZ, * )
15 * ..
16 *
17 * Purpose
18 * =======
19 *
20 * ZHSEQR computes the eigenvalues of a complex upper Hessenberg
21 * matrix H, and, optionally, the matrices T and Z from the Schur
22 * decomposition H = Z T Z**H, where T is an upper triangular matrix
23 * (the Schur form), and Z is the unitary matrix of Schur vectors.
24 *
25 * Optionally Z may be postmultiplied into an input unitary matrix Q,
26 * so that this routine can give the Schur factorization of a matrix A
27 * which has been reduced to the Hessenberg form H by the unitary
28 * matrix Q: A = Q*H*Q**H = (QZ)*T*(QZ)**H.
29 *
30 * Arguments
31 * =========
32 *
33 * JOB (input) CHARACTER*1
34 * = 'E': compute eigenvalues only;
35 * = 'S': compute eigenvalues and the Schur form T.
36 *
37 * COMPZ (input) CHARACTER*1
38 * = 'N': no Schur vectors are computed;
39 * = 'I': Z is initialized to the unit matrix and the matrix Z
40 * of Schur vectors of H is returned;
41 * = 'V': Z must contain an unitary matrix Q on entry, and
42 * the product Q*Z is returned.
43 *
44 * N (input) INTEGER
45 * The order of the matrix H. N >= 0.
46 *
47 * ILO (input) INTEGER
48 * IHI (input) INTEGER
49 * It is assumed that H is already upper triangular in rows
50 * and columns 1:ILO-1 and IHI+1:N. ILO and IHI are normally
51 * set by a previous call to ZGEBAL, and then passed to CGEHRD
52 * when the matrix output by ZGEBAL is reduced to Hessenberg
53 * form. Otherwise ILO and IHI should be set to 1 and N
54 * respectively.
55 * 1 <= ILO <= IHI <= N, if N > 0; ILO=1 and IHI=0, if N=0.
56 *
57 * H (input/output) COMPLEX*16 array, dimension (LDH,N)
58 * On entry, the upper Hessenberg matrix H.
59 * On exit, if JOB = 'S', H contains the upper triangular matrix
60 * T from the Schur decomposition (the Schur form). If
61 * JOB = 'E', the contents of H are unspecified on exit.
62 *
63 * LDH (input) INTEGER
64 * The leading dimension of the array H. LDH >= max(1,N).
65 *
66 * W (output) COMPLEX*16 array, dimension (N)
67 * The computed eigenvalues. If JOB = 'S', the eigenvalues are
68 * stored in the same order as on the diagonal of the Schur form
69 * returned in H, with W(i) = H(i,i).
70 *
71 * Z (input/output) COMPLEX*16 array, dimension (LDZ,N)
72 * If COMPZ = 'N': Z is not referenced.
73 * If COMPZ = 'I': on entry, Z need not be set, and on exit, Z
74 * contains the unitary matrix Z of the Schur vectors of H.
75 * If COMPZ = 'V': on entry Z must contain an N-by-N matrix Q,
76 * which is assumed to be equal to the unit matrix except for
77 * the submatrix Z(ILO:IHI,ILO:IHI); on exit Z contains Q*Z.
78 * Normally Q is the unitary matrix generated by ZUNGHR after
79 * the call to ZGEHRD which formed the Hessenberg matrix H.
80 *
81 * LDZ (input) INTEGER
82 * The leading dimension of the array Z.
83 * LDZ >= max(1,N) if COMPZ = 'I' or 'V'; LDZ >= 1 otherwise.
84 *
85 * WORK (workspace/output) COMPLEX*16 array, dimension (LWORK)
86 * On exit, if INFO = 0, WORK(1) returns the optimal LWORK.
87 *
88 * LWORK (input) INTEGER
89 * The dimension of the array WORK. LWORK >= max(1,N).
90 *
91 * If LWORK = -1, then a workspace query is assumed; the routine
92 * only calculates the optimal size of the WORK array, returns
93 * this value as the first entry of the WORK array, and no error
94 * message related to LWORK is issued by XERBLA.
95 *
96 * INFO (output) INTEGER
97 * = 0: successful exit
98 * < 0: if INFO = -i, the i-th argument had an illegal value
99 * > 0: if INFO = i, ZHSEQR failed to compute all the
100 * eigenvalues in a total of 30*(IHI-ILO+1) iterations;
101 * elements 1:ilo-1 and i+1:n of W contain those
102 * eigenvalues which have been successfully computed.
103 *
104 * =====================================================================
105 *
106 * .. Parameters ..
107 COMPLEX*16 ZERO, ONE
108 PARAMETER ( ZERO = ( 0.0D+0, 0.0D+0 ),
109 $ ONE = ( 1.0D+0, 0.0D+0 ) )
110 DOUBLE PRECISION RZERO, RONE, CONST
111 PARAMETER ( RZERO = 0.0D+0, RONE = 1.0D+0,
112 $ CONST = 1.5D+0 )
113 INTEGER NSMAX, LDS
114 PARAMETER ( NSMAX = 15, LDS = NSMAX )
115 * ..
116 * .. Local Scalars ..
117 LOGICAL INITZ, LQUERY, WANTT, WANTZ
118 INTEGER I, I1, I2, IERR, II, ITEMP, ITN, ITS, J, K, L,
119 $ MAXB, NH, NR, NS, NV
120 DOUBLE PRECISION OVFL, RTEMP, SMLNUM, TST1, ULP, UNFL
121 COMPLEX*16 CDUM, TAU, TEMP
122 * ..
123 * .. Local Arrays ..
124 DOUBLE PRECISION RWORK( 1 )
125 COMPLEX*16 S( LDS, NSMAX ), V( NSMAX+1 ), VV( NSMAX+1 )
126 * ..
127 * .. External Functions ..
128 LOGICAL LSAME
129 INTEGER ILAENV, IZAMAX
130 DOUBLE PRECISION DLAMCH, DLAPY2, ZLANHS
131 EXTERNAL LSAME, ILAENV, IZAMAX, DLAMCH, DLAPY2, ZLANHS
132 * ..
133 * .. External Subroutines ..
134 EXTERNAL XERBLA, ZCOPY, ZDSCAL, ZGEMV, ZLACPY, ZLAHQR,
135 $ ZLARFG, ZLARFX, ZLASET, ZSCAL
136 * ..
137 * .. Intrinsic Functions ..
138 INTRINSIC ABS, DBLE, DCONJG, DIMAG, MAX, MIN
139 * ..
140 * .. Statement Functions ..
141 DOUBLE PRECISION CABS1
142 * ..
143 * .. Statement Function definitions ..
144 CABS1( CDUM ) = ABS( DBLE( CDUM ) ) + ABS( DIMAG( CDUM ) )
145 * ..
146 * .. Executable Statements ..
147 *
148 * Decode and test the input parameters
149 *
150 WANTT = LSAME( JOB, 'S' )
151 INITZ = LSAME( COMPZ, 'I' )
152 WANTZ = INITZ .OR. LSAME( COMPZ, 'V' )
153 *
154 INFO = 0
155 WORK( 1 ) = MAX( 1, N )
156 LQUERY = ( LWORK.EQ.-1 )
157 IF( .NOT.LSAME( JOB, 'E' ) .AND. .NOT.WANTT ) THEN
158 INFO = -1
159 ELSE IF( .NOT.LSAME( COMPZ, 'N' ) .AND. .NOT.WANTZ ) THEN
160 INFO = -2
161 ELSE IF( N.LT.0 ) THEN
162 INFO = -3
163 ELSE IF( ILO.LT.1 .OR. ILO.GT.MAX( 1, N ) ) THEN
164 INFO = -4
165 ELSE IF( IHI.LT.MIN( ILO, N ) .OR. IHI.GT.N ) THEN
166 INFO = -5
167 ELSE IF( LDH.LT.MAX( 1, N ) ) THEN
168 INFO = -7
169 ELSE IF( LDZ.LT.1 .OR. WANTZ .AND. LDZ.LT.MAX( 1, N ) ) THEN
170 INFO = -10
171 ELSE IF( LWORK.LT.MAX( 1, N ) .AND. .NOT.LQUERY ) THEN
172 INFO = -12
173 END IF
174 IF( INFO.NE.0 ) THEN
175 CALL XERBLA( 'ZHSEQR', -INFO )
176 RETURN
177 ELSE IF( LQUERY ) THEN
178 RETURN
179 END IF
180 *
181 * Initialize Z, if necessary
182 *
183 IF( INITZ )
184 $ CALL ZLASET( 'Full', N, N, ZERO, ONE, Z, LDZ )
185 *
186 * Store the eigenvalues isolated by ZGEBAL.
187 *
188 DO 10 I = 1, ILO - 1
189 W( I ) = H( I, I )
190 10 CONTINUE
191 DO 20 I = IHI + 1, N
192 W( I ) = H( I, I )
193 20 CONTINUE
194 *
195 * Quick return if possible.
196 *
197 IF( N.EQ.0 )
198 $ RETURN
199 IF( ILO.EQ.IHI ) THEN
200 W( ILO ) = H( ILO, ILO )
201 RETURN
202 END IF
203 *
204 * Set rows and columns ILO to IHI to zero below the first
205 * subdiagonal.
206 *
207 DO 40 J = ILO, IHI - 2
208 DO 30 I = J + 2, N
209 H( I, J ) = ZERO
210 30 CONTINUE
211 40 CONTINUE
212 NH = IHI - ILO + 1
213 *
214 * I1 and I2 are the indices of the first row and last column of H
215 * to which transformations must be applied. If eigenvalues only are
216 * being computed, I1 and I2 are re-set inside the main loop.
217 *
218 IF( WANTT ) THEN
219 I1 = 1
220 I2 = N
221 ELSE
222 I1 = ILO
223 I2 = IHI
224 END IF
225 *
226 * Ensure that the subdiagonal elements are real.
227 *
228 DO 50 I = ILO + 1, IHI
229 TEMP = H( I, I-1 )
230 IF( DIMAG( TEMP ).NE.RZERO ) THEN
231 RTEMP = DLAPY2( DBLE( TEMP ), DIMAG( TEMP ) )
232 H( I, I-1 ) = RTEMP
233 TEMP = TEMP / RTEMP
234 IF( I2.GT.I )
235 $ CALL ZSCAL( I2-I, DCONJG( TEMP ), H( I, I+1 ), LDH )
236 CALL ZSCAL( I-I1, TEMP, H( I1, I ), 1 )
237 IF( I.LT.IHI )
238 $ H( I+1, I ) = TEMP*H( I+1, I )
239 IF( WANTZ )
240 $ CALL ZSCAL( NH, TEMP, Z( ILO, I ), 1 )
241 END IF
242 50 CONTINUE
243 *
244 * Determine the order of the multi-shift QR algorithm to be used.
245 *
246 NS = ILAENV( 4, 'ZHSEQR', JOB // COMPZ, N, ILO, IHI, -1 )
247 MAXB = ILAENV( 8, 'ZHSEQR', JOB // COMPZ, N, ILO, IHI, -1 )
248 IF( NS.LE.1 .OR. NS.GT.NH .OR. MAXB.GE.NH ) THEN
249 *
250 * Use the standard double-shift algorithm
251 *
252 CALL ZLAHQR( WANTT, WANTZ, N, ILO, IHI, H, LDH, W, ILO, IHI, Z,
253 $ LDZ, INFO )
254 RETURN
255 END IF
256 MAXB = MAX( 2, MAXB )
257 NS = MIN( NS, MAXB, NSMAX )
258 *
259 * Now 1 < NS <= MAXB < NH.
260 *
261 * Set machine-dependent constants for the stopping criterion.
262 * If norm(H) <= sqrt(OVFL), overflow should not occur.
263 *
264 UNFL = DLAMCH( 'Safe minimum' )
265 OVFL = RONE / UNFL
266 CALL DLABAD( UNFL, OVFL )
267 ULP = DLAMCH( 'Precision' )
268 SMLNUM = UNFL*( NH / ULP )
269 *
270 * ITN is the total number of multiple-shift QR iterations allowed.
271 *
272 ITN = 30*NH
273 *
274 * The main loop begins here. I is the loop index and decreases from
275 * IHI to ILO in steps of at most MAXB. Each iteration of the loop
276 * works with the active submatrix in rows and columns L to I.
277 * Eigenvalues I+1 to IHI have already converged. Either L = ILO, or
278 * H(L,L-1) is negligible so that the matrix splits.
279 *
280 I = IHI
281 60 CONTINUE
282 IF( I.LT.ILO )
283 $ GO TO 180
284 *
285 * Perform multiple-shift QR iterations on rows and columns ILO to I
286 * until a submatrix of order at most MAXB splits off at the bottom
287 * because a subdiagonal element has become negligible.
288 *
289 L = ILO
290 DO 160 ITS = 0, ITN
291 *
292 * Look for a single small subdiagonal element.
293 *
294 DO 70 K = I, L + 1, -1
295 TST1 = CABS1( H( K-1, K-1 ) ) + CABS1( H( K, K ) )
296 IF( TST1.EQ.RZERO )
297 $ TST1 = ZLANHS( '1', I-L+1, H( L, L ), LDH, RWORK )
298 IF( ABS( DBLE( H( K, K-1 ) ) ).LE.MAX( ULP*TST1, SMLNUM ) )
299 $ GO TO 80
300 70 CONTINUE
301 80 CONTINUE
302 L = K
303 IF( L.GT.ILO ) THEN
304 *
305 * H(L,L-1) is negligible.
306 *
307 H( L, L-1 ) = ZERO
308 END IF
309 *
310 * Exit from loop if a submatrix of order <= MAXB has split off.
311 *
312 IF( L.GE.I-MAXB+1 )
313 $ GO TO 170
314 *
315 * Now the active submatrix is in rows and columns L to I. If
316 * eigenvalues only are being computed, only the active submatrix
317 * need be transformed.
318 *
319 IF( .NOT.WANTT ) THEN
320 I1 = L
321 I2 = I
322 END IF
323 *
324 IF( ITS.EQ.20 .OR. ITS.EQ.30 ) THEN
325 *
326 * Exceptional shifts.
327 *
328 DO 90 II = I - NS + 1, I
329 W( II ) = CONST*( ABS( DBLE( H( II, II-1 ) ) )+
330 $ ABS( DBLE( H( II, II ) ) ) )
331 90 CONTINUE
332 ELSE
333 *
334 * Use eigenvalues of trailing submatrix of order NS as shifts.
335 *
336 CALL ZLACPY( 'Full', NS, NS, H( I-NS+1, I-NS+1 ), LDH, S,
337 $ LDS )
338 CALL ZLAHQR( .FALSE., .FALSE., NS, 1, NS, S, LDS,
339 $ W( I-NS+1 ), 1, NS, Z, LDZ, IERR )
340 IF( IERR.GT.0 ) THEN
341 *
342 * If ZLAHQR failed to compute all NS eigenvalues, use the
343 * unconverged diagonal elements as the remaining shifts.
344 *
345 DO 100 II = 1, IERR
346 W( I-NS+II ) = S( II, II )
347 100 CONTINUE
348 END IF
349 END IF
350 *
351 * Form the first column of (G-w(1)) (G-w(2)) . . . (G-w(ns))
352 * where G is the Hessenberg submatrix H(L:I,L:I) and w is
353 * the vector of shifts (stored in W). The result is
354 * stored in the local array V.
355 *
356 V( 1 ) = ONE
357 DO 110 II = 2, NS + 1
358 V( II ) = ZERO
359 110 CONTINUE
360 NV = 1
361 DO 130 J = I - NS + 1, I
362 CALL ZCOPY( NV+1, V, 1, VV, 1 )
363 CALL ZGEMV( 'No transpose', NV+1, NV, ONE, H( L, L ), LDH,
364 $ VV, 1, -W( J ), V, 1 )
365 NV = NV + 1
366 *
367 * Scale V(1:NV) so that max(abs(V(i))) = 1. If V is zero,
368 * reset it to the unit vector.
369 *
370 ITEMP = IZAMAX( NV, V, 1 )
371 RTEMP = CABS1( V( ITEMP ) )
372 IF( RTEMP.EQ.RZERO ) THEN
373 V( 1 ) = ONE
374 DO 120 II = 2, NV
375 V( II ) = ZERO
376 120 CONTINUE
377 ELSE
378 RTEMP = MAX( RTEMP, SMLNUM )
379 CALL ZDSCAL( NV, RONE / RTEMP, V, 1 )
380 END IF
381 130 CONTINUE
382 *
383 * Multiple-shift QR step
384 *
385 DO 150 K = L, I - 1
386 *
387 * The first iteration of this loop determines a reflection G
388 * from the vector V and applies it from left and right to H,
389 * thus creating a nonzero bulge below the subdiagonal.
390 *
391 * Each subsequent iteration determines a reflection G to
392 * restore the Hessenberg form in the (K-1)th column, and thus
393 * chases the bulge one step toward the bottom of the active
394 * submatrix. NR is the order of G.
395 *
396 NR = MIN( NS+1, I-K+1 )
397 IF( K.GT.L )
398 $ CALL ZCOPY( NR, H( K, K-1 ), 1, V, 1 )
399 CALL ZLARFG( NR, V( 1 ), V( 2 ), 1, TAU )
400 IF( K.GT.L ) THEN
401 H( K, K-1 ) = V( 1 )
402 DO 140 II = K + 1, I
403 H( II, K-1 ) = ZERO
404 140 CONTINUE
405 END IF
406 V( 1 ) = ONE
407 *
408 * Apply G' from the left to transform the rows of the matrix
409 * in columns K to I2.
410 *
411 CALL ZLARFX( 'Left', NR, I2-K+1, V, DCONJG( TAU ),
412 $ H( K, K ), LDH, WORK )
413 *
414 * Apply G from the right to transform the columns of the
415 * matrix in rows I1 to min(K+NR,I).
416 *
417 CALL ZLARFX( 'Right', MIN( K+NR, I )-I1+1, NR, V, TAU,
418 $ H( I1, K ), LDH, WORK )
419 *
420 IF( WANTZ ) THEN
421 *
422 * Accumulate transformations in the matrix Z
423 *
424 CALL ZLARFX( 'Right', NH, NR, V, TAU, Z( ILO, K ), LDZ,
425 $ WORK )
426 END IF
427 150 CONTINUE
428 *
429 * Ensure that H(I,I-1) is real.
430 *
431 TEMP = H( I, I-1 )
432 IF( DIMAG( TEMP ).NE.RZERO ) THEN
433 RTEMP = DLAPY2( DBLE( TEMP ), DIMAG( TEMP ) )
434 H( I, I-1 ) = RTEMP
435 TEMP = TEMP / RTEMP
436 IF( I2.GT.I )
437 $ CALL ZSCAL( I2-I, DCONJG( TEMP ), H( I, I+1 ), LDH )
438 CALL ZSCAL( I-I1, TEMP, H( I1, I ), 1 )
439 IF( WANTZ ) THEN
440 CALL ZSCAL( NH, TEMP, Z( ILO, I ), 1 )
441 END IF
442 END IF
443 *
444 160 CONTINUE
445 *
446 * Failure to converge in remaining number of iterations
447 *
448 INFO = I
449 RETURN
450 *
451 170 CONTINUE
452 *
453 * A submatrix of order <= MAXB in rows and columns L to I has split
454 * off. Use the double-shift QR algorithm to handle it.
455 *
456 CALL ZLAHQR( WANTT, WANTZ, N, L, I, H, LDH, W, ILO, IHI, Z, LDZ,
457 $ INFO )
458 IF( INFO.GT.0 )
459 $ RETURN
460 *
461 * Decrement number of remaining iterations, and return to start of
462 * the main loop with a new value of I.
463 *
464 ITN = ITN - ITS
465 I = L - 1
466 GO TO 60
467 *
468 180 CONTINUE
469 WORK( 1 ) = MAX( 1, N )
470 RETURN
471 *
472 * End of ZHSEQR
473 *
474 END