slasda.f

*> \brief \b SLASDA computes the singular value decomposition (SVD) of a real upper bidiagonal matrix with diagonal d and off-diagonal e. Used by sbdsdc.
*
*  =========== DOCUMENTATION ===========
*
* Online html documentation available at
*            http://www.netlib.org/lapack/explore-html/
*
*> \htmlonly
*> Download SLASDA + dependencies
*> <a href="http://www.netlib.org/cgi-bin/netlibfiles.tgz?format=tgz&filename=/lapack/lapack_routine/slasda.f">
*> [TGZ]</a>
*> <a href="http://www.netlib.org/cgi-bin/netlibfiles.zip?format=zip&filename=/lapack/lapack_routine/slasda.f">
*> [ZIP]</a>
*> <a href="http://www.netlib.org/cgi-bin/netlibfiles.txt?format=txt&filename=/lapack/lapack_routine/slasda.f">
*> [TXT]</a>
*> \endhtmlonly
*
*  Definition:
*  ===========
*
*       SUBROUTINE SLASDA( ICOMPQ, SMLSIZ, N, SQRE, D, E, U, LDU, VT, K,
*                          DIFL, DIFR, Z, POLES, GIVPTR, GIVCOL, LDGCOL,
*                          PERM, GIVNUM, C, S, WORK, IWORK, INFO )
*
*       .. Scalar Arguments ..
*       INTEGER            ICOMPQ, INFO, LDGCOL, LDU, N, SMLSIZ, SQRE
*       ..
*       .. Array Arguments ..
*       INTEGER            GIVCOL( LDGCOL, * ), GIVPTR( * ), IWORK( * ),
*      $                   K( * ), PERM( LDGCOL, * )
*       REAL               C( * ), D( * ), DIFL( LDU, * ), DIFR( LDU, * ),
*      $                   E( * ), GIVNUM( LDU, * ), POLES( LDU, * ),
*      $                   S( * ), U( LDU, * ), VT( LDU, * ), WORK( * ),
*      $                   Z( LDU, * )
*       ..
*
*
*> \par Purpose:
*  =============
*>
*> \verbatim
*>
*> Using a divide and conquer approach, SLASDA computes the singular
*> value decomposition (SVD) of a real upper bidiagonal N-by-M matrix
*> B with diagonal D and offdiagonal E, where M = N + SQRE. The
*> algorithm computes the singular values in the SVD B = U * S * VT.
*> The orthogonal matrices U and VT are optionally computed in
*> compact form.
*>
*> A related subroutine, SLASD0, computes the singular values and
*> the singular vectors in explicit form.
*> \endverbatim
*
*  Arguments:
*  ==========
*
*> \param[in] ICOMPQ
*> \verbatim
*>          ICOMPQ is INTEGER
*>         Specifies whether singular vectors are to be computed
*>         in compact form, as follows
*>         = 0: Compute singular values only.
*>         = 1: Compute singular vectors of upper bidiagonal
*>              matrix in compact form.
*> \endverbatim
*>
*> \param[in] SMLSIZ
*> \verbatim
*>          SMLSIZ is INTEGER
*>         The maximum size of the subproblems at the bottom of the
*>         computation tree.
*> \endverbatim
*>
*> \param[in] N
*> \verbatim
*>          N is INTEGER
*>         The row dimension of the upper bidiagonal matrix. This is
*>         also the dimension of the main diagonal array D.
*> \endverbatim
*>
*> \param[in] SQRE
*> \verbatim
*>          SQRE is INTEGER
*>         Specifies the column dimension of the bidiagonal matrix.
*>         = 0: The bidiagonal matrix has column dimension M = N;
*>         = 1: The bidiagonal matrix has column dimension M = N + 1.
*> \endverbatim
*>
*> \param[in,out] D
*> \verbatim
*>          D is REAL array, dimension ( N )
*>         On entry D contains the main diagonal of the bidiagonal
*>         matrix. On exit D, if INFO = 0, contains its singular values.
*> \endverbatim
*>
*> \param[in] E
*> \verbatim
*>          E is REAL array, dimension ( M-1 )
*>         Contains the subdiagonal entries of the bidiagonal matrix.
*>         On exit, E has been destroyed.
*> \endverbatim
*>
*> \param[out] U
*> \verbatim
*>          U is REAL array,
*>         dimension ( LDU, SMLSIZ ) if ICOMPQ = 1, and not referenced
*>         if ICOMPQ = 0. If ICOMPQ = 1, on exit, U contains the left
*>         singular vector matrices of all subproblems at the bottom
*>         level.
*> \endverbatim
*>
*> \param[in] LDU
*> \verbatim
*>          LDU is INTEGER, LDU = > N.
*>         The leading dimension of arrays U, VT, DIFL, DIFR, POLES,
*>         GIVNUM, and Z.
*> \endverbatim
*>
*> \param[out] VT
*> \verbatim
*>          VT is REAL array,
*>         dimension ( LDU, SMLSIZ+1 ) if ICOMPQ = 1, and not referenced
*>         if ICOMPQ = 0. If ICOMPQ = 1, on exit, VT**T contains the right
*>         singular vector matrices of all subproblems at the bottom
*>         level.
*> \endverbatim
*>
*> \param[out] K
*> \verbatim
*>          K is INTEGER array, dimension ( N )
*>         if ICOMPQ = 1 and dimension 1 if ICOMPQ = 0.
*>         If ICOMPQ = 1, on exit, K(I) is the dimension of the I-th
*>         secular equation on the computation tree.
*> \endverbatim
*>
*> \param[out] DIFL
*> \verbatim
*>          DIFL is REAL array, dimension ( LDU, NLVL ),
*>         where NLVL = floor(log_2 (N/SMLSIZ))).
*> \endverbatim
*>
*> \param[out] DIFR
*> \verbatim
*>          DIFR is REAL array,
*>                  dimension ( LDU, 2 * NLVL ) if ICOMPQ = 1 and
*>                  dimension ( N ) if ICOMPQ = 0.
*>         If ICOMPQ = 1, on exit, DIFL(1:N, I) and DIFR(1:N, 2 * I - 1)
*>         record distances between singular values on the I-th
*>         level and singular values on the (I -1)-th level, and
*>         DIFR(1:N, 2 * I ) contains the normalizing factors for
*>         the right singular vector matrix. See SLASD8 for details.
*> \endverbatim
*>
*> \param[out] Z
*> \verbatim
*>          Z is REAL array,
*>                  dimension ( LDU, NLVL ) if ICOMPQ = 1 and
*>                  dimension ( N ) if ICOMPQ = 0.
*>         The first K elements of Z(1, I) contain the components of
*>         the deflation-adjusted updating row vector for subproblems
*>         on the I-th level.
*> \endverbatim
*>
*> \param[out] POLES
*> \verbatim
*>          POLES is REAL array,
*>         dimension ( LDU, 2 * NLVL ) if ICOMPQ = 1, and not referenced
*>         if ICOMPQ = 0. If ICOMPQ = 1, on exit, POLES(1, 2*I - 1) and
*>         POLES(1, 2*I) contain  the new and old singular values
*>         involved in the secular equations on the I-th level.
*> \endverbatim
*>
*> \param[out] GIVPTR
*> \verbatim
*>          GIVPTR is INTEGER array,
*>         dimension ( N ) if ICOMPQ = 1, and not referenced if
*>         ICOMPQ = 0. If ICOMPQ = 1, on exit, GIVPTR( I ) records
*>         the number of Givens rotations performed on the I-th
*>         problem on the computation tree.
*> \endverbatim
*>
*> \param[out] GIVCOL
*> \verbatim
*>          GIVCOL is INTEGER array,
*>         dimension ( LDGCOL, 2 * NLVL ) if ICOMPQ = 1, and not
*>         referenced if ICOMPQ = 0. If ICOMPQ = 1, on exit, for each I,
*>         GIVCOL(1, 2 *I - 1) and GIVCOL(1, 2 *I) record the locations
*>         of Givens rotations performed on the I-th level on the
*>         computation tree.
*> \endverbatim
*>
*> \param[in] LDGCOL
*> \verbatim
*>          LDGCOL is INTEGER, LDGCOL = > N.
*>         The leading dimension of arrays GIVCOL and PERM.
*> \endverbatim
*>
*> \param[out] PERM
*> \verbatim
*>          PERM is INTEGER array, dimension ( LDGCOL, NLVL )
*>         if ICOMPQ = 1, and not referenced
*>         if ICOMPQ = 0. If ICOMPQ = 1, on exit, PERM(1, I) records
*>         permutations done on the I-th level of the computation tree.
*> \endverbatim
*>
*> \param[out] GIVNUM
*> \verbatim
*>          GIVNUM is REAL array,
*>         dimension ( LDU,  2 * NLVL ) if ICOMPQ = 1, and not
*>         referenced if ICOMPQ = 0. If ICOMPQ = 1, on exit, for each I,
*>         GIVNUM(1, 2 *I - 1) and GIVNUM(1, 2 *I) record the C- and S-
*>         values of Givens rotations performed on the I-th level on
*>         the computation tree.
*> \endverbatim
*>
*> \param[out] C
*> \verbatim
*>          C is REAL array,
*>         dimension ( N ) if ICOMPQ = 1, and dimension 1 if ICOMPQ = 0.
*>         If ICOMPQ = 1 and the I-th subproblem is not square, on exit,
*>         C( I ) contains the C-value of a Givens rotation related to
*>         the right null space of the I-th subproblem.
*> \endverbatim
*>
*> \param[out] S
*> \verbatim
*>          S is REAL array, dimension ( N ) if
*>         ICOMPQ = 1, and dimension 1 if ICOMPQ = 0. If ICOMPQ = 1
*>         and the I-th subproblem is not square, on exit, S( I )
*>         contains the S-value of a Givens rotation related to
*>         the right null space of the I-th subproblem.
*> \endverbatim
*>
*> \param[out] WORK
*> \verbatim
*>          WORK is REAL array, dimension
*>         (6 * N + (SMLSIZ + 1)*(SMLSIZ + 1)).
*> \endverbatim
*>
*> \param[out] IWORK
*> \verbatim
*>          IWORK is INTEGER array, dimension (7*N).
*> \endverbatim
*>
*> \param[out] INFO
*> \verbatim
*>          INFO is INTEGER
*>          = 0:  successful exit.
*>          < 0:  if INFO = -i, the i-th argument had an illegal value.
*>          > 0:  if INFO = 1, a singular value did not converge
*> \endverbatim
*
*  Authors:
*  ========
*
*> \author Univ. of Tennessee
*> \author Univ. of California Berkeley
*> \author Univ. of Colorado Denver
*> \author NAG Ltd.
*
*> \ingroup lasda
*
*> \par Contributors:
*  ==================
*>
*>     Ming Gu and Huan Ren, Computer Science Division, University of
*>     California at Berkeley, USA
*>
*  =====================================================================
      SUBROUTINE slasda( ICOMPQ, SMLSIZ, N, SQRE, D, E, U, LDU, VT, K,
     $                   DIFL, DIFR, Z, POLES, GIVPTR, GIVCOL, LDGCOL,
     $                   PERM, GIVNUM, C, S, WORK, IWORK, INFO )
*
*  -- LAPACK auxiliary routine --
*  -- LAPACK is a software package provided by Univ. of Tennessee,    --
*  -- Univ. of California Berkeley, Univ. of Colorado Denver and NAG Ltd..--
*
*     .. Scalar Arguments ..
      INTEGER            ICOMPQ, INFO, LDGCOL, LDU, N, SMLSIZ, SQRE
*     ..
*     .. Array Arguments ..
      INTEGER            GIVCOL( ldgcol, * ), GIVPTR( * ), IWORK( * ),
     $                   k( * ), perm( ldgcol, * )
      REAL               C( * ), D( * ), DIFL( ldu, * ), DIFR( ldu, * ),
     $                   e( * ), givnum( ldu, * ), poles( ldu, * ),
     $                   s( * ), u( ldu, * ), vt( ldu, * ), work( * ),
     $                   z( ldu, * )
*     ..
*
*  =====================================================================
*
*     .. Parameters ..
      REAL               ZERO, ONE
      parameter( zero = 0.0e+0, one = 1.0e+0 )
*     ..
*     .. Local Scalars ..
      INTEGER            I, I1, IC, IDXQ, IDXQI, IM1, INODE, ITEMP, IWK,
     $                   j, lf, ll, lvl, lvl2, m, ncc, nd, ndb1, ndiml,
     $                   ndimr, nl, nlf, nlp1, nlvl, nr, nrf, nrp1, nru,
     $                   nwork1, nwork2, smlszp, sqrei, vf, vfi, vl, vli
      REAL               ALPHA, BETA
*     ..
*     .. External Subroutines ..
      EXTERNAL           scopy, slasd6, slasdq, slasdt, slaset, xerbla
*     ..
*     .. Executable Statements ..
*
*     Test the input parameters.
*
      info = 0
*
      IF( ( icompq.LT.0 ) .OR. ( icompq.GT.1 ) ) THEN
         info = -1
      ELSE IF( smlsiz.LT.3 ) THEN
         info = -2
      ELSE IF( n.LT.0 ) THEN
         info = -3
      ELSE IF( ( sqre.LT.0 ) .OR. ( sqre.GT.1 ) ) THEN
         info = -4
      ELSE IF( ldu.LT.( n+sqre ) ) THEN
         info = -8
      ELSE IF( ldgcol.LT.n ) THEN
         info = -17
      END IF
      IF( info.NE.0 ) THEN
         CALL xerbla( 'SLASDA', -info )
         RETURN
      END IF
*
      m = n + sqre
*
*     If the input matrix is too small, call SLASDQ to find the SVD.
*
      IF( n.LE.smlsiz ) THEN
         IF( icompq.EQ.0 ) THEN
            CALL slasdq( 'U', sqre, n, 0, 0, 0, d, e, vt, ldu, u, ldu,
     $                   u, ldu, work, info )
         ELSE
            CALL slasdq( 'U', sqre, n, m, n, 0, d, e, vt, ldu, u, ldu,
     $                   u, ldu, work, info )
         END IF
         RETURN
      END IF
*
*     Book-keeping and  set up the computation tree.
*
      inode = 1
      ndiml = inode + n
      ndimr = ndiml + n
      idxq = ndimr + n
      iwk = idxq + n
*
      ncc = 0
      nru = 0
*
      smlszp = smlsiz + 1
      vf = 1
      vl = vf + m
      nwork1 = vl + m
      nwork2 = nwork1 + smlszp*smlszp
*
      CALL slasdt( n, nlvl, nd, iwork( inode ), iwork( ndiml ),
     $             iwork( ndimr ), smlsiz )
*
*     for the nodes on bottom level of the tree, solve
*     their subproblems by SLASDQ.
*
      ndb1 = ( nd+1 ) / 2
      DO 30 i = ndb1, nd
*
*        IC : center row of each node
*        NL : number of rows of left  subproblem
*        NR : number of rows of right subproblem
*        NLF: starting row of the left   subproblem
*        NRF: starting row of the right  subproblem
*
         i1 = i - 1
         ic = iwork( inode+i1 )
         nl = iwork( ndiml+i1 )
         nlp1 = nl + 1
         nr = iwork( ndimr+i1 )
         nlf = ic - nl
         nrf = ic + 1
         idxqi = idxq + nlf - 2
         vfi = vf + nlf - 1
         vli = vl + nlf - 1
         sqrei = 1
         IF( icompq.EQ.0 ) THEN
            CALL slaset( 'A', nlp1, nlp1, zero, one, work( nwork1 ),
     $                   smlszp )
            CALL slasdq( 'U', sqrei, nl, nlp1, nru, ncc, d( nlf ),
     $                   e( nlf ), work( nwork1 ), smlszp,
     $                   work( nwork2 ), nl, work( nwork2 ), nl,
     $                   work( nwork2 ), info )
            itemp = nwork1 + nl*smlszp
            CALL scopy( nlp1, work( nwork1 ), 1, work( vfi ), 1 )
            CALL scopy( nlp1, work( itemp ), 1, work( vli ), 1 )
         ELSE
            CALL slaset( 'A', nl, nl, zero, one, u( nlf, 1 ), ldu )
            CALL slaset( 'A', nlp1, nlp1, zero, one, vt( nlf, 1 ), ldu )
            CALL slasdq( 'U', sqrei, nl, nlp1, nl, ncc, d( nlf ),
     $                   e( nlf ), vt( nlf, 1 ), ldu, u( nlf, 1 ), ldu,
     $                   u( nlf, 1 ), ldu, work( nwork1 ), info )
            CALL scopy( nlp1, vt( nlf, 1 ), 1, work( vfi ), 1 )
            CALL scopy( nlp1, vt( nlf, nlp1 ), 1, work( vli ), 1 )
         END IF
         IF( info.NE.0 ) THEN
            RETURN
         END IF
         DO 10 j = 1, nl
            iwork( idxqi+j ) = j
   10    CONTINUE
         IF( ( i.EQ.nd ) .AND. ( sqre.EQ.0 ) ) THEN
            sqrei = 0
         ELSE
            sqrei = 1
         END IF
         idxqi = idxqi + nlp1
         vfi = vfi + nlp1
         vli = vli + nlp1
         nrp1 = nr + sqrei
         IF( icompq.EQ.0 ) THEN
            CALL slaset( 'A', nrp1, nrp1, zero, one, work( nwork1 ),
     $                   smlszp )
            CALL slasdq( 'U', sqrei, nr, nrp1, nru, ncc, d( nrf ),
     $                   e( nrf ), work( nwork1 ), smlszp,
     $                   work( nwork2 ), nr, work( nwork2 ), nr,
     $                   work( nwork2 ), info )
            itemp = nwork1 + ( nrp1-1 )*smlszp
            CALL scopy( nrp1, work( nwork1 ), 1, work( vfi ), 1 )
            CALL scopy( nrp1, work( itemp ), 1, work( vli ), 1 )
         ELSE
            CALL slaset( 'A', nr, nr, zero, one, u( nrf, 1 ), ldu )
            CALL slaset( 'A', nrp1, nrp1, zero, one, vt( nrf, 1 ), ldu )
            CALL slasdq( 'U', sqrei, nr, nrp1, nr, ncc, d( nrf ),
     $                   e( nrf ), vt( nrf, 1 ), ldu, u( nrf, 1 ), ldu,
     $                   u( nrf, 1 ), ldu, work( nwork1 ), info )
            CALL scopy( nrp1, vt( nrf, 1 ), 1, work( vfi ), 1 )
            CALL scopy( nrp1, vt( nrf, nrp1 ), 1, work( vli ), 1 )
         END IF
         IF( info.NE.0 ) THEN
            RETURN
         END IF
         DO 20 j = 1, nr
            iwork( idxqi+j ) = j
   20    CONTINUE
   30 CONTINUE
*
*     Now conquer each subproblem bottom-up.
*
      j = 2**nlvl
      DO 50 lvl = nlvl, 1, -1
         lvl2 = lvl*2 - 1
*
*        Find the first node LF and last node LL on
*        the current level LVL.
*
         IF( lvl.EQ.1 ) THEN
            lf = 1
            ll = 1
         ELSE
            lf = 2**( lvl-1 )
            ll = 2*lf - 1
         END IF
         DO 40 i = lf, ll
            im1 = i - 1
            ic = iwork( inode+im1 )
            nl = iwork( ndiml+im1 )
            nr = iwork( ndimr+im1 )
            nlf = ic - nl
            nrf = ic + 1
            IF( i.EQ.ll ) THEN
               sqrei = sqre
            ELSE
               sqrei = 1
            END IF
            vfi = vf + nlf - 1
            vli = vl + nlf - 1
            idxqi = idxq + nlf - 1
            alpha = d( ic )
            beta = e( ic )
            IF( icompq.EQ.0 ) THEN
               CALL slasd6( icompq, nl, nr, sqrei, d( nlf ),
     $                      work( vfi ), work( vli ), alpha, beta,
     $                      iwork( idxqi ), perm, givptr( 1 ), givcol,
     $                      ldgcol, givnum, ldu, poles, difl, difr, z,
     $                      k( 1 ), c( 1 ), s( 1 ), work( nwork1 ),
     $                      iwork( iwk ), info )
            ELSE
               j = j - 1
               CALL slasd6( icompq, nl, nr, sqrei, d( nlf ),
     $                      work( vfi ), work( vli ), alpha, beta,
     $                      iwork( idxqi ), perm( nlf, lvl ),
     $                      givptr( j ), givcol( nlf, lvl2 ), ldgcol,
     $                      givnum( nlf, lvl2 ), ldu,
     $                      poles( nlf, lvl2 ), difl( nlf, lvl ),
     $                      difr( nlf, lvl2 ), z( nlf, lvl ), k( j ),
     $                      c( j ), s( j ), work( nwork1 ),
     $                      iwork( iwk ), info )
            END IF
            IF( info.NE.0 ) THEN
               RETURN
            END IF
   40    CONTINUE
   50 CONTINUE
*
      RETURN
*
*     End of SLASDA
*
      END