1: *> \brief \b ZLAQR3 performs the unitary similarity transformation of a Hessenberg matrix to detect and deflate fully converged eigenvalues from a trailing principal submatrix (aggressive early deflation).
2: *
3: * =========== DOCUMENTATION ===========
4: *
5: * Online html documentation available at
6: * http://www.netlib.org/lapack/explore-html/
7: *
8: *> \htmlonly
9: *> Download ZLAQR3 + dependencies
10: *> <a href="http://www.netlib.org/cgi-bin/netlibfiles.tgz?format=tgz&filename=/lapack/lapack_routine/zlaqr3.f">
11: *> [TGZ]</a>
12: *> <a href="http://www.netlib.org/cgi-bin/netlibfiles.zip?format=zip&filename=/lapack/lapack_routine/zlaqr3.f">
13: *> [ZIP]</a>
14: *> <a href="http://www.netlib.org/cgi-bin/netlibfiles.txt?format=txt&filename=/lapack/lapack_routine/zlaqr3.f">
15: *> [TXT]</a>
16: *> \endhtmlonly
17: *
18: * Definition:
19: * ===========
20: *
21: * SUBROUTINE ZLAQR3( WANTT, WANTZ, N, KTOP, KBOT, NW, H, LDH, ILOZ,
22: * IHIZ, Z, LDZ, NS, ND, SH, V, LDV, NH, T, LDT,
23: * NV, WV, LDWV, WORK, LWORK )
24: *
25: * .. Scalar Arguments ..
26: * INTEGER IHIZ, ILOZ, KBOT, KTOP, LDH, LDT, LDV, LDWV,
27: * $ LDZ, LWORK, N, ND, NH, NS, NV, NW
28: * LOGICAL WANTT, WANTZ
29: * ..
30: * .. Array Arguments ..
31: * COMPLEX*16 H( LDH, * ), SH( * ), T( LDT, * ), V( LDV, * ),
32: * $ WORK( * ), WV( LDWV, * ), Z( LDZ, * )
33: * ..
34: *
35: *
36: *> \par Purpose:
37: * =============
38: *>
39: *> \verbatim
40: *>
41: *> Aggressive early deflation:
42: *>
43: *> ZLAQR3 accepts as input an upper Hessenberg matrix
44: *> H and performs an unitary similarity transformation
45: *> designed to detect and deflate fully converged eigenvalues from
46: *> a trailing principal submatrix. On output H has been over-
47: *> written by a new Hessenberg matrix that is a perturbation of
48: *> an unitary similarity transformation of H. It is to be
49: *> hoped that the final version of H has many zero subdiagonal
50: *> entries.
51: *>
52: *> \endverbatim
53: *
54: * Arguments:
55: * ==========
56: *
57: *> \param[in] WANTT
58: *> \verbatim
59: *> WANTT is LOGICAL
60: *> If .TRUE., then the Hessenberg matrix H is fully updated
61: *> so that the triangular Schur factor may be
62: *> computed (in cooperation with the calling subroutine).
63: *> If .FALSE., then only enough of H is updated to preserve
64: *> the eigenvalues.
65: *> \endverbatim
66: *>
67: *> \param[in] WANTZ
68: *> \verbatim
69: *> WANTZ is LOGICAL
70: *> If .TRUE., then the unitary matrix Z is updated so
71: *> so that the unitary Schur factor may be computed
72: *> (in cooperation with the calling subroutine).
73: *> If .FALSE., then Z is not referenced.
74: *> \endverbatim
75: *>
76: *> \param[in] N
77: *> \verbatim
78: *> N is INTEGER
79: *> The order of the matrix H and (if WANTZ is .TRUE.) the
80: *> order of the unitary matrix Z.
81: *> \endverbatim
82: *>
83: *> \param[in] KTOP
84: *> \verbatim
85: *> KTOP is INTEGER
86: *> It is assumed that either KTOP = 1 or H(KTOP,KTOP-1)=0.
87: *> KBOT and KTOP together determine an isolated block
88: *> along the diagonal of the Hessenberg matrix.
89: *> \endverbatim
90: *>
91: *> \param[in] KBOT
92: *> \verbatim
93: *> KBOT is INTEGER
94: *> It is assumed without a check that either
95: *> KBOT = N or H(KBOT+1,KBOT)=0. KBOT and KTOP together
96: *> determine an isolated block along the diagonal of the
97: *> Hessenberg matrix.
98: *> \endverbatim
99: *>
100: *> \param[in] NW
101: *> \verbatim
102: *> NW is INTEGER
103: *> Deflation window size. 1 <= NW <= (KBOT-KTOP+1).
104: *> \endverbatim
105: *>
106: *> \param[in,out] H
107: *> \verbatim
108: *> H is COMPLEX*16 array, dimension (LDH,N)
109: *> On input the initial N-by-N section of H stores the
110: *> Hessenberg matrix undergoing aggressive early deflation.
111: *> On output H has been transformed by a unitary
112: *> similarity transformation, perturbed, and the returned
113: *> to Hessenberg form that (it is to be hoped) has some
114: *> zero subdiagonal entries.
115: *> \endverbatim
116: *>
117: *> \param[in] LDH
118: *> \verbatim
119: *> LDH is INTEGER
120: *> Leading dimension of H just as declared in the calling
121: *> subroutine. N <= LDH
122: *> \endverbatim
123: *>
124: *> \param[in] ILOZ
125: *> \verbatim
126: *> ILOZ is INTEGER
127: *> \endverbatim
128: *>
129: *> \param[in] IHIZ
130: *> \verbatim
131: *> IHIZ is INTEGER
132: *> Specify the rows of Z to which transformations must be
133: *> applied if WANTZ is .TRUE.. 1 <= ILOZ <= IHIZ <= N.
134: *> \endverbatim
135: *>
136: *> \param[in,out] Z
137: *> \verbatim
138: *> Z is COMPLEX*16 array, dimension (LDZ,N)
139: *> IF WANTZ is .TRUE., then on output, the unitary
140: *> similarity transformation mentioned above has been
141: *> accumulated into Z(ILOZ:IHIZ,ILOZ:IHIZ) from the right.
142: *> If WANTZ is .FALSE., then Z is unreferenced.
143: *> \endverbatim
144: *>
145: *> \param[in] LDZ
146: *> \verbatim
147: *> LDZ is INTEGER
148: *> The leading dimension of Z just as declared in the
149: *> calling subroutine. 1 <= LDZ.
150: *> \endverbatim
151: *>
152: *> \param[out] NS
153: *> \verbatim
154: *> NS is INTEGER
155: *> The number of unconverged (ie approximate) eigenvalues
156: *> returned in SR and SI that may be used as shifts by the
157: *> calling subroutine.
158: *> \endverbatim
159: *>
160: *> \param[out] ND
161: *> \verbatim
162: *> ND is INTEGER
163: *> The number of converged eigenvalues uncovered by this
164: *> subroutine.
165: *> \endverbatim
166: *>
167: *> \param[out] SH
168: *> \verbatim
169: *> SH is COMPLEX*16 array, dimension (KBOT)
170: *> On output, approximate eigenvalues that may
171: *> be used for shifts are stored in SH(KBOT-ND-NS+1)
172: *> through SR(KBOT-ND). Converged eigenvalues are
173: *> stored in SH(KBOT-ND+1) through SH(KBOT).
174: *> \endverbatim
175: *>
176: *> \param[out] V
177: *> \verbatim
178: *> V is COMPLEX*16 array, dimension (LDV,NW)
179: *> An NW-by-NW work array.
180: *> \endverbatim
181: *>
182: *> \param[in] LDV
183: *> \verbatim
184: *> LDV is INTEGER
185: *> The leading dimension of V just as declared in the
186: *> calling subroutine. NW <= LDV
187: *> \endverbatim
188: *>
189: *> \param[in] NH
190: *> \verbatim
191: *> NH is INTEGER
192: *> The number of columns of T. NH >= NW.
193: *> \endverbatim
194: *>
195: *> \param[out] T
196: *> \verbatim
197: *> T is COMPLEX*16 array, dimension (LDT,NW)
198: *> \endverbatim
199: *>
200: *> \param[in] LDT
201: *> \verbatim
202: *> LDT is INTEGER
203: *> The leading dimension of T just as declared in the
204: *> calling subroutine. NW <= LDT
205: *> \endverbatim
206: *>
207: *> \param[in] NV
208: *> \verbatim
209: *> NV is INTEGER
210: *> The number of rows of work array WV available for
211: *> workspace. NV >= NW.
212: *> \endverbatim
213: *>
214: *> \param[out] WV
215: *> \verbatim
216: *> WV is COMPLEX*16 array, dimension (LDWV,NW)
217: *> \endverbatim
218: *>
219: *> \param[in] LDWV
220: *> \verbatim
221: *> LDWV is INTEGER
222: *> The leading dimension of W just as declared in the
223: *> calling subroutine. NW <= LDV
224: *> \endverbatim
225: *>
226: *> \param[out] WORK
227: *> \verbatim
228: *> WORK is COMPLEX*16 array, dimension (LWORK)
229: *> On exit, WORK(1) is set to an estimate of the optimal value
230: *> of LWORK for the given values of N, NW, KTOP and KBOT.
231: *> \endverbatim
232: *>
233: *> \param[in] LWORK
234: *> \verbatim
235: *> LWORK is INTEGER
236: *> The dimension of the work array WORK. LWORK = 2*NW
237: *> suffices, but greater efficiency may result from larger
238: *> values of LWORK.
239: *>
240: *> If LWORK = -1, then a workspace query is assumed; ZLAQR3
241: *> only estimates the optimal workspace size for the given
242: *> values of N, NW, KTOP and KBOT. The estimate is returned
243: *> in WORK(1). No error message related to LWORK is issued
244: *> by XERBLA. Neither H nor Z are accessed.
245: *> \endverbatim
246: *
247: * Authors:
248: * ========
249: *
250: *> \author Univ. of Tennessee
251: *> \author Univ. of California Berkeley
252: *> \author Univ. of Colorado Denver
253: *> \author NAG Ltd.
254: *
255: *> \ingroup complex16OTHERauxiliary
256: *
257: *> \par Contributors:
258: * ==================
259: *>
260: *> Karen Braman and Ralph Byers, Department of Mathematics,
261: *> University of Kansas, USA
262: *>
263: * =====================================================================
264: SUBROUTINE ZLAQR3( WANTT, WANTZ, N, KTOP, KBOT, NW, H, LDH, ILOZ,
265: $ IHIZ, Z, LDZ, NS, ND, SH, V, LDV, NH, T, LDT,
266: $ NV, WV, LDWV, WORK, LWORK )
267: *
268: * -- LAPACK auxiliary routine --
269: * -- LAPACK is a software package provided by Univ. of Tennessee, --
270: * -- Univ. of California Berkeley, Univ. of Colorado Denver and NAG Ltd..--
271: *
272: * .. Scalar Arguments ..
273: INTEGER IHIZ, ILOZ, KBOT, KTOP, LDH, LDT, LDV, LDWV,
274: $ LDZ, LWORK, N, ND, NH, NS, NV, NW
275: LOGICAL WANTT, WANTZ
276: * ..
277: * .. Array Arguments ..
278: COMPLEX*16 H( LDH, * ), SH( * ), T( LDT, * ), V( LDV, * ),
279: $ WORK( * ), WV( LDWV, * ), Z( LDZ, * )
280: * ..
281: *
282: * ================================================================
283: *
284: * .. Parameters ..
285: COMPLEX*16 ZERO, ONE
286: PARAMETER ( ZERO = ( 0.0d0, 0.0d0 ),
287: $ ONE = ( 1.0d0, 0.0d0 ) )
288: DOUBLE PRECISION RZERO, RONE
289: PARAMETER ( RZERO = 0.0d0, RONE = 1.0d0 )
290: * ..
291: * .. Local Scalars ..
292: COMPLEX*16 BETA, CDUM, S, TAU
293: DOUBLE PRECISION FOO, SAFMAX, SAFMIN, SMLNUM, ULP
294: INTEGER I, IFST, ILST, INFO, INFQR, J, JW, KCOL, KLN,
295: $ KNT, KROW, KWTOP, LTOP, LWK1, LWK2, LWK3,
296: $ LWKOPT, NMIN
297: * ..
298: * .. External Functions ..
299: DOUBLE PRECISION DLAMCH
300: INTEGER ILAENV
301: EXTERNAL DLAMCH, ILAENV
302: * ..
303: * .. External Subroutines ..
304: EXTERNAL DLABAD, ZCOPY, ZGEHRD, ZGEMM, ZLACPY, ZLAHQR,
305: $ ZLAQR4, ZLARF, ZLARFG, ZLASET, ZTREXC, ZUNMHR
306: * ..
307: * .. Intrinsic Functions ..
308: INTRINSIC ABS, DBLE, DCMPLX, DCONJG, DIMAG, INT, MAX, MIN
309: * ..
310: * .. Statement Functions ..
311: DOUBLE PRECISION CABS1
312: * ..
313: * .. Statement Function definitions ..
314: CABS1( CDUM ) = ABS( DBLE( CDUM ) ) + ABS( DIMAG( CDUM ) )
315: * ..
316: * .. Executable Statements ..
317: *
318: * ==== Estimate optimal workspace. ====
319: *
320: JW = MIN( NW, KBOT-KTOP+1 )
321: IF( JW.LE.2 ) THEN
322: LWKOPT = 1
323: ELSE
324: *
325: * ==== Workspace query call to ZGEHRD ====
326: *
327: CALL ZGEHRD( JW, 1, JW-1, T, LDT, WORK, WORK, -1, INFO )
328: LWK1 = INT( WORK( 1 ) )
329: *
330: * ==== Workspace query call to ZUNMHR ====
331: *
332: CALL ZUNMHR( 'R', 'N', JW, JW, 1, JW-1, T, LDT, WORK, V, LDV,
333: $ WORK, -1, INFO )
334: LWK2 = INT( WORK( 1 ) )
335: *
336: * ==== Workspace query call to ZLAQR4 ====
337: *
338: CALL ZLAQR4( .true., .true., JW, 1, JW, T, LDT, SH, 1, JW, V,
339: $ LDV, WORK, -1, INFQR )
340: LWK3 = INT( WORK( 1 ) )
341: *
342: * ==== Optimal workspace ====
343: *
344: LWKOPT = MAX( JW+MAX( LWK1, LWK2 ), LWK3 )
345: END IF
346: *
347: * ==== Quick return in case of workspace query. ====
348: *
349: IF( LWORK.EQ.-1 ) THEN
350: WORK( 1 ) = DCMPLX( LWKOPT, 0 )
351: RETURN
352: END IF
353: *
354: * ==== Nothing to do ...
355: * ... for an empty active block ... ====
356: NS = 0
357: ND = 0
358: WORK( 1 ) = ONE
359: IF( KTOP.GT.KBOT )
360: $ RETURN
361: * ... nor for an empty deflation window. ====
362: IF( NW.LT.1 )
363: $ RETURN
364: *
365: * ==== Machine constants ====
366: *
367: SAFMIN = DLAMCH( 'SAFE MINIMUM' )
368: SAFMAX = RONE / SAFMIN
369: CALL DLABAD( SAFMIN, SAFMAX )
370: ULP = DLAMCH( 'PRECISION' )
371: SMLNUM = SAFMIN*( DBLE( N ) / ULP )
372: *
373: * ==== Setup deflation window ====
374: *
375: JW = MIN( NW, KBOT-KTOP+1 )
376: KWTOP = KBOT - JW + 1
377: IF( KWTOP.EQ.KTOP ) THEN
378: S = ZERO
379: ELSE
380: S = H( KWTOP, KWTOP-1 )
381: END IF
382: *
383: IF( KBOT.EQ.KWTOP ) THEN
384: *
385: * ==== 1-by-1 deflation window: not much to do ====
386: *
387: SH( KWTOP ) = H( KWTOP, KWTOP )
388: NS = 1
389: ND = 0
390: IF( CABS1( S ).LE.MAX( SMLNUM, ULP*CABS1( H( KWTOP,
391: $ KWTOP ) ) ) ) THEN
392: NS = 0
393: ND = 1
394: IF( KWTOP.GT.KTOP )
395: $ H( KWTOP, KWTOP-1 ) = ZERO
396: END IF
397: WORK( 1 ) = ONE
398: RETURN
399: END IF
400: *
401: * ==== Convert to spike-triangular form. (In case of a
402: * . rare QR failure, this routine continues to do
403: * . aggressive early deflation using that part of
404: * . the deflation window that converged using INFQR
405: * . here and there to keep track.) ====
406: *
407: CALL ZLACPY( 'U', JW, JW, H( KWTOP, KWTOP ), LDH, T, LDT )
408: CALL ZCOPY( JW-1, H( KWTOP+1, KWTOP ), LDH+1, T( 2, 1 ), LDT+1 )
409: *
410: CALL ZLASET( 'A', JW, JW, ZERO, ONE, V, LDV )
411: NMIN = ILAENV( 12, 'ZLAQR3', 'SV', JW, 1, JW, LWORK )
412: IF( JW.GT.NMIN ) THEN
413: CALL ZLAQR4( .true., .true., JW, 1, JW, T, LDT, SH( KWTOP ), 1,
414: $ JW, V, LDV, WORK, LWORK, INFQR )
415: ELSE
416: CALL ZLAHQR( .true., .true., JW, 1, JW, T, LDT, SH( KWTOP ), 1,
417: $ JW, V, LDV, INFQR )
418: END IF
419: *
420: * ==== Deflation detection loop ====
421: *
422: NS = JW
423: ILST = INFQR + 1
424: DO 10 KNT = INFQR + 1, JW
425: *
426: * ==== Small spike tip deflation test ====
427: *
428: FOO = CABS1( T( NS, NS ) )
429: IF( FOO.EQ.RZERO )
430: $ FOO = CABS1( S )
431: IF( CABS1( S )*CABS1( V( 1, NS ) ).LE.MAX( SMLNUM, ULP*FOO ) )
432: $ THEN
433: *
434: * ==== One more converged eigenvalue ====
435: *
436: NS = NS - 1
437: ELSE
438: *
439: * ==== One undeflatable eigenvalue. Move it up out of the
440: * . way. (ZTREXC can not fail in this case.) ====
441: *
442: IFST = NS
443: CALL ZTREXC( 'V', JW, T, LDT, V, LDV, IFST, ILST, INFO )
444: ILST = ILST + 1
445: END IF
446: 10 CONTINUE
447: *
448: * ==== Return to Hessenberg form ====
449: *
450: IF( NS.EQ.0 )
451: $ S = ZERO
452: *
453: IF( NS.LT.JW ) THEN
454: *
455: * ==== sorting the diagonal of T improves accuracy for
456: * . graded matrices. ====
457: *
458: DO 30 I = INFQR + 1, NS
459: IFST = I
460: DO 20 J = I + 1, NS
461: IF( CABS1( T( J, J ) ).GT.CABS1( T( IFST, IFST ) ) )
462: $ IFST = J
463: 20 CONTINUE
464: ILST = I
465: IF( IFST.NE.ILST )
466: $ CALL ZTREXC( 'V', JW, T, LDT, V, LDV, IFST, ILST, INFO )
467: 30 CONTINUE
468: END IF
469: *
470: * ==== Restore shift/eigenvalue array from T ====
471: *
472: DO 40 I = INFQR + 1, JW
473: SH( KWTOP+I-1 ) = T( I, I )
474: 40 CONTINUE
475: *
476: *
477: IF( NS.LT.JW .OR. S.EQ.ZERO ) THEN
478: IF( NS.GT.1 .AND. S.NE.ZERO ) THEN
479: *
480: * ==== Reflect spike back into lower triangle ====
481: *
482: CALL ZCOPY( NS, V, LDV, WORK, 1 )
483: DO 50 I = 1, NS
484: WORK( I ) = DCONJG( WORK( I ) )
485: 50 CONTINUE
486: BETA = WORK( 1 )
487: CALL ZLARFG( NS, BETA, WORK( 2 ), 1, TAU )
488: WORK( 1 ) = ONE
489: *
490: CALL ZLASET( 'L', JW-2, JW-2, ZERO, ZERO, T( 3, 1 ), LDT )
491: *
492: CALL ZLARF( 'L', NS, JW, WORK, 1, DCONJG( TAU ), T, LDT,
493: $ WORK( JW+1 ) )
494: CALL ZLARF( 'R', NS, NS, WORK, 1, TAU, T, LDT,
495: $ WORK( JW+1 ) )
496: CALL ZLARF( 'R', JW, NS, WORK, 1, TAU, V, LDV,
497: $ WORK( JW+1 ) )
498: *
499: CALL ZGEHRD( JW, 1, NS, T, LDT, WORK, WORK( JW+1 ),
500: $ LWORK-JW, INFO )
501: END IF
502: *
503: * ==== Copy updated reduced window into place ====
504: *
505: IF( KWTOP.GT.1 )
506: $ H( KWTOP, KWTOP-1 ) = S*DCONJG( V( 1, 1 ) )
507: CALL ZLACPY( 'U', JW, JW, T, LDT, H( KWTOP, KWTOP ), LDH )
508: CALL ZCOPY( JW-1, T( 2, 1 ), LDT+1, H( KWTOP+1, KWTOP ),
509: $ LDH+1 )
510: *
511: * ==== Accumulate orthogonal matrix in order update
512: * . H and Z, if requested. ====
513: *
514: IF( NS.GT.1 .AND. S.NE.ZERO )
515: $ CALL ZUNMHR( 'R', 'N', JW, NS, 1, NS, T, LDT, WORK, V, LDV,
516: $ WORK( JW+1 ), LWORK-JW, INFO )
517: *
518: * ==== Update vertical slab in H ====
519: *
520: IF( WANTT ) THEN
521: LTOP = 1
522: ELSE
523: LTOP = KTOP
524: END IF
525: DO 60 KROW = LTOP, KWTOP - 1, NV
526: KLN = MIN( NV, KWTOP-KROW )
527: CALL ZGEMM( 'N', 'N', KLN, JW, JW, ONE, H( KROW, KWTOP ),
528: $ LDH, V, LDV, ZERO, WV, LDWV )
529: CALL ZLACPY( 'A', KLN, JW, WV, LDWV, H( KROW, KWTOP ), LDH )
530: 60 CONTINUE
531: *
532: * ==== Update horizontal slab in H ====
533: *
534: IF( WANTT ) THEN
535: DO 70 KCOL = KBOT + 1, N, NH
536: KLN = MIN( NH, N-KCOL+1 )
537: CALL ZGEMM( 'C', 'N', JW, KLN, JW, ONE, V, LDV,
538: $ H( KWTOP, KCOL ), LDH, ZERO, T, LDT )
539: CALL ZLACPY( 'A', JW, KLN, T, LDT, H( KWTOP, KCOL ),
540: $ LDH )
541: 70 CONTINUE
542: END IF
543: *
544: * ==== Update vertical slab in Z ====
545: *
546: IF( WANTZ ) THEN
547: DO 80 KROW = ILOZ, IHIZ, NV
548: KLN = MIN( NV, IHIZ-KROW+1 )
549: CALL ZGEMM( 'N', 'N', KLN, JW, JW, ONE, Z( KROW, KWTOP ),
550: $ LDZ, V, LDV, ZERO, WV, LDWV )
551: CALL ZLACPY( 'A', KLN, JW, WV, LDWV, Z( KROW, KWTOP ),
552: $ LDZ )
553: 80 CONTINUE
554: END IF
555: END IF
556: *
557: * ==== Return the number of deflations ... ====
558: *
559: ND = JW - NS
560: *
561: * ==== ... and the number of shifts. (Subtracting
562: * . INFQR from the spike length takes care
563: * . of the case of a rare QR failure while
564: * . calculating eigenvalues of the deflation
565: * . window.) ====
566: *
567: NS = NS - INFQR
568: *
569: * ==== Return optimal workspace. ====
570: *
571: WORK( 1 ) = DCMPLX( LWKOPT, 0 )
572: *
573: * ==== End of ZLAQR3 ====
574: *
575: END
CVSweb interface <joel.bertrand@systella.fr>
![[BACK]](/cvsweb/icons/back.gif){kind=icon}
Return to zlaqr3.f CVS log ![[TXT]](/cvsweb/icons/text.gif){kind=icon}
![[DIR]](/cvsweb/icons/dir.gif){kind=icon}
Up to [local] / rpl / lapack / lapack