LAPACK  3.6.1
LAPACK: Linear Algebra PACKage
ssytf2.f
Go to the documentation of this file.
1 *> \brief \b SSYTF2 computes the factorization of a real symmetric indefinite matrix, using the diagonal pivoting method (unblocked algorithm).
2 *
3 * =========== DOCUMENTATION ===========
4 *
5 * Online html documentation available at
6 * http://www.netlib.org/lapack/explore-html/
7 *
8 *> \htmlonly
9 *> Download SSYTF2 + dependencies
10 *> <a href="http://www.netlib.org/cgi-bin/netlibfiles.tgz?format=tgz&filename=/lapack/lapack_routine/ssytf2.f">
11 *> [TGZ]</a>
12 *> <a href="http://www.netlib.org/cgi-bin/netlibfiles.zip?format=zip&filename=/lapack/lapack_routine/ssytf2.f">
13 *> [ZIP]</a>
14 *> <a href="http://www.netlib.org/cgi-bin/netlibfiles.txt?format=txt&filename=/lapack/lapack_routine/ssytf2.f">
15 *> [TXT]</a>
16 *> \endhtmlonly
17 *
18 * Definition:
19 * ===========
20 *
21 * SUBROUTINE SSYTF2( UPLO, N, A, LDA, IPIV, INFO )
22 *
23 * .. Scalar Arguments ..
24 * CHARACTER UPLO
25 * INTEGER INFO, LDA, N
26 * ..
27 * .. Array Arguments ..
28 * INTEGER IPIV( * )
29 * REAL A( LDA, * )
30 * ..
31 *
32 *
33 *> \par Purpose:
34 * =============
35 *>
36 *> \verbatim
37 *>
38 *> SSYTF2 computes the factorization of a real symmetric matrix A using
39 *> the Bunch-Kaufman diagonal pivoting method:
40 *>
41 *> A = U*D*U**T or A = L*D*L**T
42 *>
43 *> where U (or L) is a product of permutation and unit upper (lower)
44 *> triangular matrices, U**T is the transpose of U, and D is symmetric and
45 *> block diagonal with 1-by-1 and 2-by-2 diagonal blocks.
46 *>
47 *> This is the unblocked version of the algorithm, calling Level 2 BLAS.
48 *> \endverbatim
49 *
50 * Arguments:
51 * ==========
52 *
53 *> \param[in] UPLO
54 *> \verbatim
55 *> UPLO is CHARACTER*1
56 *> Specifies whether the upper or lower triangular part of the
57 *> symmetric matrix A is stored:
58 *> = 'U': Upper triangular
59 *> = 'L': Lower triangular
60 *> \endverbatim
61 *>
62 *> \param[in] N
63 *> \verbatim
64 *> N is INTEGER
65 *> The order of the matrix A. N >= 0.
66 *> \endverbatim
67 *>
68 *> \param[in,out] A
69 *> \verbatim
70 *> A is REAL array, dimension (LDA,N)
71 *> On entry, the symmetric matrix A. If UPLO = 'U', the leading
72 *> n-by-n upper triangular part of A contains the upper
73 *> triangular part of the matrix A, and the strictly lower
74 *> triangular part of A is not referenced. If UPLO = 'L', the
75 *> leading n-by-n lower triangular part of A contains the lower
76 *> triangular part of the matrix A, and the strictly upper
77 *> triangular part of A is not referenced.
78 *>
79 *> On exit, the block diagonal matrix D and the multipliers used
80 *> to obtain the factor U or L (see below for further details).
81 *> \endverbatim
82 *>
83 *> \param[in] LDA
84 *> \verbatim
85 *> LDA is INTEGER
86 *> The leading dimension of the array A. LDA >= max(1,N).
87 *> \endverbatim
88 *>
89 *> \param[out] IPIV
90 *> \verbatim
91 *> IPIV is INTEGER array, dimension (N)
92 *> Details of the interchanges and the block structure of D.
93 *>
94 *> If UPLO = 'U':
95 *> If IPIV(k) > 0, then rows and columns k and IPIV(k) were
96 *> interchanged and D(k,k) is a 1-by-1 diagonal block.
97 *>
98 *> If IPIV(k) = IPIV(k-1) < 0, then rows and columns
99 *> k-1 and -IPIV(k) were interchanged and D(k-1:k,k-1:k)
100 *> is a 2-by-2 diagonal block.
101 *>
102 *> If UPLO = 'L':
103 *> If IPIV(k) > 0, then rows and columns k and IPIV(k) were
104 *> interchanged and D(k,k) is a 1-by-1 diagonal block.
105 *>
106 *> If IPIV(k) = IPIV(k+1) < 0, then rows and columns
107 *> k+1 and -IPIV(k) were interchanged and D(k:k+1,k:k+1)
108 *> is a 2-by-2 diagonal block.
109 *> \endverbatim
110 *>
111 *> \param[out] INFO
112 *> \verbatim
113 *> INFO is INTEGER
114 *> = 0: successful exit
115 *> < 0: if INFO = -k, the k-th argument had an illegal value
116 *> > 0: if INFO = k, D(k,k) is exactly zero. The factorization
117 *> has been completed, but the block diagonal matrix D is
118 *> exactly singular, and division by zero will occur if it
119 *> is used to solve a system of equations.
120 *> \endverbatim
121 *
122 * Authors:
123 * ========
124 *
125 *> \author Univ. of Tennessee
126 *> \author Univ. of California Berkeley
127 *> \author Univ. of Colorado Denver
128 *> \author NAG Ltd.
129 *
130 *> \date November 2013
131 *
132 *> \ingroup realSYcomputational
133 *
134 *> \par Further Details:
135 * =====================
136 *>
137 *> \verbatim
138 *>
139 *> If UPLO = 'U', then A = U*D*U**T, where
140 *> U = P(n)*U(n)* ... *P(k)U(k)* ...,
141 *> i.e., U is a product of terms P(k)*U(k), where k decreases from n to
142 *> 1 in steps of 1 or 2, and D is a block diagonal matrix with 1-by-1
143 *> and 2-by-2 diagonal blocks D(k). P(k) is a permutation matrix as
144 *> defined by IPIV(k), and U(k) is a unit upper triangular matrix, such
145 *> that if the diagonal block D(k) is of order s (s = 1 or 2), then
146 *>
147 *> ( I v 0 ) k-s
148 *> U(k) = ( 0 I 0 ) s
149 *> ( 0 0 I ) n-k
150 *> k-s s n-k
151 *>
152 *> If s = 1, D(k) overwrites A(k,k), and v overwrites A(1:k-1,k).
153 *> If s = 2, the upper triangle of D(k) overwrites A(k-1,k-1), A(k-1,k),
154 *> and A(k,k), and v overwrites A(1:k-2,k-1:k).
155 *>
156 *> If UPLO = 'L', then A = L*D*L**T, where
157 *> L = P(1)*L(1)* ... *P(k)*L(k)* ...,
158 *> i.e., L is a product of terms P(k)*L(k), where k increases from 1 to
159 *> n in steps of 1 or 2, and D is a block diagonal matrix with 1-by-1
160 *> and 2-by-2 diagonal blocks D(k). P(k) is a permutation matrix as
161 *> defined by IPIV(k), and L(k) is a unit lower triangular matrix, such
162 *> that if the diagonal block D(k) is of order s (s = 1 or 2), then
163 *>
164 *> ( I 0 0 ) k-1
165 *> L(k) = ( 0 I 0 ) s
166 *> ( 0 v I ) n-k-s+1
167 *> k-1 s n-k-s+1
168 *>
169 *> If s = 1, D(k) overwrites A(k,k), and v overwrites A(k+1:n,k).
170 *> If s = 2, the lower triangle of D(k) overwrites A(k,k), A(k+1,k),
171 *> and A(k+1,k+1), and v overwrites A(k+2:n,k:k+1).
172 *> \endverbatim
173 *
174 *> \par Contributors:
175 * ==================
176 *>
177 *> \verbatim
178 *>
179 *> 09-29-06 - patch from
180 *> Bobby Cheng, MathWorks
181 *>
182 *> Replace l.204 and l.372
183 *> IF( MAX( ABSAKK, COLMAX ).EQ.ZERO ) THEN
184 *> by
185 *> IF( (MAX( ABSAKK, COLMAX ).EQ.ZERO) .OR. SISNAN(ABSAKK) ) THEN
186 *>
187 *> 01-01-96 - Based on modifications by
188 *> J. Lewis, Boeing Computer Services Company
189 *> A. Petitet, Computer Science Dept., Univ. of Tenn., Knoxville, USA
190 *> 1-96 - Based on modifications by J. Lewis, Boeing Computer Services
191 *> Company
192 *>
193 *> \endverbatim
194 *
195 * =====================================================================
196  SUBROUTINE ssytf2( UPLO, N, A, LDA, IPIV, INFO )
197 *
198 * -- LAPACK computational routine (version 3.5.0) --
199 * -- LAPACK is a software package provided by Univ. of Tennessee, --
200 * -- Univ. of California Berkeley, Univ. of Colorado Denver and NAG Ltd..--
201 * November 2013
202 *
203 * .. Scalar Arguments ..
204  CHARACTER UPLO
205  INTEGER INFO, LDA, N
206 * ..
207 * .. Array Arguments ..
208  INTEGER IPIV( * )
209  REAL A( lda, * )
210 * ..
211 *
212 * =====================================================================
213 *
214 * .. Parameters ..
215  REAL ZERO, ONE
216  parameter ( zero = 0.0e+0, one = 1.0e+0 )
217  REAL EIGHT, SEVTEN
218  parameter ( eight = 8.0e+0, sevten = 17.0e+0 )
219 * ..
220 * .. Local Scalars ..
221  LOGICAL UPPER
222  INTEGER I, IMAX, J, JMAX, K, KK, KP, KSTEP
223  REAL ABSAKK, ALPHA, COLMAX, D11, D12, D21, D22, R1,
224  $ rowmax, t, wk, wkm1, wkp1
225 * ..
226 * .. External Functions ..
227  LOGICAL LSAME, SISNAN
228  INTEGER ISAMAX
229  EXTERNAL lsame, isamax, sisnan
230 * ..
231 * .. External Subroutines ..
232  EXTERNAL sscal, sswap, ssyr, xerbla
233 * ..
234 * .. Intrinsic Functions ..
235  INTRINSIC abs, max, sqrt
236 * ..
237 * .. Executable Statements ..
238 *
239 * Test the input parameters.
240 *
241  info = 0
242  upper = lsame( uplo, 'U' )
243  IF( .NOT.upper .AND. .NOT.lsame( uplo, 'L' ) ) THEN
244  info = -1
245  ELSE IF( n.LT.0 ) THEN
246  info = -2
247  ELSE IF( lda.LT.max( 1, n ) ) THEN
248  info = -4
249  END IF
250  IF( info.NE.0 ) THEN
251  CALL xerbla( 'SSYTF2', -info )
252  RETURN
253  END IF
254 *
255 * Initialize ALPHA for use in choosing pivot block size.
256 *
257  alpha = ( one+sqrt( sevten ) ) / eight
258 *
259  IF( upper ) THEN
260 *
261 * Factorize A as U*D*U**T using the upper triangle of A
262 *
263 * K is the main loop index, decreasing from N to 1 in steps of
264 * 1 or 2
265 *
266  k = n
267  10 CONTINUE
268 *
269 * If K < 1, exit from loop
270 *
271  IF( k.LT.1 )
272  $ GO TO 70
273  kstep = 1
274 *
275 * Determine rows and columns to be interchanged and whether
276 * a 1-by-1 or 2-by-2 pivot block will be used
277 *
278  absakk = abs( a( k, k ) )
279 *
280 * IMAX is the row-index of the largest off-diagonal element in
281 * column K, and COLMAX is its absolute value.
282 * Determine both COLMAX and IMAX.
283 *
284  IF( k.GT.1 ) THEN
285  imax = isamax( k-1, a( 1, k ), 1 )
286  colmax = abs( a( imax, k ) )
287  ELSE
288  colmax = zero
289  END IF
290 *
291  IF( (max( absakk, colmax ).EQ.zero) .OR. sisnan(absakk) ) THEN
292 *
293 * Column K is zero or underflow, or contains a NaN:
294 * set INFO and continue
295 *
296  IF( info.EQ.0 )
297  $ info = k
298  kp = k
299  ELSE
300  IF( absakk.GE.alpha*colmax ) THEN
301 *
302 * no interchange, use 1-by-1 pivot block
303 *
304  kp = k
305  ELSE
306 *
307 * JMAX is the column-index of the largest off-diagonal
308 * element in row IMAX, and ROWMAX is its absolute value
309 *
310  jmax = imax + isamax( k-imax, a( imax, imax+1 ), lda )
311  rowmax = abs( a( imax, jmax ) )
312  IF( imax.GT.1 ) THEN
313  jmax = isamax( imax-1, a( 1, imax ), 1 )
314  rowmax = max( rowmax, abs( a( jmax, imax ) ) )
315  END IF
316 *
317  IF( absakk.GE.alpha*colmax*( colmax / rowmax ) ) THEN
318 *
319 * no interchange, use 1-by-1 pivot block
320 *
321  kp = k
322  ELSE IF( abs( a( imax, imax ) ).GE.alpha*rowmax ) THEN
323 *
324 * interchange rows and columns K and IMAX, use 1-by-1
325 * pivot block
326 *
327  kp = imax
328  ELSE
329 *
330 * interchange rows and columns K-1 and IMAX, use 2-by-2
331 * pivot block
332 *
333  kp = imax
334  kstep = 2
335  END IF
336  END IF
337 *
338  kk = k - kstep + 1
339  IF( kp.NE.kk ) THEN
340 *
341 * Interchange rows and columns KK and KP in the leading
342 * submatrix A(1:k,1:k)
343 *
344  CALL sswap( kp-1, a( 1, kk ), 1, a( 1, kp ), 1 )
345  CALL sswap( kk-kp-1, a( kp+1, kk ), 1, a( kp, kp+1 ),
346  $ lda )
347  t = a( kk, kk )
348  a( kk, kk ) = a( kp, kp )
349  a( kp, kp ) = t
350  IF( kstep.EQ.2 ) THEN
351  t = a( k-1, k )
352  a( k-1, k ) = a( kp, k )
353  a( kp, k ) = t
354  END IF
355  END IF
356 *
357 * Update the leading submatrix
358 *
359  IF( kstep.EQ.1 ) THEN
360 *
361 * 1-by-1 pivot block D(k): column k now holds
362 *
363 * W(k) = U(k)*D(k)
364 *
365 * where U(k) is the k-th column of U
366 *
367 * Perform a rank-1 update of A(1:k-1,1:k-1) as
368 *
369 * A := A - U(k)*D(k)*U(k)**T = A - W(k)*1/D(k)*W(k)**T
370 *
371  r1 = one / a( k, k )
372  CALL ssyr( uplo, k-1, -r1, a( 1, k ), 1, a, lda )
373 *
374 * Store U(k) in column k
375 *
376  CALL sscal( k-1, r1, a( 1, k ), 1 )
377  ELSE
378 *
379 * 2-by-2 pivot block D(k): columns k and k-1 now hold
380 *
381 * ( W(k-1) W(k) ) = ( U(k-1) U(k) )*D(k)
382 *
383 * where U(k) and U(k-1) are the k-th and (k-1)-th columns
384 * of U
385 *
386 * Perform a rank-2 update of A(1:k-2,1:k-2) as
387 *
388 * A := A - ( U(k-1) U(k) )*D(k)*( U(k-1) U(k) )**T
389 * = A - ( W(k-1) W(k) )*inv(D(k))*( W(k-1) W(k) )**T
390 *
391  IF( k.GT.2 ) THEN
392 *
393  d12 = a( k-1, k )
394  d22 = a( k-1, k-1 ) / d12
395  d11 = a( k, k ) / d12
396  t = one / ( d11*d22-one )
397  d12 = t / d12
398 *
399  DO 30 j = k - 2, 1, -1
400  wkm1 = d12*( d11*a( j, k-1 )-a( j, k ) )
401  wk = d12*( d22*a( j, k )-a( j, k-1 ) )
402  DO 20 i = j, 1, -1
403  a( i, j ) = a( i, j ) - a( i, k )*wk -
404  $ a( i, k-1 )*wkm1
405  20 CONTINUE
406  a( j, k ) = wk
407  a( j, k-1 ) = wkm1
408  30 CONTINUE
409 *
410  END IF
411 *
412  END IF
413  END IF
414 *
415 * Store details of the interchanges in IPIV
416 *
417  IF( kstep.EQ.1 ) THEN
418  ipiv( k ) = kp
419  ELSE
420  ipiv( k ) = -kp
421  ipiv( k-1 ) = -kp
422  END IF
423 *
424 * Decrease K and return to the start of the main loop
425 *
426  k = k - kstep
427  GO TO 10
428 *
429  ELSE
430 *
431 * Factorize A as L*D*L**T using the lower triangle of A
432 *
433 * K is the main loop index, increasing from 1 to N in steps of
434 * 1 or 2
435 *
436  k = 1
437  40 CONTINUE
438 *
439 * If K > N, exit from loop
440 *
441  IF( k.GT.n )
442  $ GO TO 70
443  kstep = 1
444 *
445 * Determine rows and columns to be interchanged and whether
446 * a 1-by-1 or 2-by-2 pivot block will be used
447 *
448  absakk = abs( a( k, k ) )
449 *
450 * IMAX is the row-index of the largest off-diagonal element in
451 * column K, and COLMAX is its absolute value.
452 * Determine both COLMAX and IMAX.
453 *
454  IF( k.LT.n ) THEN
455  imax = k + isamax( n-k, a( k+1, k ), 1 )
456  colmax = abs( a( imax, k ) )
457  ELSE
458  colmax = zero
459  END IF
460 *
461  IF( (max( absakk, colmax ).EQ.zero) .OR. sisnan(absakk) ) THEN
462 *
463 * Column K is zero or underflow, or contains a NaN:
464 * set INFO and continue
465 *
466  IF( info.EQ.0 )
467  $ info = k
468  kp = k
469  ELSE
470  IF( absakk.GE.alpha*colmax ) THEN
471 *
472 * no interchange, use 1-by-1 pivot block
473 *
474  kp = k
475  ELSE
476 *
477 * JMAX is the column-index of the largest off-diagonal
478 * element in row IMAX, and ROWMAX is its absolute value
479 *
480  jmax = k - 1 + isamax( imax-k, a( imax, k ), lda )
481  rowmax = abs( a( imax, jmax ) )
482  IF( imax.LT.n ) THEN
483  jmax = imax + isamax( n-imax, a( imax+1, imax ), 1 )
484  rowmax = max( rowmax, abs( a( jmax, imax ) ) )
485  END IF
486 *
487  IF( absakk.GE.alpha*colmax*( colmax / rowmax ) ) THEN
488 *
489 * no interchange, use 1-by-1 pivot block
490 *
491  kp = k
492  ELSE IF( abs( a( imax, imax ) ).GE.alpha*rowmax ) THEN
493 *
494 * interchange rows and columns K and IMAX, use 1-by-1
495 * pivot block
496 *
497  kp = imax
498  ELSE
499 *
500 * interchange rows and columns K+1 and IMAX, use 2-by-2
501 * pivot block
502 *
503  kp = imax
504  kstep = 2
505  END IF
506  END IF
507 *
508  kk = k + kstep - 1
509  IF( kp.NE.kk ) THEN
510 *
511 * Interchange rows and columns KK and KP in the trailing
512 * submatrix A(k:n,k:n)
513 *
514  IF( kp.LT.n )
515  $ CALL sswap( n-kp, a( kp+1, kk ), 1, a( kp+1, kp ), 1 )
516  CALL sswap( kp-kk-1, a( kk+1, kk ), 1, a( kp, kk+1 ),
517  $ lda )
518  t = a( kk, kk )
519  a( kk, kk ) = a( kp, kp )
520  a( kp, kp ) = t
521  IF( kstep.EQ.2 ) THEN
522  t = a( k+1, k )
523  a( k+1, k ) = a( kp, k )
524  a( kp, k ) = t
525  END IF
526  END IF
527 *
528 * Update the trailing submatrix
529 *
530  IF( kstep.EQ.1 ) THEN
531 *
532 * 1-by-1 pivot block D(k): column k now holds
533 *
534 * W(k) = L(k)*D(k)
535 *
536 * where L(k) is the k-th column of L
537 *
538  IF( k.LT.n ) THEN
539 *
540 * Perform a rank-1 update of A(k+1:n,k+1:n) as
541 *
542 * A := A - L(k)*D(k)*L(k)**T = A - W(k)*(1/D(k))*W(k)**T
543 *
544  d11 = one / a( k, k )
545  CALL ssyr( uplo, n-k, -d11, a( k+1, k ), 1,
546  $ a( k+1, k+1 ), lda )
547 *
548 * Store L(k) in column K
549 *
550  CALL sscal( n-k, d11, a( k+1, k ), 1 )
551  END IF
552  ELSE
553 *
554 * 2-by-2 pivot block D(k)
555 *
556  IF( k.LT.n-1 ) THEN
557 *
558 * Perform a rank-2 update of A(k+2:n,k+2:n) as
559 *
560 * A := A - ( (A(k) A(k+1))*D(k)**(-1) ) * (A(k) A(k+1))**T
561 *
562 * where L(k) and L(k+1) are the k-th and (k+1)-th
563 * columns of L
564 *
565  d21 = a( k+1, k )
566  d11 = a( k+1, k+1 ) / d21
567  d22 = a( k, k ) / d21
568  t = one / ( d11*d22-one )
569  d21 = t / d21
570 *
571  DO 60 j = k + 2, n
572 *
573  wk = d21*( d11*a( j, k )-a( j, k+1 ) )
574  wkp1 = d21*( d22*a( j, k+1 )-a( j, k ) )
575 *
576  DO 50 i = j, n
577  a( i, j ) = a( i, j ) - a( i, k )*wk -
578  $ a( i, k+1 )*wkp1
579  50 CONTINUE
580 *
581  a( j, k ) = wk
582  a( j, k+1 ) = wkp1
583 *
584  60 CONTINUE
585  END IF
586  END IF
587  END IF
588 *
589 * Store details of the interchanges in IPIV
590 *
591  IF( kstep.EQ.1 ) THEN
592  ipiv( k ) = kp
593  ELSE
594  ipiv( k ) = -kp
595  ipiv( k+1 ) = -kp
596  END IF
597 *
598 * Increase K and return to the start of the main loop
599 *
600  k = k + kstep
601  GO TO 40
602 *
603  END IF
604 *
605  70 CONTINUE
606 *
607  RETURN
608 *
609 * End of SSYTF2
610 *
611  END
subroutine xerbla(SRNAME, INFO)
XERBLA
Definition: xerbla.f:62
subroutine sscal(N, SA, SX, INCX)
SSCAL
Definition: sscal.f:55
subroutine sswap(N, SX, INCX, SY, INCY)
SSWAP
Definition: sswap.f:53
subroutine ssyr(UPLO, N, ALPHA, X, INCX, A, LDA)
SSYR
Definition: ssyr.f:134
subroutine ssytf2(UPLO, N, A, LDA, IPIV, INFO)
SSYTF2 computes the factorization of a real symmetric indefinite matrix, using the diagonal pivoting ...
Definition: ssytf2.f:197