lib/PDL/MatrixOps/svd.c

filter: Statementstmt 100% 45 / 45 Branchbran 97.8% 45 / 46 Conditioncond n/a MC/DCmcdc n/a Subroutinesub n/a Podpod n/a totaltotal 98.9% 90 / 91 CC 0 SCAR 0
CC
0
Cov
0%
CRAP 0
« lib/PDL/Slices.pd ↑ Summary lib/PDL/MatrixOps/eigens.c »
1 /* From bryant@sioux.stanford.edu Sat Apr 3 14:57:54 1993
2 Return-Path: <bryant@sioux.stanford.edu>
3 Received: from sioux.stanford.edu by alnitak.usc.edu (4.1/SMI-4.1+ucs-3.6)
4 id AA12724; Sat, 3 Apr 93 14:57:52 PST
5 Received: from oglala.ice (oglala.Stanford.EDU) by sioux.stanford.edu (4.1/inc-1.0)
6 id AA07300; Sat, 3 Apr 93 14:53:25 PST
7 Date: Sat, 3 Apr 93 14:53:25 PST
8 From: bryant@sioux.stanford.edu (Bryant Marks)
9 Message-Id: <9304032253.AA07300@sioux.stanford.edu>
10 To: ajayshah@rcf.usc.edu
11 Subject: Re: SVD
12 Status: ORr
13  
14  
15 > Hi! Long ago you sent me an svd routine in C based on code
16 > from Nash in Pascal. Has this changed any over the years? (Your
17 > email is dated July 1992). Is your code available by anon ftp?
18  
19 Hi Ajay,
20  
21 I don't think I have changed the code -- but here's my most recent
22 version of the code, you can check to see if it's any different.
23 Currently it's not available via anonymous ftp but feel free to
24 redistribute the code -- it seems to work well in the application
25 I'm using it in.
26  
27  
28 Bryant
29 */
30  
31 /*This SVD routine is based on pgs 30-48 of "Compact Numerical Methods
32 for Computers" by J.C. Nash (1990), used to compute the pseudoinverse.
33 Modifications include:
34 Translation from Pascal to ANSI C.
35 Array indexing from 0 rather than 1.
36 Float replaced by double everywhere.
37 Support for the Matrix structure.
38 I changed the array indexing so that the matricies (float [][])
39 could be replaced be a single list (double *) for more
40 efficient communication with Mathematica.
41 */
42  
43 /* rjrw 7/7/99: changed z back to a vector, moved one line... */
44  
45 /*
46 Derek A. Lamb 2016: added comments to aid understanding, since
47 Nash's book will only get more difficult to find in the future.
48 */
49  
50 /*
51 Form a singular value decomposition of matrix A.
52 The SVD is thin. To get a full SVD, zero-pad A on the bottom,
53 transposing if is tall, so nCol == nRow. If zero-pad on right per
54 some literature, the column rotation doesn't happen since it
55 thinks it's already finished.
56 Input:
57 A is stored in the nRow*nCol elements of U
58 Upon return:
59 array U will become the U of an svd.
60 array V will become the square (nCol*nCol) matrix V of the svd.
61 S will contain the nCol singular values.
62  
63 The input matrix A must have nRow >= nCol. If it does
64 not, one should input the transpose of A, A", to find the the svd
65 of A, since A = U x S x V" and A" = V x S x U". (The " means transpose.)
66 */
67  
68 #include <math.h>
69 #define TOLERANCE 1.0e-22
70 #define SVD_ROTATE_COL(M, colind, colind2, rowind, ncols, nrows, cos0, sin0) \
71 for (rowind=0; rowind<nrows; rowind++) \
72 SVD_ROTATE_VALS(M[ncols*rowind+colind], M[ncols*rowind+colind2], cos0, sin0)
73 #define SVD_ROTATE_VALS(colval1, colval2, cos0, sin0) \
74 { \
75 double d1 = colval1, d2 = colval2; \
76 colval1 = d1*cos0 + d2*sin0; colval2 = -d1*sin0 + d2*cos0; \
77 }
78 #define PRINTMAT(M, colind, rowind, ncols, nrows) \
79 printf(#M ":\n"); \
80 for (rowind=0;rowind<nrows;rowind++) { \
81 for (colind=0;colind<ncols;colind++) \
82 printf("%4.2g ",M[rowind*ncols + colind]); \
83 printf("\n"); \
84 }
85 #define PRINTVEC(V, colind, ncols) \
86 printf(#V " vector:\n"); \
87 for (colind=0;colind<ncols;colind++) \
88 printf("%4.2g ",V[colind]); \
89 printf("\n");
90  
91 #if DEBUG
92 #include <stdio.h>
93 #endif
94  
95 30 void SVD(double *U, double *V, double *S, int nRow, int nCol)
96 {
97 int i, j, k, EstColRank, RotCount, SweepCount, slimit;
98 double eps, e2, tol, vt, p, x0, y0, q, r, c0, s0;
99 30 eps = TOLERANCE;
100 /*set a limit on the number of sweeps allowed. A suggested limit is slimit=max([nCol/4],6).*/
101 30 slimit = nCol/4;
102 30 ▶ if (slimit < 6.0)
Branch: 1 branch
BranchTrueFalseTotal
if (slimit < 6.0) 30 0 30
103 30 slimit = 6;
104 30 SweepCount = 0;
105 30 e2 = 10.0*nRow*eps*eps;
106 30 tol = eps*.1; /*set convergence tolerances */
107 30 EstColRank = nCol; /* current estimate of rank */
108 /* Set V matrix to the unit matrix of order nCol. */
109 217 ▶ for (i=0; i<nCol; i++)
Branch: 1 branch
BranchTrueFalseTotal
for (i=0; i<nCol; i++) 187 30 217
110 1946 ▶ for (j=0; j<nCol; j++)
Branch: 1 branch
BranchTrueFalseTotal
for (j=0; j<nCol; j++) 1759 187 1946
111 1759 ▶ V[ nCol*i + j ] = i == j ? 1.0 : 0.0;
Branch: 1 branch
BranchTrueFalseTotal
V[ nCol*i + j ] = i == j ? 1.0 : 0.0; 187 1572 1759
112 #if DEBUG
113 printf("BEFORE "); PRINTMAT(U, j, i, nCol, nRow)
114 printf("BEFORE "); PRINTMAT(V, j, i, nCol, nCol)
115 #endif
116 30 RotCount = EstColRank*(EstColRank-1)/2;
117 /*until convergence is achieved or too many sweeps are carried out*/
118 207 ▶ while (RotCount != 0 && SweepCount <= slimit) {
Branch: 2 branches
BranchTrueFalseTotal
while (RotCount != 0 && SweepCount <= slimit) { 199 8 207
while (RotCount != 0 && SweepCount <= slimit) { 177 22 199
119 177 RotCount = EstColRank*(EstColRank-1)/2; /* rotation counter */
120 177 SweepCount++;
121 1203 ▶ for (j=0; j<EstColRank-1; j++) { /* main cyclic Jacobi sweep */
Branch: 1 branch
BranchTrueFalseTotal
for (j=0; j<EstColRank-1; j++) { /* main cyclic Jacobi sweep */ 1026 177 1203
122 6245 ▶ for (k=j+1; k<EstColRank; k++) {
Branch: 1 branch
BranchTrueFalseTotal
for (k=j+1; k<EstColRank; k++) { 5219 1026 6245
123 5219 p = q = r = 0.0;
124 /*
125 Some helpful definitions from Nash's book (pg 34) to
126 understand this p, q, & r rotation business:
127 p = x"y; (" means transpose)
128 q = x"x - y"y;
129 v = sqrt(4*p^2+q^2);
130 if (q>=0) {
131 cos(phi) = sqrt((v+q)/(2*v));
132 sin(phi) = p/(v*cos(phi));
133 } else if (q<0) {,
134 (sgn(p)=+1 for p>=0, -1 for p<0);
135 sin(phi) = sgn(p)*sqrt((v-q)/(2*v));
136 cos(phi) = p/(v*sin(phi));
137 }
138 This formulation avoids the subtraction of two nearly
139 equal numbers, which is bound to happen to q and v as
140 the matrix approaches orthogonality.
141 */
142 109676 ▶ for (i=0; i<nRow; i++) {
Branch: 1 branch
BranchTrueFalseTotal
for (i=0; i<nRow; i++) { 104457 5219 109676
143 104457 x0 = U[nCol*i+j]; y0 = U[nCol*i+k];
144 104457 p += x0*y0; q += x0*x0; r += y0*y0;
145 }
146 5219 S[j] = q; S[k] = r;
147 /* Convergence test: will rotation exchange order of columns?*/
148 5219 ▶ if (q >= r) { /* check if columns are ordered */
Branch: 1 branch
BranchTrueFalseTotal
if (q >= r) { /* check if columns are ordered */ 4716 503 5219
149 /* columns are ordered, so try convergence test */
150 4716 ▶ if (q<=e2*S[0] || fabs(p)<=tol*q) {
Branch: 2 branches
BranchTrueFalseTotal
if (q<=e2*S[0] || fabs(p)<=tol*q) { 4714 2 4716
if (q<=e2*S[0] || fabs(p)<=tol*q) { 511 4203 4714
151 /* There is no more work on this particular pair of
152 columns in the current sweep. The first condition
153 checks for very small column norms in BOTH
154 columns, for which no rotation makes sense. The
155 second condition determines if the inner product
156 is small with respect to the larger of the
157 columns, which implies a very small rotation
158 angle. */
159 513 RotCount--;
160 } else {
161 /* columns are in order, but their inner product is not small */
162 4203 p /= q; r = 1 - r/q; vt = sqrt(4*p*p+r*r);
163 /* DAL thinks the fabs is unnecessary in the
164 next line: vt is non-negative; q>=r, r/q <=1
165 so after the assignment 0<= r <=1, so r/vt is
166 positive, so everything inside the sqrt
167 should be positive even without the fabs. abs
168 isn't in Nash's book. c0 and s0 are cos(phi) and sin(phi) as above for q>=0*/
169 4203 c0 = sqrt(fabs(.5*(1+r/vt))); s0 = p/(vt*c0);
170 87708 ▶ SVD_ROTATE_COL(U, j, k, i, nCol, nRow, c0, s0)
Branch: 1 branch
BranchTrueFalseTotal
SVD_ROTATE_COL(U, j, k, i, nCol, nRow, c0, s0) 83505 4203 87708
171 56818 ▶ SVD_ROTATE_COL(V, j, k, i, nCol, nCol, c0, s0)
Branch: 1 branch
BranchTrueFalseTotal
SVD_ROTATE_COL(V, j, k, i, nCol, nCol, c0, s0) 52615 4203 56818
172 }
173 } else {
174 /* columns out of order -- must rotate */
175 /* note: r>q, and cannot be zero since both are sums
176 of squares for the svd. In the case of a real
177 symmetric matrix, this assumption must be
178 questioned. */
179 503 p /= r; q = q/r-1; vt = sqrt(4*p*p+q*q);
180 503 s0 = sqrt(fabs(.5*(1-q/vt)));
181 /* DAL wondering about the fabs again, since after
182 assignment q is <0 and vt is again positive, so
183 everything inside the fabs should be positive
184 already */
185 503 ▶ if (p<0) s0 = -s0; /*s0 and c0 are sin(phi) and cos(phi) as above for q<0 */
Branch: 1 branch
BranchTrueFalseTotal
if (p<0) s0 = -s0; /*s0 and c0 are sin(phi) and cos(phi) as above for q<0 */ 219 284 503
186 503 c0 = p/(vt*s0);
187 11599 ▶ SVD_ROTATE_COL(U, j, k, i, nCol, nRow, c0, s0)
Branch: 1 branch
BranchTrueFalseTotal
SVD_ROTATE_COL(U, j, k, i, nCol, nRow, c0, s0) 11096 503 11599
188 6590 ▶ SVD_ROTATE_COL(V, j, k, i, nCol, nCol, c0, s0)
Branch: 1 branch
BranchTrueFalseTotal
SVD_ROTATE_COL(V, j, k, i, nCol, nCol, c0, s0) 6087 503 6590
189 }
190 /* Both angle calculations have been set up so that
191 large numbers do not occur in intermediate
192 quantities. This is easy in the svd case, since
193 quantities x2,y2 cannot be negative.*/
194 } /* loop on k */
195 } /* loop on j */
196 189 ▶ while (EstColRank>=3 && S[EstColRank-1]<=S[0]*tol+tol*tol)
Branch: 2 branches
BranchTrueFalseTotal
while (EstColRank>=3 && S[EstColRank-1]<=S[0]*tol+tol*tol) 167 22 189
while (EstColRank>=3 && S[EstColRank-1]<=S[0]*tol+tol*tol) 12 155 167
197 12 EstColRank--;
198 }
199 217 ▶ for (j = 0; j < nCol; j++)
Branch: 1 branch
BranchTrueFalseTotal
for (j = 0; j < nCol; j++) 187 30 217
200 187 S[j] = sqrt(S[j]);
201 507 ▶ for (i=0; i < nRow; i++)
Branch: 1 branch
BranchTrueFalseTotal
for (i=0; i < nRow; i++) 477 30 507
202 3764 ▶ for (j=0; j < nCol; j++)
Branch: 1 branch
BranchTrueFalseTotal
for (j=0; j < nCol; j++) 3287 477 3764
203 3287 ▶ if (U[ nCol*i + j ])
Branch: 1 branch
BranchTrueFalseTotal
if (U[ nCol*i + j ]) 3232 55 3287
204 3232 U[ nCol*i + j ] /= S[j];
205 #if DEBUG
206 if (SweepCount > slimit)
207 fprintf(stderr, "Sweeps = %d\n", SweepCount);
208 printf("AFTER "); PRINTMAT(U, j, i, nCol, nRow)
209 printf("AFTER "); PRINTMAT(V, j, i, nCol, nCol)
210 PRINTVEC(S, j, nCol)
211 #endif
212 30 }
213  
214 /* build this with `cc -DMAIN lib/PDL/MatrixOps/svd.c` */
215 #ifdef MAIN
216 #include <stdio.h>
217 #define NC 2
218 #define NR 2
219 #define NC2 2
220 #define NR2 3
221 int main()
222 {
223 int i,j;
224 double u[NC*NR] = { 1, 3, -4, 3 }, v[NC*NC], z[NC];
225 double u2[NC2*NR2] = { 3, 1, -1, 3, -2, 3 }, v2[NC2*NC2], z2[NC2];
226 printf("BEFORE "); PRINTMAT(u, j, i, NC, NR)
227 SVD(u, v, z, NR, NC);
228 PRINTMAT(u, j, i, NC, NR)
229 PRINTMAT(v, j, i, NC, NC)
230 PRINTVEC(z, j, NC)
231 printf("BEFORE "); PRINTMAT(u2, j, i, NC2, NR2)
232 SVD(u2, v2, z2, NR2, NC2);
233 PRINTMAT(u2, j, i, NC2, NR2)
234 PRINTMAT(v2, j, i, NC2, NC2)
235 PRINTVEC(z2, j, NC2)
236 return 0;
237 }
238 #endif
« lib/PDL/Slices.pd ↑ Summary lib/PDL/MatrixOps/eigens.c »