001:       SUBROUTINE SGGLSE( M, N, P, A, LDA, B, LDB, C, D, X, WORK, LWORK,
002:      $                   INFO )
003: *
004: *  -- LAPACK driver routine (version 3.2) --
005: *     Univ. of Tennessee, Univ. of California Berkeley and NAG Ltd..
006: *     November 2006
007: *
008: *     .. Scalar Arguments ..
009:       INTEGER            INFO, LDA, LDB, LWORK, M, N, P
010: *     ..
011: *     .. Array Arguments ..
012:       REAL               A( LDA, * ), B( LDB, * ), C( * ), D( * ),
013:      $                   WORK( * ), X( * )
014: *     ..
015: *
016: *  Purpose
017: *  =======
018: *
019: *  SGGLSE solves the linear equality-constrained least squares (LSE)
020: *  problem:
021: *
022: *          minimize || c - A*x ||_2   subject to   B*x = d
023: *
024: *  where A is an M-by-N matrix, B is a P-by-N matrix, c is a given
025: *  M-vector, and d is a given P-vector. It is assumed that
026: *  P <= N <= M+P, and
027: *
028: *           rank(B) = P and  rank( (A) ) = N.
029: *                                ( (B) )
030: *
031: *  These conditions ensure that the LSE problem has a unique solution,
032: *  which is obtained using a generalized RQ factorization of the
033: *  matrices (B, A) given by
034: *
035: *     B = (0 R)*Q,   A = Z*T*Q.
036: *
037: *  Arguments
038: *  =========
039: *
040: *  M       (input) INTEGER
041: *          The number of rows of the matrix A.  M >= 0.
042: *
043: *  N       (input) INTEGER
044: *          The number of columns of the matrices A and B. N >= 0.
045: *
046: *  P       (input) INTEGER
047: *          The number of rows of the matrix B. 0 <= P <= N <= M+P.
048: *
049: *  A       (input/output) REAL array, dimension (LDA,N)
050: *          On entry, the M-by-N matrix A.
051: *          On exit, the elements on and above the diagonal of the array
052: *          contain the min(M,N)-by-N upper trapezoidal matrix T.
053: *
054: *  LDA     (input) INTEGER
055: *          The leading dimension of the array A. LDA >= max(1,M).
056: *
057: *  B       (input/output) REAL array, dimension (LDB,N)
058: *          On entry, the P-by-N matrix B.
059: *          On exit, the upper triangle of the subarray B(1:P,N-P+1:N)
060: *          contains the P-by-P upper triangular matrix R.
061: *
062: *  LDB     (input) INTEGER
063: *          The leading dimension of the array B. LDB >= max(1,P).
064: *
065: *  C       (input/output) REAL array, dimension (M)
066: *          On entry, C contains the right hand side vector for the
067: *          least squares part of the LSE problem.
068: *          On exit, the residual sum of squares for the solution
069: *          is given by the sum of squares of elements N-P+1 to M of
070: *          vector C.
071: *
072: *  D       (input/output) REAL array, dimension (P)
073: *          On entry, D contains the right hand side vector for the
074: *          constrained equation.
075: *          On exit, D is destroyed.
076: *
077: *  X       (output) REAL array, dimension (N)
078: *          On exit, X is the solution of the LSE problem.
079: *
080: *  WORK    (workspace/output) REAL array, dimension (MAX(1,LWORK))
081: *          On exit, if INFO = 0, WORK(1) returns the optimal LWORK.
082: *
083: *  LWORK   (input) INTEGER
084: *          The dimension of the array WORK. LWORK >= max(1,M+N+P).
085: *          For optimum performance LWORK >= P+min(M,N)+max(M,N)*NB,
086: *          where NB is an upper bound for the optimal blocksizes for
087: *          SGEQRF, SGERQF, SORMQR and SORMRQ.
088: *
089: *          If LWORK = -1, then a workspace query is assumed; the routine
090: *          only calculates the optimal size of the WORK array, returns
091: *          this value as the first entry of the WORK array, and no error
092: *          message related to LWORK is issued by XERBLA.
093: *
094: *  INFO    (output) INTEGER
095: *          = 0:  successful exit.
096: *          < 0:  if INFO = -i, the i-th argument had an illegal value.
097: *          = 1:  the upper triangular factor R associated with B in the
098: *                generalized RQ factorization of the pair (B, A) is
099: *                singular, so that rank(B) < P; the least squares
100: *                solution could not be computed.
101: *          = 2:  the (N-P) by (N-P) part of the upper trapezoidal factor
102: *                T associated with A in the generalized RQ factorization
103: *                of the pair (B, A) is singular, so that
104: *                rank( (A) ) < N; the least squares solution could not
105: *                    ( (B) )
106: *                be computed.
107: *
108: *  =====================================================================
109: *
110: *     .. Parameters ..
111:       REAL               ONE
112:       PARAMETER          ( ONE = 1.0E+0 )
113: *     ..
114: *     .. Local Scalars ..
115:       LOGICAL            LQUERY
116:       INTEGER            LOPT, LWKMIN, LWKOPT, MN, NB, NB1, NB2, NB3,
117:      $                   NB4, NR
118: *     ..
119: *     .. External Subroutines ..
120:       EXTERNAL           SAXPY, SCOPY, SGEMV, SGGRQF, SORMQR, SORMRQ,
121:      $                   STRMV, STRTRS, XERBLA
122: *     ..
123: *     .. External Functions ..
124:       INTEGER            ILAENV
125:       EXTERNAL           ILAENV 
126: *     ..
127: *     .. Intrinsic Functions ..
128:       INTRINSIC          INT, MAX, MIN
129: *     ..
130: *     .. Executable Statements ..
131: *
132: *     Test the input parameters
133: *
134:       INFO = 0
135:       MN = MIN( M, N )
136:       LQUERY = ( LWORK.EQ.-1 )
137:       IF( M.LT.0 ) THEN
138:          INFO = -1
139:       ELSE IF( N.LT.0 ) THEN
140:          INFO = -2
141:       ELSE IF( P.LT.0 .OR. P.GT.N .OR. P.LT.N-M ) THEN
142:          INFO = -3
143:       ELSE IF( LDA.LT.MAX( 1, M ) ) THEN
144:          INFO = -5
145:       ELSE IF( LDB.LT.MAX( 1, P ) ) THEN
146:          INFO = -7
147:       END IF
148: *
149: *     Calculate workspace
150: *
151:       IF( INFO.EQ.0) THEN
152:          IF( N.EQ.0 ) THEN
153:             LWKMIN = 1
154:             LWKOPT = 1
155:          ELSE
156:             NB1 = ILAENV( 1, 'SGEQRF', ' ', M, N, -1, -1 )
157:             NB2 = ILAENV( 1, 'SGERQF', ' ', M, N, -1, -1 )
158:             NB3 = ILAENV( 1, 'SORMQR', ' ', M, N, P, -1 )
159:             NB4 = ILAENV( 1, 'SORMRQ', ' ', M, N, P, -1 )
160:             NB = MAX( NB1, NB2, NB3, NB4 )
161:             LWKMIN = M + N + P
162:             LWKOPT = P + MN + MAX( M, N )*NB
163:          END IF
164:          WORK( 1 ) = LWKOPT
165: *
166:          IF( LWORK.LT.LWKMIN .AND. .NOT.LQUERY ) THEN
167:             INFO = -12
168:          END IF
169:       END IF
170: *
171:       IF( INFO.NE.0 ) THEN
172:          CALL XERBLA( 'SGGLSE', -INFO )
173:          RETURN
174:       ELSE IF( LQUERY ) THEN
175:          RETURN
176:       END IF
177: *
178: *     Quick return if possible
179: *
180:       IF( N.EQ.0 )
181:      $   RETURN
182: *
183: *     Compute the GRQ factorization of matrices B and A:
184: *
185: *            B*Q' = (  0  T12 ) P   Z'*A*Q' = ( R11 R12 ) N-P
186: *                     N-P  P                  (  0  R22 ) M+P-N
187: *                                               N-P  P
188: *
189: *     where T12 and R11 are upper triangular, and Q and Z are
190: *     orthogonal.
191: *
192:       CALL SGGRQF( P, M, N, B, LDB, WORK, A, LDA, WORK( P+1 ),
193:      $             WORK( P+MN+1 ), LWORK-P-MN, INFO )
194:       LOPT = WORK( P+MN+1 )
195: *
196: *     Update c = Z'*c = ( c1 ) N-P
197: *                       ( c2 ) M+P-N
198: *
199:       CALL SORMQR( 'Left', 'Transpose', M, 1, MN, A, LDA, WORK( P+1 ),
200:      $             C, MAX( 1, M ), WORK( P+MN+1 ), LWORK-P-MN, INFO )
201:       LOPT = MAX( LOPT, INT( WORK( P+MN+1 ) ) )
202: *
203: *     Solve T12*x2 = d for x2
204: *
205:       IF( P.GT.0 ) THEN
206:          CALL STRTRS( 'Upper', 'No transpose', 'Non-unit', P, 1,
207:      $                B( 1, N-P+1 ), LDB, D, P, INFO )
208: *
209:          IF( INFO.GT.0 ) THEN
210:             INFO = 1
211:             RETURN
212:          END IF
213: *
214: *        Put the solution in X
215: *
216:          CALL SCOPY( P, D, 1, X( N-P+1 ), 1 )
217: *
218: *        Update c1
219: *
220:          CALL SGEMV( 'No transpose', N-P, P, -ONE, A( 1, N-P+1 ), LDA,
221:      $               D, 1, ONE, C, 1 )
222:       END IF
223: *
224: *     Solve R11*x1 = c1 for x1
225: *
226:       IF( N.GT.P ) THEN
227:          CALL STRTRS( 'Upper', 'No transpose', 'Non-unit', N-P, 1,
228:      $                A, LDA, C, N-P, INFO )
229: *
230:          IF( INFO.GT.0 ) THEN
231:             INFO = 2
232:             RETURN
233:          END IF
234: *
235: *        Put the solution in X
236: *
237:          CALL SCOPY( N-P, C, 1, X, 1 )
238:       END IF
239: *
240: *     Compute the residual vector:
241: *
242:       IF( M.LT.N ) THEN
243:          NR = M + P - N
244:          IF( NR.GT.0 )
245:      $      CALL SGEMV( 'No transpose', NR, N-M, -ONE, A( N-P+1, M+1 ),
246:      $                  LDA, D( NR+1 ), 1, ONE, C( N-P+1 ), 1 )
247:       ELSE
248:          NR = P
249:       END IF
250:       IF( NR.GT.0 ) THEN
251:          CALL STRMV( 'Upper', 'No transpose', 'Non unit', NR,
252:      $               A( N-P+1, N-P+1 ), LDA, D, 1 )
253:          CALL SAXPY( NR, -ONE, D, 1, C( N-P+1 ), 1 )
254:       END IF
255: *
256: *     Backward transformation x = Q'*x
257: *
258:       CALL SORMRQ( 'Left', 'Transpose', N, 1, P, B, LDB, WORK( 1 ), X,
259:      $             N, WORK( P+MN+1 ), LWORK-P-MN, INFO )
260:       WORK( 1 ) = P + MN + MAX( LOPT, INT( WORK( P+MN+1 ) ) )
261: *
262:       RETURN
263: *
264: *     End of SGGLSE
265: *
266:       END
267: