LAPACK  3.8.0
LAPACK: Linear Algebra PACKage
zlaqr0.f
Go to the documentation of this file.
1 *> \brief \b ZLAQR0 computes the eigenvalues of a Hessenberg matrix, and optionally the matrices from the Schur decomposition.
2 *
3 * =========== DOCUMENTATION ===========
4 *
5 * Online html documentation available at
6 * http://www.netlib.org/lapack/explore-html/
7 *
8 *> \htmlonly
9 *> Download ZLAQR0 + dependencies
10 *> <a href="http://www.netlib.org/cgi-bin/netlibfiles.tgz?format=tgz&filename=/lapack/lapack_routine/zlaqr0.f">
11 *> [TGZ]</a>
12 *> <a href="http://www.netlib.org/cgi-bin/netlibfiles.zip?format=zip&filename=/lapack/lapack_routine/zlaqr0.f">
13 *> [ZIP]</a>
14 *> <a href="http://www.netlib.org/cgi-bin/netlibfiles.txt?format=txt&filename=/lapack/lapack_routine/zlaqr0.f">
15 *> [TXT]</a>
16 *> \endhtmlonly
17 *
18 * Definition:
19 * ===========
20 *
21 * SUBROUTINE ZLAQR0( WANTT, WANTZ, N, ILO, IHI, H, LDH, W, ILOZ,
22 * IHIZ, Z, LDZ, WORK, LWORK, INFO )
23 *
24 * .. Scalar Arguments ..
25 * INTEGER IHI, IHIZ, ILO, ILOZ, INFO, LDH, LDZ, LWORK, N
26 * LOGICAL WANTT, WANTZ
27 * ..
28 * .. Array Arguments ..
29 * COMPLEX*16 H( LDH, * ), W( * ), WORK( * ), Z( LDZ, * )
30 * ..
31 *
32 *
33 *> \par Purpose:
34 * =============
35 *>
36 *> \verbatim
37 *>
38 *> ZLAQR0 computes the eigenvalues of a Hessenberg matrix H
39 *> and, optionally, the matrices T and Z from the Schur decomposition
40 *> H = Z T Z**H, where T is an upper triangular matrix (the
41 *> Schur form), and Z is the unitary matrix of Schur vectors.
42 *>
43 *> Optionally Z may be postmultiplied into an input unitary
44 *> matrix Q so that this routine can give the Schur factorization
45 *> of a matrix A which has been reduced to the Hessenberg form H
46 *> by the unitary matrix Q: A = Q*H*Q**H = (QZ)*H*(QZ)**H.
47 *> \endverbatim
48 *
49 * Arguments:
50 * ==========
51 *
52 *> \param[in] WANTT
53 *> \verbatim
54 *> WANTT is LOGICAL
55 *> = .TRUE. : the full Schur form T is required;
56 *> = .FALSE.: only eigenvalues are required.
57 *> \endverbatim
58 *>
59 *> \param[in] WANTZ
60 *> \verbatim
61 *> WANTZ is LOGICAL
62 *> = .TRUE. : the matrix of Schur vectors Z is required;
63 *> = .FALSE.: Schur vectors are not required.
64 *> \endverbatim
65 *>
66 *> \param[in] N
67 *> \verbatim
68 *> N is INTEGER
69 *> The order of the matrix H. N .GE. 0.
70 *> \endverbatim
71 *>
72 *> \param[in] ILO
73 *> \verbatim
74 *> ILO is INTEGER
75 *> \endverbatim
76 *>
77 *> \param[in] IHI
78 *> \verbatim
79 *> IHI is INTEGER
80 *>
81 *> It is assumed that H is already upper triangular in rows
82 *> and columns 1:ILO-1 and IHI+1:N and, if ILO.GT.1,
83 *> H(ILO,ILO-1) is zero. ILO and IHI are normally set by a
84 *> previous call to ZGEBAL, and then passed to ZGEHRD when the
85 *> matrix output by ZGEBAL is reduced to Hessenberg form.
86 *> Otherwise, ILO and IHI should be set to 1 and N,
87 *> respectively. If N.GT.0, then 1.LE.ILO.LE.IHI.LE.N.
88 *> If N = 0, then ILO = 1 and IHI = 0.
89 *> \endverbatim
90 *>
91 *> \param[in,out] H
92 *> \verbatim
93 *> H is COMPLEX*16 array, dimension (LDH,N)
94 *> On entry, the upper Hessenberg matrix H.
95 *> On exit, if INFO = 0 and WANTT is .TRUE., then H
96 *> contains the upper triangular matrix T from the Schur
97 *> decomposition (the Schur form). If INFO = 0 and WANT is
98 *> .FALSE., then the contents of H are unspecified on exit.
99 *> (The output value of H when INFO.GT.0 is given under the
100 *> description of INFO below.)
101 *>
102 *> This subroutine may explicitly set H(i,j) = 0 for i.GT.j and
103 *> j = 1, 2, ... ILO-1 or j = IHI+1, IHI+2, ... N.
104 *> \endverbatim
105 *>
106 *> \param[in] LDH
107 *> \verbatim
108 *> LDH is INTEGER
109 *> The leading dimension of the array H. LDH .GE. max(1,N).
110 *> \endverbatim
111 *>
112 *> \param[out] W
113 *> \verbatim
114 *> W is COMPLEX*16 array, dimension (N)
115 *> The computed eigenvalues of H(ILO:IHI,ILO:IHI) are stored
116 *> in W(ILO:IHI). If WANTT is .TRUE., then the eigenvalues are
117 *> stored in the same order as on the diagonal of the Schur
118 *> form returned in H, with W(i) = H(i,i).
119 *> \endverbatim
120 *>
121 *> \param[in] ILOZ
122 *> \verbatim
123 *> ILOZ is INTEGER
124 *> \endverbatim
125 *>
126 *> \param[in] IHIZ
127 *> \verbatim
128 *> IHIZ is INTEGER
129 *> Specify the rows of Z to which transformations must be
130 *> applied if WANTZ is .TRUE..
131 *> 1 .LE. ILOZ .LE. ILO; IHI .LE. IHIZ .LE. N.
132 *> \endverbatim
133 *>
134 *> \param[in,out] Z
135 *> \verbatim
136 *> Z is COMPLEX*16 array, dimension (LDZ,IHI)
137 *> If WANTZ is .FALSE., then Z is not referenced.
138 *> If WANTZ is .TRUE., then Z(ILO:IHI,ILOZ:IHIZ) is
139 *> replaced by Z(ILO:IHI,ILOZ:IHIZ)*U where U is the
140 *> orthogonal Schur factor of H(ILO:IHI,ILO:IHI).
141 *> (The output value of Z when INFO.GT.0 is given under
142 *> the description of INFO below.)
143 *> \endverbatim
144 *>
145 *> \param[in] LDZ
146 *> \verbatim
147 *> LDZ is INTEGER
148 *> The leading dimension of the array Z. if WANTZ is .TRUE.
149 *> then LDZ.GE.MAX(1,IHIZ). Otherwize, LDZ.GE.1.
150 *> \endverbatim
151 *>
152 *> \param[out] WORK
153 *> \verbatim
154 *> WORK is COMPLEX*16 array, dimension LWORK
155 *> On exit, if LWORK = -1, WORK(1) returns an estimate of
156 *> the optimal value for LWORK.
157 *> \endverbatim
158 *>
159 *> \param[in] LWORK
160 *> \verbatim
161 *> LWORK is INTEGER
162 *> The dimension of the array WORK. LWORK .GE. max(1,N)
163 *> is sufficient, but LWORK typically as large as 6*N may
164 *> be required for optimal performance. A workspace query
165 *> to determine the optimal workspace size is recommended.
166 *>
167 *> If LWORK = -1, then ZLAQR0 does a workspace query.
168 *> In this case, ZLAQR0 checks the input parameters and
169 *> estimates the optimal workspace size for the given
170 *> values of N, ILO and IHI. The estimate is returned
171 *> in WORK(1). No error message related to LWORK is
172 *> issued by XERBLA. Neither H nor Z are accessed.
173 *> \endverbatim
174 *>
175 *> \param[out] INFO
176 *> \verbatim
177 *> INFO is INTEGER
178 *> = 0: successful exit
179 *> .GT. 0: if INFO = i, ZLAQR0 failed to compute all of
180 *> the eigenvalues. Elements 1:ilo-1 and i+1:n of WR
181 *> and WI contain those eigenvalues which have been
182 *> successfully computed. (Failures are rare.)
183 *>
184 *> If INFO .GT. 0 and WANT is .FALSE., then on exit,
185 *> the remaining unconverged eigenvalues are the eigen-
186 *> values of the upper Hessenberg matrix rows and
187 *> columns ILO through INFO of the final, output
188 *> value of H.
189 *>
190 *> If INFO .GT. 0 and WANTT is .TRUE., then on exit
191 *>
192 *> (*) (initial value of H)*U = U*(final value of H)
193 *>
194 *> where U is a unitary matrix. The final
195 *> value of H is upper Hessenberg and triangular in
196 *> rows and columns INFO+1 through IHI.
197 *>
198 *> If INFO .GT. 0 and WANTZ is .TRUE., then on exit
199 *>
200 *> (final value of Z(ILO:IHI,ILOZ:IHIZ)
201 *> = (initial value of Z(ILO:IHI,ILOZ:IHIZ)*U
202 *>
203 *> where U is the unitary matrix in (*) (regard-
204 *> less of the value of WANTT.)
205 *>
206 *> If INFO .GT. 0 and WANTZ is .FALSE., then Z is not
207 *> accessed.
208 *> \endverbatim
209 *
210 * Authors:
211 * ========
212 *
213 *> \author Univ. of Tennessee
214 *> \author Univ. of California Berkeley
215 *> \author Univ. of Colorado Denver
216 *> \author NAG Ltd.
217 *
218 *> \date December 2016
219 *
220 *> \ingroup complex16OTHERauxiliary
221 *
222 *> \par Contributors:
223 * ==================
224 *>
225 *> Karen Braman and Ralph Byers, Department of Mathematics,
226 *> University of Kansas, USA
227 *
228 *> \par References:
229 * ================
230 *>
231 *> K. Braman, R. Byers and R. Mathias, The Multi-Shift QR
232 *> Algorithm Part I: Maintaining Well Focused Shifts, and Level 3
233 *> Performance, SIAM Journal of Matrix Analysis, volume 23, pages
234 *> 929--947, 2002.
235 *> \n
236 *> K. Braman, R. Byers and R. Mathias, The Multi-Shift QR
237 *> Algorithm Part II: Aggressive Early Deflation, SIAM Journal
238 *> of Matrix Analysis, volume 23, pages 948--973, 2002.
239 *>
240 * =====================================================================
241  SUBROUTINE zlaqr0( WANTT, WANTZ, N, ILO, IHI, H, LDH, W, ILOZ,
242  $ IHIZ, Z, LDZ, WORK, LWORK, INFO )
243 *
244 * -- LAPACK auxiliary routine (version 3.7.0) --
245 * -- LAPACK is a software package provided by Univ. of Tennessee, --
246 * -- Univ. of California Berkeley, Univ. of Colorado Denver and NAG Ltd..--
247 * December 2016
248 *
249 * .. Scalar Arguments ..
250  INTEGER IHI, IHIZ, ILO, ILOZ, INFO, LDH, LDZ, LWORK, N
251  LOGICAL WANTT, WANTZ
252 * ..
253 * .. Array Arguments ..
254  COMPLEX*16 H( ldh, * ), W( * ), WORK( * ), Z( ldz, * )
255 * ..
256 *
257 * ================================================================
258 *
259 * .. Parameters ..
260 *
261 * ==== Matrices of order NTINY or smaller must be processed by
262 * . ZLAHQR because of insufficient subdiagonal scratch space.
263 * . (This is a hard limit.) ====
264  INTEGER NTINY
265  parameter( ntiny = 11 )
266 *
267 * ==== Exceptional deflation windows: try to cure rare
268 * . slow convergence by varying the size of the
269 * . deflation window after KEXNW iterations. ====
270  INTEGER KEXNW
271  parameter( kexnw = 5 )
272 *
273 * ==== Exceptional shifts: try to cure rare slow convergence
274 * . with ad-hoc exceptional shifts every KEXSH iterations.
275 * . ====
276  INTEGER KEXSH
277  parameter( kexsh = 6 )
278 *
279 * ==== The constant WILK1 is used to form the exceptional
280 * . shifts. ====
281  DOUBLE PRECISION WILK1
282  parameter( wilk1 = 0.75d0 )
283  COMPLEX*16 ZERO, ONE
284  parameter( zero = ( 0.0d0, 0.0d0 ),
285  $ one = ( 1.0d0, 0.0d0 ) )
286  DOUBLE PRECISION TWO
287  parameter( two = 2.0d0 )
288 * ..
289 * .. Local Scalars ..
290  COMPLEX*16 AA, BB, CC, CDUM, DD, DET, RTDISC, SWAP, TR2
291  DOUBLE PRECISION S
292  INTEGER I, INF, IT, ITMAX, K, KACC22, KBOT, KDU, KS,
293  $ kt, ktop, ku, kv, kwh, kwtop, kwv, ld, ls,
294  $ lwkopt, ndec, ndfl, nh, nho, nibble, nmin, ns,
295  $ nsmax, nsr, nve, nw, nwmax, nwr, nwupbd
296  LOGICAL SORTED
297  CHARACTER JBCMPZ*2
298 * ..
299 * .. External Functions ..
300  INTEGER ILAENV
301  EXTERNAL ilaenv
302 * ..
303 * .. Local Arrays ..
304  COMPLEX*16 ZDUM( 1, 1 )
305 * ..
306 * .. External Subroutines ..
307  EXTERNAL zlacpy, zlahqr, zlaqr3, zlaqr4, zlaqr5
308 * ..
309 * .. Intrinsic Functions ..
310  INTRINSIC abs, dble, dcmplx, dimag, int, max, min, mod,
311  $ sqrt
312 * ..
313 * .. Statement Functions ..
314  DOUBLE PRECISION CABS1
315 * ..
316 * .. Statement Function definitions ..
317  cabs1( cdum ) = abs( dble( cdum ) ) + abs( dimag( cdum ) )
318 * ..
319 * .. Executable Statements ..
320  info = 0
321 *
322 * ==== Quick return for N = 0: nothing to do. ====
323 *
324  IF( n.EQ.0 ) THEN
325  work( 1 ) = one
326  RETURN
327  END IF
328 *
329  IF( n.LE.ntiny ) THEN
330 *
331 * ==== Tiny matrices must use ZLAHQR. ====
332 *
333  lwkopt = 1
334  IF( lwork.NE.-1 )
335  $ CALL zlahqr( wantt, wantz, n, ilo, ihi, h, ldh, w, iloz,
336  $ ihiz, z, ldz, info )
337  ELSE
338 *
339 * ==== Use small bulge multi-shift QR with aggressive early
340 * . deflation on larger-than-tiny matrices. ====
341 *
342 * ==== Hope for the best. ====
343 *
344  info = 0
345 *
346 * ==== Set up job flags for ILAENV. ====
347 *
348  IF( wantt ) THEN
349  jbcmpz( 1: 1 ) = 'S'
350  ELSE
351  jbcmpz( 1: 1 ) = 'E'
352  END IF
353  IF( wantz ) THEN
354  jbcmpz( 2: 2 ) = 'V'
355  ELSE
356  jbcmpz( 2: 2 ) = 'N'
357  END IF
358 *
359 * ==== NWR = recommended deflation window size. At this
360 * . point, N .GT. NTINY = 11, so there is enough
361 * . subdiagonal workspace for NWR.GE.2 as required.
362 * . (In fact, there is enough subdiagonal space for
363 * . NWR.GE.3.) ====
364 *
365  nwr = ilaenv( 13, 'ZLAQR0', jbcmpz, n, ilo, ihi, lwork )
366  nwr = max( 2, nwr )
367  nwr = min( ihi-ilo+1, ( n-1 ) / 3, nwr )
368 *
369 * ==== NSR = recommended number of simultaneous shifts.
370 * . At this point N .GT. NTINY = 11, so there is at
371 * . enough subdiagonal workspace for NSR to be even
372 * . and greater than or equal to two as required. ====
373 *
374  nsr = ilaenv( 15, 'ZLAQR0', jbcmpz, n, ilo, ihi, lwork )
375  nsr = min( nsr, ( n+6 ) / 9, ihi-ilo )
376  nsr = max( 2, nsr-mod( nsr, 2 ) )
377 *
378 * ==== Estimate optimal workspace ====
379 *
380 * ==== Workspace query call to ZLAQR3 ====
381 *
382  CALL zlaqr3( wantt, wantz, n, ilo, ihi, nwr+1, h, ldh, iloz,
383  $ ihiz, z, ldz, ls, ld, w, h, ldh, n, h, ldh, n, h,
384  $ ldh, work, -1 )
385 *
386 * ==== Optimal workspace = MAX(ZLAQR5, ZLAQR3) ====
387 *
388  lwkopt = max( 3*nsr / 2, int( work( 1 ) ) )
389 *
390 * ==== Quick return in case of workspace query. ====
391 *
392  IF( lwork.EQ.-1 ) THEN
393  work( 1 ) = dcmplx( lwkopt, 0 )
394  RETURN
395  END IF
396 *
397 * ==== ZLAHQR/ZLAQR0 crossover point ====
398 *
399  nmin = ilaenv( 12, 'ZLAQR0', jbcmpz, n, ilo, ihi, lwork )
400  nmin = max( ntiny, nmin )
401 *
402 * ==== Nibble crossover point ====
403 *
404  nibble = ilaenv( 14, 'ZLAQR0', jbcmpz, n, ilo, ihi, lwork )
405  nibble = max( 0, nibble )
406 *
407 * ==== Accumulate reflections during ttswp? Use block
408 * . 2-by-2 structure during matrix-matrix multiply? ====
409 *
410  kacc22 = ilaenv( 16, 'ZLAQR0', jbcmpz, n, ilo, ihi, lwork )
411  kacc22 = max( 0, kacc22 )
412  kacc22 = min( 2, kacc22 )
413 *
414 * ==== NWMAX = the largest possible deflation window for
415 * . which there is sufficient workspace. ====
416 *
417  nwmax = min( ( n-1 ) / 3, lwork / 2 )
418  nw = nwmax
419 *
420 * ==== NSMAX = the Largest number of simultaneous shifts
421 * . for which there is sufficient workspace. ====
422 *
423  nsmax = min( ( n+6 ) / 9, 2*lwork / 3 )
424  nsmax = nsmax - mod( nsmax, 2 )
425 *
426 * ==== NDFL: an iteration count restarted at deflation. ====
427 *
428  ndfl = 1
429 *
430 * ==== ITMAX = iteration limit ====
431 *
432  itmax = max( 30, 2*kexsh )*max( 10, ( ihi-ilo+1 ) )
433 *
434 * ==== Last row and column in the active block ====
435 *
436  kbot = ihi
437 *
438 * ==== Main Loop ====
439 *
440  DO 70 it = 1, itmax
441 *
442 * ==== Done when KBOT falls below ILO ====
443 *
444  IF( kbot.LT.ilo )
445  $ GO TO 80
446 *
447 * ==== Locate active block ====
448 *
449  DO 10 k = kbot, ilo + 1, -1
450  IF( h( k, k-1 ).EQ.zero )
451  $ GO TO 20
452  10 CONTINUE
453  k = ilo
454  20 CONTINUE
455  ktop = k
456 *
457 * ==== Select deflation window size:
458 * . Typical Case:
459 * . If possible and advisable, nibble the entire
460 * . active block. If not, use size MIN(NWR,NWMAX)
461 * . or MIN(NWR+1,NWMAX) depending upon which has
462 * . the smaller corresponding subdiagonal entry
463 * . (a heuristic).
464 * .
465 * . Exceptional Case:
466 * . If there have been no deflations in KEXNW or
467 * . more iterations, then vary the deflation window
468 * . size. At first, because, larger windows are,
469 * . in general, more powerful than smaller ones,
470 * . rapidly increase the window to the maximum possible.
471 * . Then, gradually reduce the window size. ====
472 *
473  nh = kbot - ktop + 1
474  nwupbd = min( nh, nwmax )
475  IF( ndfl.LT.kexnw ) THEN
476  nw = min( nwupbd, nwr )
477  ELSE
478  nw = min( nwupbd, 2*nw )
479  END IF
480  IF( nw.LT.nwmax ) THEN
481  IF( nw.GE.nh-1 ) THEN
482  nw = nh
483  ELSE
484  kwtop = kbot - nw + 1
485  IF( cabs1( h( kwtop, kwtop-1 ) ).GT.
486  $ cabs1( h( kwtop-1, kwtop-2 ) ) )nw = nw + 1
487  END IF
488  END IF
489  IF( ndfl.LT.kexnw ) THEN
490  ndec = -1
491  ELSE IF( ndec.GE.0 .OR. nw.GE.nwupbd ) THEN
492  ndec = ndec + 1
493  IF( nw-ndec.LT.2 )
494  $ ndec = 0
495  nw = nw - ndec
496  END IF
497 *
498 * ==== Aggressive early deflation:
499 * . split workspace under the subdiagonal into
500 * . - an nw-by-nw work array V in the lower
501 * . left-hand-corner,
502 * . - an NW-by-at-least-NW-but-more-is-better
503 * . (NW-by-NHO) horizontal work array along
504 * . the bottom edge,
505 * . - an at-least-NW-but-more-is-better (NHV-by-NW)
506 * . vertical work array along the left-hand-edge.
507 * . ====
508 *
509  kv = n - nw + 1
510  kt = nw + 1
511  nho = ( n-nw-1 ) - kt + 1
512  kwv = nw + 2
513  nve = ( n-nw ) - kwv + 1
514 *
515 * ==== Aggressive early deflation ====
516 *
517  CALL zlaqr3( wantt, wantz, n, ktop, kbot, nw, h, ldh, iloz,
518  $ ihiz, z, ldz, ls, ld, w, h( kv, 1 ), ldh, nho,
519  $ h( kv, kt ), ldh, nve, h( kwv, 1 ), ldh, work,
520  $ lwork )
521 *
522 * ==== Adjust KBOT accounting for new deflations. ====
523 *
524  kbot = kbot - ld
525 *
526 * ==== KS points to the shifts. ====
527 *
528  ks = kbot - ls + 1
529 *
530 * ==== Skip an expensive QR sweep if there is a (partly
531 * . heuristic) reason to expect that many eigenvalues
532 * . will deflate without it. Here, the QR sweep is
533 * . skipped if many eigenvalues have just been deflated
534 * . or if the remaining active block is small.
535 *
536  IF( ( ld.EQ.0 ) .OR. ( ( 100*ld.LE.nw*nibble ) .AND. ( kbot-
537  $ ktop+1.GT.min( nmin, nwmax ) ) ) ) THEN
538 *
539 * ==== NS = nominal number of simultaneous shifts.
540 * . This may be lowered (slightly) if ZLAQR3
541 * . did not provide that many shifts. ====
542 *
543  ns = min( nsmax, nsr, max( 2, kbot-ktop ) )
544  ns = ns - mod( ns, 2 )
545 *
546 * ==== If there have been no deflations
547 * . in a multiple of KEXSH iterations,
548 * . then try exceptional shifts.
549 * . Otherwise use shifts provided by
550 * . ZLAQR3 above or from the eigenvalues
551 * . of a trailing principal submatrix. ====
552 *
553  IF( mod( ndfl, kexsh ).EQ.0 ) THEN
554  ks = kbot - ns + 1
555  DO 30 i = kbot, ks + 1, -2
556  w( i ) = h( i, i ) + wilk1*cabs1( h( i, i-1 ) )
557  w( i-1 ) = w( i )
558  30 CONTINUE
559  ELSE
560 *
561 * ==== Got NS/2 or fewer shifts? Use ZLAQR4 or
562 * . ZLAHQR on a trailing principal submatrix to
563 * . get more. (Since NS.LE.NSMAX.LE.(N+6)/9,
564 * . there is enough space below the subdiagonal
565 * . to fit an NS-by-NS scratch array.) ====
566 *
567  IF( kbot-ks+1.LE.ns / 2 ) THEN
568  ks = kbot - ns + 1
569  kt = n - ns + 1
570  CALL zlacpy( 'A', ns, ns, h( ks, ks ), ldh,
571  $ h( kt, 1 ), ldh )
572  IF( ns.GT.nmin ) THEN
573  CALL zlaqr4( .false., .false., ns, 1, ns,
574  $ h( kt, 1 ), ldh, w( ks ), 1, 1,
575  $ zdum, 1, work, lwork, inf )
576  ELSE
577  CALL zlahqr( .false., .false., ns, 1, ns,
578  $ h( kt, 1 ), ldh, w( ks ), 1, 1,
579  $ zdum, 1, inf )
580  END IF
581  ks = ks + inf
582 *
583 * ==== In case of a rare QR failure use
584 * . eigenvalues of the trailing 2-by-2
585 * . principal submatrix. Scale to avoid
586 * . overflows, underflows and subnormals.
587 * . (The scale factor S can not be zero,
588 * . because H(KBOT,KBOT-1) is nonzero.) ====
589 *
590  IF( ks.GE.kbot ) THEN
591  s = cabs1( h( kbot-1, kbot-1 ) ) +
592  $ cabs1( h( kbot, kbot-1 ) ) +
593  $ cabs1( h( kbot-1, kbot ) ) +
594  $ cabs1( h( kbot, kbot ) )
595  aa = h( kbot-1, kbot-1 ) / s
596  cc = h( kbot, kbot-1 ) / s
597  bb = h( kbot-1, kbot ) / s
598  dd = h( kbot, kbot ) / s
599  tr2 = ( aa+dd ) / two
600  det = ( aa-tr2 )*( dd-tr2 ) - bb*cc
601  rtdisc = sqrt( -det )
602  w( kbot-1 ) = ( tr2+rtdisc )*s
603  w( kbot ) = ( tr2-rtdisc )*s
604 *
605  ks = kbot - 1
606  END IF
607  END IF
608 *
609  IF( kbot-ks+1.GT.ns ) THEN
610 *
611 * ==== Sort the shifts (Helps a little) ====
612 *
613  sorted = .false.
614  DO 50 k = kbot, ks + 1, -1
615  IF( sorted )
616  $ GO TO 60
617  sorted = .true.
618  DO 40 i = ks, k - 1
619  IF( cabs1( w( i ) ).LT.cabs1( w( i+1 ) ) )
620  $ THEN
621  sorted = .false.
622  swap = w( i )
623  w( i ) = w( i+1 )
624  w( i+1 ) = swap
625  END IF
626  40 CONTINUE
627  50 CONTINUE
628  60 CONTINUE
629  END IF
630  END IF
631 *
632 * ==== If there are only two shifts, then use
633 * . only one. ====
634 *
635  IF( kbot-ks+1.EQ.2 ) THEN
636  IF( cabs1( w( kbot )-h( kbot, kbot ) ).LT.
637  $ cabs1( w( kbot-1 )-h( kbot, kbot ) ) ) THEN
638  w( kbot-1 ) = w( kbot )
639  ELSE
640  w( kbot ) = w( kbot-1 )
641  END IF
642  END IF
643 *
644 * ==== Use up to NS of the the smallest magnatiude
645 * . shifts. If there aren't NS shifts available,
646 * . then use them all, possibly dropping one to
647 * . make the number of shifts even. ====
648 *
649  ns = min( ns, kbot-ks+1 )
650  ns = ns - mod( ns, 2 )
651  ks = kbot - ns + 1
652 *
653 * ==== Small-bulge multi-shift QR sweep:
654 * . split workspace under the subdiagonal into
655 * . - a KDU-by-KDU work array U in the lower
656 * . left-hand-corner,
657 * . - a KDU-by-at-least-KDU-but-more-is-better
658 * . (KDU-by-NHo) horizontal work array WH along
659 * . the bottom edge,
660 * . - and an at-least-KDU-but-more-is-better-by-KDU
661 * . (NVE-by-KDU) vertical work WV arrow along
662 * . the left-hand-edge. ====
663 *
664  kdu = 3*ns - 3
665  ku = n - kdu + 1
666  kwh = kdu + 1
667  nho = ( n-kdu+1-4 ) - ( kdu+1 ) + 1
668  kwv = kdu + 4
669  nve = n - kdu - kwv + 1
670 *
671 * ==== Small-bulge multi-shift QR sweep ====
672 *
673  CALL zlaqr5( wantt, wantz, kacc22, n, ktop, kbot, ns,
674  $ w( ks ), h, ldh, iloz, ihiz, z, ldz, work,
675  $ 3, h( ku, 1 ), ldh, nve, h( kwv, 1 ), ldh,
676  $ nho, h( ku, kwh ), ldh )
677  END IF
678 *
679 * ==== Note progress (or the lack of it). ====
680 *
681  IF( ld.GT.0 ) THEN
682  ndfl = 1
683  ELSE
684  ndfl = ndfl + 1
685  END IF
686 *
687 * ==== End of main loop ====
688  70 CONTINUE
689 *
690 * ==== Iteration limit exceeded. Set INFO to show where
691 * . the problem occurred and exit. ====
692 *
693  info = kbot
694  80 CONTINUE
695  END IF
696 *
697 * ==== Return the optimal value of LWORK. ====
698 *
699  work( 1 ) = dcmplx( lwkopt, 0 )
700 *
701 * ==== End of ZLAQR0 ====
702 *
703  END
subroutine zlaqr5(WANTT, WANTZ, KACC22, N, KTOP, KBOT, NSHFTS, S, H, LDH, ILOZ, IHIZ, Z, LDZ, V, LDV, U, LDU, NV, WV, LDWV, NH, WH, LDWH)
ZLAQR5 performs a single small-bulge multi-shift QR sweep.
Definition: zlaqr5.f:251
subroutine zlaqr0(WANTT, WANTZ, N, ILO, IHI, H, LDH, W, ILOZ, IHIZ, Z, LDZ, WORK, LWORK, INFO)
ZLAQR0 computes the eigenvalues of a Hessenberg matrix, and optionally the matrices from the Schur de...
Definition: zlaqr0.f:243
subroutine zlaqr4(WANTT, WANTZ, N, ILO, IHI, H, LDH, W, ILOZ, IHIZ, Z, LDZ, WORK, LWORK, INFO)
ZLAQR4 computes the eigenvalues of a Hessenberg matrix, and optionally the matrices from the Schur de...
Definition: zlaqr4.f:249
subroutine zlaqr3(WANTT, WANTZ, N, KTOP, KBOT, NW, H, LDH, ILOZ, IHIZ, Z, LDZ, NS, ND, SH, V, LDV, NH, T, LDT, NV, WV, LDWV, WORK, LWORK)
ZLAQR3 performs the unitary similarity transformation of a Hessenberg matrix to detect and deflate fu...
Definition: zlaqr3.f:269
subroutine zlahqr(WANTT, WANTZ, N, ILO, IHI, H, LDH, W, ILOZ, IHIZ, Z, LDZ, INFO)
ZLAHQR computes the eigenvalues and Schur factorization of an upper Hessenberg matrix, using the double-shift/single-shift QR algorithm.
Definition: zlahqr.f:197
subroutine zlacpy(UPLO, M, N, A, LDA, B, LDB)
ZLACPY copies all or part of one two-dimensional array to another.
Definition: zlacpy.f:105