Debian Codegraph @

src/ImathTest/testTinySVD.cpp

raw
1 //
2 // SPDX-License-Identifier: BSD-3-Clause
3 // Copyright Contributors to the OpenEXR Project.
4 //
5
6 #ifdef NDEBUG
7 # undef NDEBUG
8 #endif
9
10 #include <ImathMatrixAlgo.h>
11 #include <algorithm>
12 #include <assert.h>
13 #include <cmath>
14 #include <iostream>
15 #include <limits>
16
17 template <typename T>
18 void
19 verifyOrthonormal (const IMATH_INTERNAL_NAMESPACE::Matrix33<T>& A)
20 {
21 const T valueEps = T (100) * std::numeric_limits<T>::epsilon();
22
23 const IMATH_INTERNAL_NAMESPACE::Matrix33<T> prod = A * A.transposed();
24 for (int i = 0; i < 3; ++i)
25 {
26 for (int j = 0; j < 3; ++j)
27 {
28 if (i == j)
29 assert (std::abs (prod[i][j] - 1) < valueEps);
30 else
31 assert (std::abs (prod[i][j]) < valueEps);
32 }
33 }
34 }
35
36 template <typename T>
37 void
38 verifyOrthonormal (const IMATH_INTERNAL_NAMESPACE::Matrix44<T>& A)
39 {
40 const T valueEps = T (100) * std::numeric_limits<T>::epsilon();
41
42 const IMATH_INTERNAL_NAMESPACE::Matrix44<T> prod = A * A.transposed();
43 for (int i = 0; i < 4; ++i)
44 {
45 for (int j = 0; j < 4; ++j)
46 {
47 if (i == j)
48 assert (std::abs (prod[i][j] - 1) <= valueEps);
49 else
50 assert (std::abs (prod[i][j]) <= valueEps);
51 }
52 }
53 }
54
55 template <typename T>
56 void
57 verifyTinySVD_3x3 (const IMATH_INTERNAL_NAMESPACE::Matrix33<T>& A)
58 {
59 T maxEntry = 0;
60 for (int i = 0; i < 3; ++i)
61 for (int j = 0; j < 3; ++j)
62 maxEntry = std::max (maxEntry, std::abs (A[i][j]));
63
64 const T eps = std::numeric_limits<T>::epsilon();
65 const T valueEps = maxEntry * T (10) * eps;
66
67 for (int i = 0; i < 2; ++i)
68 {
69 const bool posDet = (i == 0);
70
71 IMATH_INTERNAL_NAMESPACE::Matrix33<T> U, V;
72 IMATH_INTERNAL_NAMESPACE::Vec3<T> S;
73 IMATH_INTERNAL_NAMESPACE::jacobiSVD (A, U, S, V, eps, posDet);
74
75 IMATH_INTERNAL_NAMESPACE::Matrix33<T> S_times_Vt;
76 for (int i = 0; i < 3; ++i)
77 for (int j = 0; j < 3; ++j)
78 S_times_Vt[i][j] = S[j] * V[i][j];
79 S_times_Vt.transpose();
80
81 // Verify that the product of the matrices is A:
82 const IMATH_INTERNAL_NAMESPACE::Matrix33<T> product = U * S_times_Vt;
83 for (int i = 0; i < 3; ++i)
84 for (int j = 0; j < 3; ++j)
85 assert (std::abs (product[i][j] - A[i][j]) <= valueEps);
86
87 // Verify that U and V are orthogonal:
88 if (posDet)
89 {
90 assert (U.determinant() > 0.9);
91 assert (V.determinant() > 0.9);
92 }
93
94 // Verify that the singular values are sorted:
95 for (int i = 0; i < 2; ++i)
96 assert (S[i] >= S[i + 1]);
97
98 // Verify that all the SVs except maybe the last one are positive:
99 for (int i = 0; i < 2; ++i)
100 assert (S[i] >= T (0));
101
102 if (!posDet)
103 assert (S[2] >= T (0));
104
105 verifyOrthonormal (U);
106 verifyOrthonormal (V);
107 }
108 }
109
110 template <typename T>
111 void
112 verifyTinySVD_4x4 (const IMATH_INTERNAL_NAMESPACE::Matrix44<T>& A)
113 {
114 T maxEntry = 0;
115 for (int i = 0; i < 4; ++i)
116 for (int j = 0; j < 4; ++j)
117 maxEntry = std::max (maxEntry, std::abs (A[i][j]));
118
119 const T eps = std::numeric_limits<T>::epsilon();
120 const T valueEps = maxEntry * T (100) * eps;
121
122 for (int i = 0; i < 2; ++i)
123 {
124 const bool posDet = (i == 0);
125
126 IMATH_INTERNAL_NAMESPACE::Matrix44<T> U, V;
127 IMATH_INTERNAL_NAMESPACE::Vec4<T> S;
128 IMATH_INTERNAL_NAMESPACE::jacobiSVD (A, U, S, V, eps, posDet);
129
130 IMATH_INTERNAL_NAMESPACE::Matrix44<T> S_times_Vt;
131 for (int i = 0; i < 4; ++i)
132 for (int j = 0; j < 4; ++j)
133 S_times_Vt[i][j] = S[j] * V[i][j];
134 S_times_Vt.transpose();
135
136 // Verify that the product of the matrices is A:
137 const IMATH_INTERNAL_NAMESPACE::Matrix44<T> product = U * S_times_Vt;
138 for (int i = 0; i < 4; ++i)
139 for (int j = 0; j < 4; ++j)
140 assert (std::abs (product[i][j] - A[i][j]) <= valueEps);
141
142 // Verify that U and V have positive determinant if requested:
143 if (posDet)
144 {
145 assert (U.determinant() > 0.99);
146 assert (V.determinant() > 0.99);
147 }
148
149 // Verify that the singular values are sorted:
150 for (int i = 0; i < 3; ++i)
151 assert (S[i] >= S[i + 1]);
152
153 // Verify that all the SVs except maybe the last one are positive:
154 for (int i = 0; i < 3; ++i)
155 assert (S[i] >= T (0));
156
157 if (!posDet)
158 assert (S[3] >= T (0));
159
160 verifyOrthonormal (U);
161 verifyOrthonormal (V);
162 }
163 }
164
165 template <typename T>
166 void
167 testTinySVD_3x3 (const IMATH_INTERNAL_NAMESPACE::Matrix33<T>& A)
168 {
169 std::cout << "Verifying SVD for [[" << A[0][0] << ", " << A[0][1] << ", " << A[0][2] << "], "
170 << "[" << A[1][0] << ", " << A[1][1] << ", " << A[1][2] << "], "
171 << "[" << A[2][0] << ", " << A[2][1] << ", " << A[2][2] << "]]\n";
172
173 verifyTinySVD_3x3 (A);
174 verifyTinySVD_3x3 (A.transposed());
175
176 // Try all different orderings of the columns of A:
177 int cols[3] = { 0, 1, 2 };
178 do
179 {
180 IMATH_INTERNAL_NAMESPACE::Matrix33<T> B;
181 for (int i = 0; i < 3; ++i)
182 for (int j = 0; j < 3; ++j)
183 B[i][j] = A[i][cols[j]];
184
185 verifyTinySVD_3x3 (B);
186 } while (std::next_permutation (cols, cols + 3));
187 }
188
189 template <typename T>
190 void
191 testTinySVD_3x3 (const T a,
192 const T b,
193 const T c,
194 const T d,
195 const T e,
196 const T f,
197 const T g,
198 const T h,
199 const T i)
200 {
201 const IMATH_INTERNAL_NAMESPACE::Matrix33<T> A (a, b, c, d, e, f, g, h, i);
202 testTinySVD_3x3 (A);
203 }
204
205 template <typename T>
206 void
207 testTinySVD_4x4 (const IMATH_INTERNAL_NAMESPACE::Matrix44<T>& A)
208 {
209 std::cout << "Verifying SVD for [[" << A[0][0] << ", " << A[0][1] << ", " << A[0][2] << ", "
210 << A[0][3] << "], "
211 << "[" << A[1][0] << ", " << A[1][1] << ", " << A[1][2] << ", " << A[1][3] << "], "
212 << "[" << A[2][0] << ", " << A[2][1] << ", " << A[2][2] << ", " << A[2][3] << "], "
213 << "[" << A[3][0] << ", " << A[3][1] << ", " << A[3][2] << ", " << A[3][3] << "]]\n";
214
215 verifyTinySVD_4x4 (A);
216 verifyTinySVD_4x4 (A.transposed());
217
218 // Try all different orderings of the columns of A:
219 int cols[4] = { 0, 1, 2, 3 };
220 do
221 {
222 IMATH_INTERNAL_NAMESPACE::Matrix44<T> B;
223 for (int i = 0; i < 4; ++i)
224 for (int j = 0; j < 4; ++j)
225 B[i][j] = A[i][cols[j]];
226
227 verifyTinySVD_4x4 (B);
228 } while (std::next_permutation (cols, cols + 4));
229 }
230
231 template <typename T>
232 void
233 testTinySVD_4x4 (const T a,
234 const T b,
235 const T c,
236 const T d,
237 const T e,
238 const T f,
239 const T g,
240 const T h,
241 const T i,
242 const T j,
243 const T k,
244 const T l,
245 const T m,
246 const T n,
247 const T o,
248 const T p)
249 {
250 const IMATH_INTERNAL_NAMESPACE::Matrix44<T> A (a, b, c, d, e, f, g, h, i, j, k, l, m, n, o, p);
251 testTinySVD_4x4 (A);
252 }
253
254 template <typename T>
255 void
256 testTinySVDImp()
257 {
258 // Try a bunch of 3x3 matrices:
259 testTinySVD_3x3<T> (1, 0, 0, 0, 1, 0, 0, 0, 1);
260 testTinySVD_3x3<T> (1, 0, 0, 0, -1, 0, 0, 0, 1);
261 testTinySVD_3x3<T> (0, 0, 0, 0, 0, 0, 0, 0, 0);
262 testTinySVD_3x3<T> (0, 0, 0, 0, 0, 0, 0, 0, 1);
263 testTinySVD_3x3<T> (1, 0, 0, 0, 1, 0, 0, 0, 0);
264 testTinySVD_3x3<T> (1, 0, 0, 0, 0, 0, 0, 0, 0);
265 testTinySVD_3x3<T> (1, 0, 0, T(1e-10), 0, 0, 0, 0, 0);
266 testTinySVD_3x3<T> (1, 0, 0, T(1e-10), 0, 0, 0, 0, 100000);
267 testTinySVD_3x3<T> (1, 2, 3, 4, 5, 6, 7, 8, 9);
268 testTinySVD_3x3<T> (1, 2, 3, 4, 5, 6, 7, 8, 9);
269 testTinySVD_3x3<T> (outerProduct (
270 IMATH_INTERNAL_NAMESPACE::Vec3<T> (100, T(1e-5), 0),
271 IMATH_INTERNAL_NAMESPACE::Vec3<T> (100, T(1e-5), 0)));
272 testTinySVD_3x3<T> (outerProduct (
273 IMATH_INTERNAL_NAMESPACE::Vec3<T> (245, 20, 1),
274 IMATH_INTERNAL_NAMESPACE::Vec3<T> (256, 300, 20)));
275 testTinySVD_3x3<T> (
276 outerProduct (
277 IMATH_INTERNAL_NAMESPACE::Vec3<T> (245, 20, 1),
278 IMATH_INTERNAL_NAMESPACE::Vec3<T> (245, 20, 1)) +
279 outerProduct (
280 IMATH_INTERNAL_NAMESPACE::Vec3<T> (1, 2, 3),
281 IMATH_INTERNAL_NAMESPACE::Vec3<T> (1, 2, 3)));
282
283 // Some problematic matrices from SVDTest:
284 testTinySVD_3x3<T> (
285 T(0.0023588321752040036),
286 T(-0.0096558131480729038),
287 T(0.0010959850449366493),
288 T(0.0088671829608044754),
289 T(0.0016771794267033666),
290 T(-0.0043081475729438235),
291 T(0.003976050440932701),
292 T(0.0019880497026345716),
293 T(0.0089576046614601966));
294 testTinySVD_3x3<T> (
295 T(2.3588321752040035e-09),
296 T(-9.6558131480729038e-09),
297 T(1.0959850449366498e-09),
298 T(8.8671829608044748e-09),
299 T(1.6771794267033661e-09),
300 T(-4.3081475729438225e-09),
301 T(3.9760504409327016e-09),
302 T(1.9880497026345722e-09),
303 T(8.9576046614601957e-09));
304 testTinySVD_3x3<T> (
305 T(-0.46673855799602715),
306 T(0.67466260360310948),
307 T(0.97646986796448998),
308 T(-0.032460753747103721),
309 T(0.046584527749418278),
310 T(0.067431228641151142),
311 T(-0.088885055229687815),
312 T(0.1280389179308779),
313 T(0.18532617511453064));
314 testTinySVD_3x3<T> (T(1e-8), 0, 0, 0, T(1e-8), 0, 0, 0, T(1e-8));
315 testTinySVD_3x3<T> (1, 0, 0, 0, T(.00036), 0, T(1e-18), 0, T(.00018));
316 testTinySVD_3x3<T> (T(1.3), 0, 0, 0, T(.0003), 0, T(1e-17), 0, 0);
317 testTinySVD_3x3<T> (1, 0, 0, 0, T(1e-2), 0, 0, 0, T(1e-2));
318 testTinySVD_3x3<T> (1, 0, 0, 0, 1, 0, 0, 0, 0);
319 testTinySVD_3x3<T> (1, 0, 0, 0, T(1e-3), 0, 0, 0, T(1e-6));
320 testTinySVD_3x3<T> (
321 T(0.59588638570136332),
322 T(-0.79761234126107794),
323 -1,
324 T(0.39194500425202045),
325 T(0.91763115383440363),
326 T(-0.341818175044664),
327 T(-0.45056075218951946),
328 T(-0.71259057727425101),
329 T(0.47125008216720271));
330 testTinySVD_3x3<T> (
331 T(4.38805348e-09),
332 T(-2.53189691e-09),
333 T(-4.65678607e-09),
334 T(-3.23000099e-10),
335 T(1.86370294e-10),
336 T(3.42781192e-10),
337 T(-4.61572824e-09),
338 T(2.6632645e-09),
339 T(4.89840346e-09));
340 // problematic 2x2 one for lapack on suse (see below), padded with 0's
341 testTinySVD_3x3<T> (0, T(-1.00000003e-22), 0, T(1.00000001e-07), 0, 0, 0, 0, 0);
342 // problematic 2x2 one for lapack on suse (see below), padded with 0's and 1
343 testTinySVD_3x3<T> (0, T(-1.00000003e-22), 0, T(1.00000001e-07), 0, 0, 0, 0, 1);
344
345 // Now, 4x4 matrices:
346 testTinySVD_4x4<T> (1, 0, 0, 0, 0, 1, 0, 0, 0, 0, 1, 0, 0, 0, 0, 1);
347 testTinySVD_4x4<T> (1, 0, 0, 0, 0, -1, 0, 0, 0, 0, 1, 0, 0, 0, 0, 1);
348 testTinySVD_4x4<T> (1, 0, 0, 0, 0, 1, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0);
349 testTinySVD_4x4<T> (1, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0);
350 testTinySVD_4x4<T> (0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0);
351 testTinySVD_4x4<T> (1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0);
352 testTinySVD_4x4<T> (1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16);
353 testTinySVD_4x4<T> (
354 0,
355 T(-1.00000003e-22),
356 0,
357 0,
358 T(00000001e-07),
359 0,
360 0,
361 0,
362 0,
363 0,
364 1,
365 0,
366 0,
367 0,
368 0,
369 1);
370 testTinySVD_4x4<T> (outerProduct (
371 IMATH_INTERNAL_NAMESPACE::Vec4<T> (100, T(1e-5), 0, 0),
372 IMATH_INTERNAL_NAMESPACE::Vec4<T> (100, T(1e-5), 0, 0)));
373 testTinySVD_4x4<T> (outerProduct (
374 IMATH_INTERNAL_NAMESPACE::Vec4<T> (245, 20, 1, T(0.5)),
375 IMATH_INTERNAL_NAMESPACE::Vec4<T> (256, 300, 20, 10)));
376 testTinySVD_4x4<T> (
377 outerProduct (
378 IMATH_INTERNAL_NAMESPACE::Vec4<T> (245, 20, 1, T(0.5)),
379 IMATH_INTERNAL_NAMESPACE::Vec4<T> (256, 300, 20, 10)) +
380 outerProduct (
381 IMATH_INTERNAL_NAMESPACE::Vec4<T> (30, 10, 10, 10),
382 IMATH_INTERNAL_NAMESPACE::Vec4<T> (1, 2, 3, 3)));
383 }
384
385 void
386 testTinySVD()
387 {
388 std::cout << "Testing TinySVD algorithms in single precision..." << std::endl;
389 testTinySVDImp<float>();
390
391 std::cout << "Testing TinySVD algorithms in double precision..." << std::endl;
392 testTinySVDImp<double>();
393 }