MorphoGraphX
Eigenvalues.hpp
1 //
2 // Eigen-decomposition for symmetric 3x3 real matrices.
3 // Public domain, copied from the public domain Java library JAMA.
4 //
5 // Returns sorted list of eigenvectors and eigenvalues of a matrix
6 //
7 // Usage:
8 // void EigenDecompSym3x3(double matrix[3][3], double eigenvecs[3][3], double eigenvals[3]);
9 //
10 
11 //
12 // This file is part of MorphoGraphX - http://www.MorphoGraphX.org
13 // Copyright (C) 2012-2015 Richard S. Smith and collaborators.
14 //
15 // If you use MorphoGraphX in your work, please cite:
16 // http://dx.doi.org/10.7554/eLife.05864
17 //
18 // MorphoGraphX is free software, and is licensed under under the terms of the
19 // GNU General (GPL) Public License version 2.0, http://www.gnu.org/licenses.
20 //
21 #ifndef EIGENVALUES_H
22 #define EIGENVALUES_H
23 
24 #include <Config.hpp>
25 
26 #include <cuda/CudaGlobal.hpp>
27 #include <math.h>
28 
29 namespace {
30 
31 #ifdef MAX
32 # undef MAX
33 #endif
34 
35 #define MAX(a, b) ((a) > (b) ? (a) : (b))
36 
37 #define n 3
38 
39 CU_HOST_DEVICE
40 static double hypot2(double x, double y) {
41  return sqrt(x * x + y * y);
42 }
43 
44 // Symmetric Householder reduction to tridiagonal form.
45 
46 CU_HOST_DEVICE
47 static void tred2(double V[n][n], double d[n], double e[n])
48 {
49 
50  // This is derived from the Algol procedures tred2 by
51  // Bowdler, Martin, Reinsch, and Wilkinson, Handbook for
52  // Auto. Comp., Vol.ii-Linear Algebra, and the corresponding
53  // Fortran subroutine in EISPACK.
54 
55  for(int j = 0; j < n; j++) {
56  d[j] = V[n - 1][j];
57  }
58 
59  // Householder reduction to tridiagonal form.
60 
61  for(int i = n - 1; i > 0; i--) {
62 
63  // Scale to avoid under/overflow.
64 
65  double scale = 0.0;
66  double h = 0.0;
67  for(int k = 0; k < i; k++) {
68  scale = scale + fabs(d[k]);
69  }
70  if(scale == 0.0) {
71  e[i] = d[i - 1];
72  for(int j = 0; j < i; j++) {
73  d[j] = V[i - 1][j];
74  V[i][j] = 0.0;
75  V[j][i] = 0.0;
76  }
77  } else {
78 
79  // Generate Householder vector.
80 
81  for(int k = 0; k < i; k++) {
82  d[k] /= scale;
83  h += d[k] * d[k];
84  }
85  double f = d[i - 1];
86  double g = sqrt(h);
87  if(f > 0) {
88  g = -g;
89  }
90  e[i] = scale * g;
91  h = h - f * g;
92  d[i - 1] = f - g;
93  for(int j = 0; j < i; j++) {
94  e[j] = 0.0;
95  }
96 
97  // Apply similarity transformation to remaining columns.
98 
99  for(int j = 0; j < i; j++) {
100  f = d[j];
101  V[j][i] = f;
102  g = e[j] + V[j][j] * f;
103  for(int k = j + 1; k <= i - 1; k++) {
104  g += V[k][j] * d[k];
105  e[k] += V[k][j] * f;
106  }
107  e[j] = g;
108  }
109  f = 0.0;
110  for(int j = 0; j < i; j++) {
111  e[j] /= h;
112  f += e[j] * d[j];
113  }
114  double hh = f / (h + h);
115  for(int j = 0; j < i; j++) {
116  e[j] -= hh * d[j];
117  }
118  for(int j = 0; j < i; j++) {
119  f = d[j];
120  g = e[j];
121  for(int k = j; k <= i - 1; k++) {
122  V[k][j] -= (f * e[k] + g * d[k]);
123  }
124  d[j] = V[i - 1][j];
125  V[i][j] = 0.0;
126  }
127  }
128  d[i] = h;
129  }
130 
131  // Accumulate transformations.
132 
133  for(int i = 0; i < n - 1; i++) {
134  V[n - 1][i] = V[i][i];
135  V[i][i] = 1.0;
136  double h = d[i + 1];
137  if(h != 0.0) {
138  for(int k = 0; k <= i; k++) {
139  d[k] = V[k][i + 1] / h;
140  }
141  for(int j = 0; j <= i; j++) {
142  double g = 0.0;
143  for(int k = 0; k <= i; k++) {
144  g += V[k][i + 1] * V[k][j];
145  }
146  for(int k = 0; k <= i; k++) {
147  V[k][j] -= g * d[k];
148  }
149  }
150  }
151  for(int k = 0; k <= i; k++) {
152  V[k][i + 1] = 0.0;
153  }
154  }
155  for(int j = 0; j < n; j++) {
156  d[j] = V[n - 1][j];
157  V[n - 1][j] = 0.0;
158  }
159  V[n - 1][n - 1] = 1.0;
160  e[0] = 0.0;
161 }
162 
163 // Symmetric tridiagonal QL algorithm.
164 CU_HOST_DEVICE
165 static void tql2(double V[n][n], double d[n], double e[n])
166 {
167 
168  // This is derived from the Algol procedures tql2, by
169  // Bowdler, Martin, Reinsch, and Wilkinson, Handbook for
170  // Auto. Comp., Vol.ii-Linear Algebra, and the corresponding
171  // Fortran subroutine in EISPACK.
172 
173  for(int i = 1; i < n; i++) {
174  e[i - 1] = e[i];
175  }
176  e[n - 1] = 0.0;
177 
178  double f = 0.0;
179  double tst1 = 0.0;
180  double eps = pow(2.0, -52.0);
181  for(int l = 0; l < n; l++) {
182 
183  // Find small subdiagonal element
184 
185  tst1 = MAX(tst1, fabs(d[l]) + fabs(e[l]));
186  int m = l;
187  while(m < n) {
188  if(fabs(e[m]) <= eps * tst1) {
189  break;
190  }
191  m++;
192  }
193 
194  // If m == l, d[l] is an eigenvalue,
195  // otherwise, iterate.
196 
197  if(m > l) {
198  int iter = 0;
199  do {
200  iter = iter + 1; // (Could check iteration count here.)
201 
202  // Compute implicit shift
203 
204  double g = d[l];
205  double p = (d[l + 1] - g) / (2.0 * e[l]);
206  double r = hypot2(p, 1.0);
207  if(p < 0) {
208  r = -r;
209  }
210  d[l] = e[l] / (p + r);
211  d[l + 1] = e[l] * (p + r);
212  double dl1 = d[l + 1];
213  double h = g - d[l];
214  for(int i = l + 2; i < n; i++) {
215  d[i] -= h;
216  }
217  f = f + h;
218 
219  // Implicit QL transformation.
220 
221  p = d[m];
222  double c = 1.0;
223  double c2 = c;
224  double c3 = c;
225  double el1 = e[l + 1];
226  double s = 0.0;
227  double s2 = 0.0;
228  for(int i = m - 1; i >= l; i--) {
229  c3 = c2;
230  c2 = c;
231  s2 = s;
232  g = c * e[i];
233  h = c * p;
234  r = hypot2(p, e[i]);
235  e[i + 1] = s * r;
236  s = e[i] / r;
237  c = p / r;
238  p = c * d[i] - s * g;
239  d[i + 1] = h + s * (c * g + s * d[i]);
240 
241  // Accumulate transformation.
242 
243  for(int k = 0; k < n; k++) {
244  h = V[k][i + 1];
245  V[k][i + 1] = s * V[k][i] + c * h;
246  V[k][i] = c * V[k][i] - s * h;
247  }
248  }
249  p = -s * s2 * c3 * el1 * e[l] / dl1;
250  e[l] = s * p;
251  d[l] = c * p;
252 
253  // Check for convergence.
254 
255  } while(fabs(e[l]) > eps * tst1);
256  }
257  d[l] = d[l] + f;
258  e[l] = 0.0;
259  }
260 
261  // Sort eigenvalues and corresponding vectors.
262 
263  for(int i = 0; i < n - 1; i++) {
264  int k = i;
265  double p = d[i];
266  for(int j = i + 1; j < n; j++) {
267  if(d[j] < p) {
268  k = j;
269  p = d[j];
270  }
271  }
272  if(k != i) {
273  d[k] = d[i];
274  d[i] = p;
275  for(int j = 0; j < n; j++) {
276  p = V[j][i];
277  V[j][i] = V[j][k];
278  V[j][k] = p;
279  }
280  }
281  }
282 }
283 }
284 
285 CU_HOST_DEVICE
286 void EigenDecompSym3x3(double A[n][n], double V[n][n], double d[n])
287 {
288  double e[n];
289  for(int i = 0; i < n; i++) {
290  for(int j = 0; j < n; j++) {
291  V[i][j] = A[i][j];
292  }
293  }
294  tred2(V, d, e);
295  tql2(V, d, e);
296 }
297 
298 #endif
CU_HOST_DEVICE Vector< dim, T > fabs(const Vector< dim, T > &v)
Return the vector whose component is the absolute value of the input vector.
Definition: Vector.hpp:1185