1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17 package org.hipparchus.linear;
18
19 import org.hipparchus.complex.Complex;
20 import org.hipparchus.exception.LocalizedCoreFormats;
21 import org.hipparchus.exception.MathIllegalArgumentException;
22 import org.hipparchus.exception.MathIllegalStateException;
23 import org.hipparchus.util.FastMath;
24 import org.hipparchus.util.Precision;
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39 public class ComplexSchurTransformer {
40
41 private static final int MAX_ITERATIONS = 100;
42
43
44 private final Complex[][] matrixP;
45
46 private final Complex[][] matrixT;
47
48 private FieldMatrix<Complex> cachedP;
49
50 private FieldMatrix<Complex> cachedT;
51
52 private FieldMatrix<Complex> cachedPt;
53
54
55 private final double epsilon;
56
57
58
59
60
61
62
63 public ComplexSchurTransformer(final FieldMatrix<Complex> matrix) {
64 this(matrix, Precision.EPSILON);
65 }
66
67
68
69
70
71
72
73
74 public ComplexSchurTransformer(final FieldMatrix<Complex> matrix, final double epsilon) {
75 if (!matrix.isSquare()) {
76 throw new MathIllegalArgumentException(LocalizedCoreFormats.NON_SQUARE_MATRIX,
77 matrix.getRowDimension(), matrix.getColumnDimension());
78 }
79
80 this.epsilon = epsilon;
81 final int n = matrix.getRowDimension();
82 matrixP = new Complex[n][n];
83 matrixT = new Complex[n][n];
84
85
86 for (int i = 0; i < n; i++) {
87 for (int j = 0; j < n; j++) {
88 matrixT[i][j] = matrix.getEntry(i, j);
89 matrixP[i][j] = (i == j) ? Complex.ONE : Complex.ZERO;
90 }
91 }
92
93
94 transformToHessenberg();
95
96
97 transformToSchur();
98 }
99
100
101
102
103
104
105
106 public FieldMatrix<Complex> getP() {
107 if (cachedP == null) {
108 cachedP = MatrixUtils.createFieldMatrix(matrixP);
109 }
110 return cachedP;
111 }
112
113
114
115
116
117
118
119 public FieldMatrix<Complex> getPT() {
120 if (cachedPt == null) {
121 cachedPt = getP().transpose().map(Complex::conjugate);
122 }
123 return cachedPt;
124 }
125
126
127
128
129
130
131 public FieldMatrix<Complex> getT() {
132 if (cachedT == null) {
133 cachedT = MatrixUtils.createFieldMatrix(matrixT);
134 }
135 return cachedT;
136 }
137
138
139
140
141 private void transformToHessenberg() {
142 final int n = matrixT.length;
143
144 for (int k = 0; k < n - 2; k++) {
145
146 double normSq = 0;
147 for (int i = k + 1; i < n; i++) {
148 normSq += matrixT[i][k].norm() * matrixT[i][k].norm();
149 }
150
151 if (normSq == 0) {
152 continue;
153 }
154
155 double normX = FastMath.sqrt(normSq);
156 Complex pivot = matrixT[k + 1][k];
157
158
159 Complex alpha;
160 if (pivot.norm() != 0) {
161 alpha = pivot.divide(pivot.norm()).multiply(normX).negate();
162 } else {
163 alpha = new Complex(-normX);
164 }
165
166
167
168 int uLen = n - (k + 1);
169 Complex[] u = new Complex[uLen];
170 u[0] = pivot.subtract(alpha);
171 for (int i = 1; i < uLen; i++) {
172 u[i] = matrixT[k + 1 + i][k];
173 }
174
175 double uNormSq = normSq - pivot.norm() * pivot.norm() + u[0].norm() * u[0].norm();
176 if (uNormSq == 0) {
177 continue;
178 }
179 double beta = 2.0 / uNormSq;
180
181
182
183
184
185 for (int j = k + 1; j < n; j++) {
186 Complex dot = Complex.ZERO;
187 for (int i = 0; i < uLen; i++) {
188 dot = dot.add(u[i].conjugate().multiply(matrixT[k + 1 + i][j]));
189 }
190 dot = dot.multiply(beta);
191
192 for (int i = 0; i < uLen; i++) {
193 matrixT[k + 1 + i][j] = matrixT[k + 1 + i][j].subtract(dot.multiply(u[i]));
194 }
195 }
196
197
198
199 for (int i = 0; i < n; i++) {
200 Complex dot = Complex.ZERO;
201 for (int j = 0; j < uLen; j++) {
202 dot = dot.add(matrixT[i][k + 1 + j].multiply(u[j]));
203 }
204 dot = dot.multiply(beta);
205
206 for (int j = 0; j < uLen; j++) {
207 matrixT[i][k + 1 + j] = matrixT[i][k + 1 + j].subtract(dot.multiply(u[j].conjugate()));
208 }
209 }
210
211
212 for (int i = 0; i < n; i++) {
213 Complex dot = Complex.ZERO;
214 for (int j = 0; j < uLen; j++) {
215 dot = dot.add(matrixP[i][k + 1 + j].multiply(u[j]));
216 }
217 dot = dot.multiply(beta);
218
219 for (int j = 0; j < uLen; j++) {
220 matrixP[i][k + 1 + j] = matrixP[i][k + 1 + j].subtract(dot.multiply(u[j].conjugate()));
221 }
222 }
223
224
225 matrixT[k + 1][k] = alpha;
226 for (int i = k + 2; i < n; i++) {
227 matrixT[i][k] = Complex.ZERO;
228 }
229 }
230 }
231
232
233
234
235 private void transformToSchur() {
236 final int n = matrixT.length;
237 final double norm = getNorm();
238 final ComplexShiftInfo shift = new ComplexShiftInfo();
239
240 int iteration = 0;
241 int iu = n - 1;
242 while (iu > 0) {
243 final int il = findSmallSubDiagonalElement(iu, norm);
244
245 if (il == iu) {
246
247 matrixT[iu][iu] = matrixT[iu][iu].add(shift.exShift);
248 iu--;
249 iteration = 0;
250 } else {
251 computeShift(iu, iteration, shift);
252 if (++iteration > MAX_ITERATIONS) {
253 throw new MathIllegalStateException(LocalizedCoreFormats.CONVERGENCE_FAILED,
254 MAX_ITERATIONS);
255 }
256
257 performQRStep(il, iu, shift);
258 }
259 }
260 if (n > 0) {
261 matrixT[0][0] = matrixT[0][0].add(shift.exShift);
262 }
263 }
264
265 private double getNorm() {
266 double norm = 0.0;
267 for (final Complex[] complexes : matrixT) {
268 for (int j = 0; j < matrixT.length; j++) {
269 norm += complexes[j].norm();
270 }
271 }
272 return norm;
273 }
274
275 private int findSmallSubDiagonalElement(final int startIdx, final double norm) {
276 int l = startIdx;
277 while (l > 0) {
278 double s = matrixT[l - 1][l - 1].norm() + matrixT[l][l].norm();
279 if (s == 0.0) {
280 s = norm;
281 }
282 if (matrixT[l][l - 1].norm() < epsilon * s) {
283 break;
284 }
285 l--;
286 }
287 return l;
288 }
289
290 private void computeShift(final int idx, final int iteration,
291 final ComplexShiftInfo shift) {
292
293
294 if (iteration == 10 || iteration == 20 || iteration == 30) {
295
296 shift.exShift = shift.exShift.add(shift.x);
297
298
299
300 double norm1 = matrixT[idx][idx - 1].norm();
301 double norm2 = (idx > 1) ? matrixT[idx - 1][idx - 2].norm() : 0.0;
302 double s = norm1 + norm2;
303
304
305
306
307
308 double alpha = (iteration == 30) ? 0.964 : 0.75;
309
310 shift.x = new Complex(alpha * s);
311
312
313 for (int i = 0; i <= idx; i++) {
314 matrixT[i][i] = matrixT[i][i].subtract(shift.x);
315 }
316 return;
317 }
318
319
320
321 Complex a = matrixT[idx - 1][idx - 1];
322 Complex b = matrixT[idx - 1][idx];
323 Complex c = matrixT[idx][idx - 1];
324 Complex d = matrixT[idx][idx];
325
326 Complex tr = a.add(d);
327 Complex det = a.multiply(d).subtract(b.multiply(c));
328
329
330 Complex discriminant = tr.multiply(tr).subtract(det.multiply(4));
331 Complex sqrtDisc = discriminant.sqrt();
332
333 Complex root1 = tr.add(sqrtDisc).multiply(0.5);
334 Complex root2 = tr.subtract(sqrtDisc).multiply(0.5);
335
336
337 if (root1.subtract(d).norm() < root2.subtract(d).norm()) {
338 shift.x = root1;
339 } else {
340 shift.x = root2;
341 }
342 }
343
344 private void performQRStep(final int il, final int iu, final ComplexShiftInfo shift) {
345 Complex x = matrixT[il][il].subtract(shift.x);
346 Complex y = matrixT[il + 1][il];
347
348 for (int k = il; k < iu; k++) {
349 if (k > il) {
350 x = matrixT[k][k - 1];
351 y = matrixT[k + 1][k - 1];
352 }
353
354 double absX = x.norm();
355 double absY = y.norm();
356
357 if (absY == 0) {
358 continue;
359 }
360
361 double norm = FastMath.hypot(absX, absY);
362 if (norm == 0) {
363 continue;
364 }
365
366 double c = absX / norm;
367 Complex alpha = (absX == 0) ? Complex.ONE : x.divide(absX);
368 Complex s = alpha.multiply(y.conjugate()).divide(norm);
369
370
371
372 int startCol = (k == il) ? k : k - 1;
373 for (int j = startCol; j < matrixT.length; j++) {
374 Complex t1 = matrixT[k][j];
375 Complex t2 = matrixT[k + 1][j];
376 matrixT[k][j] = t1.multiply(c).add(s.multiply(t2));
377 matrixT[k + 1][j] = t1.multiply(s.conjugate()).negate().add(t2.multiply(c));
378 }
379
380
381 for (int i = 0; i <= FastMath.min(iu, k + 2); i++) {
382 Complex t1 = matrixT[i][k];
383 Complex t2 = matrixT[i][k + 1];
384 matrixT[i][k] = t1.multiply(c).add(t2.multiply(s.conjugate()));
385 matrixT[i][k + 1] = t1.multiply(s).negate().add(t2.multiply(c));
386 }
387
388
389 for (int i = 0; i < matrixP.length; i++) {
390 Complex p1 = matrixP[i][k];
391 Complex p2 = matrixP[i][k + 1];
392 matrixP[i][k] = p1.multiply(c).add(p2.multiply(s.conjugate()));
393 matrixP[i][k + 1] = p1.multiply(s).negate().add(p2.multiply(c));
394 }
395
396 if (k > il) {
397 matrixT[k + 1][k - 1] = Complex.ZERO;
398 }
399 }
400 }
401
402 private static class ComplexShiftInfo {
403
404
405 private Complex x = Complex.ZERO;
406
407
408 private Complex exShift = Complex.ZERO;
409
410 }
411
412 public static Complex[] getEigenvalues(FieldMatrix<Complex> matrix) {
413
414 ComplexSchurTransformer transformer = new ComplexSchurTransformer(matrix);
415
416
417 FieldMatrix<Complex> T = transformer.getT();
418
419
420 int n = T.getRowDimension();
421 Complex[] eigenvalues = new Complex[n];
422
423 for (int i = 0; i < n; i++) {
424 eigenvalues[i] = T.getEntry(i, i);
425 }
426
427 return eigenvalues;
428 }
429 }