001:       SUBROUTINE DGEBAL( JOB, N, A, LDA, ILO, IHI, SCALE, INFO )
002: *
003: *  -- LAPACK routine (version 3.2) --
004: *     Univ. of Tennessee, Univ. of California Berkeley and NAG Ltd..
005: *     November 2006
006: *
007: *     .. Scalar Arguments ..
008:       CHARACTER          JOB
009:       INTEGER            IHI, ILO, INFO, LDA, N
010: *     ..
011: *     .. Array Arguments ..
012:       DOUBLE PRECISION   A( LDA, * ), SCALE( * )
013: *     ..
014: *
015: *  Purpose
016: *  =======
017: *
018: *  DGEBAL balances a general real matrix A.  This involves, first,
019: *  permuting A by a similarity transformation to isolate eigenvalues
020: *  in the first 1 to ILO-1 and last IHI+1 to N elements on the
021: *  diagonal; and second, applying a diagonal similarity transformation
022: *  to rows and columns ILO to IHI to make the rows and columns as
023: *  close in norm as possible.  Both steps are optional.
024: *
025: *  Balancing may reduce the 1-norm of the matrix, and improve the
026: *  accuracy of the computed eigenvalues and/or eigenvectors.
027: *
028: *  Arguments
029: *  =========
030: *
031: *  JOB     (input) CHARACTER*1
032: *          Specifies the operations to be performed on A:
033: *          = 'N':  none:  simply set ILO = 1, IHI = N, SCALE(I) = 1.0
034: *                  for i = 1,...,N;
035: *          = 'P':  permute only;
036: *          = 'S':  scale only;
037: *          = 'B':  both permute and scale.
038: *
039: *  N       (input) INTEGER
040: *          The order of the matrix A.  N >= 0.
041: *
042: *  A       (input/output) DOUBLE PRECISION array, dimension (LDA,N)
043: *          On entry, the input matrix A.
044: *          On exit,  A is overwritten by the balanced matrix.
045: *          If JOB = 'N', A is not referenced.
046: *          See Further Details.
047: *
048: *  LDA     (input) INTEGER
049: *          The leading dimension of the array A.  LDA >= max(1,N).
050: *
051: *  ILO     (output) INTEGER
052: *  IHI     (output) INTEGER
053: *          ILO and IHI are set to integers such that on exit
054: *          A(i,j) = 0 if i > j and j = 1,...,ILO-1 or I = IHI+1,...,N.
055: *          If JOB = 'N' or 'S', ILO = 1 and IHI = N.
056: *
057: *  SCALE   (output) DOUBLE PRECISION array, dimension (N)
058: *          Details of the permutations and scaling factors applied to
059: *          A.  If P(j) is the index of the row and column interchanged
060: *          with row and column j and D(j) is the scaling factor
061: *          applied to row and column j, then
062: *          SCALE(j) = P(j)    for j = 1,...,ILO-1
063: *                   = D(j)    for j = ILO,...,IHI
064: *                   = P(j)    for j = IHI+1,...,N.
065: *          The order in which the interchanges are made is N to IHI+1,
066: *          then 1 to ILO-1.
067: *
068: *  INFO    (output) INTEGER
069: *          = 0:  successful exit.
070: *          < 0:  if INFO = -i, the i-th argument had an illegal value.
071: *
072: *  Further Details
073: *  ===============
074: *
075: *  The permutations consist of row and column interchanges which put
076: *  the matrix in the form
077: *
078: *             ( T1   X   Y  )
079: *     P A P = (  0   B   Z  )
080: *             (  0   0   T2 )
081: *
082: *  where T1 and T2 are upper triangular matrices whose eigenvalues lie
083: *  along the diagonal.  The column indices ILO and IHI mark the starting
084: *  and ending columns of the submatrix B. Balancing consists of applying
085: *  a diagonal similarity transformation inv(D) * B * D to make the
086: *  1-norms of each row of B and its corresponding column nearly equal.
087: *  The output matrix is
088: *
089: *     ( T1     X*D          Y    )
090: *     (  0  inv(D)*B*D  inv(D)*Z ).
091: *     (  0      0           T2   )
092: *
093: *  Information about the permutations P and the diagonal matrix D is
094: *  returned in the vector SCALE.
095: *
096: *  This subroutine is based on the EISPACK routine BALANC.
097: *
098: *  Modified by Tzu-Yi Chen, Computer Science Division, University of
099: *    California at Berkeley, USA
100: *
101: *  =====================================================================
102: *
103: *     .. Parameters ..
104:       DOUBLE PRECISION   ZERO, ONE
105:       PARAMETER          ( ZERO = 0.0D+0, ONE = 1.0D+0 )
106:       DOUBLE PRECISION   SCLFAC
107:       PARAMETER          ( SCLFAC = 2.0D+0 )
108:       DOUBLE PRECISION   FACTOR
109:       PARAMETER          ( FACTOR = 0.95D+0 )
110: *     ..
111: *     .. Local Scalars ..
112:       LOGICAL            NOCONV
113:       INTEGER            I, ICA, IEXC, IRA, J, K, L, M
114:       DOUBLE PRECISION   C, CA, F, G, R, RA, S, SFMAX1, SFMAX2, SFMIN1,
115:      $                   SFMIN2
116: *     ..
117: *     .. External Functions ..
118:       LOGICAL            LSAME
119:       INTEGER            IDAMAX
120:       DOUBLE PRECISION   DLAMCH
121:       EXTERNAL           LSAME, IDAMAX, DLAMCH
122: *     ..
123: *     .. External Subroutines ..
124:       EXTERNAL           DSCAL, DSWAP, XERBLA
125: *     ..
126: *     .. Intrinsic Functions ..
127:       INTRINSIC          ABS, MAX, MIN
128: *     ..
129: *     .. Executable Statements ..
130: *
131: *     Test the input parameters
132: *
133:       INFO = 0
134:       IF( .NOT.LSAME( JOB, 'N' ) .AND. .NOT.LSAME( JOB, 'P' ) .AND.
135:      $    .NOT.LSAME( JOB, 'S' ) .AND. .NOT.LSAME( JOB, 'B' ) ) THEN
136:          INFO = -1
137:       ELSE IF( N.LT.0 ) THEN
138:          INFO = -2
139:       ELSE IF( LDA.LT.MAX( 1, N ) ) THEN
140:          INFO = -4
141:       END IF
142:       IF( INFO.NE.0 ) THEN
143:          CALL XERBLA( 'DGEBAL', -INFO )
144:          RETURN
145:       END IF
146: *
147:       K = 1
148:       L = N
149: *
150:       IF( N.EQ.0 )
151:      $   GO TO 210
152: *
153:       IF( LSAME( JOB, 'N' ) ) THEN
154:          DO 10 I = 1, N
155:             SCALE( I ) = ONE
156:    10    CONTINUE
157:          GO TO 210
158:       END IF
159: *
160:       IF( LSAME( JOB, 'S' ) )
161:      $   GO TO 120
162: *
163: *     Permutation to isolate eigenvalues if possible
164: *
165:       GO TO 50
166: *
167: *     Row and column exchange.
168: *
169:    20 CONTINUE
170:       SCALE( M ) = J
171:       IF( J.EQ.M )
172:      $   GO TO 30
173: *
174:       CALL DSWAP( L, A( 1, J ), 1, A( 1, M ), 1 )
175:       CALL DSWAP( N-K+1, A( J, K ), LDA, A( M, K ), LDA )
176: *
177:    30 CONTINUE
178:       GO TO ( 40, 80 )IEXC
179: *
180: *     Search for rows isolating an eigenvalue and push them down.
181: *
182:    40 CONTINUE
183:       IF( L.EQ.1 )
184:      $   GO TO 210
185:       L = L - 1
186: *
187:    50 CONTINUE
188:       DO 70 J = L, 1, -1
189: *
190:          DO 60 I = 1, L
191:             IF( I.EQ.J )
192:      $         GO TO 60
193:             IF( A( J, I ).NE.ZERO )
194:      $         GO TO 70
195:    60    CONTINUE
196: *
197:          M = L
198:          IEXC = 1
199:          GO TO 20
200:    70 CONTINUE
201: *
202:       GO TO 90
203: *
204: *     Search for columns isolating an eigenvalue and push them left.
205: *
206:    80 CONTINUE
207:       K = K + 1
208: *
209:    90 CONTINUE
210:       DO 110 J = K, L
211: *
212:          DO 100 I = K, L
213:             IF( I.EQ.J )
214:      $         GO TO 100
215:             IF( A( I, J ).NE.ZERO )
216:      $         GO TO 110
217:   100    CONTINUE
218: *
219:          M = K
220:          IEXC = 2
221:          GO TO 20
222:   110 CONTINUE
223: *
224:   120 CONTINUE
225:       DO 130 I = K, L
226:          SCALE( I ) = ONE
227:   130 CONTINUE
228: *
229:       IF( LSAME( JOB, 'P' ) )
230:      $   GO TO 210
231: *
232: *     Balance the submatrix in rows K to L.
233: *
234: *     Iterative loop for norm reduction
235: *
236:       SFMIN1 = DLAMCH( 'S' ) / DLAMCH( 'P' )
237:       SFMAX1 = ONE / SFMIN1
238:       SFMIN2 = SFMIN1*SCLFAC
239:       SFMAX2 = ONE / SFMIN2
240:   140 CONTINUE
241:       NOCONV = .FALSE.
242: *
243:       DO 200 I = K, L
244:          C = ZERO
245:          R = ZERO
246: *
247:          DO 150 J = K, L
248:             IF( J.EQ.I )
249:      $         GO TO 150
250:             C = C + ABS( A( J, I ) )
251:             R = R + ABS( A( I, J ) )
252:   150    CONTINUE
253:          ICA = IDAMAX( L, A( 1, I ), 1 )
254:          CA = ABS( A( ICA, I ) )
255:          IRA = IDAMAX( N-K+1, A( I, K ), LDA )
256:          RA = ABS( A( I, IRA+K-1 ) )
257: *
258: *        Guard against zero C or R due to underflow.
259: *
260:          IF( C.EQ.ZERO .OR. R.EQ.ZERO )
261:      $      GO TO 200
262:          G = R / SCLFAC
263:          F = ONE
264:          S = C + R
265:   160    CONTINUE
266:          IF( C.GE.G .OR. MAX( F, C, CA ).GE.SFMAX2 .OR.
267:      $       MIN( R, G, RA ).LE.SFMIN2 )GO TO 170
268:          F = F*SCLFAC
269:          C = C*SCLFAC
270:          CA = CA*SCLFAC
271:          R = R / SCLFAC
272:          G = G / SCLFAC
273:          RA = RA / SCLFAC
274:          GO TO 160
275: *
276:   170    CONTINUE
277:          G = C / SCLFAC
278:   180    CONTINUE
279:          IF( G.LT.R .OR. MAX( R, RA ).GE.SFMAX2 .OR.
280:      $       MIN( F, C, G, CA ).LE.SFMIN2 )GO TO 190
281:          F = F / SCLFAC
282:          C = C / SCLFAC
283:          G = G / SCLFAC
284:          CA = CA / SCLFAC
285:          R = R*SCLFAC
286:          RA = RA*SCLFAC
287:          GO TO 180
288: *
289: *        Now balance.
290: *
291:   190    CONTINUE
292:          IF( ( C+R ).GE.FACTOR*S )
293:      $      GO TO 200
294:          IF( F.LT.ONE .AND. SCALE( I ).LT.ONE ) THEN
295:             IF( F*SCALE( I ).LE.SFMIN1 )
296:      $         GO TO 200
297:          END IF
298:          IF( F.GT.ONE .AND. SCALE( I ).GT.ONE ) THEN
299:             IF( SCALE( I ).GE.SFMAX1 / F )
300:      $         GO TO 200
301:          END IF
302:          G = ONE / F
303:          SCALE( I ) = SCALE( I )*F
304:          NOCONV = .TRUE.
305: *
306:          CALL DSCAL( N-K+1, G, A( I, K ), LDA )
307:          CALL DSCAL( L, F, A( 1, I ), 1 )
308: *
309:   200 CONTINUE
310: *
311:       IF( NOCONV )
312:      $   GO TO 140
313: *
314:   210 CONTINUE
315:       ILO = K
316:       IHI = L
317: *
318:       RETURN
319: *
320: *     End of DGEBAL
321: *
322:       END
323: