1CGELSD(1) LAPACK driver routine (version 3.1) CGELSD(1)
2
6 CGELSD - the minimum-norm solution to a real linear least squares prob‐
7 lem
8
10 SUBROUTINE CGELSD( M, N, NRHS, A, LDA, B, LDB, S, RCOND, RANK, WORK,
11 LWORK, RWORK, IWORK, INFO )
12 INTEGER INFO, LDA, LDB, LWORK, M, N, NRHS, RANK
14 REAL RCOND
16 INTEGER IWORK( * )
18 REAL RWORK( * ), S( * )
20 COMPLEX A( LDA, * ), B( LDB, * ), WORK( * )
22
24 CGELSD computes the minimum-norm solution to a real linear least
25 squares problem:
26 minimize 2-norm(| b - A*x |)
27 using the singular value decomposition (SVD) of A. A is an M-by-N
28 matrix which may be rank-deficient.
29 Several right hand side vectors b and solution vectors x can be handled
31 in a single call; they are stored as the columns of the M-by-NRHS right
32 hand side matrix B and the N-by-NRHS solution matrix X.
33 The problem is solved in three steps:
35 (1) Reduce the coefficient matrix A to bidiagonal form with
36 Householder tranformations, reducing the original problem
37 into a "bidiagonal least squares problem" (BLS)
38 (2) Solve the BLS using a divide and conquer approach.
39 (3) Apply back all the Householder tranformations to solve
40 the original least squares problem.
41 The effective rank of A is determined by treating as zero those singu‐
43 lar values which are less than RCOND times the largest singular value.
44 The divide and conquer algorithm makes very mild assumptions about
46 floating point arithmetic. It will work on machines with a guard digit
47 in add/subtract, or on those binary machines without guard digits which
48 subtract like the Cray X-MP, Cray Y-MP, Cray C-90, or Cray-2. It could
49 conceivably fail on hexadecimal or decimal machines without guard dig‐
50 its, but we know of none.
51
54 M (input) INTEGER
55 The number of rows of the matrix A. M >= 0.
56 N (input) INTEGER
58 The number of columns of the matrix A. N >= 0.
59 NRHS (input) INTEGER
61 The number of right hand sides, i.e., the number of columns of
62 the matrices B and X. NRHS >= 0.
63 A (input/output) COMPLEX array, dimension (LDA,N)
65 On entry, the M-by-N matrix A. On exit, A has been destroyed.
66 LDA (input) INTEGER
68 The leading dimension of the array A. LDA >= max(1,M).
69 B (input/output) COMPLEX array, dimension (LDB,NRHS)
71 On entry, the M-by-NRHS right hand side matrix B. On exit, B
72 is overwritten by the N-by-NRHS solution matrix X. If m >= n
73 and RANK = n, the residual sum-of-squares for the solution in
74 the i-th column is given by the sum of squares of the modulus
75 of elements n+1:m in that column.
76 LDB (input) INTEGER
78 The leading dimension of the array B. LDB >= max(1,M,N).
79 S (output) REAL array, dimension (min(M,N))
81 The singular values of A in decreasing order. The condition
82 number of A in the 2-norm = S(1)/S(min(m,n)).
83 RCOND (input) REAL
85 RCOND is used to determine the effective rank of A. Singular
86 values S(i) <= RCOND*S(1) are treated as zero. If RCOND < 0,
87 machine precision is used instead.
88 RANK (output) INTEGER
90 The effective rank of A, i.e., the number of singular values
91 which are greater than RCOND*S(1).
92 WORK (workspace/output) COMPLEX array, dimension (MAX(1,LWORK))
94 On exit, if INFO = 0, WORK(1) returns the optimal LWORK.
95 LWORK (input) INTEGER
97 The dimension of the array WORK. LWORK must be at least 1. The
98 exact minimum amount of workspace needed depends on M, N and
99 NRHS. As long as LWORK is at least 2 * N + N * NRHS if M is
100 greater than or equal to N or 2 * M + M * NRHS if M is less
101 than N, the code will execute correctly. For good performance,
102 LWORK should generally be larger.
103 If LWORK = -1, then a workspace query is assumed; the routine
105 only calculates the optimal size of the array WORK and the min‐
106 imum sizes of the arrays RWORK and IWORK, and returns these
107 values as the first entries of the WORK, RWORK and IWORK
108 arrays, and no error message related to LWORK is issued by
109 XERBLA.
110 RWORK (workspace) REAL array, dimension (MAX(1,LRWORK))
112 LRWORK >= 10*N + 2*N*SMLSIZ + 8*N*NLVL + 3*SMLSIZ*NRHS + (SML‐
113 SIZ+1)**2 if M is greater than or equal to N or 10*M + 2*M*SML‐
114 SIZ + 8*M*NLVL + 3*SMLSIZ*NRHS + (SMLSIZ+1)**2 if M is less
115 than N, the code will execute correctly. SMLSIZ is returned by
116 ILAENV and is equal to the maximum size of the subproblems at
117 the bottom of the computation tree (usually about 25), and NLVL
118 = MAX( 0, INT( LOG_2( MIN( M,N )/(SMLSIZ+1) ) ) + 1 ) On exit,
119 if INFO = 0, RWORK(1) returns the minimum LRWORK.
120 IWORK (workspace) INTEGER array, dimension (MAX(1,LIWORK))
122 LIWORK >= max(1, 3*MINMN*NLVL + 11*MINMN), where MINMN = MIN(
123 M,N ). On exit, if INFO = 0, IWORK(1) returns the minimum
124 LIWORK.
125 INFO (output) INTEGER
127 = 0: successful exit
128 < 0: if INFO = -i, the i-th argument had an illegal value.
129 > 0: the algorithm for computing the SVD failed to converge;
130 if INFO = i, i off-diagonal elements of an intermediate bidiag‐
131 onal form did not converge to zero.
132
134 Based on contributions by
135 Ming Gu and Ren-Cang Li, Computer Science Division, University of
136 California at Berkeley, USA
137 Osni Marques, LBNL/NERSC, USA
138 LAPACK driver routine (version 3.N1o)vember 2006 CGELSD(1)