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