Debian Codegraph @

Modules/ThirdParty/VNL/src/vxl/v3p/netlib/lapack/double/dsptrf.f

raw
1 SUBROUTINE DSPTRF( UPLO, N, AP, IPIV, INFO )
2 *
3 * -- LAPACK routine (version 2.0) --
4 * Univ. of Tennessee, Univ. of California Berkeley, NAG Ltd.,
5 * Courant Institute, Argonne National Lab, and Rice University
6 * March 31, 1993
7 *
8 * .. Scalar Arguments ..
9 CHARACTER UPLO
10 INTEGER INFO, N
11 * ..
12 * .. Array Arguments ..
13 INTEGER IPIV( * )
14 DOUBLE PRECISION AP( * )
15 * ..
16 *
17 * Purpose
18 * =======
19 *
20 * DSPTRF computes the factorization of a real symmetric matrix A stored
21 * in packed format using the Bunch-Kaufman diagonal pivoting method:
22 *
23 * A = U*D*U**T or A = L*D*L**T
24 *
25 * where U (or L) is a product of permutation and unit upper (lower)
26 * triangular matrices, and D is symmetric and block diagonal with
27 * 1-by-1 and 2-by-2 diagonal blocks.
28 *
29 * Arguments
30 * =========
31 *
32 * UPLO (input) CHARACTER*1
33 * = 'U': Upper triangle of A is stored;
34 * = 'L': Lower triangle of A is stored.
35 *
36 * N (input) INTEGER
37 * The order of the matrix A. N >= 0.
38 *
39 * AP (input/output) DOUBLE PRECISION array, dimension (N*(N+1)/2)
40 * On entry, the upper or lower triangle of the symmetric matrix
41 * A, packed columnwise in a linear array. The j-th column of A
42 * is stored in the array AP as follows:
43 * if UPLO = 'U', AP(i + (j-1)*j/2) = A(i,j) for 1<=i<=j;
44 * if UPLO = 'L', AP(i + (j-1)*(2n-j)/2) = A(i,j) for j<=i<=n.
45 *
46 * On exit, the block diagonal matrix D and the multipliers used
47 * to obtain the factor U or L, stored as a packed triangular
48 * matrix overwriting A (see below for further details).
49 *
50 * IPIV (output) INTEGER array, dimension (N)
51 * Details of the interchanges and the block structure of D.
52 * If IPIV(k) > 0, then rows and columns k and IPIV(k) were
53 * interchanged and D(k,k) is a 1-by-1 diagonal block.
54 * If UPLO = 'U' and IPIV(k) = IPIV(k-1) < 0, then rows and
55 * columns k-1 and -IPIV(k) were interchanged and D(k-1:k,k-1:k)
56 * is a 2-by-2 diagonal block. If UPLO = 'L' and IPIV(k) =
57 * IPIV(k+1) < 0, then rows and columns k+1 and -IPIV(k) were
58 * interchanged and D(k:k+1,k:k+1) is a 2-by-2 diagonal block.
59 *
60 * INFO (output) INTEGER
61 * = 0: successful exit
62 * < 0: if INFO = -i, the i-th argument had an illegal value
63 * > 0: if INFO = i, D(i,i) is exactly zero. The factorization
64 * has been completed, but the block diagonal matrix D is
65 * exactly singular, and division by zero will occur if it
66 * is used to solve a system of equations.
67 *
68 * Further Details
69 * ===============
70 *
71 * If UPLO = 'U', then A = U*D*U', where
72 * U = P(n)*U(n)* ... *P(k)U(k)* ...,
73 * i.e., U is a product of terms P(k)*U(k), where k decreases from n to
74 * 1 in steps of 1 or 2, and D is a block diagonal matrix with 1-by-1
75 * and 2-by-2 diagonal blocks D(k). P(k) is a permutation matrix as
76 * defined by IPIV(k), and U(k) is a unit upper triangular matrix, such
77 * that if the diagonal block D(k) is of order s (s = 1 or 2), then
78 *
79 * ( I v 0 ) k-s
80 * U(k) = ( 0 I 0 ) s
81 * ( 0 0 I ) n-k
82 * k-s s n-k
83 *
84 * If s = 1, D(k) overwrites A(k,k), and v overwrites A(1:k-1,k).
85 * If s = 2, the upper triangle of D(k) overwrites A(k-1,k-1), A(k-1,k),
86 * and A(k,k), and v overwrites A(1:k-2,k-1:k).
87 *
88 * If UPLO = 'L', then A = L*D*L', where
89 * L = P(1)*L(1)* ... *P(k)*L(k)* ...,
90 * i.e., L is a product of terms P(k)*L(k), where k increases from 1 to
91 * n in steps of 1 or 2, and D is a block diagonal matrix with 1-by-1
92 * and 2-by-2 diagonal blocks D(k). P(k) is a permutation matrix as
93 * defined by IPIV(k), and L(k) is a unit lower triangular matrix, such
94 * that if the diagonal block D(k) is of order s (s = 1 or 2), then
95 *
96 * ( I 0 0 ) k-1
97 * L(k) = ( 0 I 0 ) s
98 * ( 0 v I ) n-k-s+1
99 * k-1 s n-k-s+1
100 *
101 * If s = 1, D(k) overwrites A(k,k), and v overwrites A(k+1:n,k).
102 * If s = 2, the lower triangle of D(k) overwrites A(k,k), A(k+1,k),
103 * and A(k+1,k+1), and v overwrites A(k+2:n,k:k+1).
104 *
105 * =====================================================================
106 *
107 * .. Parameters ..
108 DOUBLE PRECISION ZERO, ONE
109 PARAMETER ( ZERO = 0.0D+0, ONE = 1.0D+0 )
110 DOUBLE PRECISION EIGHT, SEVTEN
111 PARAMETER ( EIGHT = 8.0D+0, SEVTEN = 17.0D+0 )
112 * ..
113 * .. Local Scalars ..
114 LOGICAL UPPER
115 INTEGER IMAX, J, JMAX, K, KC, KK, KNC, KP, KPC, KSTEP,
116 $ KX, NPP
117 DOUBLE PRECISION ABSAKK, ALPHA, C, COLMAX, R1, R2, ROWMAX, S, T
118 * ..
119 * .. External Functions ..
120 LOGICAL LSAME
121 INTEGER IDAMAX
122 EXTERNAL LSAME, IDAMAX
123 * ..
124 * .. External Subroutines ..
125 EXTERNAL DLAEV2, DROT, DSCAL, DSPR, DSWAP, XERBLA
126 * ..
127 * .. Intrinsic Functions ..
128 INTRINSIC ABS, MAX, SQRT
129 * ..
130 * .. Executable Statements ..
131 *
132 * Test the input parameters.
133 *
134 INFO = 0
135 UPPER = LSAME( UPLO, 'U' )
136 IF( .NOT.UPPER .AND. .NOT.LSAME( UPLO, 'L' ) ) THEN
137 INFO = -1
138 ELSE IF( N.LT.0 ) THEN
139 INFO = -2
140 END IF
141 IF( INFO.NE.0 ) THEN
142 CALL XERBLA( 'DSPTRF', -INFO )
143 RETURN
144 END IF
145 *
146 * Initialize ALPHA for use in choosing pivot block size.
147 *
148 ALPHA = ( ONE+SQRT( SEVTEN ) ) / EIGHT
149 *
150 IF( UPPER ) THEN
151 *
152 * Factorize A as U*D*U' using the upper triangle of A
153 *
154 * K is the main loop index, decreasing from N to 1 in steps of
155 * 1 or 2
156 *
157 K = N
158 KC = ( N-1 )*N / 2 + 1
159 10 CONTINUE
160 KNC = KC
161 *
162 * If K < 1, exit from loop
163 *
164 IF( K.LT.1 )
165 $ GO TO 70
166 KSTEP = 1
167 *
168 * Determine rows and columns to be interchanged and whether
169 * a 1-by-1 or 2-by-2 pivot block will be used
170 *
171 ABSAKK = ABS( AP( KC+K-1 ) )
172 *
173 * IMAX is the row-index of the largest off-diagonal element in
174 * column K, and COLMAX is its absolute value
175 *
176 IF( K.GT.1 ) THEN
177 IMAX = IDAMAX( K-1, AP( KC ), 1 )
178 COLMAX = ABS( AP( KC+IMAX-1 ) )
179 ELSE
180 COLMAX = ZERO
181 END IF
182 *
183 IF( MAX( ABSAKK, COLMAX ).EQ.ZERO ) THEN
184 *
185 * Column K is zero: set INFO and continue
186 *
187 IF( INFO.EQ.0 )
188 $ INFO = K
189 KP = K
190 ELSE
191 IF( ABSAKK.GE.ALPHA*COLMAX ) THEN
192 *
193 * no interchange, use 1-by-1 pivot block
194 *
195 KP = K
196 ELSE
197 *
198 * JMAX is the column-index of the largest off-diagonal
199 * element in row IMAX, and ROWMAX is its absolute value
200 *
201 ROWMAX = ZERO
202 JMAX = IMAX
203 KX = IMAX*( IMAX+1 ) / 2 + IMAX
204 DO 20 J = IMAX + 1, K
205 IF( ABS( AP( KX ) ).GT.ROWMAX ) THEN
206 ROWMAX = ABS( AP( KX ) )
207 JMAX = J
208 END IF
209 KX = KX + J
210 20 CONTINUE
211 KPC = ( IMAX-1 )*IMAX / 2 + 1
212 IF( IMAX.GT.1 ) THEN
213 JMAX = IDAMAX( IMAX-1, AP( KPC ), 1 )
214 ROWMAX = MAX( ROWMAX, ABS( AP( KPC+JMAX-1 ) ) )
215 END IF
216 *
217 IF( ABSAKK.GE.ALPHA*COLMAX*( COLMAX / ROWMAX ) ) THEN
218 *
219 * no interchange, use 1-by-1 pivot block
220 *
221 KP = K
222 ELSE IF( ABS( AP( KPC+IMAX-1 ) ).GE.ALPHA*ROWMAX ) THEN
223 *
224 * interchange rows and columns K and IMAX, use 1-by-1
225 * pivot block
226 *
227 KP = IMAX
228 ELSE
229 *
230 * interchange rows and columns K-1 and IMAX, use 2-by-2
231 * pivot block
232 *
233 KP = IMAX
234 KSTEP = 2
235 END IF
236 END IF
237 *
238 KK = K - KSTEP + 1
239 IF( KSTEP.EQ.2 )
240 $ KNC = KNC - K + 1
241 IF( KP.NE.KK ) THEN
242 *
243 * Interchange rows and columns KK and KP in the leading
244 * submatrix A(1:k,1:k)
245 *
246 CALL DSWAP( KP-1, AP( KNC ), 1, AP( KPC ), 1 )
247 KX = KPC + KP - 1
248 DO 30 J = KP + 1, KK - 1
249 KX = KX + J - 1
250 T = AP( KNC+J-1 )
251 AP( KNC+J-1 ) = AP( KX )
252 AP( KX ) = T
253 30 CONTINUE
254 T = AP( KNC+KK-1 )
255 AP( KNC+KK-1 ) = AP( KPC+KP-1 )
256 AP( KPC+KP-1 ) = T
257 IF( KSTEP.EQ.2 ) THEN
258 T = AP( KC+K-2 )
259 AP( KC+K-2 ) = AP( KC+KP-1 )
260 AP( KC+KP-1 ) = T
261 END IF
262 END IF
263 *
264 * Update the leading submatrix
265 *
266 IF( KSTEP.EQ.1 ) THEN
267 *
268 * 1-by-1 pivot block D(k): column k now holds
269 *
270 * W(k) = U(k)*D(k)
271 *
272 * where U(k) is the k-th column of U
273 *
274 * Perform a rank-1 update of A(1:k-1,1:k-1) as
275 *
276 * A := A - U(k)*D(k)*U(k)' = A - W(k)*1/D(k)*W(k)'
277 *
278 R1 = ONE / AP( KC+K-1 )
279 CALL DSPR( UPLO, K-1, -R1, AP( KC ), 1, AP )
280 *
281 * Store U(k) in column k
282 *
283 CALL DSCAL( K-1, R1, AP( KC ), 1 )
284 ELSE
285 *
286 * 2-by-2 pivot block D(k): columns k and k-1 now hold
287 *
288 * ( W(k-1) W(k) ) = ( U(k-1) U(k) )*D(k)
289 *
290 * where U(k) and U(k-1) are the k-th and (k-1)-th columns
291 * of U
292 *
293 * Perform a rank-2 update of A(1:k-2,1:k-2) as
294 *
295 * A := A - ( U(k-1) U(k) )*D(k)*( U(k-1) U(k) )'
296 * = A - ( W(k-1) W(k) )*inv(D(k))*( W(k-1) W(k) )'
297 *
298 * Convert this to two rank-1 updates by using the eigen-
299 * decomposition of D(k)
300 *
301 CALL DLAEV2( AP( KC-1 ), AP( KC+K-2 ), AP( KC+K-1 ), R1,
302 $ R2, C, S )
303 R1 = ONE / R1
304 R2 = ONE / R2
305 CALL DROT( K-2, AP( KNC ), 1, AP( KC ), 1, C, S )
306 CALL DSPR( UPLO, K-2, -R1, AP( KNC ), 1, AP )
307 CALL DSPR( UPLO, K-2, -R2, AP( KC ), 1, AP )
308 *
309 * Store U(k) and U(k-1) in columns k and k-1
310 *
311 CALL DSCAL( K-2, R1, AP( KNC ), 1 )
312 CALL DSCAL( K-2, R2, AP( KC ), 1 )
313 CALL DROT( K-2, AP( KNC ), 1, AP( KC ), 1, C, -S )
314 END IF
315 END IF
316 *
317 * Store details of the interchanges in IPIV
318 *
319 IF( KSTEP.EQ.1 ) THEN
320 IPIV( K ) = KP
321 ELSE
322 IPIV( K ) = -KP
323 IPIV( K-1 ) = -KP
324 END IF
325 *
326 * Decrease K and return to the start of the main loop
327 *
328 K = K - KSTEP
329 KC = KNC - K
330 GO TO 10
331 *
332 ELSE
333 *
334 * Factorize A as L*D*L' using the lower triangle of A
335 *
336 * K is the main loop index, increasing from 1 to N in steps of
337 * 1 or 2
338 *
339 K = 1
340 KC = 1
341 NPP = N*( N+1 ) / 2
342 40 CONTINUE
343 KNC = KC
344 *
345 * If K > N, exit from loop
346 *
347 IF( K.GT.N )
348 $ GO TO 70
349 KSTEP = 1
350 *
351 * Determine rows and columns to be interchanged and whether
352 * a 1-by-1 or 2-by-2 pivot block will be used
353 *
354 ABSAKK = ABS( AP( KC ) )
355 *
356 * IMAX is the row-index of the largest off-diagonal element in
357 * column K, and COLMAX is its absolute value
358 *
359 IF( K.LT.N ) THEN
360 IMAX = K + IDAMAX( N-K, AP( KC+1 ), 1 )
361 COLMAX = ABS( AP( KC+IMAX-K ) )
362 ELSE
363 COLMAX = ZERO
364 END IF
365 *
366 IF( MAX( ABSAKK, COLMAX ).EQ.ZERO ) THEN
367 *
368 * Column K is zero: set INFO and continue
369 *
370 IF( INFO.EQ.0 )
371 $ INFO = K
372 KP = K
373 ELSE
374 IF( ABSAKK.GE.ALPHA*COLMAX ) THEN
375 *
376 * no interchange, use 1-by-1 pivot block
377 *
378 KP = K
379 ELSE
380 *
381 * JMAX is the column-index of the largest off-diagonal
382 * element in row IMAX, and ROWMAX is its absolute value
383 *
384 ROWMAX = ZERO
385 KX = KC + IMAX - K
386 DO 50 J = K, IMAX - 1
387 IF( ABS( AP( KX ) ).GT.ROWMAX ) THEN
388 ROWMAX = ABS( AP( KX ) )
389 JMAX = J
390 END IF
391 KX = KX + N - J
392 50 CONTINUE
393 KPC = NPP - ( N-IMAX+1 )*( N-IMAX+2 ) / 2 + 1
394 IF( IMAX.LT.N ) THEN
395 JMAX = IMAX + IDAMAX( N-IMAX, AP( KPC+1 ), 1 )
396 ROWMAX = MAX( ROWMAX, ABS( AP( KPC+JMAX-IMAX ) ) )
397 END IF
398 *
399 IF( ABSAKK.GE.ALPHA*COLMAX*( COLMAX / ROWMAX ) ) THEN
400 *
401 * no interchange, use 1-by-1 pivot block
402 *
403 KP = K
404 ELSE IF( ABS( AP( KPC ) ).GE.ALPHA*ROWMAX ) THEN
405 *
406 * interchange rows and columns K and IMAX, use 1-by-1
407 * pivot block
408 *
409 KP = IMAX
410 ELSE
411 *
412 * interchange rows and columns K+1 and IMAX, use 2-by-2
413 * pivot block
414 *
415 KP = IMAX
416 KSTEP = 2
417 END IF
418 END IF
419 *
420 KK = K + KSTEP - 1
421 IF( KSTEP.EQ.2 )
422 $ KNC = KNC + N - K + 1
423 IF( KP.NE.KK ) THEN
424 *
425 * Interchange rows and columns KK and KP in the trailing
426 * submatrix A(k:n,k:n)
427 *
428 IF( KP.LT.N )
429 $ CALL DSWAP( N-KP, AP( KNC+KP-KK+1 ), 1, AP( KPC+1 ),
430 $ 1 )
431 KX = KNC + KP - KK
432 DO 60 J = KK + 1, KP - 1
433 KX = KX + N - J + 1
434 T = AP( KNC+J-KK )
435 AP( KNC+J-KK ) = AP( KX )
436 AP( KX ) = T
437 60 CONTINUE
438 T = AP( KNC )
439 AP( KNC ) = AP( KPC )
440 AP( KPC ) = T
441 IF( KSTEP.EQ.2 ) THEN
442 T = AP( KC+1 )
443 AP( KC+1 ) = AP( KC+KP-K )
444 AP( KC+KP-K ) = T
445 END IF
446 END IF
447 *
448 * Update the trailing submatrix
449 *
450 IF( KSTEP.EQ.1 ) THEN
451 *
452 * 1-by-1 pivot block D(k): column k now holds
453 *
454 * W(k) = L(k)*D(k)
455 *
456 * where L(k) is the k-th column of L
457 *
458 IF( K.LT.N ) THEN
459 *
460 * Perform a rank-1 update of A(k+1:n,k+1:n) as
461 *
462 * A := A - L(k)*D(k)*L(k)' = A - W(k)*(1/D(k))*W(k)'
463 *
464 R1 = ONE / AP( KC )
465 CALL DSPR( UPLO, N-K, -R1, AP( KC+1 ), 1,
466 $ AP( KC+N-K+1 ) )
467 *
468 * Store L(k) in column K
469 *
470 CALL DSCAL( N-K, R1, AP( KC+1 ), 1 )
471 END IF
472 ELSE
473 *
474 * 2-by-2 pivot block D(k): columns K and K+1 now hold
475 *
476 * ( W(k) W(k+1) ) = ( L(k) L(k+1) )*D(k)
477 *
478 * where L(k) and L(k+1) are the k-th and (k+1)-th columns
479 * of L
480 *
481 IF( K.LT.N-1 ) THEN
482 *
483 * Perform a rank-2 update of A(k+2:n,k+2:n) as
484 *
485 * A := A - ( L(k) L(k+1) )*D(k)*( L(k) L(k+1) )'
486 * = A - ( W(k) W(k+1) )*inv(D(k))*( W(k) W(k+1) )'
487 *
488 * Convert this to two rank-1 updates by using the eigen-
489 * decomposition of D(k)
490 *
491 CALL DLAEV2( AP( KC ), AP( KC+1 ), AP( KNC ), R1, R2,
492 $ C, S )
493 R1 = ONE / R1
494 R2 = ONE / R2
495 CALL DROT( N-K-1, AP( KC+2 ), 1, AP( KNC+1 ), 1, C,
496 $ S )
497 CALL DSPR( UPLO, N-K-1, -R1, AP( KC+2 ), 1,
498 $ AP( KNC+N-K ) )
499 CALL DSPR( UPLO, N-K-1, -R2, AP( KNC+1 ), 1,
500 $ AP( KNC+N-K ) )
501 *
502 * Store L(k) and L(k+1) in columns k and k+1
503 *
504 CALL DSCAL( N-K-1, R1, AP( KC+2 ), 1 )
505 CALL DSCAL( N-K-1, R2, AP( KNC+1 ), 1 )
506 CALL DROT( N-K-1, AP( KC+2 ), 1, AP( KNC+1 ), 1, C,
507 $ -S )
508 END IF
509 END IF
510 END IF
511 *
512 * Store details of the interchanges in IPIV
513 *
514 IF( KSTEP.EQ.1 ) THEN
515 IPIV( K ) = KP
516 ELSE
517 IPIV( K ) = -KP
518 IPIV( K+1 ) = -KP
519 END IF
520 *
521 * Increase K and return to the start of the main loop
522 *
523 K = K + KSTEP
524 KC = KNC + N - K + 2
525 GO TO 40
526 *
527 END IF
528 *
529 70 CONTINUE
530 RETURN
531 *
532 * End of DSPTRF
533 *
534 END