001:       SUBROUTINE SLASDT( N, LVL, ND, INODE, NDIML, NDIMR, MSUB )
002: *
003: *  -- LAPACK auxiliary routine (version 3.2) --
004: *     Univ. of Tennessee, Univ. of California Berkeley and NAG Ltd..
005: *     November 2006
006: *
007: *     .. Scalar Arguments ..
008:       INTEGER            LVL, MSUB, N, ND
009: *     ..
010: *     .. Array Arguments ..
011:       INTEGER            INODE( * ), NDIML( * ), NDIMR( * )
012: *     ..
013: *
014: *  Purpose
015: *  =======
016: *
017: *  SLASDT creates a tree of subproblems for bidiagonal divide and
018: *  conquer.
019: *
020: *  Arguments
021: *  =========
022: *
023: *   N      (input) INTEGER
024: *          On entry, the number of diagonal elements of the
025: *          bidiagonal matrix.
026: *
027: *   LVL    (output) INTEGER
028: *          On exit, the number of levels on the computation tree.
029: *
030: *   ND     (output) INTEGER
031: *          On exit, the number of nodes on the tree.
032: *
033: *   INODE  (output) INTEGER array, dimension ( N )
034: *          On exit, centers of subproblems.
035: *
036: *   NDIML  (output) INTEGER array, dimension ( N )
037: *          On exit, row dimensions of left children.
038: *
039: *   NDIMR  (output) INTEGER array, dimension ( N )
040: *          On exit, row dimensions of right children.
041: *
042: *   MSUB   (input) INTEGER.
043: *          On entry, the maximum row dimension each subproblem at the
044: *          bottom of the tree can be of.
045: *
046: *  Further Details
047: *  ===============
048: *
049: *  Based on contributions by
050: *     Ming Gu and Huan Ren, Computer Science Division, University of
051: *     California at Berkeley, USA
052: *
053: *  =====================================================================
054: *
055: *     .. Parameters ..
056:       REAL               TWO
057:       PARAMETER          ( TWO = 2.0E+0 )
058: *     ..
059: *     .. Local Scalars ..
060:       INTEGER            I, IL, IR, LLST, MAXN, NCRNT, NLVL
061:       REAL               TEMP
062: *     ..
063: *     .. Intrinsic Functions ..
064:       INTRINSIC          INT, LOG, MAX, REAL
065: *     ..
066: *     .. Executable Statements ..
067: *
068: *     Find the number of levels on the tree.
069: *
070:       MAXN = MAX( 1, N )
071:       TEMP = LOG( REAL( MAXN ) / REAL( MSUB+1 ) ) / LOG( TWO )
072:       LVL = INT( TEMP ) + 1
073: *
074:       I = N / 2
075:       INODE( 1 ) = I + 1
076:       NDIML( 1 ) = I
077:       NDIMR( 1 ) = N - I - 1
078:       IL = 0
079:       IR = 1
080:       LLST = 1
081:       DO 20 NLVL = 1, LVL - 1
082: *
083: *        Constructing the tree at (NLVL+1)-st level. The number of
084: *        nodes created on this level is LLST * 2.
085: *
086:          DO 10 I = 0, LLST - 1
087:             IL = IL + 2
088:             IR = IR + 2
089:             NCRNT = LLST + I
090:             NDIML( IL ) = NDIML( NCRNT ) / 2
091:             NDIMR( IL ) = NDIML( NCRNT ) - NDIML( IL ) - 1
092:             INODE( IL ) = INODE( NCRNT ) - NDIMR( IL ) - 1
093:             NDIML( IR ) = NDIMR( NCRNT ) / 2
094:             NDIMR( IR ) = NDIMR( NCRNT ) - NDIML( IR ) - 1
095:             INODE( IR ) = INODE( NCRNT ) + NDIML( IR ) + 1
096:    10    CONTINUE
097:          LLST = LLST*2
098:    20 CONTINUE
099:       ND = LLST*2 - 1
100: *
101:       RETURN
102: *
103: *     End of SLASDT
104: *
105:       END
106: