001:       SUBROUTINE SLASDA( ICOMPQ, SMLSIZ, N, SQRE, D, E, U, LDU, VT, K,
002:      $                   DIFL, DIFR, Z, POLES, GIVPTR, GIVCOL, LDGCOL,
003:      $                   PERM, GIVNUM, C, S, WORK, IWORK, INFO )
004: *
005: *  -- LAPACK auxiliary routine (version 3.2) --
006: *     Univ. of Tennessee, Univ. of California Berkeley and NAG Ltd..
007: *     November 2006
008: *
009: *     .. Scalar Arguments ..
010:       INTEGER            ICOMPQ, INFO, LDGCOL, LDU, N, SMLSIZ, SQRE
011: *     ..
012: *     .. Array Arguments ..
013:       INTEGER            GIVCOL( LDGCOL, * ), GIVPTR( * ), IWORK( * ),
014:      $                   K( * ), PERM( LDGCOL, * )
015:       REAL               C( * ), D( * ), DIFL( LDU, * ), DIFR( LDU, * ),
016:      $                   E( * ), GIVNUM( LDU, * ), POLES( LDU, * ),
017:      $                   S( * ), U( LDU, * ), VT( LDU, * ), WORK( * ),
018:      $                   Z( LDU, * )
019: *     ..
020: *
021: *  Purpose
022: *  =======
023: *
024: *  Using a divide and conquer approach, SLASDA computes the singular
025: *  value decomposition (SVD) of a real upper bidiagonal N-by-M matrix
026: *  B with diagonal D and offdiagonal E, where M = N + SQRE. The
027: *  algorithm computes the singular values in the SVD B = U * S * VT.
028: *  The orthogonal matrices U and VT are optionally computed in
029: *  compact form.
030: *
031: *  A related subroutine, SLASD0, computes the singular values and
032: *  the singular vectors in explicit form.
033: *
034: *  Arguments
035: *  =========
036: *
037: *  ICOMPQ (input) INTEGER
038: *         Specifies whether singular vectors are to be computed
039: *         in compact form, as follows
040: *         = 0: Compute singular values only.
041: *         = 1: Compute singular vectors of upper bidiagonal
042: *              matrix in compact form.
043: *
044: *  SMLSIZ (input) INTEGER
045: *         The maximum size of the subproblems at the bottom of the
046: *         computation tree.
047: *
048: *  N      (input) INTEGER
049: *         The row dimension of the upper bidiagonal matrix. This is
050: *         also the dimension of the main diagonal array D.
051: *
052: *  SQRE   (input) INTEGER
053: *         Specifies the column dimension of the bidiagonal matrix.
054: *         = 0: The bidiagonal matrix has column dimension M = N;
055: *         = 1: The bidiagonal matrix has column dimension M = N + 1.
056: *
057: *  D      (input/output) REAL array, dimension ( N )
058: *         On entry D contains the main diagonal of the bidiagonal
059: *         matrix. On exit D, if INFO = 0, contains its singular values.
060: *
061: *  E      (input) REAL array, dimension ( M-1 )
062: *         Contains the subdiagonal entries of the bidiagonal matrix.
063: *         On exit, E has been destroyed.
064: *
065: *  U      (output) REAL array,
066: *         dimension ( LDU, SMLSIZ ) if ICOMPQ = 1, and not referenced
067: *         if ICOMPQ = 0. If ICOMPQ = 1, on exit, U contains the left
068: *         singular vector matrices of all subproblems at the bottom
069: *         level.
070: *
071: *  LDU    (input) INTEGER, LDU = > N.
072: *         The leading dimension of arrays U, VT, DIFL, DIFR, POLES,
073: *         GIVNUM, and Z.
074: *
075: *  VT     (output) REAL array,
076: *         dimension ( LDU, SMLSIZ+1 ) if ICOMPQ = 1, and not referenced
077: *         if ICOMPQ = 0. If ICOMPQ = 1, on exit, VT' contains the right
078: *         singular vector matrices of all subproblems at the bottom
079: *         level.
080: *
081: *  K      (output) INTEGER array, dimension ( N ) 
082: *         if ICOMPQ = 1 and dimension 1 if ICOMPQ = 0.
083: *         If ICOMPQ = 1, on exit, K(I) is the dimension of the I-th
084: *         secular equation on the computation tree.
085: *
086: *  DIFL   (output) REAL array, dimension ( LDU, NLVL ),
087: *         where NLVL = floor(log_2 (N/SMLSIZ))).
088: *
089: *  DIFR   (output) REAL array,
090: *                  dimension ( LDU, 2 * NLVL ) if ICOMPQ = 1 and
091: *                  dimension ( N ) if ICOMPQ = 0.
092: *         If ICOMPQ = 1, on exit, DIFL(1:N, I) and DIFR(1:N, 2 * I - 1)
093: *         record distances between singular values on the I-th
094: *         level and singular values on the (I -1)-th level, and
095: *         DIFR(1:N, 2 * I ) contains the normalizing factors for
096: *         the right singular vector matrix. See SLASD8 for details.
097: *
098: *  Z      (output) REAL array,
099: *                  dimension ( LDU, NLVL ) if ICOMPQ = 1 and
100: *                  dimension ( N ) if ICOMPQ = 0.
101: *         The first K elements of Z(1, I) contain the components of
102: *         the deflation-adjusted updating row vector for subproblems
103: *         on the I-th level.
104: *
105: *  POLES  (output) REAL array,
106: *         dimension ( LDU, 2 * NLVL ) if ICOMPQ = 1, and not referenced
107: *         if ICOMPQ = 0. If ICOMPQ = 1, on exit, POLES(1, 2*I - 1) and
108: *         POLES(1, 2*I) contain  the new and old singular values
109: *         involved in the secular equations on the I-th level.
110: *
111: *  GIVPTR (output) INTEGER array,
112: *         dimension ( N ) if ICOMPQ = 1, and not referenced if
113: *         ICOMPQ = 0. If ICOMPQ = 1, on exit, GIVPTR( I ) records
114: *         the number of Givens rotations performed on the I-th
115: *         problem on the computation tree.
116: *
117: *  GIVCOL (output) INTEGER array,
118: *         dimension ( LDGCOL, 2 * NLVL ) if ICOMPQ = 1, and not
119: *         referenced if ICOMPQ = 0. If ICOMPQ = 1, on exit, for each I,
120: *         GIVCOL(1, 2 *I - 1) and GIVCOL(1, 2 *I) record the locations
121: *         of Givens rotations performed on the I-th level on the
122: *         computation tree.
123: *
124: *  LDGCOL (input) INTEGER, LDGCOL = > N.
125: *         The leading dimension of arrays GIVCOL and PERM.
126: *
127: *  PERM   (output) INTEGER array, dimension ( LDGCOL, NLVL ) 
128: *         if ICOMPQ = 1, and not referenced
129: *         if ICOMPQ = 0. If ICOMPQ = 1, on exit, PERM(1, I) records
130: *         permutations done on the I-th level of the computation tree.
131: *
132: *  GIVNUM (output) REAL array,
133: *         dimension ( LDU,  2 * NLVL ) if ICOMPQ = 1, and not
134: *         referenced if ICOMPQ = 0. If ICOMPQ = 1, on exit, for each I,
135: *         GIVNUM(1, 2 *I - 1) and GIVNUM(1, 2 *I) record the C- and S-
136: *         values of Givens rotations performed on the I-th level on
137: *         the computation tree.
138: *
139: *  C      (output) REAL array,
140: *         dimension ( N ) if ICOMPQ = 1, and dimension 1 if ICOMPQ = 0.
141: *         If ICOMPQ = 1 and the I-th subproblem is not square, on exit,
142: *         C( I ) contains the C-value of a Givens rotation related to
143: *         the right null space of the I-th subproblem.
144: *
145: *  S      (output) REAL array, dimension ( N ) if
146: *         ICOMPQ = 1, and dimension 1 if ICOMPQ = 0. If ICOMPQ = 1
147: *         and the I-th subproblem is not square, on exit, S( I )
148: *         contains the S-value of a Givens rotation related to
149: *         the right null space of the I-th subproblem.
150: *
151: *  WORK   (workspace) REAL array, dimension
152: *         (6 * N + (SMLSIZ + 1)*(SMLSIZ + 1)).
153: *
154: *  IWORK  (workspace) INTEGER array, dimension (7*N).
155: *
156: *  INFO   (output) INTEGER
157: *          = 0:  successful exit.
158: *          < 0:  if INFO = -i, the i-th argument had an illegal value.
159: *          > 0:  if INFO = 1, an singular value did not converge
160: *
161: *  Further Details
162: *  ===============
163: *
164: *  Based on contributions by
165: *     Ming Gu and Huan Ren, Computer Science Division, University of
166: *     California at Berkeley, USA
167: *
168: *  =====================================================================
169: *
170: *     .. Parameters ..
171:       REAL               ZERO, ONE
172:       PARAMETER          ( ZERO = 0.0E+0, ONE = 1.0E+0 )
173: *     ..
174: *     .. Local Scalars ..
175:       INTEGER            I, I1, IC, IDXQ, IDXQI, IM1, INODE, ITEMP, IWK,
176:      $                   J, LF, LL, LVL, LVL2, M, NCC, ND, NDB1, NDIML,
177:      $                   NDIMR, NL, NLF, NLP1, NLVL, NR, NRF, NRP1, NRU,
178:      $                   NWORK1, NWORK2, SMLSZP, SQREI, VF, VFI, VL, VLI
179:       REAL               ALPHA, BETA
180: *     ..
181: *     .. External Subroutines ..
182:       EXTERNAL           SCOPY, SLASD6, SLASDQ, SLASDT, SLASET, XERBLA
183: *     ..
184: *     .. Executable Statements ..
185: *
186: *     Test the input parameters.
187: *
188:       INFO = 0
189: *
190:       IF( ( ICOMPQ.LT.0 ) .OR. ( ICOMPQ.GT.1 ) ) THEN
191:          INFO = -1
192:       ELSE IF( SMLSIZ.LT.3 ) THEN
193:          INFO = -2
194:       ELSE IF( N.LT.0 ) THEN
195:          INFO = -3
196:       ELSE IF( ( SQRE.LT.0 ) .OR. ( SQRE.GT.1 ) ) THEN
197:          INFO = -4
198:       ELSE IF( LDU.LT.( N+SQRE ) ) THEN
199:          INFO = -8
200:       ELSE IF( LDGCOL.LT.N ) THEN
201:          INFO = -17
202:       END IF
203:       IF( INFO.NE.0 ) THEN
204:          CALL XERBLA( 'SLASDA', -INFO )
205:          RETURN
206:       END IF
207: *
208:       M = N + SQRE
209: *
210: *     If the input matrix is too small, call SLASDQ to find the SVD.
211: *
212:       IF( N.LE.SMLSIZ ) THEN
213:          IF( ICOMPQ.EQ.0 ) THEN
214:             CALL SLASDQ( 'U', SQRE, N, 0, 0, 0, D, E, VT, LDU, U, LDU,
215:      $                   U, LDU, WORK, INFO )
216:          ELSE
217:             CALL SLASDQ( 'U', SQRE, N, M, N, 0, D, E, VT, LDU, U, LDU,
218:      $                   U, LDU, WORK, INFO )
219:          END IF
220:          RETURN
221:       END IF
222: *
223: *     Book-keeping and  set up the computation tree.
224: *
225:       INODE = 1
226:       NDIML = INODE + N
227:       NDIMR = NDIML + N
228:       IDXQ = NDIMR + N
229:       IWK = IDXQ + N
230: *
231:       NCC = 0
232:       NRU = 0
233: *
234:       SMLSZP = SMLSIZ + 1
235:       VF = 1
236:       VL = VF + M
237:       NWORK1 = VL + M
238:       NWORK2 = NWORK1 + SMLSZP*SMLSZP
239: *
240:       CALL SLASDT( N, NLVL, ND, IWORK( INODE ), IWORK( NDIML ),
241:      $             IWORK( NDIMR ), SMLSIZ )
242: *
243: *     for the nodes on bottom level of the tree, solve
244: *     their subproblems by SLASDQ.
245: *
246:       NDB1 = ( ND+1 ) / 2
247:       DO 30 I = NDB1, ND
248: *
249: *        IC : center row of each node
250: *        NL : number of rows of left  subproblem
251: *        NR : number of rows of right subproblem
252: *        NLF: starting row of the left   subproblem
253: *        NRF: starting row of the right  subproblem
254: *
255:          I1 = I - 1
256:          IC = IWORK( INODE+I1 )
257:          NL = IWORK( NDIML+I1 )
258:          NLP1 = NL + 1
259:          NR = IWORK( NDIMR+I1 )
260:          NLF = IC - NL
261:          NRF = IC + 1
262:          IDXQI = IDXQ + NLF - 2
263:          VFI = VF + NLF - 1
264:          VLI = VL + NLF - 1
265:          SQREI = 1
266:          IF( ICOMPQ.EQ.0 ) THEN
267:             CALL SLASET( 'A', NLP1, NLP1, ZERO, ONE, WORK( NWORK1 ),
268:      $                   SMLSZP )
269:             CALL SLASDQ( 'U', SQREI, NL, NLP1, NRU, NCC, D( NLF ),
270:      $                   E( NLF ), WORK( NWORK1 ), SMLSZP,
271:      $                   WORK( NWORK2 ), NL, WORK( NWORK2 ), NL,
272:      $                   WORK( NWORK2 ), INFO )
273:             ITEMP = NWORK1 + NL*SMLSZP
274:             CALL SCOPY( NLP1, WORK( NWORK1 ), 1, WORK( VFI ), 1 )
275:             CALL SCOPY( NLP1, WORK( ITEMP ), 1, WORK( VLI ), 1 )
276:          ELSE
277:             CALL SLASET( 'A', NL, NL, ZERO, ONE, U( NLF, 1 ), LDU )
278:             CALL SLASET( 'A', NLP1, NLP1, ZERO, ONE, VT( NLF, 1 ), LDU )
279:             CALL SLASDQ( 'U', SQREI, NL, NLP1, NL, NCC, D( NLF ),
280:      $                   E( NLF ), VT( NLF, 1 ), LDU, U( NLF, 1 ), LDU,
281:      $                   U( NLF, 1 ), LDU, WORK( NWORK1 ), INFO )
282:             CALL SCOPY( NLP1, VT( NLF, 1 ), 1, WORK( VFI ), 1 )
283:             CALL SCOPY( NLP1, VT( NLF, NLP1 ), 1, WORK( VLI ), 1 )
284:          END IF
285:          IF( INFO.NE.0 ) THEN
286:             RETURN
287:          END IF
288:          DO 10 J = 1, NL
289:             IWORK( IDXQI+J ) = J
290:    10    CONTINUE
291:          IF( ( I.EQ.ND ) .AND. ( SQRE.EQ.0 ) ) THEN
292:             SQREI = 0
293:          ELSE
294:             SQREI = 1
295:          END IF
296:          IDXQI = IDXQI + NLP1
297:          VFI = VFI + NLP1
298:          VLI = VLI + NLP1
299:          NRP1 = NR + SQREI
300:          IF( ICOMPQ.EQ.0 ) THEN
301:             CALL SLASET( 'A', NRP1, NRP1, ZERO, ONE, WORK( NWORK1 ),
302:      $                   SMLSZP )
303:             CALL SLASDQ( 'U', SQREI, NR, NRP1, NRU, NCC, D( NRF ),
304:      $                   E( NRF ), WORK( NWORK1 ), SMLSZP,
305:      $                   WORK( NWORK2 ), NR, WORK( NWORK2 ), NR,
306:      $                   WORK( NWORK2 ), INFO )
307:             ITEMP = NWORK1 + ( NRP1-1 )*SMLSZP
308:             CALL SCOPY( NRP1, WORK( NWORK1 ), 1, WORK( VFI ), 1 )
309:             CALL SCOPY( NRP1, WORK( ITEMP ), 1, WORK( VLI ), 1 )
310:          ELSE
311:             CALL SLASET( 'A', NR, NR, ZERO, ONE, U( NRF, 1 ), LDU )
312:             CALL SLASET( 'A', NRP1, NRP1, ZERO, ONE, VT( NRF, 1 ), LDU )
313:             CALL SLASDQ( 'U', SQREI, NR, NRP1, NR, NCC, D( NRF ),
314:      $                   E( NRF ), VT( NRF, 1 ), LDU, U( NRF, 1 ), LDU,
315:      $                   U( NRF, 1 ), LDU, WORK( NWORK1 ), INFO )
316:             CALL SCOPY( NRP1, VT( NRF, 1 ), 1, WORK( VFI ), 1 )
317:             CALL SCOPY( NRP1, VT( NRF, NRP1 ), 1, WORK( VLI ), 1 )
318:          END IF
319:          IF( INFO.NE.0 ) THEN
320:             RETURN
321:          END IF
322:          DO 20 J = 1, NR
323:             IWORK( IDXQI+J ) = J
324:    20    CONTINUE
325:    30 CONTINUE
326: *
327: *     Now conquer each subproblem bottom-up.
328: *
329:       J = 2**NLVL
330:       DO 50 LVL = NLVL, 1, -1
331:          LVL2 = LVL*2 - 1
332: *
333: *        Find the first node LF and last node LL on
334: *        the current level LVL.
335: *
336:          IF( LVL.EQ.1 ) THEN
337:             LF = 1
338:             LL = 1
339:          ELSE
340:             LF = 2**( LVL-1 )
341:             LL = 2*LF - 1
342:          END IF
343:          DO 40 I = LF, LL
344:             IM1 = I - 1
345:             IC = IWORK( INODE+IM1 )
346:             NL = IWORK( NDIML+IM1 )
347:             NR = IWORK( NDIMR+IM1 )
348:             NLF = IC - NL
349:             NRF = IC + 1
350:             IF( I.EQ.LL ) THEN
351:                SQREI = SQRE
352:             ELSE
353:                SQREI = 1
354:             END IF
355:             VFI = VF + NLF - 1
356:             VLI = VL + NLF - 1
357:             IDXQI = IDXQ + NLF - 1
358:             ALPHA = D( IC )
359:             BETA = E( IC )
360:             IF( ICOMPQ.EQ.0 ) THEN
361:                CALL SLASD6( ICOMPQ, NL, NR, SQREI, D( NLF ),
362:      $                      WORK( VFI ), WORK( VLI ), ALPHA, BETA,
363:      $                      IWORK( IDXQI ), PERM, GIVPTR( 1 ), GIVCOL,
364:      $                      LDGCOL, GIVNUM, LDU, POLES, DIFL, DIFR, Z,
365:      $                      K( 1 ), C( 1 ), S( 1 ), WORK( NWORK1 ),
366:      $                      IWORK( IWK ), INFO )
367:             ELSE
368:                J = J - 1
369:                CALL SLASD6( ICOMPQ, NL, NR, SQREI, D( NLF ),
370:      $                      WORK( VFI ), WORK( VLI ), ALPHA, BETA,
371:      $                      IWORK( IDXQI ), PERM( NLF, LVL ),
372:      $                      GIVPTR( J ), GIVCOL( NLF, LVL2 ), LDGCOL,
373:      $                      GIVNUM( NLF, LVL2 ), LDU,
374:      $                      POLES( NLF, LVL2 ), DIFL( NLF, LVL ),
375:      $                      DIFR( NLF, LVL2 ), Z( NLF, LVL ), K( J ),
376:      $                      C( J ), S( J ), WORK( NWORK1 ),
377:      $                      IWORK( IWK ), INFO )
378:             END IF
379:             IF( INFO.NE.0 ) THEN
380:                RETURN
381:             END IF
382:    40    CONTINUE
383:    50 CONTINUE
384: *
385:       RETURN
386: *
387: *     End of SLASDA
388: *
389:       END
390: