1 SUBROUTINE DSYEQUB( UPLO, N, A, LDA, S, SCOND, AMAX, WORK, INFO )
2 *
3 * -- LAPACK routine (version 3.2.2) --
4 * -- Contributed by James Demmel, Deaglan Halligan, Yozo Hida and --
5 * -- Jason Riedy of Univ. of California Berkeley. --
6 * -- June 2010 --
7 *
8 * -- LAPACK is a software package provided by Univ. of Tennessee, --
9 * -- Univ. of California Berkeley and NAG Ltd. --
10 *
11 IMPLICIT NONE
12 * ..
13 * .. Scalar Arguments ..
14 INTEGER INFO, LDA, N
15 DOUBLE PRECISION AMAX, SCOND
16 CHARACTER UPLO
17 * ..
18 * .. Array Arguments ..
19 DOUBLE PRECISION A( LDA, * ), S( * ), WORK( * )
20 * ..
21 *
22 * Purpose
23 * =======
24 *
25 * DSYEQUB computes row and column scalings intended to equilibrate a
26 * symmetric matrix A and reduce its condition number
27 * (with respect to the two-norm). S contains the scale factors,
28 * S(i) = 1/sqrt(A(i,i)), chosen so that the scaled matrix B with
29 * elements B(i,j) = S(i)*A(i,j)*S(j) has ones on the diagonal. This
30 * choice of S puts the condition number of B within a factor N of the
31 * smallest possible condition number over all possible diagonal
32 * scalings.
33 *
34 * Arguments
35 * =========
36 *
37 * UPLO (input) CHARACTER*1
38 * Specifies whether the details of the factorization are stored
39 * as an upper or lower triangular matrix.
40 * = 'U': Upper triangular, form is A = U*D*U**T;
41 * = 'L': Lower triangular, form is A = L*D*L**T.
42 *
43 * N (input) INTEGER
44 * The order of the matrix A. N >= 0.
45 *
46 * A (input) DOUBLE PRECISION array, dimension (LDA,N)
47 * The N-by-N symmetric matrix whose scaling
48 * factors are to be computed. Only the diagonal elements of A
49 * are referenced.
50 *
51 * LDA (input) INTEGER
52 * The leading dimension of the array A. LDA >= max(1,N).
53 *
54 * S (output) DOUBLE PRECISION array, dimension (N)
55 * If INFO = 0, S contains the scale factors for A.
56 *
57 * SCOND (output) DOUBLE PRECISION
58 * If INFO = 0, S contains the ratio of the smallest S(i) to
59 * the largest S(i). If SCOND >= 0.1 and AMAX is neither too
60 * large nor too small, it is not worth scaling by S.
61 *
62 * AMAX (output) DOUBLE PRECISION
63 * Absolute value of largest matrix element. If AMAX is very
64 * close to overflow or very close to underflow, the matrix
65 * should be scaled.
66 *
67 * WORK (workspace) DOUBLE PRECISION array, dimension (3*N)
68 *
69 * INFO (output) INTEGER
70 * = 0: successful exit
71 * < 0: if INFO = -i, the i-th argument had an illegal value
72 * > 0: if INFO = i, the i-th diagonal element is nonpositive.
73 *
74 * Further Details
75 * ======= =======
76 *
77 * Reference: Livne, O.E. and Golub, G.H., "Scaling by Binormalization",
78 * Numerical Algorithms, vol. 35, no. 1, pp. 97-120, January 2004.
79 * DOI 10.1023/B:NUMA.0000016606.32820.69
80 * Tech report version: http://ruready.utah.edu/archive/papers/bin.pdf
81 *
82 * =====================================================================
83 *
84 * .. Parameters ..
85 DOUBLE PRECISION ONE, ZERO
86 PARAMETER ( ONE = 1.0D+0, ZERO = 0.0D+0 )
87 INTEGER MAX_ITER
88 PARAMETER ( MAX_ITER = 100 )
89 * ..
90 * .. Local Scalars ..
91 INTEGER I, J, ITER
92 DOUBLE PRECISION AVG, STD, TOL, C0, C1, C2, T, U, SI, D, BASE,
93 $ SMIN, SMAX, SMLNUM, BIGNUM, SCALE, SUMSQ
94 LOGICAL UP
95 * ..
96 * .. External Functions ..
97 DOUBLE PRECISION DLAMCH
98 LOGICAL LSAME
99 EXTERNAL DLAMCH, LSAME
100 * ..
101 * .. External Subroutines ..
102 EXTERNAL DLASSQ
103 * ..
104 * .. Intrinsic Functions ..
105 INTRINSIC ABS, INT, LOG, MAX, MIN, SQRT
106 * ..
107 * .. Executable Statements ..
108 *
109 * Test input parameters.
110 *
111 INFO = 0
112 IF ( .NOT. ( LSAME( UPLO, 'U' ) .OR. LSAME( UPLO, 'L' ) ) ) THEN
113 INFO = -1
114 ELSE IF ( N .LT. 0 ) THEN
115 INFO = -2
116 ELSE IF ( LDA .LT. MAX( 1, N ) ) THEN
117 INFO = -4
118 END IF
119 IF ( INFO .NE. 0 ) THEN
120 CALL XERBLA( 'DSYEQUB', -INFO )
121 RETURN
122 END IF
123
124 UP = LSAME( UPLO, 'U' )
125 AMAX = ZERO
126 *
127 * Quick return if possible.
128 *
129 IF ( N .EQ. 0 ) THEN
130 SCOND = ONE
131 RETURN
132 END IF
133
134 DO I = 1, N
135 S( I ) = ZERO
136 END DO
137
138 AMAX = ZERO
139 IF ( UP ) THEN
140 DO J = 1, N
141 DO I = 1, J-1
142 S( I ) = MAX( S( I ), ABS( A( I, J ) ) )
143 S( J ) = MAX( S( J ), ABS( A( I, J ) ) )
144 AMAX = MAX( AMAX, ABS( A(I, J) ) )
145 END DO
146 S( J ) = MAX( S( J ), ABS( A( J, J ) ) )
147 AMAX = MAX( AMAX, ABS( A( J, J ) ) )
148 END DO
149 ELSE
150 DO J = 1, N
151 S( J ) = MAX( S( J ), ABS( A( J, J ) ) )
152 AMAX = MAX( AMAX, ABS( A( J, J ) ) )
153 DO I = J+1, N
154 S( I ) = MAX( S( I ), ABS( A( I, J ) ) )
155 S( J ) = MAX( S( J ), ABS( A( I, J ) ) )
156 AMAX = MAX( AMAX, ABS( A( I, J ) ) )
157 END DO
158 END DO
159 END IF
160 DO J = 1, N
161 S( J ) = 1.0D+0 / S( J )
162 END DO
163
164 TOL = ONE / SQRT(2.0D0 * N)
165
166 DO ITER = 1, MAX_ITER
167 SCALE = 0.0D+0
168 SUMSQ = 0.0D+0
169 * BETA = |A|S
170 DO I = 1, N
171 WORK(I) = ZERO
172 END DO
173 IF ( UP ) THEN
174 DO J = 1, N
175 DO I = 1, J-1
176 T = ABS( A( I, J ) )
177 WORK( I ) = WORK( I ) + ABS( A( I, J ) ) * S( J )
178 WORK( J ) = WORK( J ) + ABS( A( I, J ) ) * S( I )
179 END DO
180 WORK( J ) = WORK( J ) + ABS( A( J, J ) ) * S( J )
181 END DO
182 ELSE
183 DO J = 1, N
184 WORK( J ) = WORK( J ) + ABS( A( J, J ) ) * S( J )
185 DO I = J+1, N
186 T = ABS( A( I, J ) )
187 WORK( I ) = WORK( I ) + ABS( A( I, J ) ) * S( J )
188 WORK( J ) = WORK( J ) + ABS( A( I, J ) ) * S( I )
189 END DO
190 END DO
191 END IF
192
193 * avg = s^T beta / n
194 AVG = 0.0D+0
195 DO I = 1, N
196 AVG = AVG + S( I )*WORK( I )
197 END DO
198 AVG = AVG / N
199
200 STD = 0.0D+0
201 DO I = 2*N+1, 3*N
202 WORK( I ) = S( I-2*N ) * WORK( I-2*N ) - AVG
203 END DO
204 CALL DLASSQ( N, WORK( 2*N+1 ), 1, SCALE, SUMSQ )
205 STD = SCALE * SQRT( SUMSQ / N )
206
207 IF ( STD .LT. TOL * AVG ) GOTO 999
208
209 DO I = 1, N
210 T = ABS( A( I, I ) )
211 SI = S( I )
212 C2 = ( N-1 ) * T
213 C1 = ( N-2 ) * ( WORK( I ) - T*SI )
214 C0 = -(T*SI)*SI + 2*WORK( I )*SI - N*AVG
215 D = C1*C1 - 4*C0*C2
216
217 IF ( D .LE. 0 ) THEN
218 INFO = -1
219 RETURN
220 END IF
221 SI = -2*C0 / ( C1 + SQRT( D ) )
222
223 D = SI - S( I )
224 U = ZERO
225 IF ( UP ) THEN
226 DO J = 1, I
227 T = ABS( A( J, I ) )
228 U = U + S( J )*T
229 WORK( J ) = WORK( J ) + D*T
230 END DO
231 DO J = I+1,N
232 T = ABS( A( I, J ) )
233 U = U + S( J )*T
234 WORK( J ) = WORK( J ) + D*T
235 END DO
236 ELSE
237 DO J = 1, I
238 T = ABS( A( I, J ) )
239 U = U + S( J )*T
240 WORK( J ) = WORK( J ) + D*T
241 END DO
242 DO J = I+1,N
243 T = ABS( A( J, I ) )
244 U = U + S( J )*T
245 WORK( J ) = WORK( J ) + D*T
246 END DO
247 END IF
248
249 AVG = AVG + ( U + WORK( I ) ) * D / N
250 S( I ) = SI
251
252 END DO
253
254 END DO
255
256 999 CONTINUE
257
258 SMLNUM = DLAMCH( 'SAFEMIN' )
259 BIGNUM = ONE / SMLNUM
260 SMIN = BIGNUM
261 SMAX = ZERO
262 T = ONE / SQRT(AVG)
263 BASE = DLAMCH( 'B' )
264 U = ONE / LOG( BASE )
265 DO I = 1, N
266 S( I ) = BASE ** INT( U * LOG( S( I ) * T ) )
267 SMIN = MIN( SMIN, S( I ) )
268 SMAX = MAX( SMAX, S( I ) )
269 END DO
270 SCOND = MAX( SMIN, SMLNUM ) / MIN( SMAX, BIGNUM )
271 *
272 END
2 *
3 * -- LAPACK routine (version 3.2.2) --
4 * -- Contributed by James Demmel, Deaglan Halligan, Yozo Hida and --
5 * -- Jason Riedy of Univ. of California Berkeley. --
6 * -- June 2010 --
7 *
8 * -- LAPACK is a software package provided by Univ. of Tennessee, --
9 * -- Univ. of California Berkeley and NAG Ltd. --
10 *
11 IMPLICIT NONE
12 * ..
13 * .. Scalar Arguments ..
14 INTEGER INFO, LDA, N
15 DOUBLE PRECISION AMAX, SCOND
16 CHARACTER UPLO
17 * ..
18 * .. Array Arguments ..
19 DOUBLE PRECISION A( LDA, * ), S( * ), WORK( * )
20 * ..
21 *
22 * Purpose
23 * =======
24 *
25 * DSYEQUB computes row and column scalings intended to equilibrate a
26 * symmetric matrix A and reduce its condition number
27 * (with respect to the two-norm). S contains the scale factors,
28 * S(i) = 1/sqrt(A(i,i)), chosen so that the scaled matrix B with
29 * elements B(i,j) = S(i)*A(i,j)*S(j) has ones on the diagonal. This
30 * choice of S puts the condition number of B within a factor N of the
31 * smallest possible condition number over all possible diagonal
32 * scalings.
33 *
34 * Arguments
35 * =========
36 *
37 * UPLO (input) CHARACTER*1
38 * Specifies whether the details of the factorization are stored
39 * as an upper or lower triangular matrix.
40 * = 'U': Upper triangular, form is A = U*D*U**T;
41 * = 'L': Lower triangular, form is A = L*D*L**T.
42 *
43 * N (input) INTEGER
44 * The order of the matrix A. N >= 0.
45 *
46 * A (input) DOUBLE PRECISION array, dimension (LDA,N)
47 * The N-by-N symmetric matrix whose scaling
48 * factors are to be computed. Only the diagonal elements of A
49 * are referenced.
50 *
51 * LDA (input) INTEGER
52 * The leading dimension of the array A. LDA >= max(1,N).
53 *
54 * S (output) DOUBLE PRECISION array, dimension (N)
55 * If INFO = 0, S contains the scale factors for A.
56 *
57 * SCOND (output) DOUBLE PRECISION
58 * If INFO = 0, S contains the ratio of the smallest S(i) to
59 * the largest S(i). If SCOND >= 0.1 and AMAX is neither too
60 * large nor too small, it is not worth scaling by S.
61 *
62 * AMAX (output) DOUBLE PRECISION
63 * Absolute value of largest matrix element. If AMAX is very
64 * close to overflow or very close to underflow, the matrix
65 * should be scaled.
66 *
67 * WORK (workspace) DOUBLE PRECISION array, dimension (3*N)
68 *
69 * INFO (output) INTEGER
70 * = 0: successful exit
71 * < 0: if INFO = -i, the i-th argument had an illegal value
72 * > 0: if INFO = i, the i-th diagonal element is nonpositive.
73 *
74 * Further Details
75 * ======= =======
76 *
77 * Reference: Livne, O.E. and Golub, G.H., "Scaling by Binormalization",
78 * Numerical Algorithms, vol. 35, no. 1, pp. 97-120, January 2004.
79 * DOI 10.1023/B:NUMA.0000016606.32820.69
80 * Tech report version: http://ruready.utah.edu/archive/papers/bin.pdf
81 *
82 * =====================================================================
83 *
84 * .. Parameters ..
85 DOUBLE PRECISION ONE, ZERO
86 PARAMETER ( ONE = 1.0D+0, ZERO = 0.0D+0 )
87 INTEGER MAX_ITER
88 PARAMETER ( MAX_ITER = 100 )
89 * ..
90 * .. Local Scalars ..
91 INTEGER I, J, ITER
92 DOUBLE PRECISION AVG, STD, TOL, C0, C1, C2, T, U, SI, D, BASE,
93 $ SMIN, SMAX, SMLNUM, BIGNUM, SCALE, SUMSQ
94 LOGICAL UP
95 * ..
96 * .. External Functions ..
97 DOUBLE PRECISION DLAMCH
98 LOGICAL LSAME
99 EXTERNAL DLAMCH, LSAME
100 * ..
101 * .. External Subroutines ..
102 EXTERNAL DLASSQ
103 * ..
104 * .. Intrinsic Functions ..
105 INTRINSIC ABS, INT, LOG, MAX, MIN, SQRT
106 * ..
107 * .. Executable Statements ..
108 *
109 * Test input parameters.
110 *
111 INFO = 0
112 IF ( .NOT. ( LSAME( UPLO, 'U' ) .OR. LSAME( UPLO, 'L' ) ) ) THEN
113 INFO = -1
114 ELSE IF ( N .LT. 0 ) THEN
115 INFO = -2
116 ELSE IF ( LDA .LT. MAX( 1, N ) ) THEN
117 INFO = -4
118 END IF
119 IF ( INFO .NE. 0 ) THEN
120 CALL XERBLA( 'DSYEQUB', -INFO )
121 RETURN
122 END IF
123
124 UP = LSAME( UPLO, 'U' )
125 AMAX = ZERO
126 *
127 * Quick return if possible.
128 *
129 IF ( N .EQ. 0 ) THEN
130 SCOND = ONE
131 RETURN
132 END IF
133
134 DO I = 1, N
135 S( I ) = ZERO
136 END DO
137
138 AMAX = ZERO
139 IF ( UP ) THEN
140 DO J = 1, N
141 DO I = 1, J-1
142 S( I ) = MAX( S( I ), ABS( A( I, J ) ) )
143 S( J ) = MAX( S( J ), ABS( A( I, J ) ) )
144 AMAX = MAX( AMAX, ABS( A(I, J) ) )
145 END DO
146 S( J ) = MAX( S( J ), ABS( A( J, J ) ) )
147 AMAX = MAX( AMAX, ABS( A( J, J ) ) )
148 END DO
149 ELSE
150 DO J = 1, N
151 S( J ) = MAX( S( J ), ABS( A( J, J ) ) )
152 AMAX = MAX( AMAX, ABS( A( J, J ) ) )
153 DO I = J+1, N
154 S( I ) = MAX( S( I ), ABS( A( I, J ) ) )
155 S( J ) = MAX( S( J ), ABS( A( I, J ) ) )
156 AMAX = MAX( AMAX, ABS( A( I, J ) ) )
157 END DO
158 END DO
159 END IF
160 DO J = 1, N
161 S( J ) = 1.0D+0 / S( J )
162 END DO
163
164 TOL = ONE / SQRT(2.0D0 * N)
165
166 DO ITER = 1, MAX_ITER
167 SCALE = 0.0D+0
168 SUMSQ = 0.0D+0
169 * BETA = |A|S
170 DO I = 1, N
171 WORK(I) = ZERO
172 END DO
173 IF ( UP ) THEN
174 DO J = 1, N
175 DO I = 1, J-1
176 T = ABS( A( I, J ) )
177 WORK( I ) = WORK( I ) + ABS( A( I, J ) ) * S( J )
178 WORK( J ) = WORK( J ) + ABS( A( I, J ) ) * S( I )
179 END DO
180 WORK( J ) = WORK( J ) + ABS( A( J, J ) ) * S( J )
181 END DO
182 ELSE
183 DO J = 1, N
184 WORK( J ) = WORK( J ) + ABS( A( J, J ) ) * S( J )
185 DO I = J+1, N
186 T = ABS( A( I, J ) )
187 WORK( I ) = WORK( I ) + ABS( A( I, J ) ) * S( J )
188 WORK( J ) = WORK( J ) + ABS( A( I, J ) ) * S( I )
189 END DO
190 END DO
191 END IF
192
193 * avg = s^T beta / n
194 AVG = 0.0D+0
195 DO I = 1, N
196 AVG = AVG + S( I )*WORK( I )
197 END DO
198 AVG = AVG / N
199
200 STD = 0.0D+0
201 DO I = 2*N+1, 3*N
202 WORK( I ) = S( I-2*N ) * WORK( I-2*N ) - AVG
203 END DO
204 CALL DLASSQ( N, WORK( 2*N+1 ), 1, SCALE, SUMSQ )
205 STD = SCALE * SQRT( SUMSQ / N )
206
207 IF ( STD .LT. TOL * AVG ) GOTO 999
208
209 DO I = 1, N
210 T = ABS( A( I, I ) )
211 SI = S( I )
212 C2 = ( N-1 ) * T
213 C1 = ( N-2 ) * ( WORK( I ) - T*SI )
214 C0 = -(T*SI)*SI + 2*WORK( I )*SI - N*AVG
215 D = C1*C1 - 4*C0*C2
216
217 IF ( D .LE. 0 ) THEN
218 INFO = -1
219 RETURN
220 END IF
221 SI = -2*C0 / ( C1 + SQRT( D ) )
222
223 D = SI - S( I )
224 U = ZERO
225 IF ( UP ) THEN
226 DO J = 1, I
227 T = ABS( A( J, I ) )
228 U = U + S( J )*T
229 WORK( J ) = WORK( J ) + D*T
230 END DO
231 DO J = I+1,N
232 T = ABS( A( I, J ) )
233 U = U + S( J )*T
234 WORK( J ) = WORK( J ) + D*T
235 END DO
236 ELSE
237 DO J = 1, I
238 T = ABS( A( I, J ) )
239 U = U + S( J )*T
240 WORK( J ) = WORK( J ) + D*T
241 END DO
242 DO J = I+1,N
243 T = ABS( A( J, I ) )
244 U = U + S( J )*T
245 WORK( J ) = WORK( J ) + D*T
246 END DO
247 END IF
248
249 AVG = AVG + ( U + WORK( I ) ) * D / N
250 S( I ) = SI
251
252 END DO
253
254 END DO
255
256 999 CONTINUE
257
258 SMLNUM = DLAMCH( 'SAFEMIN' )
259 BIGNUM = ONE / SMLNUM
260 SMIN = BIGNUM
261 SMAX = ZERO
262 T = ONE / SQRT(AVG)
263 BASE = DLAMCH( 'B' )
264 U = ONE / LOG( BASE )
265 DO I = 1, N
266 S( I ) = BASE ** INT( U * LOG( S( I ) * T ) )
267 SMIN = MIN( SMIN, S( I ) )
268 SMAX = MAX( SMAX, S( I ) )
269 END DO
270 SCOND = MAX( SMIN, SMLNUM ) / MIN( SMAX, BIGNUM )
271 *
272 END