LAPACK  3.10.1 LAPACK: Linear Algebra PACKage
zsptrf.f
Go to the documentation of this file.
1 *> \brief \b ZSPTRF
2 *
3 * =========== DOCUMENTATION ===========
4 *
5 * Online html documentation available at
6 * http://www.netlib.org/lapack/explore-html/
7 *
8 *> \htmlonly
10 *> <a href="http://www.netlib.org/cgi-bin/netlibfiles.tgz?format=tgz&filename=/lapack/lapack_routine/zsptrf.f">
11 *> [TGZ]</a>
12 *> <a href="http://www.netlib.org/cgi-bin/netlibfiles.zip?format=zip&filename=/lapack/lapack_routine/zsptrf.f">
13 *> [ZIP]</a>
14 *> <a href="http://www.netlib.org/cgi-bin/netlibfiles.txt?format=txt&filename=/lapack/lapack_routine/zsptrf.f">
15 *> [TXT]</a>
16 *> \endhtmlonly
17 *
18 * Definition:
19 * ===========
20 *
21 * SUBROUTINE ZSPTRF( 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*16 AP( * )
30 * ..
31 *
32 *
33 *> \par Purpose:
34 * =============
35 *>
36 *> \verbatim
37 *>
38 *> ZSPTRF 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*16 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 *> \ingroup complex16OTHERcomputational
112 *
113 *> \par Further Details:
114 * =====================
115 *>
116 *> \verbatim
117 *>
118 *> 5-96 - Based on modifications by J. Lewis, Boeing Computer Services
119 *> Company
120 *>
121 *> If UPLO = 'U', then A = U*D*U**T, where
122 *> U = P(n)*U(n)* ... *P(k)U(k)* ...,
123 *> i.e., U is a product of terms P(k)*U(k), where k decreases from n to
124 *> 1 in steps of 1 or 2, and D is a block diagonal matrix with 1-by-1
125 *> and 2-by-2 diagonal blocks D(k). P(k) is a permutation matrix as
126 *> defined by IPIV(k), and U(k) is a unit upper triangular matrix, such
127 *> that if the diagonal block D(k) is of order s (s = 1 or 2), then
128 *>
129 *> ( I v 0 ) k-s
130 *> U(k) = ( 0 I 0 ) s
131 *> ( 0 0 I ) n-k
132 *> k-s s n-k
133 *>
134 *> If s = 1, D(k) overwrites A(k,k), and v overwrites A(1:k-1,k).
135 *> If s = 2, the upper triangle of D(k) overwrites A(k-1,k-1), A(k-1,k),
136 *> and A(k,k), and v overwrites A(1:k-2,k-1:k).
137 *>
138 *> If UPLO = 'L', then A = L*D*L**T, where
139 *> L = P(1)*L(1)* ... *P(k)*L(k)* ...,
140 *> i.e., L is a product of terms P(k)*L(k), where k increases from 1 to
141 *> n in steps of 1 or 2, and D is a block diagonal matrix with 1-by-1
142 *> and 2-by-2 diagonal blocks D(k). P(k) is a permutation matrix as
143 *> defined by IPIV(k), and L(k) is a unit lower triangular matrix, such
144 *> that if the diagonal block D(k) is of order s (s = 1 or 2), then
145 *>
146 *> ( I 0 0 ) k-1
147 *> L(k) = ( 0 I 0 ) s
148 *> ( 0 v I ) n-k-s+1
149 *> k-1 s n-k-s+1
150 *>
151 *> If s = 1, D(k) overwrites A(k,k), and v overwrites A(k+1:n,k).
152 *> If s = 2, the lower triangle of D(k) overwrites A(k,k), A(k+1,k),
153 *> and A(k+1,k+1), and v overwrites A(k+2:n,k:k+1).
154 *> \endverbatim
155 *>
156 * =====================================================================
157  SUBROUTINE zsptrf( UPLO, N, AP, IPIV, INFO )
158 *
159 * -- LAPACK computational routine --
160 * -- LAPACK is a software package provided by Univ. of Tennessee, --
161 * -- Univ. of California Berkeley, Univ. of Colorado Denver and NAG Ltd..--
162 *
163 * .. Scalar Arguments ..
164  CHARACTER UPLO
165  INTEGER INFO, N
166 * ..
167 * .. Array Arguments ..
168  INTEGER IPIV( * )
169  COMPLEX*16 AP( * )
170 * ..
171 *
172 * =====================================================================
173 *
174 * .. Parameters ..
175  DOUBLE PRECISION ZERO, ONE
176  parameter( zero = 0.0d+0, one = 1.0d+0 )
177  DOUBLE PRECISION EIGHT, SEVTEN
178  parameter( eight = 8.0d+0, sevten = 17.0d+0 )
179  COMPLEX*16 CONE
180  parameter( cone = ( 1.0d+0, 0.0d+0 ) )
181 * ..
182 * .. Local Scalars ..
183  LOGICAL UPPER
184  INTEGER I, IMAX, J, JMAX, K, KC, KK, KNC, KP, KPC,
185  \$ KSTEP, KX, NPP
186  DOUBLE PRECISION ABSAKK, ALPHA, COLMAX, ROWMAX
187  COMPLEX*16 D11, D12, D21, D22, R1, T, WK, WKM1, WKP1, ZDUM
188 * ..
189 * .. External Functions ..
190  LOGICAL LSAME
191  INTEGER IZAMAX
192  EXTERNAL lsame, izamax
193 * ..
194 * .. External Subroutines ..
195  EXTERNAL xerbla, zscal, zspr, zswap
196 * ..
197 * .. Intrinsic Functions ..
198  INTRINSIC abs, dble, dimag, max, sqrt
199 * ..
200 * .. Statement Functions ..
201  DOUBLE PRECISION CABS1
202 * ..
203 * .. Statement Function definitions ..
204  cabs1( zdum ) = abs( dble( zdum ) ) + abs( dimag( zdum ) )
205 * ..
206 * .. Executable Statements ..
207 *
208 * Test the input parameters.
209 *
210  info = 0
211  upper = lsame( uplo, 'U' )
212  IF( .NOT.upper .AND. .NOT.lsame( uplo, 'L' ) ) THEN
213  info = -1
214  ELSE IF( n.LT.0 ) THEN
215  info = -2
216  END IF
217  IF( info.NE.0 ) THEN
218  CALL xerbla( 'ZSPTRF', -info )
219  RETURN
220  END IF
221 *
222 * Initialize ALPHA for use in choosing pivot block size.
223 *
224  alpha = ( one+sqrt( sevten ) ) / eight
225 *
226  IF( upper ) THEN
227 *
228 * Factorize A as U*D*U**T using the upper triangle of A
229 *
230 * K is the main loop index, decreasing from N to 1 in steps of
231 * 1 or 2
232 *
233  k = n
234  kc = ( n-1 )*n / 2 + 1
235  10 CONTINUE
236  knc = kc
237 *
238 * If K < 1, exit from loop
239 *
240  IF( k.LT.1 )
241  \$ GO TO 110
242  kstep = 1
243 *
244 * Determine rows and columns to be interchanged and whether
245 * a 1-by-1 or 2-by-2 pivot block will be used
246 *
247  absakk = cabs1( ap( kc+k-1 ) )
248 *
249 * IMAX is the row-index of the largest off-diagonal element in
250 * column K, and COLMAX is its absolute value
251 *
252  IF( k.GT.1 ) THEN
253  imax = izamax( k-1, ap( kc ), 1 )
254  colmax = cabs1( ap( kc+imax-1 ) )
255  ELSE
256  colmax = zero
257  END IF
258 *
259  IF( max( absakk, colmax ).EQ.zero ) THEN
260 *
261 * Column K is zero: set INFO and continue
262 *
263  IF( info.EQ.0 )
264  \$ info = k
265  kp = k
266  ELSE
267  IF( absakk.GE.alpha*colmax ) THEN
268 *
269 * no interchange, use 1-by-1 pivot block
270 *
271  kp = k
272  ELSE
273 *
274  rowmax = zero
275  jmax = imax
276  kx = imax*( imax+1 ) / 2 + imax
277  DO 20 j = imax + 1, k
278  IF( cabs1( ap( kx ) ).GT.rowmax ) THEN
279  rowmax = cabs1( ap( kx ) )
280  jmax = j
281  END IF
282  kx = kx + j
283  20 CONTINUE
284  kpc = ( imax-1 )*imax / 2 + 1
285  IF( imax.GT.1 ) THEN
286  jmax = izamax( imax-1, ap( kpc ), 1 )
287  rowmax = max( rowmax, cabs1( ap( kpc+jmax-1 ) ) )
288  END IF
289 *
290  IF( absakk.GE.alpha*colmax*( colmax / rowmax ) ) THEN
291 *
292 * no interchange, use 1-by-1 pivot block
293 *
294  kp = k
295  ELSE IF( cabs1( ap( kpc+imax-1 ) ).GE.alpha*rowmax ) THEN
296 *
297 * interchange rows and columns K and IMAX, use 1-by-1
298 * pivot block
299 *
300  kp = imax
301  ELSE
302 *
303 * interchange rows and columns K-1 and IMAX, use 2-by-2
304 * pivot block
305 *
306  kp = imax
307  kstep = 2
308  END IF
309  END IF
310 *
311  kk = k - kstep + 1
312  IF( kstep.EQ.2 )
313  \$ knc = knc - k + 1
314  IF( kp.NE.kk ) THEN
315 *
316 * Interchange rows and columns KK and KP in the leading
317 * submatrix A(1:k,1:k)
318 *
319  CALL zswap( kp-1, ap( knc ), 1, ap( kpc ), 1 )
320  kx = kpc + kp - 1
321  DO 30 j = kp + 1, kk - 1
322  kx = kx + j - 1
323  t = ap( knc+j-1 )
324  ap( knc+j-1 ) = ap( kx )
325  ap( kx ) = t
326  30 CONTINUE
327  t = ap( knc+kk-1 )
328  ap( knc+kk-1 ) = ap( kpc+kp-1 )
329  ap( kpc+kp-1 ) = t
330  IF( kstep.EQ.2 ) THEN
331  t = ap( kc+k-2 )
332  ap( kc+k-2 ) = ap( kc+kp-1 )
333  ap( kc+kp-1 ) = t
334  END IF
335  END IF
336 *
337 * Update the leading submatrix
338 *
339  IF( kstep.EQ.1 ) THEN
340 *
341 * 1-by-1 pivot block D(k): column k now holds
342 *
343 * W(k) = U(k)*D(k)
344 *
345 * where U(k) is the k-th column of U
346 *
347 * Perform a rank-1 update of A(1:k-1,1:k-1) as
348 *
349 * A := A - U(k)*D(k)*U(k)**T = A - W(k)*1/D(k)*W(k)**T
350 *
351  r1 = cone / ap( kc+k-1 )
352  CALL zspr( uplo, k-1, -r1, ap( kc ), 1, ap )
353 *
354 * Store U(k) in column k
355 *
356  CALL zscal( k-1, r1, ap( kc ), 1 )
357  ELSE
358 *
359 * 2-by-2 pivot block D(k): columns k and k-1 now hold
360 *
361 * ( W(k-1) W(k) ) = ( U(k-1) U(k) )*D(k)
362 *
363 * where U(k) and U(k-1) are the k-th and (k-1)-th columns
364 * of U
365 *
366 * Perform a rank-2 update of A(1:k-2,1:k-2) as
367 *
368 * A := A - ( U(k-1) U(k) )*D(k)*( U(k-1) U(k) )**T
369 * = A - ( W(k-1) W(k) )*inv(D(k))*( W(k-1) W(k) )**T
370 *
371  IF( k.GT.2 ) THEN
372 *
373  d12 = ap( k-1+( k-1 )*k / 2 )
374  d22 = ap( k-1+( k-2 )*( k-1 ) / 2 ) / d12
375  d11 = ap( k+( k-1 )*k / 2 ) / d12
376  t = cone / ( d11*d22-cone )
377  d12 = t / d12
378 *
379  DO 50 j = k - 2, 1, -1
380  wkm1 = d12*( d11*ap( j+( k-2 )*( k-1 ) / 2 )-
381  \$ ap( j+( k-1 )*k / 2 ) )
382  wk = d12*( d22*ap( j+( k-1 )*k / 2 )-
383  \$ ap( j+( k-2 )*( k-1 ) / 2 ) )
384  DO 40 i = j, 1, -1
385  ap( i+( j-1 )*j / 2 ) = ap( i+( j-1 )*j / 2 ) -
386  \$ ap( i+( k-1 )*k / 2 )*wk -
387  \$ ap( i+( k-2 )*( k-1 ) / 2 )*wkm1
388  40 CONTINUE
389  ap( j+( k-1 )*k / 2 ) = wk
390  ap( j+( k-2 )*( k-1 ) / 2 ) = wkm1
391  50 CONTINUE
392 *
393  END IF
394  END IF
395  END IF
396 *
397 * Store details of the interchanges in IPIV
398 *
399  IF( kstep.EQ.1 ) THEN
400  ipiv( k ) = kp
401  ELSE
402  ipiv( k ) = -kp
403  ipiv( k-1 ) = -kp
404  END IF
405 *
406 * Decrease K and return to the start of the main loop
407 *
408  k = k - kstep
409  kc = knc - k
410  GO TO 10
411 *
412  ELSE
413 *
414 * Factorize A as L*D*L**T using the lower triangle of A
415 *
416 * K is the main loop index, increasing from 1 to N in steps of
417 * 1 or 2
418 *
419  k = 1
420  kc = 1
421  npp = n*( n+1 ) / 2
422  60 CONTINUE
423  knc = kc
424 *
425 * If K > N, exit from loop
426 *
427  IF( k.GT.n )
428  \$ GO TO 110
429  kstep = 1
430 *
431 * Determine rows and columns to be interchanged and whether
432 * a 1-by-1 or 2-by-2 pivot block will be used
433 *
434  absakk = cabs1( ap( kc ) )
435 *
436 * IMAX is the row-index of the largest off-diagonal element in
437 * column K, and COLMAX is its absolute value
438 *
439  IF( k.LT.n ) THEN
440  imax = k + izamax( n-k, ap( kc+1 ), 1 )
441  colmax = cabs1( ap( kc+imax-k ) )
442  ELSE
443  colmax = zero
444  END IF
445 *
446  IF( max( absakk, colmax ).EQ.zero ) THEN
447 *
448 * Column K is zero: set INFO and continue
449 *
450  IF( info.EQ.0 )
451  \$ info = k
452  kp = k
453  ELSE
454  IF( absakk.GE.alpha*colmax ) THEN
455 *
456 * no interchange, use 1-by-1 pivot block
457 *
458  kp = k
459  ELSE
460 *
461 * JMAX is the column-index of the largest off-diagonal
462 * element in row IMAX, and ROWMAX is its absolute value
463 *
464  rowmax = zero
465  kx = kc + imax - k
466  DO 70 j = k, imax - 1
467  IF( cabs1( ap( kx ) ).GT.rowmax ) THEN
468  rowmax = cabs1( ap( kx ) )
469  jmax = j
470  END IF
471  kx = kx + n - j
472  70 CONTINUE
473  kpc = npp - ( n-imax+1 )*( n-imax+2 ) / 2 + 1
474  IF( imax.LT.n ) THEN
475  jmax = imax + izamax( n-imax, ap( kpc+1 ), 1 )
476  rowmax = max( rowmax, cabs1( ap( kpc+jmax-imax ) ) )
477  END IF
478 *
479  IF( absakk.GE.alpha*colmax*( colmax / rowmax ) ) THEN
480 *
481 * no interchange, use 1-by-1 pivot block
482 *
483  kp = k
484  ELSE IF( cabs1( ap( kpc ) ).GE.alpha*rowmax ) THEN
485 *
486 * interchange rows and columns K and IMAX, use 1-by-1
487 * pivot block
488 *
489  kp = imax
490  ELSE
491 *
492 * interchange rows and columns K+1 and IMAX, use 2-by-2
493 * pivot block
494 *
495  kp = imax
496  kstep = 2
497  END IF
498  END IF
499 *
500  kk = k + kstep - 1
501  IF( kstep.EQ.2 )
502  \$ knc = knc + n - k + 1
503  IF( kp.NE.kk ) THEN
504 *
505 * Interchange rows and columns KK and KP in the trailing
506 * submatrix A(k:n,k:n)
507 *
508  IF( kp.LT.n )
509  \$ CALL zswap( n-kp, ap( knc+kp-kk+1 ), 1, ap( kpc+1 ),
510  \$ 1 )
511  kx = knc + kp - kk
512  DO 80 j = kk + 1, kp - 1
513  kx = kx + n - j + 1
514  t = ap( knc+j-kk )
515  ap( knc+j-kk ) = ap( kx )
516  ap( kx ) = t
517  80 CONTINUE
518  t = ap( knc )
519  ap( knc ) = ap( kpc )
520  ap( kpc ) = t
521  IF( kstep.EQ.2 ) THEN
522  t = ap( kc+1 )
523  ap( kc+1 ) = ap( kc+kp-k )
524  ap( kc+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  r1 = cone / ap( kc )
545  CALL zspr( uplo, n-k, -r1, ap( kc+1 ), 1,
546  \$ ap( kc+n-k+1 ) )
547 *
548 * Store L(k) in column K
549 *
550  CALL zscal( n-k, r1, ap( kc+1 ), 1 )
551  END IF
552  ELSE
553 *
554 * 2-by-2 pivot block D(k): columns K and K+1 now hold
555 *
556 * ( W(k) W(k+1) ) = ( L(k) L(k+1) )*D(k)
557 *
558 * where L(k) and L(k+1) are the k-th and (k+1)-th columns
559 * of L
560 *
561  IF( k.LT.n-1 ) THEN
562 *
563 * Perform a rank-2 update of A(k+2:n,k+2:n) as
564 *
565 * A := A - ( L(k) L(k+1) )*D(k)*( L(k) L(k+1) )**T
566 * = A - ( W(k) W(k+1) )*inv(D(k))*( W(k) W(k+1) )**T
567 *
568 * where L(k) and L(k+1) are the k-th and (k+1)-th
569 * columns of L
570 *
571  d21 = ap( k+1+( k-1 )*( 2*n-k ) / 2 )
572  d11 = ap( k+1+k*( 2*n-k-1 ) / 2 ) / d21
573  d22 = ap( k+( k-1 )*( 2*n-k ) / 2 ) / d21
574  t = cone / ( d11*d22-cone )
575  d21 = t / d21
576 *
577  DO 100 j = k + 2, n
578  wk = d21*( d11*ap( j+( k-1 )*( 2*n-k ) / 2 )-
579  \$ ap( j+k*( 2*n-k-1 ) / 2 ) )
580  wkp1 = d21*( d22*ap( j+k*( 2*n-k-1 ) / 2 )-
581  \$ ap( j+( k-1 )*( 2*n-k ) / 2 ) )
582  DO 90 i = j, n
583  ap( i+( j-1 )*( 2*n-j ) / 2 ) = ap( i+( j-1 )*
584  \$ ( 2*n-j ) / 2 ) - ap( i+( k-1 )*( 2*n-k ) /
585  \$ 2 )*wk - ap( i+k*( 2*n-k-1 ) / 2 )*wkp1
586  90 CONTINUE
587  ap( j+( k-1 )*( 2*n-k ) / 2 ) = wk
588  ap( j+k*( 2*n-k-1 ) / 2 ) = wkp1
589  100 CONTINUE
590  END IF
591  END IF
592  END IF
593 *
594 * Store details of the interchanges in IPIV
595 *
596  IF( kstep.EQ.1 ) THEN
597  ipiv( k ) = kp
598  ELSE
599  ipiv( k ) = -kp
600  ipiv( k+1 ) = -kp
601  END IF
602 *
603 * Increase K and return to the start of the main loop
604 *
605  k = k + kstep
606  kc = knc + n - k + 2
607  GO TO 60
608 *
609  END IF
610 *
611  110 CONTINUE
612  RETURN
613 *
614 * End of ZSPTRF
615 *
616  END
subroutine xerbla(SRNAME, INFO)
XERBLA
Definition: xerbla.f:60
subroutine zswap(N, ZX, INCX, ZY, INCY)
ZSWAP
Definition: zswap.f:81
subroutine zscal(N, ZA, ZX, INCX)
ZSCAL
Definition: zscal.f:78
subroutine zspr(UPLO, N, ALPHA, X, INCX, AP)
ZSPR performs the symmetrical rank-1 update of a complex symmetric packed matrix.
Definition: zspr.f:132
subroutine zsptrf(UPLO, N, AP, IPIV, INFO)
ZSPTRF
Definition: zsptrf.f:158