LAPACK 3.11.0
LAPACK: Linear Algebra PACKage
Loading...
Searching...
No Matches

◆ ssptrf()

subroutine ssptrf ( character  UPLO,
integer  N,
real, dimension( * )  AP,
integer, dimension( * )  IPIV,
integer  INFO 
)

SSPTRF

Download SSPTRF + dependencies [TGZ] [ZIP] [TXT]

Purpose:
 SSPTRF computes the factorization of a real symmetric matrix A stored
 in packed format using the Bunch-Kaufman diagonal pivoting method:

    A = U*D*U**T  or  A = L*D*L**T

 where U (or L) is a product of permutation and unit upper (lower)
 triangular matrices, and D is symmetric and block diagonal with
 1-by-1 and 2-by-2 diagonal blocks.
Parameters
[in]UPLO
          UPLO is CHARACTER*1
          = 'U':  Upper triangle of A is stored;
          = 'L':  Lower triangle of A is stored.
[in]N
          N is INTEGER
          The order of the matrix A.  N >= 0.
[in,out]AP
          AP is REAL array, dimension (N*(N+1)/2)
          On entry, the upper or lower triangle of the symmetric matrix
          A, packed columnwise in a linear array.  The j-th column of A
          is stored in the array AP as follows:
          if UPLO = 'U', AP(i + (j-1)*j/2) = A(i,j) for 1<=i<=j;
          if UPLO = 'L', AP(i + (j-1)*(2n-j)/2) = A(i,j) for j<=i<=n.

          On exit, the block diagonal matrix D and the multipliers used
          to obtain the factor U or L, stored as a packed triangular
          matrix overwriting A (see below for further details).
[out]IPIV
          IPIV is INTEGER array, dimension (N)
          Details of the interchanges and the block structure of D.
          If IPIV(k) > 0, then rows and columns k and IPIV(k) were
          interchanged and D(k,k) is a 1-by-1 diagonal block.
          If UPLO = 'U' and IPIV(k) = IPIV(k-1) < 0, then rows and
          columns k-1 and -IPIV(k) were interchanged and D(k-1:k,k-1:k)
          is a 2-by-2 diagonal block.  If UPLO = 'L' and IPIV(k) =
          IPIV(k+1) < 0, then rows and columns k+1 and -IPIV(k) were
          interchanged and D(k:k+1,k:k+1) is a 2-by-2 diagonal block.
[out]INFO
          INFO is INTEGER
          = 0: successful exit
          < 0: if INFO = -i, the i-th argument had an illegal value
          > 0: if INFO = i, D(i,i) is exactly zero.  The factorization
               has been completed, but the block diagonal matrix D is
               exactly singular, and division by zero will occur if it
               is used to solve a system of equations.
Author
Univ. of Tennessee
Univ. of California Berkeley
Univ. of Colorado Denver
NAG Ltd.
Further Details:
  5-96 - Based on modifications by J. Lewis, Boeing Computer Services
         Company

  If UPLO = 'U', then A = U*D*U**T, where
     U = P(n)*U(n)* ... *P(k)U(k)* ...,
  i.e., U is a product of terms P(k)*U(k), where k decreases from n to
  1 in steps of 1 or 2, and D is a block diagonal matrix with 1-by-1
  and 2-by-2 diagonal blocks D(k).  P(k) is a permutation matrix as
  defined by IPIV(k), and U(k) is a unit upper triangular matrix, such
  that if the diagonal block D(k) is of order s (s = 1 or 2), then

             (   I    v    0   )   k-s
     U(k) =  (   0    I    0   )   s
             (   0    0    I   )   n-k
                k-s   s   n-k

  If s = 1, D(k) overwrites A(k,k), and v overwrites A(1:k-1,k).
  If s = 2, the upper triangle of D(k) overwrites A(k-1,k-1), A(k-1,k),
  and A(k,k), and v overwrites A(1:k-2,k-1:k).

  If UPLO = 'L', then A = L*D*L**T, where
     L = P(1)*L(1)* ... *P(k)*L(k)* ...,
  i.e., L is a product of terms P(k)*L(k), where k increases from 1 to
  n in steps of 1 or 2, and D is a block diagonal matrix with 1-by-1
  and 2-by-2 diagonal blocks D(k).  P(k) is a permutation matrix as
  defined by IPIV(k), and L(k) is a unit lower triangular matrix, such
  that if the diagonal block D(k) is of order s (s = 1 or 2), then

             (   I    0     0   )  k-1
     L(k) =  (   0    I     0   )  s
             (   0    v     I   )  n-k-s+1
                k-1   s  n-k-s+1

  If s = 1, D(k) overwrites A(k,k), and v overwrites A(k+1:n,k).
  If s = 2, the lower triangle of D(k) overwrites A(k,k), A(k+1,k),
  and A(k+1,k+1), and v overwrites A(k+2:n,k:k+1).

Definition at line 156 of file ssptrf.f.

157*
158* -- LAPACK computational routine --
159* -- LAPACK is a software package provided by Univ. of Tennessee, --
160* -- Univ. of California Berkeley, Univ. of Colorado Denver and NAG Ltd..--
161*
162* .. Scalar Arguments ..
163 CHARACTER UPLO
164 INTEGER INFO, N
165* ..
166* .. Array Arguments ..
167 INTEGER IPIV( * )
168 REAL AP( * )
169* ..
170*
171* =====================================================================
172*
173* .. Parameters ..
174 REAL ZERO, ONE
175 parameter( zero = 0.0e+0, one = 1.0e+0 )
176 REAL EIGHT, SEVTEN
177 parameter( eight = 8.0e+0, sevten = 17.0e+0 )
178* ..
179* .. Local Scalars ..
180 LOGICAL UPPER
181 INTEGER I, IMAX, J, JMAX, K, KC, KK, KNC, KP, KPC,
182 $ KSTEP, KX, NPP
183 REAL ABSAKK, ALPHA, COLMAX, D11, D12, D21, D22, R1,
184 $ ROWMAX, T, WK, WKM1, WKP1
185* ..
186* .. External Functions ..
187 LOGICAL LSAME
188 INTEGER ISAMAX
189 EXTERNAL lsame, isamax
190* ..
191* .. External Subroutines ..
192 EXTERNAL sscal, sspr, sswap, xerbla
193* ..
194* .. Intrinsic Functions ..
195 INTRINSIC abs, max, sqrt
196* ..
197* .. Executable Statements ..
198*
199* Test the input parameters.
200*
201 info = 0
202 upper = lsame( uplo, 'U' )
203 IF( .NOT.upper .AND. .NOT.lsame( uplo, 'L' ) ) THEN
204 info = -1
205 ELSE IF( n.LT.0 ) THEN
206 info = -2
207 END IF
208 IF( info.NE.0 ) THEN
209 CALL xerbla( 'SSPTRF', -info )
210 RETURN
211 END IF
212*
213* Initialize ALPHA for use in choosing pivot block size.
214*
215 alpha = ( one+sqrt( sevten ) ) / eight
216*
217 IF( upper ) THEN
218*
219* Factorize A as U*D*U**T using the upper triangle of A
220*
221* K is the main loop index, decreasing from N to 1 in steps of
222* 1 or 2
223*
224 k = n
225 kc = ( n-1 )*n / 2 + 1
226 10 CONTINUE
227 knc = kc
228*
229* If K < 1, exit from loop
230*
231 IF( k.LT.1 )
232 $ GO TO 110
233 kstep = 1
234*
235* Determine rows and columns to be interchanged and whether
236* a 1-by-1 or 2-by-2 pivot block will be used
237*
238 absakk = abs( ap( kc+k-1 ) )
239*
240* IMAX is the row-index of the largest off-diagonal element in
241* column K, and COLMAX is its absolute value
242*
243 IF( k.GT.1 ) THEN
244 imax = isamax( k-1, ap( kc ), 1 )
245 colmax = abs( ap( kc+imax-1 ) )
246 ELSE
247 colmax = zero
248 END IF
249*
250 IF( max( absakk, colmax ).EQ.zero ) THEN
251*
252* Column K is zero: set INFO and continue
253*
254 IF( info.EQ.0 )
255 $ info = k
256 kp = k
257 ELSE
258 IF( absakk.GE.alpha*colmax ) THEN
259*
260* no interchange, use 1-by-1 pivot block
261*
262 kp = k
263 ELSE
264*
265 rowmax = zero
266 jmax = imax
267 kx = imax*( imax+1 ) / 2 + imax
268 DO 20 j = imax + 1, k
269 IF( abs( ap( kx ) ).GT.rowmax ) THEN
270 rowmax = abs( ap( kx ) )
271 jmax = j
272 END IF
273 kx = kx + j
274 20 CONTINUE
275 kpc = ( imax-1 )*imax / 2 + 1
276 IF( imax.GT.1 ) THEN
277 jmax = isamax( imax-1, ap( kpc ), 1 )
278 rowmax = max( rowmax, abs( ap( kpc+jmax-1 ) ) )
279 END IF
280*
281 IF( absakk.GE.alpha*colmax*( colmax / rowmax ) ) THEN
282*
283* no interchange, use 1-by-1 pivot block
284*
285 kp = k
286 ELSE IF( abs( ap( kpc+imax-1 ) ).GE.alpha*rowmax ) THEN
287*
288* interchange rows and columns K and IMAX, use 1-by-1
289* pivot block
290*
291 kp = imax
292 ELSE
293*
294* interchange rows and columns K-1 and IMAX, use 2-by-2
295* pivot block
296*
297 kp = imax
298 kstep = 2
299 END IF
300 END IF
301*
302 kk = k - kstep + 1
303 IF( kstep.EQ.2 )
304 $ knc = knc - k + 1
305 IF( kp.NE.kk ) THEN
306*
307* Interchange rows and columns KK and KP in the leading
308* submatrix A(1:k,1:k)
309*
310 CALL sswap( kp-1, ap( knc ), 1, ap( kpc ), 1 )
311 kx = kpc + kp - 1
312 DO 30 j = kp + 1, kk - 1
313 kx = kx + j - 1
314 t = ap( knc+j-1 )
315 ap( knc+j-1 ) = ap( kx )
316 ap( kx ) = t
317 30 CONTINUE
318 t = ap( knc+kk-1 )
319 ap( knc+kk-1 ) = ap( kpc+kp-1 )
320 ap( kpc+kp-1 ) = t
321 IF( kstep.EQ.2 ) THEN
322 t = ap( kc+k-2 )
323 ap( kc+k-2 ) = ap( kc+kp-1 )
324 ap( kc+kp-1 ) = t
325 END IF
326 END IF
327*
328* Update the leading submatrix
329*
330 IF( kstep.EQ.1 ) THEN
331*
332* 1-by-1 pivot block D(k): column k now holds
333*
334* W(k) = U(k)*D(k)
335*
336* where U(k) is the k-th column of U
337*
338* Perform a rank-1 update of A(1:k-1,1:k-1) as
339*
340* A := A - U(k)*D(k)*U(k)**T = A - W(k)*1/D(k)*W(k)**T
341*
342 r1 = one / ap( kc+k-1 )
343 CALL sspr( uplo, k-1, -r1, ap( kc ), 1, ap )
344*
345* Store U(k) in column k
346*
347 CALL sscal( k-1, r1, ap( kc ), 1 )
348 ELSE
349*
350* 2-by-2 pivot block D(k): columns k and k-1 now hold
351*
352* ( W(k-1) W(k) ) = ( U(k-1) U(k) )*D(k)
353*
354* where U(k) and U(k-1) are the k-th and (k-1)-th columns
355* of U
356*
357* Perform a rank-2 update of A(1:k-2,1:k-2) as
358*
359* A := A - ( U(k-1) U(k) )*D(k)*( U(k-1) U(k) )**T
360* = A - ( W(k-1) W(k) )*inv(D(k))*( W(k-1) W(k) )**T
361*
362 IF( k.GT.2 ) THEN
363*
364 d12 = ap( k-1+( k-1 )*k / 2 )
365 d22 = ap( k-1+( k-2 )*( k-1 ) / 2 ) / d12
366 d11 = ap( k+( k-1 )*k / 2 ) / d12
367 t = one / ( d11*d22-one )
368 d12 = t / d12
369*
370 DO 50 j = k - 2, 1, -1
371 wkm1 = d12*( d11*ap( j+( k-2 )*( k-1 ) / 2 )-
372 $ ap( j+( k-1 )*k / 2 ) )
373 wk = d12*( d22*ap( j+( k-1 )*k / 2 )-
374 $ ap( j+( k-2 )*( k-1 ) / 2 ) )
375 DO 40 i = j, 1, -1
376 ap( i+( j-1 )*j / 2 ) = ap( i+( j-1 )*j / 2 ) -
377 $ ap( i+( k-1 )*k / 2 )*wk -
378 $ ap( i+( k-2 )*( k-1 ) / 2 )*wkm1
379 40 CONTINUE
380 ap( j+( k-1 )*k / 2 ) = wk
381 ap( j+( k-2 )*( k-1 ) / 2 ) = wkm1
382 50 CONTINUE
383*
384 END IF
385*
386 END IF
387 END IF
388*
389* Store details of the interchanges in IPIV
390*
391 IF( kstep.EQ.1 ) THEN
392 ipiv( k ) = kp
393 ELSE
394 ipiv( k ) = -kp
395 ipiv( k-1 ) = -kp
396 END IF
397*
398* Decrease K and return to the start of the main loop
399*
400 k = k - kstep
401 kc = knc - k
402 GO TO 10
403*
404 ELSE
405*
406* Factorize A as L*D*L**T using the lower triangle of A
407*
408* K is the main loop index, increasing from 1 to N in steps of
409* 1 or 2
410*
411 k = 1
412 kc = 1
413 npp = n*( n+1 ) / 2
414 60 CONTINUE
415 knc = kc
416*
417* If K > N, exit from loop
418*
419 IF( k.GT.n )
420 $ GO TO 110
421 kstep = 1
422*
423* Determine rows and columns to be interchanged and whether
424* a 1-by-1 or 2-by-2 pivot block will be used
425*
426 absakk = abs( ap( kc ) )
427*
428* IMAX is the row-index of the largest off-diagonal element in
429* column K, and COLMAX is its absolute value
430*
431 IF( k.LT.n ) THEN
432 imax = k + isamax( n-k, ap( kc+1 ), 1 )
433 colmax = abs( ap( kc+imax-k ) )
434 ELSE
435 colmax = zero
436 END IF
437*
438 IF( max( absakk, colmax ).EQ.zero ) THEN
439*
440* Column K is zero: set INFO and continue
441*
442 IF( info.EQ.0 )
443 $ info = k
444 kp = k
445 ELSE
446 IF( absakk.GE.alpha*colmax ) THEN
447*
448* no interchange, use 1-by-1 pivot block
449*
450 kp = k
451 ELSE
452*
453* JMAX is the column-index of the largest off-diagonal
454* element in row IMAX, and ROWMAX is its absolute value
455*
456 rowmax = zero
457 kx = kc + imax - k
458 DO 70 j = k, imax - 1
459 IF( abs( ap( kx ) ).GT.rowmax ) THEN
460 rowmax = abs( ap( kx ) )
461 jmax = j
462 END IF
463 kx = kx + n - j
464 70 CONTINUE
465 kpc = npp - ( n-imax+1 )*( n-imax+2 ) / 2 + 1
466 IF( imax.LT.n ) THEN
467 jmax = imax + isamax( n-imax, ap( kpc+1 ), 1 )
468 rowmax = max( rowmax, abs( ap( kpc+jmax-imax ) ) )
469 END IF
470*
471 IF( absakk.GE.alpha*colmax*( colmax / rowmax ) ) THEN
472*
473* no interchange, use 1-by-1 pivot block
474*
475 kp = k
476 ELSE IF( abs( ap( kpc ) ).GE.alpha*rowmax ) THEN
477*
478* interchange rows and columns K and IMAX, use 1-by-1
479* pivot block
480*
481 kp = imax
482 ELSE
483*
484* interchange rows and columns K+1 and IMAX, use 2-by-2
485* pivot block
486*
487 kp = imax
488 kstep = 2
489 END IF
490 END IF
491*
492 kk = k + kstep - 1
493 IF( kstep.EQ.2 )
494 $ knc = knc + n - k + 1
495 IF( kp.NE.kk ) THEN
496*
497* Interchange rows and columns KK and KP in the trailing
498* submatrix A(k:n,k:n)
499*
500 IF( kp.LT.n )
501 $ CALL sswap( n-kp, ap( knc+kp-kk+1 ), 1, ap( kpc+1 ),
502 $ 1 )
503 kx = knc + kp - kk
504 DO 80 j = kk + 1, kp - 1
505 kx = kx + n - j + 1
506 t = ap( knc+j-kk )
507 ap( knc+j-kk ) = ap( kx )
508 ap( kx ) = t
509 80 CONTINUE
510 t = ap( knc )
511 ap( knc ) = ap( kpc )
512 ap( kpc ) = t
513 IF( kstep.EQ.2 ) THEN
514 t = ap( kc+1 )
515 ap( kc+1 ) = ap( kc+kp-k )
516 ap( kc+kp-k ) = t
517 END IF
518 END IF
519*
520* Update the trailing submatrix
521*
522 IF( kstep.EQ.1 ) THEN
523*
524* 1-by-1 pivot block D(k): column k now holds
525*
526* W(k) = L(k)*D(k)
527*
528* where L(k) is the k-th column of L
529*
530 IF( k.LT.n ) THEN
531*
532* Perform a rank-1 update of A(k+1:n,k+1:n) as
533*
534* A := A - L(k)*D(k)*L(k)**T = A - W(k)*(1/D(k))*W(k)**T
535*
536 r1 = one / ap( kc )
537 CALL sspr( uplo, n-k, -r1, ap( kc+1 ), 1,
538 $ ap( kc+n-k+1 ) )
539*
540* Store L(k) in column K
541*
542 CALL sscal( n-k, r1, ap( kc+1 ), 1 )
543 END IF
544 ELSE
545*
546* 2-by-2 pivot block D(k): columns K and K+1 now hold
547*
548* ( W(k) W(k+1) ) = ( L(k) L(k+1) )*D(k)
549*
550* where L(k) and L(k+1) are the k-th and (k+1)-th columns
551* of L
552*
553 IF( k.LT.n-1 ) THEN
554*
555* Perform a rank-2 update of A(k+2:n,k+2:n) as
556*
557* A := A - ( L(k) L(k+1) )*D(k)*( L(k) L(k+1) )**T
558* = A - ( W(k) W(k+1) )*inv(D(k))*( W(k) W(k+1) )**T
559*
560* where L(k) and L(k+1) are the k-th and (k+1)-th
561* columns of L
562*
563 d21 = ap( k+1+( k-1 )*( 2*n-k ) / 2 )
564 d11 = ap( k+1+k*( 2*n-k-1 ) / 2 ) / d21
565 d22 = ap( k+( k-1 )*( 2*n-k ) / 2 ) / d21
566 t = one / ( d11*d22-one )
567 d21 = t / d21
568*
569 DO 100 j = k + 2, n
570 wk = d21*( d11*ap( j+( k-1 )*( 2*n-k ) / 2 )-
571 $ ap( j+k*( 2*n-k-1 ) / 2 ) )
572 wkp1 = d21*( d22*ap( j+k*( 2*n-k-1 ) / 2 )-
573 $ ap( j+( k-1 )*( 2*n-k ) / 2 ) )
574*
575 DO 90 i = j, n
576 ap( i+( j-1 )*( 2*n-j ) / 2 ) = ap( i+( j-1 )*
577 $ ( 2*n-j ) / 2 ) - ap( i+( k-1 )*( 2*n-k ) /
578 $ 2 )*wk - ap( i+k*( 2*n-k-1 ) / 2 )*wkp1
579 90 CONTINUE
580*
581 ap( j+( k-1 )*( 2*n-k ) / 2 ) = wk
582 ap( j+k*( 2*n-k-1 ) / 2 ) = wkp1
583*
584 100 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 kc = knc + n - k + 2
602 GO TO 60
603*
604 END IF
605*
606 110 CONTINUE
607 RETURN
608*
609* End of SSPTRF
610*
integer function isamax(N, SX, INCX)
ISAMAX
Definition: isamax.f:71
subroutine xerbla(SRNAME, INFO)
XERBLA
Definition: xerbla.f:60
logical function lsame(CA, CB)
LSAME
Definition: lsame.f:53
subroutine sswap(N, SX, INCX, SY, INCY)
SSWAP
Definition: sswap.f:82
subroutine sscal(N, SA, SX, INCX)
SSCAL
Definition: sscal.f:79
subroutine sspr(UPLO, N, ALPHA, X, INCX, AP)
SSPR
Definition: sspr.f:127
Here is the call graph for this function:
Here is the caller graph for this function: