View Javadoc
1   /*
2    * Licensed to the Hipparchus project under one or more
3    * contributor license agreements.  See the NOTICE file distributed with
4    * this work for additional information regarding copyright ownership.
5    * The Hipparchus project licenses this file to You under the Apache License, Version 2.0
6    * (the "License"); you may not use this file except in compliance with
7    * the License.  You may obtain a copy of the License at
8    *
9    *      https://www.apache.org/licenses/LICENSE-2.0
10   *
11   * Unless required by applicable law or agreed to in writing, software
12   * distributed under the License is distributed on an "AS IS" BASIS,
13   * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
14   * See the License for the specific language governing permissions and
15   * limitations under the License.
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   * Class transforming a general complex matrix to Schur form.
28   * <p>A m &times; m complex matrix A can be written as the product of three matrices: A = P
29   * &times; T &times; P<sup>H</sup> with P a unitary matrix and T an upper triangular
30   * matrix. Both P and T are m &times; m matrices.</p>
31   * <p>Transformation to Schur form is often not a goal by itself, but it is an
32   * intermediate step in more general decomposition algorithms like
33   * {@link ComplexEigenDecomposition eigen decomposition}. This class is therefore
34   * intended for expert use. As a consequence of this explicitly limited scope,
35   * many methods directly returns references to internal arrays, not copies.</p>
36   *
37   * @see <a href="http://mathworld.wolfram.com/SchurDecomposition.html">Schur Decomposition - MathWorld</a>
38   */
39  public class ComplexSchurTransformer {
40      /** Maximum allowed iterations for convergence of the transformation. */
41      private static final int MAX_ITERATIONS = 100;
42  
43      /** P matrix. */
44      private final Complex[][] matrixP;
45      /** T matrix. */
46      private final Complex[][] matrixT;
47      /** Cached value of P. */
48      private FieldMatrix<Complex> cachedP;
49      /** Cached value of T. */
50      private FieldMatrix<Complex> cachedT;
51      /** Cached value of Pt. */
52      private FieldMatrix<Complex> cachedPt;
53  
54      /** Epsilon criteria. */
55      private final double epsilon;
56  
57      /**
58       * Build the transformation to Schur form of a general complex matrix.
59       *
60       * @param matrix matrix to transform
61       * @throws MathIllegalArgumentException if the matrix is not square
62       */
63      public ComplexSchurTransformer(final FieldMatrix<Complex> matrix) {
64          this(matrix, Precision.EPSILON);
65      }
66  
67      /**
68       * Build the transformation to Schur form of a general complex matrix.
69       *
70       * @param matrix matrix to transform
71       * @param epsilon convergence criteria
72       * @throws MathIllegalArgumentException if the matrix is not square
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          // Initialize T with the input matrix and P with Identity
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          // 1. Reduce to Hessenberg form
94          transformToHessenberg();
95  
96          // 2. Reduce Hessenberg to Schur form (Triangular)
97          transformToSchur();
98      }
99  
100     /**
101      * Returns the unitary matrix P of the transform.
102      * <p>P is a unitary matrix, i.e. its inverse is also its conjugate transpose.</p>
103      *
104      * @return the P matrix
105      */
106     public FieldMatrix<Complex> getP() {
107         if (cachedP == null) {
108             cachedP = MatrixUtils.createFieldMatrix(matrixP);
109         }
110         return cachedP;
111     }
112 
113     /**
114      * Returns the conjugate transpose of the matrix P of the transform.
115      * <p>P is a unitary matrix, i.e. its inverse is also its conjugate transpose.</p>
116      *
117      * @return the conjugate transpose of the P matrix
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      * Returns the triangular Schur matrix T of the transform.
128      *
129      * @return the T matrix
130      */
131     public FieldMatrix<Complex> getT() {
132         if (cachedT == null) {
133             cachedT = MatrixUtils.createFieldMatrix(matrixT);
134         }
135         return cachedT;
136     }
137 
138     /**
139      * Transform the matrix to Hessenberg form using Householder reflections.
140      */
141     private void transformToHessenberg() {
142         final int n = matrixT.length;
143 
144         for (int k = 0; k < n - 2; k++) {
145             // Find Householder vector to eliminate T[k+2..n][k]
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             // Compute alpha = - (pivot / |pivot|) * normX
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             // u = x - alpha * e1
167             // Copy u to a separate array to avoid corrupting it during the Left Multiply
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             // Apply P = I - beta * u * u^H
182 
183             // 1. Left Multiply: T = P * T
184             // Affects rows k+1 .. n
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             // 2. Right Multiply: T = T * P^H
198             // Affects columns k+1 .. n
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             // 3. Update P: P = P * P^H
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             // Restore Hessenberg form manually in column k
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      * Transform Hessenberg matrix to Schur form using Single-Shift QR Algorithm.
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                 // Convergence: Add accumulated shift back to eigenvalue
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       // If iterations are high, use ad-hoc (exceptional) shifts to break cycles.
293       // We check iterations 10, 20, and 30 to inject shifts if convergence is stalling.
294       if (iteration == 10 || iteration == 20 || iteration == 30) {
295         // Accumulate the previous shift into the total shift
296         shift.exShift = shift.exShift.add(shift.x);
297 
298         // Calculate the magnitude of the sub-diagonal elements to determine the scale
299         // Safe check for bounds is included.
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         // Vary the shift strategy to ensure we don't get stuck in a specific cycle.
305         // - Iteration 10 & 20: Use the classic empirical shift factor 0.75
306         // - Iteration 30: Use 0.964, a heuristic value (from JAMA/EISPACK) known to break
307         //   cycles that are stable under 0.75.
308         double alpha = (iteration == 30) ? 0.964 : 0.75;
309 
310         shift.x = new Complex(alpha * s);
311 
312         // Subtract this new exceptional shift from the diagonal to stabilize the matrix
313         for (int i = 0; i <= idx; i++) {
314           matrixT[i][i] = matrixT[i][i].subtract(shift.x);
315         }
316         return;
317       }
318 
319       // Standard Wilkinson Shift
320       // Computes the eigenvalues of the bottom 2x2 block and selects the one closest to T[idx][idx]
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       // Roots of characteristic equation: x^2 - tr*x + det = 0
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       // Choose the root closer to d (the bottom-right element) to maximize convergence
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             // Apply G to T (from left) -> Row ops
371             // IMPORTANT: If k > il, we must update the column k-1 (the bulge) as well.
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             // Apply G^H to T (from right) -> Col ops
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             // Accumulate P
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         /** Current shift. */
405         private Complex x = Complex.ZERO;
406 
407         /** Accumulated shift. */
408         private Complex exShift = Complex.ZERO;
409 
410     }
411 
412     public static Complex[] getEigenvalues(FieldMatrix<Complex> matrix) {
413       // 1. Perform the Schur Decomposition
414       ComplexSchurTransformer transformer = new ComplexSchurTransformer(matrix);
415 
416       // 2. Get the upper triangular matrix T
417       FieldMatrix<Complex> T = transformer.getT();
418 
419       // 3. Extract the diagonal entries
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 }