| 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| for (i=0; i<nCol; i++) |
187 |
30 |
217 |
|
| 110 |
1946 |
▶ | for (j=0; j<nCol; j++) |
Branch: 1 branch
| Branch | True | False | Total |
| for (j=0; j<nCol; j++) |
1759 |
187 |
1946 |
|
| 111 |
1759 |
▶ | V[ nCol*i + j ] = i == j ? 1.0 : 0.0; |
Branch: 1 branch
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| for (i=0; i < nRow; i++) |
477 |
30 |
507 |
|
| 202 |
3764 |
▶ | for (j=0; j < nCol; j++) |
Branch: 1 branch
| Branch | True | False | Total |
| for (j=0; j < nCol; j++) |
3287 |
477 |
3764 |
|
| 203 |
3287 |
▶ | if (U[ nCol*i + j ]) |
Branch: 1 branch
| Branch | True | False | Total |
| 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 |