Debian Codegraph @

packages/kokkos-kernels/batched/dense/impl/KokkosBatched_Schur_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_SCHUR_SERIAL_INTERNAL_HPP
17 #define KOKKOSBATCHED_SCHUR_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_ApplyGivens_Serial_Internal.hpp"
24 #include "KokkosBatched_Schur2x2_Serial_Internal.hpp"
25 #include "KokkosBatched_HessenbergQR_WithShift_Serial_Internal.hpp"
26 #include "KokkosBatched_Francis_Serial_Internal.hpp"
27
28 namespace KokkosBatched {
29
30 ///
31 /// Serial Internal Impl
32 /// ====================
33 ///
34 /// this impl follows the flame interface of householder transformation
35 ///
36 struct SerialSchurInternal {
37 /// Given a strictly Hessenberg matrix H (m x m), this computes schur
38 /// decomposition using the Francis method and stores them into a vector e.
39 /// This routine does not scale nor balance the matrix for the numerical
40 /// stability.
41 /// H = Z T Z^H and T = Z^H H Z
42 /// Parameters:
43 /// [in]m
44 /// A dimension of the square matrix H.
45 /// [in/out]H, [in]hs0, [in]hs1
46 /// Real Hessenberg matrix H(m x m) with strides hs0 and hs1.
47 /// Entering the routine, H is assumed to have a upper Hessenberg form,
48 /// where all subdiagonals are zero. The matrix is overwritten as a upper
49 /// triangular T on exit.
50 /// [in/out]Z, [in]zs0, [in]zs1
51 /// Unitary matrix resulting from Schur decomposition. With a restarting
52 /// option, the matrix may contain previous partial computation results.
53 /// [in/out]w, [in]wlen
54 /// Contiguous workspace of which size is wlen. When restart is true, this
55 /// workspace is not corrupted after the previous iteration. Temporarily,
56 /// it stores subdiag values and given rotations. wlen should be at least
57 /// 3*m.
58 /// [in]restart(false)
59 /// With a restart option, the routine assume that the matrix H and the
60 /// vector e contain the partial results from the previous run. When m = 1
61 /// or 2, this option won't work as the routine always computes the all
62 /// eigenvalues.
63 /// [in]user_max_iteration(300)
64 /// Unlike LAPACK which uses various methods for different types of
65 /// matrices, this routine uses the Francis method only. A user can set
66 /// the maximum number of iterations. When it reaches the maximum
67 /// iteration counts without converging all eigenvalues, the routine
68 /// returns -1.
69 template <typename RealType>
70 KOKKOS_INLINE_FUNCTION static int invoke(const int m,
71 /* */ RealType *H, const int hs0, const int hs1,
72 /* */ RealType *Z, const int zs0, const int zs1,
73 /* */ RealType *w, const int wlen, const bool restart = false,
74 const int user_max_iteration = -1) {
75 typedef RealType real_type;
76 typedef Kokkos::ArithTraits<real_type> ats;
77 const real_type /* one(1), */ zero(0), tol = 1e2 * ats::epsilon();
78 const int max_iteration = user_max_iteration < 0 ? 300 : user_max_iteration;
79 if (wlen < m * 5) Kokkos::abort("Error: provided workspace is smaller than 3*m");
80
81 int r_val = 0;
82 if (restart) {
83 if (m <= 2) Kokkos::abort("Error: restart option cannot be used for m=1 or m=2");
84 } else {
85 /// do not touch input
86 /// SerialSetIdentityInternal::invoke(m, Z, zs0, zs1);
87 }
88
89 // workspaces
90 real_type *subdiags = w;
91 Kokkos::pair<real_type, real_type> *Gs = (Kokkos::pair<real_type, real_type> *)(w + m);
92 if (!restart) {
93 /// initialize workspace and Gs
94 for (int i = 0; i < m; ++i) subdiags[i] = zero;
95 }
96
97 const int hs = hs0 + hs1; /// diagonal stride
98 switch (m) {
99 case 0: { /* do nothing */ break;
100 }
101 case 1: { /* do nothing */ break;
102 }
103 case 2: {
104 /// compute eigenvalues from the characteristic determinant equation
105 bool is_complex;
106 Kokkos::complex<real_type> lambda1, lambda2;
107 Kokkos::pair<real_type, real_type> G;
108 SerialSchur2x2Internal::invoke(H, H + hs1, H + hs0, H + hs, &G, &lambda1, &lambda2, &is_complex);
109
110 G.second = -G.second; // transpose
111 SerialApplyRightGivensInternal::invoke(G, 2, Z, zs0, Z + zs1, zs0);
112 break;
113 }
114 default: {
115 /// Francis method
116 int iter(0); /// iteration count
117 bool converge = false; /// bool to check all eigenvalues are converged
118
119 while (!converge && iter < max_iteration) {
120 /// Step 1: find a set of unrevealed eigenvalues
121 int cnt = 1;
122
123 /// find mbeg (first nonzero subdiag value)
124 for (; cnt < m; ++cnt) {
125 const auto val = ats::abs(*(H + cnt * hs - hs1));
126 if (val > tol) break;
127 }
128 const int mbeg = cnt - 1;
129
130 /// find mend (first zero subdiag value)
131 for (; cnt < m; ++cnt) {
132 const auto val = ats::abs(*(H + cnt * hs - hs1));
133 if (val < tol) break;
134 }
135 const int mend = cnt;
136 const int mdiff = mend - mbeg;
137 const int mend_minus_two_mult_hs0 = (mend - 2) * hs0;
138
139 /// Step 2: if there exist non-converged eigen values
140 if (1 < mdiff) {
141 #if 0 /// implicit QR with shift for testing
142 {
143 /// Rayleigh quotient shift
144 const real_type shift = *(H+(mend-1)*hs);
145 SerialHessenbergQR_WithShiftInternal::invoke(mbeg, mend, m,
146 H, hs0, hs1,
147 shift,
148 Gs, true);
149
150 for (int i=mbeg;i<(mend-1);++i) {
151 const Kokkos::pair<real_type,real_type> G(Gs[i].first, -Gs[i].second);
152 SerialApplyRightGivensInternal::invoke(G, m,
153 Z+i*zs1, zs0,
154 Z+i*zs1+zs1, zs0);
155 }
156 }
157 #endif
158
159 #if 1
160 {
161 /// find a complex eigen pair
162 Kokkos::complex<real_type> lambda1, lambda2;
163 bool is_complex;
164 real_type *sub2x2 = H + (mend - 2) * hs;
165 if (2 == mdiff) {
166 Kokkos::pair<real_type, real_type> G;
167 SerialSchur2x2Internal::invoke(sub2x2, sub2x2 + hs1, sub2x2 + hs0, sub2x2 + hs, &G, &lambda1, &lambda2,
168 &is_complex);
169 subdiags[mend - 1] = sub2x2[hs0];
170
171 /// apply G' from left
172 G.second = -G.second;
173 SerialApplyLeftGivensInternal::invoke(G, m - mend, sub2x2 + 2 * hs1, hs1, sub2x2 + hs0 + 2 * hs1, hs1);
174
175 /// apply (G')' from right
176 SerialApplyRightGivensInternal::invoke(G, mend - 2, sub2x2 - mend_minus_two_mult_hs0, hs0,
177 sub2x2 + hs1 - mend_minus_two_mult_hs0, hs0);
178 sub2x2[hs0] = zero;
179
180 /// apply (G')' from right to compute Z
181 SerialApplyRightGivensInternal::invoke(G, m, Z + (mend - 2) * zs1, zs0, Z + (mend - 1) * zs1, zs0);
182
183 } else {
184 SerialWilkinsonShiftInternal::invoke(sub2x2[0], sub2x2[hs1], sub2x2[hs0], sub2x2[hs], &lambda1,
185 &lambda2, &is_complex);
186
187 SerialFrancisInternal::invoke(mbeg, mend, m, H, hs0, hs1, lambda1, lambda2, is_complex, Gs, true);
188 /* */ auto &val1 = *(sub2x2 + hs0);
189 /* */ auto &val2 = *(sub2x2 - hs1);
190 const auto abs_val1 = ats::abs(val1);
191 const auto abs_val2 = ats::abs(val2);
192
193 for (int i = mbeg; i < (mend - 1); ++i) {
194 const Kokkos::pair<real_type, real_type> G0(Gs[2 * i].first, -Gs[2 * i].second);
195 const Kokkos::pair<real_type, real_type> G1(Gs[2 * i + 1].first, -Gs[2 * i + 1].second);
196 SerialApplyRightGivensInternal::invoke(G0, m, Z + i * zs1, zs0, Z + i * zs1 + 1 * zs1, zs0);
197 SerialApplyRightGivensInternal::invoke(G1, m, Z + i * zs1, zs0, Z + i * zs1 + 2 * zs1, zs0);
198 }
199
200 /// convergence check
201 if (abs_val1 < tol) {
202 val1 = zero;
203 } else if (abs_val2 < tol) {
204 /// preserve the standard schur form
205 Kokkos::pair<real_type, real_type> G;
206 SerialSchur2x2Internal::invoke(sub2x2, sub2x2 + hs1, sub2x2 + hs0, sub2x2 + hs, &G, &lambda1,
207 &lambda2, &is_complex);
208 subdiags[mend - 1] = val1;
209
210 /// apply G' from left
211 G.second = -G.second;
212 SerialApplyLeftGivensInternal::invoke(G, m - mend, sub2x2 + 2 * hs1, hs1, sub2x2 + hs0 + 2 * hs1,
213 hs1);
214
215 // apply (G')' from right
216 SerialApplyRightGivensInternal::invoke(G, mend - 2, sub2x2 - mend_minus_two_mult_hs0, hs0,
217 sub2x2 + hs1 - mend_minus_two_mult_hs0, hs0);
218 val1 = zero;
219 val2 = zero;
220
221 // apply (G')' from right
222 SerialApplyRightGivensInternal::invoke(G, m, Z + (mend - 2) * zs1, zs0, Z + (mend - 1) * zs1, zs0);
223 }
224 }
225 }
226 #endif
227 } else {
228 /// all eigenvalues are converged
229 converge = true;
230 }
231 ++iter;
232 }
233 /// Step 3: record missing real eigenvalues from the diagonals
234 if (converge) {
235 // recover subdiags
236 real_type *Hs = H - hs1;
237 for (int i = 1; i < m; ++i) {
238 Hs[i * hs] = subdiags[i];
239 }
240 r_val = 0;
241 } else {
242 r_val = -1;
243 }
244 break;
245 }
246 }
247 return r_val;
248 }
249 };
250
251 } // namespace KokkosBatched
252
253 #endif