Debian Codegraph @

src/ImathTest/testJacobiEigenSolver.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 <ImathMatrix.h>
11 #include <ImathMatrixAlgo.h>
12 #include <algorithm>
13 #include <cassert>
14 #include <cmath>
15 #include <ctime>
16 #include <iostream>
17 #include <limits>
18 #include <math.h>
19
20 using namespace std;
21 using namespace IMATH_INTERNAL_NAMESPACE;
22
23 // clang-format off
24
25 const Matrix33<double> A33_1 ( 1, 0, 0, 0, 1, 0, 0, 0, 1 );
26 const Matrix33<double> A33_2 ( 1, 0, 0, 0,-1, 0, 0, 0, 1 );
27 const Matrix33<double> A33_3 ( 1, 0, 0, 0, 1, 0, 0, 0, 0 );
28 const Matrix33<double> A33_4 ( 1, 0, 0, 0, 0, 0, 0, 0, 0 );
29 const Matrix33<double> A33_5 ( 0, 0, 0, 0, 0, 0, 0, 0, 0 );
30 const Matrix33<double> A33_6 ( 1, 0, 0, 0, 1e-10, 0, 0, 0, 0 );
31 const Matrix33<double> A33_7 ( 1, 0, 0, 0, 1e-10, 0, 0, 0, 1e+10 );
32 const Matrix33<double> A33_8 (
33 0.25058694044821, 0.49427229444416, 0.81415724537748,
34 0.49427229444416, 0.80192384710853, -0.61674948224910,
35 0.81415724537748, -0.61674948224910, -1.28486154645285);
36
37 const Matrix44<double> A44_1 ( 1, 0, 0, 0, 0, 1, 0, 0, 0, 0, 1, 0, 0, 0, 0, 1 );
38 const Matrix44<double> A44_2 ( 1, 0, 0, 0, 0,-1, 0, 0, 0, 0, 1, 0, 0, 0, 0, 1 );
39 const Matrix44<double> A44_3 ( 1, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 );
40 const Matrix44<double> A44_4 ( 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 );
41 const Matrix44<double> A44_5 ( 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 );
42 const Matrix44<double> A44_6 ( 1, 0, 0, 0, 0, 1e-20, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0);
43 const Matrix44<double> A44_7 ( 1, 0, 0, 0, 0, 1e-20, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1e+20 );
44 const Matrix44<double> A44_8 (
45 4.05747631538951, 0.16358123075600, 0.11541756047409, -1.65369223465270,
46 0.16358123075600, 0.57629829390780, 3.88542912704029, 0.92016316185369,
47 0.11541756047409, 3.88542912704029, 0.65367032943707, -0.21971103270410,
48 -1.65369223465270, 0.92016316185369, -0.21971103270410, -0.28108876552761);
49
50 // clang-format on
51
52 template <typename TM>
53 void
54 verifyOrthonormal (const TM& A, const typename TM::BaseType threshold)
55 {
56 const TM prod = A * A.transposed ();
57 for (unsigned int i = 0; i < TM::dimensions (); ++i)
58 for (unsigned int j = 0; j < TM::dimensions (); ++j)
59 if (i == j)
60 assert (std::abs (prod[i][j] - 1) < threshold);
61 else
62 assert (std::abs (prod[i][j]) < threshold);
63 }
64
65 template <typename TM>
66 typename TM::BaseType
67 computeThreshold(const TM& A)
68 {
69 typedef typename TM::BaseType T;
70 T maxAbsEntry(0);
71
72 for (unsigned int i = 0; i < TM::dimensions (); ++i)
73 for (unsigned int j = 0; j < TM::dimensions (); ++j)
74 maxAbsEntry = std::max (maxAbsEntry, std::abs (A[i][j]));
75
76 const T eps = std::numeric_limits<T>::epsilon();
77 maxAbsEntry = std::max(maxAbsEntry, eps);
78
79 return maxAbsEntry * T(100) * eps;
80 }
81
82 template<class TM>
83 void
84 testJacobiEigenSolver(const TM& A)
85 {
86 using std::abs;
87
88 typedef typename TM::BaseType T;
89 typedef typename TM::BaseVecType TV;
90
91 const T threshold = computeThreshold(A);
92
93 TM AA(A);
94 TV S;
95 TM V;
96
97 jacobiEigenSolver(AA, S, V);
98
99 // Orthogonality of V
100 verifyOrthonormal(V, threshold);
101
102 // Determinant of V
103 assert(abs(V.determinant()) - 1 < threshold);
104
105 // Determinant of A and S
106 TM MS;
107 for (unsigned int i = 0; i < TM::dimensions (); ++i)
108 for (unsigned int j = 0; j < TM::dimensions (); ++j)
109 if (i == j)
110 MS[i][j] = S[i];
111 else
112 MS[i][j] = 0;
113
114 assert (abs (A.determinant()) - abs (MS.determinant()) < threshold);
115
116 // A = V * S * V^T
117 TM MA = V * MS * V.transposed();
118
119 for (unsigned int i = 0; i < TM::dimensions (); ++i)
120 for (unsigned int j = 0; j < TM::dimensions (); ++j)
121 assert (abs (A[i][j] - MA[i][j]) < threshold);
122 }
123
124 template<class TM>
125 void
126 testMinMaxEigenValue(const TM& A)
127 {
128 typedef typename TM::BaseVecType TV;
129 typedef typename TM::BaseType T;
130
131 TV minV, maxV, S;
132 TM U, V;
133
134 const T threshold = computeThreshold(A);
135
136 {
137 TM A1(A);
138 minEigenVector(A1, minV);
139 TM A2(A);
140 maxEigenVector(A2, maxV);
141 }
142 {
143 TM A3(A);
144 jacobiSVD(A3, U, S, V);
145 }
146
147 const int dim = TM::dimensions();
148
149 for (int i = 0; i < dim; ++i)
150 {
151 assert(abs(minV[i]-V[i][dim - 1]) < threshold);
152 assert(abs(maxV[i]-V[i][0]) < threshold);
153 }
154 }
155
156 template <class T>
157 void
158 testJacobiTiming()
159 {
160
161 int rounds(100000);
162 clock_t tJacobi,tSVD, t;
163
164 {
165 Matrix33<T> A,V,U;
166 Vec3<T> S;
167
168 t = clock();
169 for (int i = 0; i < rounds; ++i)
170 {
171 A = Matrix33<T>(A33_7);
172 jacobiEigenSolver(A, S, V);
173 A = Matrix33<T>(A33_8);
174 jacobiEigenSolver(A, S, V);
175 }
176 tJacobi = clock() - t;
177 cout << "Jacobi EigenSolver of 3x3 matrices took " << tJacobi << " clocks." << endl;
178
179 t = clock();
180 for (int i = 0; i < rounds; ++i)
181 {
182 A = Matrix33<T>(A33_7);
183 jacobiSVD(A, U, S, V);
184 A = Matrix33<T>(A33_8);
185 jacobiSVD(A, U, S, V);
186 }
187 tSVD = clock() - t;
188 cout << "TinySVD of 3x3 matrices took " << tSVD << " clocks." << endl;
189 cout << (float)(tSVD-tJacobi)*100.0f/(float)(tSVD) << "% speed up." << endl;
190 }
191
192 {
193 Matrix44<T> A,V,U;
194 Vec4<T> S;
195
196 t = clock();
197 for (int i = 0; i < rounds; ++i)
198 {
199 A = Matrix44<T>(A44_7);
200 jacobiEigenSolver(A, S, V);
201 A = Matrix44<T>(A44_8);
202 jacobiEigenSolver(A, S, V);
203 }
204 tJacobi = clock() - t;
205 cout << "Jacobi EigenSolver of 4x4 matrices took " << tJacobi << " clocks" << endl;
206
207 t = clock();
208 for (int i = 0; i < rounds; ++i)
209 {
210 A = Matrix44<T>(A44_7);
211 jacobiSVD(A, U, S, V);
212 A = Matrix44<T>(A44_8);
213 jacobiSVD(A, U, S, V);
214 }
215 tSVD = clock() - t;
216 cout << "TinySVD of 4x4 matrices took " << tSVD << " clocks" << endl;
217 cout << (float)(tSVD-tJacobi)*100.0f/(float)(tSVD) << "% speed up." << endl;
218 }
219 }
220
221 template <class T>
222 void
223 testJacobiEigenSolverImp()
224 {
225 testJacobiEigenSolver(Matrix33<T>(A33_1));
226 testJacobiEigenSolver(Matrix33<T>(A33_2));
227 testJacobiEigenSolver(Matrix33<T>(A33_3));
228 testJacobiEigenSolver(Matrix33<T>(A33_4));
229 testJacobiEigenSolver(Matrix33<T>(A33_5));
230 testJacobiEigenSolver(Matrix33<T>(A33_6));
231 testJacobiEigenSolver(Matrix33<T>(A33_7));
232 testJacobiEigenSolver(Matrix33<T>(A33_8));
233
234 testJacobiEigenSolver(Matrix44<T>(A44_1));
235 testJacobiEigenSolver(Matrix44<T>(A44_2));
236 testJacobiEigenSolver(Matrix44<T>(A44_3));
237 testJacobiEigenSolver(Matrix44<T>(A44_4));
238 testJacobiEigenSolver(Matrix44<T>(A44_5));
239 testJacobiEigenSolver(Matrix44<T>(A44_6));
240 testJacobiEigenSolver(Matrix44<T>(A44_7));
241 testJacobiEigenSolver(Matrix44<T>(A44_8));
242 }
243
244 template <class T>
245 void
246 testMinMaxEigenValueImp()
247 {
248 testMinMaxEigenValue(Matrix33<T>(A33_7));
249 testMinMaxEigenValue(Matrix33<T>(A33_8));
250
251 testMinMaxEigenValue(Matrix44<T>(A44_7));
252 testMinMaxEigenValue(Matrix44<T>(A44_8));
253 }
254
255 void
256 testJacobiEigenSolver()
257 {
258 cout << endl;
259 cout << "************ Testing IMATH_INTERNAL_NAMESPACE::ImathJacobiEigenSolver ************"
260 << endl;
261
262 cout << "Jacobi EigenSolver in single precision...";
263 testJacobiEigenSolverImp<float>();
264 cout << "PASS" << endl;
265
266 cout << "Jacobi EigenSolver in double precision...";
267 testJacobiEigenSolverImp<double>();
268 cout << "PASS" << endl;
269
270 cout << "Min/Max EigenValue in single precision...";
271 testMinMaxEigenValueImp<float>();
272 cout << "PASS" << endl;
273
274 cout << "Min/Max EigenValue in double precision...";
275 testMinMaxEigenValueImp<double>();
276 cout << "PASS" << endl;
277
278 cout << "Timing Jacobi EigenSolver in single precision...\n";
279 testJacobiTiming<float>();
280
281 cout << "Timing Jacobi EigenSolver in double precision...\n";
282 testJacobiTiming<double>();
283
284 cout << "************ ALL PASS ************" << endl;
285 }