| 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 |