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

◆ dsptrf()

subroutine dsptrf ( character  uplo,
integer  n,
double precision, dimension( * )  ap,
integer, dimension( * )  ipiv,
integer  info 
)

DSPTRF

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

Purpose:
 DSPTRF 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 DOUBLE PRECISION 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:
  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).
Contributors:
J. Lewis, Boeing Computer Services Company

Definition at line 158 of file dsptrf.f.

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