Debian Codegraph @

packages/kokkos-kernels/batched/dense/impl/KokkosBatched_Eigenvalue_Serial_Internal.hpp

raw
1 //@HEADER
2 // ************************************************************************
3 //
4 // Kokkos v. 4.0
5 // Copyright (2022) National Technology & Engineering
6 // Solutions of Sandia, LLC (NTESS).
7 //
8 // Under the terms of Contract DE-NA0003525 with NTESS,
9 // the U.S. Government retains certain rights in this software.
10 //
11 // Part of Kokkos, under the Apache License v2.0 with LLVM Exceptions.
12 // See https://kokkos.org/LICENSE for license information.
13 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
14 //
15 //@HEADER
16 #ifndef KOKKOSBATCHED_EIGENVALUE_SERIAL_INTERNAL_HPP
17 #define KOKKOSBATCHED_EIGENVALUE_SERIAL_INTERNAL_HPP
18
19 /// \author Kyungjoo Kim ([email protected])
20
21 #include "KokkosBatched_Util.hpp"
22 #include "KokkosBatched_WilkinsonShift_Serial_Internal.hpp"
23 #include "KokkosBatched_Schur2x2_Serial_Internal.hpp"
24 #include "KokkosBatched_HessenbergQR_WithShift_Serial_Internal.hpp"
25 #include "KokkosBatched_Francis_Serial_Internal.hpp"
26
27 namespace KokkosBatched {
28
29 ///
30 /// Serial Internal Impl
31 /// ====================
32 ///
33 /// this impl follows the flame interface of householder transformation
34 ///
35 struct SerialEigenvalueInternal {
36 /// Given a strictly Hessenberg matrix H (m x m), this computes all
37 /// eigenvalues using the Francis method and stores them into a vector e. This
38 /// routine does not scale nor balance the matrix for the numerical stability.
39 ///
40 /// Parameters:
41 /// [in]m
42 /// A dimension of the square matrix H.
43 /// [in/out]H, [in]hs0, [in]hs1
44 /// Real Hessenberg matrix H(m x m) with strides hs0 and hs1.
45 /// Entering the routine, H is assumed to have a upper Hessenberg form,
46 /// where all subdiagonals are zero. The matrix is overwritten on exit.
47 /// [out]er, [in]ers, [out]ei, [in]eis
48 /// A complex vector er(m)+ei(m)i with a stride ers and eis to store
49 /// computed eigenvalues. For a complex eigen pair, it stores a+bi and
50 /// a-bi consecutively.
51 /// [in]restart(false)
52 /// With a restart option, the routine assume that the matrix H and the
53 /// vector e contain the partial results from the previous run. When m = 1
54 /// or 2, this option won't work as the routine always computes the all
55 /// eigenvalues.
56 /// [in]max_iteration(300)
57 /// Unlike LAPACK which uses various methods for different types of
58 /// matrices, this routine uses the Francis method only. A user can set
59 /// the maximum number of iterations. When it reaches the maximum
60 /// iteration counts without converging all eigenvalues, the routine
61 /// returns -1.
62 template <typename RealType>
63 KOKKOS_INLINE_FUNCTION static int invoke(const int m,
64 /* */ RealType *H, const int hs0, const int hs1,
65 /* */ RealType *er, const int ers,
66 /* */ RealType *ei, const int eis, const bool restart = false,
67 const int user_max_iteration = -1) {
68 typedef RealType real_type;
69 typedef Kokkos::ArithTraits<real_type> ats;
70 const real_type zero(0), nan(ats::nan()), tol = 1e2 * ats::epsilon();
71 const int max_iteration = user_max_iteration < 0 ? 300 : user_max_iteration;
72
73 int r_val = 0;
74 if (restart) {
75 if (m <= 2) {
76 Kokkos::abort("Error: restart option cannot be used for m=1 or m=2");
77 }
78 } else {
79 for (int i = 0; i < m; ++i) er[i * ers] = nan;
80 }
81
82 const int hs = hs0 + hs1; /// diagonal stride
83 switch (m) {
84 case 0: { /* do nothing */ break;
85 }
86 case 1: {
87 er[0] = H[0];
88 ei[0] = zero;
89 break;
90 }
91 case 2: {
92 /// compute eigenvalues from the characteristic determinant equation
93 bool is_complex;
94 Kokkos::complex<real_type> lambda1, lambda2;
95 SerialWilkinsonShiftInternal::invoke(H[0], H[hs1], H[hs0], H[hs], &lambda1, &lambda2, &is_complex);
96 er[0] = lambda1.real();
97 ei[0] = lambda1.imag();
98 er[1] = lambda2.real();
99 ei[1] = lambda2.imag();
100 break;
101 }
102 default: {
103 /// Francis method
104 int iter(0); /// iteration count
105 bool converge = false; /// bool to check all eigenvalues are converged
106
107 while (!converge && iter < max_iteration) {
108 /// Step 1: find a set of unrevealed eigenvalues
109 int cnt = 1;
110
111 /// find mbeg (first nonzero subdiag value)
112 for (; cnt < m; ++cnt) {
113 const auto val = ats::abs(*(H + cnt * hs - hs1));
114 if (val > tol) break;
115 }
116 const int mbeg = cnt - 1;
117
118 /// find mend (first zero subdiag value)
119 for (; cnt < m; ++cnt) {
120 const auto val = ats::abs(*(H + cnt * hs - hs1));
121 if (val < tol) break;
122 }
123 const int mend = cnt;
124 const int mdiff = mend - mbeg;
125
126 /// Step 2: if there exist non-converged eigen values
127 if (1 < mdiff) {
128 #if 0 /// implicit QR with shift for testing
129 {
130 /// Rayleigh quotient shift
131 const real_type shift = *(H+(mend-1)*hs);
132 SerialHessenbergQR_WithShiftInternal::invoke(0, mdiff, mdiff,
133 H+hs*mbeg, hs0, hs1,
134 shift);
135 real_type *sub2x2 = H+(mend-2)*hs;
136 const auto val = ats::abs(sub2x2[hs0]);
137 if (val < tol) { /// this eigenvalue converges
138 er[(mend-1)*ers] = sub2x2[hs]; ei[(mend-1)*eis] = zero;
139 }
140 }
141 #endif
142
143 #if 1 /// Francis double shift method
144 {
145 /// find a complex eigen pair
146 Kokkos::complex<real_type> lambda1, lambda2;
147 bool is_complex;
148 real_type *sub2x2 = H + (mend - 2) * hs;
149 if (2 == mdiff) {
150 SerialWilkinsonShiftInternal::invoke(sub2x2[0], sub2x2[hs1], sub2x2[hs0], sub2x2[hs], &lambda1,
151 &lambda2, &is_complex);
152 sub2x2[hs0] = zero;
153
154 /// eigenvalues are from wilkinson shift
155 er[(mbeg + 0) * ers] = lambda1.real();
156 ei[(mbeg + 0) * eis] = lambda1.imag();
157 er[(mbeg + 1) * ers] = lambda2.real();
158 ei[(mbeg + 1) * eis] = lambda2.imag();
159 } else {
160 SerialWilkinsonShiftInternal::invoke(sub2x2[0], sub2x2[hs1], sub2x2[hs0], sub2x2[hs], &lambda1,
161 &lambda2, &is_complex);
162
163 SerialFrancisInternal::invoke(0, mdiff, mdiff, H + hs * mbeg, hs0, hs1, lambda1, lambda2, is_complex);
164 /* */ auto &val1 = *(sub2x2 + hs0);
165 /* */ auto &val2 = *(sub2x2 - hs1);
166 const auto abs_val1 = ats::abs(val1);
167 const auto abs_val2 = ats::abs(val2);
168
169 /// convergence check
170 if (abs_val1 < tol) {
171 er[(mend - 1) * ers] = sub2x2[hs];
172 ei[(mend - 1) * eis] = zero;
173 val1 = zero;
174 } else if (abs_val2 < tol) {
175 er[(mend - 2) * ers] = lambda1.real();
176 ei[(mend - 2) * eis] = lambda1.imag();
177 er[(mend - 1) * ers] = lambda2.real();
178 ei[(mend - 1) * eis] = lambda2.imag();
179
180 val1 = zero;
181 val2 = zero;
182 }
183 }
184 }
185 #endif
186
187 } else {
188 /// all eigenvalues are converged
189 converge = true;
190 }
191 ++iter;
192 }
193 /// Step 3: record missing real eigenvalues from the diagonals
194 if (converge) {
195 // record undetected eigenvalues
196 for (int i = 0; i < m; ++i)
197 if (ats::isNan(er[i * ers])) {
198 er[i * ers] = H[i * hs];
199 ei[i * eis] = zero;
200 }
201 r_val = 0;
202 } else {
203 r_val = -1;
204 }
205 break;
206 }
207 }
208 return r_val;
209 }
210
211 /// complex interface
212 template <typename RealType>
213 KOKKOS_INLINE_FUNCTION static int invoke(const int m,
214 /* */ RealType *H, const int hs0, const int hs1,
215 /* */ Kokkos::complex<RealType> *e, const int es,
216 const int max_iteration = 300, const RealType user_tolerence = RealType(-1),
217 const bool restart = false) {
218 RealType *er = (RealType *)e;
219 RealType *ei = er + 1;
220 const int two_es = 2 * es;
221 return invoke(m, H, hs0, hs1, er, two_es, ei, two_es, user_tolerence, restart, max_iteration);
222 }
223 };
224
225 } // namespace KokkosBatched
226
227 #endif