LAPACK  3.10.0
LAPACK: Linear Algebra PACKage

◆ dgelsy()

subroutine dgelsy ( integer  M,
integer  N,
integer  NRHS,
double precision, dimension( lda, * )  A,
integer  LDA,
double precision, dimension( ldb, * )  B,
integer  LDB,
integer, dimension( * )  JPVT,
double precision  RCOND,
integer  RANK,
double precision, dimension( * )  WORK,
integer  LWORK,
integer  INFO 
)

DGELSY solves overdetermined or underdetermined systems for GE matrices

Download DGELSY + dependencies [TGZ] [ZIP] [TXT]

Purpose:
 DGELSY computes the minimum-norm solution to a real linear least
 squares problem:
     minimize || A * X - B ||
 using a complete orthogonal factorization of A.  A is an M-by-N
 matrix which may be rank-deficient.

 Several right hand side vectors b and solution vectors x can be
 handled in a single call; they are stored as the columns of the
 M-by-NRHS right hand side matrix B and the N-by-NRHS solution
 matrix X.

 The routine first computes a QR factorization with column pivoting:
     A * P = Q * [ R11 R12 ]
                 [  0  R22 ]
 with R11 defined as the largest leading submatrix whose estimated
 condition number is less than 1/RCOND.  The order of R11, RANK,
 is the effective rank of A.

 Then, R22 is considered to be negligible, and R12 is annihilated
 by orthogonal transformations from the right, arriving at the
 complete orthogonal factorization:
    A * P = Q * [ T11 0 ] * Z
                [  0  0 ]
 The minimum-norm solution is then
    X = P * Z**T [ inv(T11)*Q1**T*B ]
                 [        0         ]
 where Q1 consists of the first RANK columns of Q.

 This routine is basically identical to the original xGELSX except
 three differences:
   o The call to the subroutine xGEQPF has been substituted by the
     the call to the subroutine xGEQP3. This subroutine is a Blas-3
     version of the QR factorization with column pivoting.
   o Matrix B (the right hand side) is updated with Blas-3.
   o The permutation of matrix B (the right hand side) is faster and
     more simple.
Parameters
[in]M
          M is INTEGER
          The number of rows of the matrix A.  M >= 0.
[in]N
          N is INTEGER
          The number of columns of the matrix A.  N >= 0.
[in]NRHS
          NRHS is INTEGER
          The number of right hand sides, i.e., the number of
          columns of matrices B and X. NRHS >= 0.
[in,out]A
          A is DOUBLE PRECISION array, dimension (LDA,N)
          On entry, the M-by-N matrix A.
          On exit, A has been overwritten by details of its
          complete orthogonal factorization.
[in]LDA
          LDA is INTEGER
          The leading dimension of the array A.  LDA >= max(1,M).
[in,out]B
          B is DOUBLE PRECISION array, dimension (LDB,NRHS)
          On entry, the M-by-NRHS right hand side matrix B.
          On exit, the N-by-NRHS solution matrix X.
[in]LDB
          LDB is INTEGER
          The leading dimension of the array B. LDB >= max(1,M,N).
[in,out]JPVT
          JPVT is INTEGER array, dimension (N)
          On entry, if JPVT(i) .ne. 0, the i-th column of A is permuted
          to the front of AP, otherwise column i is a free column.
          On exit, if JPVT(i) = k, then the i-th column of AP
          was the k-th column of A.
[in]RCOND
          RCOND is DOUBLE PRECISION
          RCOND is used to determine the effective rank of A, which
          is defined as the order of the largest leading triangular
          submatrix R11 in the QR factorization with pivoting of A,
          whose estimated condition number < 1/RCOND.
[out]RANK
          RANK is INTEGER
          The effective rank of A, i.e., the order of the submatrix
          R11.  This is the same as the order of the submatrix T11
          in the complete orthogonal factorization of A.
[out]WORK
          WORK is DOUBLE PRECISION array, dimension (MAX(1,LWORK))
          On exit, if INFO = 0, WORK(1) returns the optimal LWORK.
[in]LWORK
          LWORK is INTEGER
          The dimension of the array WORK.
          The unblocked strategy requires that:
             LWORK >= MAX( MN+3*N+1, 2*MN+NRHS ),
          where MN = min( M, N ).
          The block algorithm requires that:
             LWORK >= MAX( MN+2*N+NB*(N+1), 2*MN+NB*NRHS ),
          where NB is an upper bound on the blocksize returned
          by ILAENV for the routines DGEQP3, DTZRZF, STZRQF, DORMQR,
          and DORMRZ.

          If LWORK = -1, then a workspace query is assumed; the routine
          only calculates the optimal size of the WORK array, returns
          this value as the first entry of the WORK array, and no error
          message related to LWORK is issued by XERBLA.
[out]INFO
          INFO is INTEGER
          = 0: successful exit
          < 0: If INFO = -i, the i-th argument had an illegal value.
Author
Univ. of Tennessee
Univ. of California Berkeley
Univ. of Colorado Denver
NAG Ltd.
Contributors:
A. Petitet, Computer Science Dept., Univ. of Tenn., Knoxville, USA
E. Quintana-Orti, Depto. de Informatica, Universidad Jaime I, Spain
G. Quintana-Orti, Depto. de Informatica, Universidad Jaime I, Spain

Definition at line 202 of file dgelsy.f.

204 *
205 * -- LAPACK driver routine --
206 * -- LAPACK is a software package provided by Univ. of Tennessee, --
207 * -- Univ. of California Berkeley, Univ. of Colorado Denver and NAG Ltd..--
208 *
209 * .. Scalar Arguments ..
210  INTEGER INFO, LDA, LDB, LWORK, M, N, NRHS, RANK
211  DOUBLE PRECISION RCOND
212 * ..
213 * .. Array Arguments ..
214  INTEGER JPVT( * )
215  DOUBLE PRECISION A( LDA, * ), B( LDB, * ), WORK( * )
216 * ..
217 *
218 * =====================================================================
219 *
220 * .. Parameters ..
221  INTEGER IMAX, IMIN
222  parameter( imax = 1, imin = 2 )
223  DOUBLE PRECISION ZERO, ONE
224  parameter( zero = 0.0d+0, one = 1.0d+0 )
225 * ..
226 * .. Local Scalars ..
227  LOGICAL LQUERY
228  INTEGER I, IASCL, IBSCL, ISMAX, ISMIN, J, LWKMIN,
229  $ LWKOPT, MN, NB, NB1, NB2, NB3, NB4
230  DOUBLE PRECISION ANRM, BIGNUM, BNRM, C1, C2, S1, S2, SMAX,
231  $ SMAXPR, SMIN, SMINPR, SMLNUM, WSIZE
232 * ..
233 * .. External Functions ..
234  INTEGER ILAENV
235  DOUBLE PRECISION DLAMCH, DLANGE
236  EXTERNAL ilaenv, dlamch, dlange
237 * ..
238 * .. External Subroutines ..
239  EXTERNAL dcopy, dgeqp3, dlabad, dlaic1, dlascl, dlaset,
241 * ..
242 * .. Intrinsic Functions ..
243  INTRINSIC abs, max, min
244 * ..
245 * .. Executable Statements ..
246 *
247  mn = min( m, n )
248  ismin = mn + 1
249  ismax = 2*mn + 1
250 *
251 * Test the input arguments.
252 *
253  info = 0
254  lquery = ( lwork.EQ.-1 )
255  IF( m.LT.0 ) THEN
256  info = -1
257  ELSE IF( n.LT.0 ) THEN
258  info = -2
259  ELSE IF( nrhs.LT.0 ) THEN
260  info = -3
261  ELSE IF( lda.LT.max( 1, m ) ) THEN
262  info = -5
263  ELSE IF( ldb.LT.max( 1, m, n ) ) THEN
264  info = -7
265  END IF
266 *
267 * Figure out optimal block size
268 *
269  IF( info.EQ.0 ) THEN
270  IF( mn.EQ.0 .OR. nrhs.EQ.0 ) THEN
271  lwkmin = 1
272  lwkopt = 1
273  ELSE
274  nb1 = ilaenv( 1, 'DGEQRF', ' ', m, n, -1, -1 )
275  nb2 = ilaenv( 1, 'DGERQF', ' ', m, n, -1, -1 )
276  nb3 = ilaenv( 1, 'DORMQR', ' ', m, n, nrhs, -1 )
277  nb4 = ilaenv( 1, 'DORMRQ', ' ', m, n, nrhs, -1 )
278  nb = max( nb1, nb2, nb3, nb4 )
279  lwkmin = mn + max( 2*mn, n + 1, mn + nrhs )
280  lwkopt = max( lwkmin,
281  $ mn + 2*n + nb*( n + 1 ), 2*mn + nb*nrhs )
282  END IF
283  work( 1 ) = lwkopt
284 *
285  IF( lwork.LT.lwkmin .AND. .NOT.lquery ) THEN
286  info = -12
287  END IF
288  END IF
289 *
290  IF( info.NE.0 ) THEN
291  CALL xerbla( 'DGELSY', -info )
292  RETURN
293  ELSE IF( lquery ) THEN
294  RETURN
295  END IF
296 *
297 * Quick return if possible
298 *
299  IF( mn.EQ.0 .OR. nrhs.EQ.0 ) THEN
300  rank = 0
301  RETURN
302  END IF
303 *
304 * Get machine parameters
305 *
306  smlnum = dlamch( 'S' ) / dlamch( 'P' )
307  bignum = one / smlnum
308  CALL dlabad( smlnum, bignum )
309 *
310 * Scale A, B if max entries outside range [SMLNUM,BIGNUM]
311 *
312  anrm = dlange( 'M', m, n, a, lda, work )
313  iascl = 0
314  IF( anrm.GT.zero .AND. anrm.LT.smlnum ) THEN
315 *
316 * Scale matrix norm up to SMLNUM
317 *
318  CALL dlascl( 'G', 0, 0, anrm, smlnum, m, n, a, lda, info )
319  iascl = 1
320  ELSE IF( anrm.GT.bignum ) THEN
321 *
322 * Scale matrix norm down to BIGNUM
323 *
324  CALL dlascl( 'G', 0, 0, anrm, bignum, m, n, a, lda, info )
325  iascl = 2
326  ELSE IF( anrm.EQ.zero ) THEN
327 *
328 * Matrix all zero. Return zero solution.
329 *
330  CALL dlaset( 'F', max( m, n ), nrhs, zero, zero, b, ldb )
331  rank = 0
332  GO TO 70
333  END IF
334 *
335  bnrm = dlange( 'M', m, nrhs, b, ldb, work )
336  ibscl = 0
337  IF( bnrm.GT.zero .AND. bnrm.LT.smlnum ) THEN
338 *
339 * Scale matrix norm up to SMLNUM
340 *
341  CALL dlascl( 'G', 0, 0, bnrm, smlnum, m, nrhs, b, ldb, info )
342  ibscl = 1
343  ELSE IF( bnrm.GT.bignum ) THEN
344 *
345 * Scale matrix norm down to BIGNUM
346 *
347  CALL dlascl( 'G', 0, 0, bnrm, bignum, m, nrhs, b, ldb, info )
348  ibscl = 2
349  END IF
350 *
351 * Compute QR factorization with column pivoting of A:
352 * A * P = Q * R
353 *
354  CALL dgeqp3( m, n, a, lda, jpvt, work( 1 ), work( mn+1 ),
355  $ lwork-mn, info )
356  wsize = mn + work( mn+1 )
357 *
358 * workspace: MN+2*N+NB*(N+1).
359 * Details of Householder rotations stored in WORK(1:MN).
360 *
361 * Determine RANK using incremental condition estimation
362 *
363  work( ismin ) = one
364  work( ismax ) = one
365  smax = abs( a( 1, 1 ) )
366  smin = smax
367  IF( abs( a( 1, 1 ) ).EQ.zero ) THEN
368  rank = 0
369  CALL dlaset( 'F', max( m, n ), nrhs, zero, zero, b, ldb )
370  GO TO 70
371  ELSE
372  rank = 1
373  END IF
374 *
375  10 CONTINUE
376  IF( rank.LT.mn ) THEN
377  i = rank + 1
378  CALL dlaic1( imin, rank, work( ismin ), smin, a( 1, i ),
379  $ a( i, i ), sminpr, s1, c1 )
380  CALL dlaic1( imax, rank, work( ismax ), smax, a( 1, i ),
381  $ a( i, i ), smaxpr, s2, c2 )
382 *
383  IF( smaxpr*rcond.LE.sminpr ) THEN
384  DO 20 i = 1, rank
385  work( ismin+i-1 ) = s1*work( ismin+i-1 )
386  work( ismax+i-1 ) = s2*work( ismax+i-1 )
387  20 CONTINUE
388  work( ismin+rank ) = c1
389  work( ismax+rank ) = c2
390  smin = sminpr
391  smax = smaxpr
392  rank = rank + 1
393  GO TO 10
394  END IF
395  END IF
396 *
397 * workspace: 3*MN.
398 *
399 * Logically partition R = [ R11 R12 ]
400 * [ 0 R22 ]
401 * where R11 = R(1:RANK,1:RANK)
402 *
403 * [R11,R12] = [ T11, 0 ] * Y
404 *
405  IF( rank.LT.n )
406  $ CALL dtzrzf( rank, n, a, lda, work( mn+1 ), work( 2*mn+1 ),
407  $ lwork-2*mn, info )
408 *
409 * workspace: 2*MN.
410 * Details of Householder rotations stored in WORK(MN+1:2*MN)
411 *
412 * B(1:M,1:NRHS) := Q**T * B(1:M,1:NRHS)
413 *
414  CALL dormqr( 'Left', 'Transpose', m, nrhs, mn, a, lda, work( 1 ),
415  $ b, ldb, work( 2*mn+1 ), lwork-2*mn, info )
416  wsize = max( wsize, 2*mn+work( 2*mn+1 ) )
417 *
418 * workspace: 2*MN+NB*NRHS.
419 *
420 * B(1:RANK,1:NRHS) := inv(T11) * B(1:RANK,1:NRHS)
421 *
422  CALL dtrsm( 'Left', 'Upper', 'No transpose', 'Non-unit', rank,
423  $ nrhs, one, a, lda, b, ldb )
424 *
425  DO 40 j = 1, nrhs
426  DO 30 i = rank + 1, n
427  b( i, j ) = zero
428  30 CONTINUE
429  40 CONTINUE
430 *
431 * B(1:N,1:NRHS) := Y**T * B(1:N,1:NRHS)
432 *
433  IF( rank.LT.n ) THEN
434  CALL dormrz( 'Left', 'Transpose', n, nrhs, rank, n-rank, a,
435  $ lda, work( mn+1 ), b, ldb, work( 2*mn+1 ),
436  $ lwork-2*mn, info )
437  END IF
438 *
439 * workspace: 2*MN+NRHS.
440 *
441 * B(1:N,1:NRHS) := P * B(1:N,1:NRHS)
442 *
443  DO 60 j = 1, nrhs
444  DO 50 i = 1, n
445  work( jpvt( i ) ) = b( i, j )
446  50 CONTINUE
447  CALL dcopy( n, work( 1 ), 1, b( 1, j ), 1 )
448  60 CONTINUE
449 *
450 * workspace: N.
451 *
452 * Undo scaling
453 *
454  IF( iascl.EQ.1 ) THEN
455  CALL dlascl( 'G', 0, 0, anrm, smlnum, n, nrhs, b, ldb, info )
456  CALL dlascl( 'U', 0, 0, smlnum, anrm, rank, rank, a, lda,
457  $ info )
458  ELSE IF( iascl.EQ.2 ) THEN
459  CALL dlascl( 'G', 0, 0, anrm, bignum, n, nrhs, b, ldb, info )
460  CALL dlascl( 'U', 0, 0, bignum, anrm, rank, rank, a, lda,
461  $ info )
462  END IF
463  IF( ibscl.EQ.1 ) THEN
464  CALL dlascl( 'G', 0, 0, smlnum, bnrm, n, nrhs, b, ldb, info )
465  ELSE IF( ibscl.EQ.2 ) THEN
466  CALL dlascl( 'G', 0, 0, bignum, bnrm, n, nrhs, b, ldb, info )
467  END IF
468 *
469  70 CONTINUE
470  work( 1 ) = lwkopt
471 *
472  RETURN
473 *
474 * End of DGELSY
475 *
double precision function dlamch(CMACH)
DLAMCH
Definition: dlamch.f:69
subroutine dlabad(SMALL, LARGE)
DLABAD
Definition: dlabad.f:74
subroutine dlascl(TYPE, KL, KU, CFROM, CTO, M, N, A, LDA, INFO)
DLASCL multiplies a general rectangular matrix by a real scalar defined as cto/cfrom.
Definition: dlascl.f:143
subroutine dlaset(UPLO, M, N, ALPHA, BETA, A, LDA)
DLASET initializes the off-diagonal elements and the diagonal elements of a matrix to given values.
Definition: dlaset.f:110
integer function ilaenv(ISPEC, NAME, OPTS, N1, N2, N3, N4)
ILAENV
Definition: ilaenv.f:162
subroutine xerbla(SRNAME, INFO)
XERBLA
Definition: xerbla.f:60
subroutine dcopy(N, DX, INCX, DY, INCY)
DCOPY
Definition: dcopy.f:82
subroutine dtrsm(SIDE, UPLO, TRANSA, DIAG, M, N, ALPHA, A, LDA, B, LDB)
DTRSM
Definition: dtrsm.f:181
double precision function dlange(NORM, M, N, A, LDA, WORK)
DLANGE returns the value of the 1-norm, Frobenius norm, infinity-norm, or the largest absolute value ...
Definition: dlange.f:114
subroutine dgeqp3(M, N, A, LDA, JPVT, TAU, WORK, LWORK, INFO)
DGEQP3
Definition: dgeqp3.f:151
subroutine dlaic1(JOB, J, X, SEST, W, GAMMA, SESTPR, S, C)
DLAIC1 applies one step of incremental condition estimation.
Definition: dlaic1.f:134
subroutine dormqr(SIDE, TRANS, M, N, K, A, LDA, TAU, C, LDC, WORK, LWORK, INFO)
DORMQR
Definition: dormqr.f:167
subroutine dtzrzf(M, N, A, LDA, TAU, WORK, LWORK, INFO)
DTZRZF
Definition: dtzrzf.f:151
subroutine dormrz(SIDE, TRANS, M, N, K, L, A, LDA, TAU, C, LDC, WORK, LWORK, INFO)
DORMRZ
Definition: dormrz.f:187
Here is the call graph for this function:
Here is the caller graph for this function: