Debian Codegraph @

packages/kokkos-kernels/batched/dense/impl/KokkosBatched_Eigendecomposition_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_EIGENDECOMPOSITION_SERIAL_INTERNAL_HPP
17 #define KOKKOSBATCHED_EIGENDECOMPOSITION_SERIAL_INTERNAL_HPP
18
19 /// \author Kyungjoo Kim ([email protected])
20
21 #include "KokkosBatched_Util.hpp"
22 #include "KokkosBatched_SetIdentity_Internal.hpp"
23 #include "KokkosBatched_SetTriangular_Internal.hpp"
24 #include "KokkosBatched_Normalize_Internal.hpp"
25 #include "KokkosBatched_Hessenberg_Serial_Internal.hpp"
26 #include "KokkosBatched_ApplyQ_Serial_Internal.hpp"
27 #include "KokkosBatched_Schur_Serial_Internal.hpp"
28 #include "KokkosBatched_RightEigenvectorFromSchur_Serial_Internal.hpp"
29 #include "KokkosBatched_LeftEigenvectorFromSchur_Serial_Internal.hpp"
30 #include "KokkosBatched_Gemm_Serial_Internal.hpp"
31
32 namespace KokkosBatched {
33
34 ///
35 /// Serial Internal Impl
36 /// ====================
37
38 struct SerialEigendecompositionInternal {
39 /// Given a general nonsymmetric matrix A (m x m), it performs
40 /// eigendecomposition of the matrix.
41 ///
42 /// Parameters:
43 /// [in]m
44 /// A dimension of the square matrix H.
45 /// [in/out]A, [in]as0, [in]as1
46 /// Real general nonsymmetric matrix A(m x m) with strides as0 and as1.
47 /// A is first condensed to a upper Hessenberg form. Then, the Francis
48 /// double shift QR algorithm is applied to compute its Schur form.
49 /// On exit, A stores a quasi upper triangular matrix of the Schur
50 /// decomposition.
51 /// [out]er, [in]ers, [out]ei, [in]eis
52 /// A complex vector er(m)+ei(m)i with a stride ers and eis to store
53 /// computed eigenvalues. For a complex eigen pair, it stores a+bi and
54 /// a-bi consecutively.
55 /// [out]UL, [in]uls0, [in] uls1
56 /// Left eigenvectors UL(m x m) with strides uls0 and uls1. When UL is
57 /// NULL, the left eigenvectors are not computed.
58 /// [out]UR, [in]urs0, [in] urs1
59 /// Right eigenvectors UR(m x m) with strides urs0 and urs1. When UR is
60 /// NULL, the right eigenvectors are not computed.
61 /// [out]w, [in]wlen
62 /// Workspace
63 template <typename RealType>
64 KOKKOS_INLINE_FUNCTION static int device_invoke(const int m, RealType* A, const int as0, const int as1, RealType* er,
65 const int ers, RealType* ei, const int eis, RealType* UL,
66 const int uls0, const int uls1, RealType* UR, const int urs0,
67 const int urs1, RealType* w, const int wlen) {
68 /// until debugging is done, comment out the code
69 /// testing happens only for TPLs on host.
70 static_assert(false,
71 "Serial eigendecomposition on device and/or without LAPACK "
72 "is not implemented yet");
73 // typedef RealType real_type;
74 // typedef Kokkos::ArithTraits<real_type> ats;
75
76 // const real_type one(1), zero(0), tol = 1e2*ats::epsilon();
77 // //const Kokkos::pair<real_type,real_type> identity(one, zero);
78
79 // /// step 0: input checking
80 // assert( (wlen >= (2*m*m+5*m)) && "Eigendecomposition: workspace
81 // size is too small"); real_type *w_now = w; int wlen_now = wlen;
82 // assert( (wlen_now >= 0) && "Eigendecomposition: workspace size is
83 // negative");
84
85 // const bool is_UL = UL != NULL, is_UR = UR != NULL;
86 // assert((is_UL || is_UR) && "Eigendecomposition: neither left nor
87 // right eigenvectors were requested. Use SerialEigenvalueInternal
88 // instead.");
89
90 // real_type *QZ = w_now; w_now += (m*m); wlen_now -= (m*m);
91 // assert( (wlen_now >= 0) && "Eigendecomposition: QZ allocation
92 // fails");
93
94 // const int qzs0 = m, qzs1 = 1, qzs = m+1; /// row major
95 // const int as = as0+as1;
96
97 // /// step 1: Hessenberg reduction A = Q H Q^H
98 // /// Q is stored in QZ
99 //
100 ////////////////////////////////////////////////////////////////////////////
101 // DO NOT USE
102 //
103 // #ifdef KOKKOS_ACTIVE_EXECUTION_MEMORY_SPACE_HOST
104 // <host code>
105 // #else
106 // <device code>
107 // #endif
108 //
109 // DO THIS INSTEAD
110 //
111 // KOKKOS_IF_ON_HOST((<host code>))
112 // KOKKOS_IF_ON_DEVICE((<device code>))
113 //
114 ////////////////////////////////////////////////////////////////////////////
115 // #if (defined(KOKKOSKERNELS_ENABLE_TPL_MKL) && (__INTEL_MKL__ >= 2018)) &&
116 // defined(KOKKOS_ACTIVE_EXECUTION_MEMORY_SPACE_HOST)
117 // {
118 // real_type *t = w_now; w_now += m; wlen_now -= m;
119 // assert( (wlen_now >= 0) && "Eigendecomposition: Hessenberg
120 // reduction workspace t allocation fail");
121
122 // if (as0 == 1 || as1 == 1) { /// if mkl can be interfaced, use it
123 // const auto matrix_layout = ( as1 == 1 ? LAPACK_ROW_MAJOR :
124 // LAPACK_COL_MAJOR ); LAPACKE_dgehrd(matrix_layout, m, 1, m, A,
125 // m, t);
126
127 // SerialSetIdentityInternal::invoke(m, QZ, qzs0, qzs1);
128 // LAPACKE_dorghr(matrix_layout, m, 1, m, QZ, m, t);
129 // } else { /// for arbitrary strides, there is no choice to use
130 // tpls
131 // real_type *ww = w_now; w_now += m; wlen_now -= m;
132 // assert( (wlen_now >= 0) && "Eigendecomposition: Hessenberg
133 // reduction workspace ww allocation fail");
134
135 // SerialHessenbergInternal::invoke(m, m,
136 // A, as0, as1,
137 // t, 1,
138 // ww);
139
140 // SerialSetIdentityInternal::invoke(m, QZ, qzs0, qzs1);
141 // SerialApplyQ_LeftForwardInternal::invoke(m-1, m-1, m-1,
142 // A+as0, as0, as1,
143 // t, 1,
144 // QZ+qzs, qzs0, qzs1,
145 // ww);
146 // /// recovery of workspace for ww
147 // w_now -= m; wlen_now += m;
148 // }
149 // /// recovery of workspace for t
150 // w_now -= m; wlen_now += m;
151
152 // /// clean up H
153 // SerialSetLowerTriangularInternal::invoke(m, m,
154 // 2,
155 // zero,
156 // A, as0, as1);
157 // }
158 // #else
159 // {
160 // real_type *t = w_now; w_now += m; wlen_now -= m;
161 // real_type *ww = w_now; w_now += m; wlen_now -= m;
162 // assert( (wlen_now >= 0) && "Eigendecomposition: Hessenberg
163 // reduction workspace t and ww allocation fail");
164
165 // SerialHessenbergInternal::invoke(m, m,
166 // A, as0, as1,
167 // t, 1,
168 // ww);
169
170 // SerialSetIdentityInternal::invoke(m, QZ, qzs0, qzs1);
171 // SerialApplyQ_LeftForwardInternal::invoke(m-1, m-1, m-1,
172 // A+as0, as0, as1,
173 // t, 1,
174 // QZ+qzs, qzs0, qzs1,
175 // ww);
176
177 // /// clean up H
178 // SerialSetLowerTriangularInternal::invoke(m, m,
179 // 2,
180 // zero,
181 // A, as0, as1);
182
183 // /// recover workspace
184 // w_now -= (2*m); wlen_now += (2*m);
185 // }
186 // #endif
187 // /// step 2: Schur decomposition H = Z T Z^H
188 // /// Z is applied to QZ
189 // {
190 // int r_val = 0;
191 // real_type *ww = w_now; w_now += (5*m); wlen_now -= (5*m);
192 // assert( (wlen_now >= 0) && "Eigendecomposition: Schur
193 // decomposition workspace ww allocation fails"); do {
194 // const bool restart = (r_val < 0);
195 // r_val = SerialSchurInternal::invoke(m,
196 // A, as0, as1,
197 // QZ, qzs0, qzs1,
198 // ww, 5*m,
199 // restart);
200 // } while (r_val < 0 && false);
201 // // for a testing purpose, we run the Schur decomposition with a
202 // finite number of Francis iterations w_now -= (5*m); wlen_now +=
203 // (5*m);
204 // }
205
206 // /// Step 3: Extract iigenvalues and eigenvectors from T = V S V^-1
207 // ///
208 // {
209 // /// extract eigenvalues
210 // real_type *AA = A-as1;
211 // int *blks = (int*)w_now; w_now += m; wlen_now -= m;
212 // assert( (wlen_now >= 0) && "Eigendecomposition: Eigenvector
213 // workspace blks allocation fails");
214
215 // {
216 // int i=0;
217 // for (;i<(m-1);) {
218 // const real_type subdiag = ats::abs(AA[(i+1)*as]);
219 // const real_type diag = A[i*as];
220 // if (subdiag < tol) {
221 // er[i*ers] = diag;
222 // ei[i*eis] = zero;
223 // blks[i] = 1;
224 // i+=1;
225 // } else {
226 // const real_type offdiag = ats::abs(A[i*as+as1]);
227 // const real_type sqrt_mult_suboffdiags =
228 // ats::sqrt(subdiag*offdiag); er[(i )*ers] = diag;
229 // er[(i+1)*ers] = diag;
230 // ei[(i )*eis] = sqrt_mult_suboffdiags;
231 // ei[(i+1)*eis] = -sqrt_mult_suboffdiags;
232 // blks[i ] = 2;
233 // blks[i+1] = 2; /// consider backward iteration
234 // i+=2;
235 // }
236 // }
237 // if (i<m) { /// take care the remainder
238 // er[i*ers] = A[i*as];
239 // ei[i*eis] = zero;
240 // blks[i] = 1;
241 // }
242 // }
243
244 // {
245 // real_type *V = w_now; w_now += (m*m); wlen_now -= (m*m);
246 // assert( (wlen_now >= 0) && "Eigendecomposition: Eigenvector
247 // workspace V allocation fails");
248
249 // const int vs0 = 1, vs1 = m;
250 // real_type *ww = w_now; w_now += 2*m; wlen_now -= 2*m;
251 // assert( (wlen_now >= 0) && "Eigendecomposition: Eigenvector
252 // workspace w allocation fails");
253
254 // /// Right eigenvectors V
255 // if (is_UR) {
256 // SerialRightEigenvectorFromSchurInternal
257 // ::invoke(m,
258 // A, as0, as1,
259 // V, vs0, vs1,
260 // ww,
261 // blks);
262
263 // /// QZ V
264 // SerialGemmInternal<Algo::Gemm::Unblocked>::
265 // invoke(m, m, m,
266 // one,
267 // QZ, qzs0, qzs1,
268 // V, vs0, vs1,
269 // zero,
270 // UR, urs0, urs1);
271 // int j=0;
272 // for (;j<m;) {
273 // if (ats::abs(ei[j*eis]) < tol) {
274 // /// a real eigenvalue
275 // SerialNormalizeInternal::invoke(m,
276 // UR+j*urs1, urs0);
277 // j+=1;
278 // } else {
279 // /// a complex pair of eigenvalues
280 // SerialNormalizeInternal::invoke(m,
281 // UR+(j )*urs1, urs0,
282 // UR+(j+1)*urs1, urs0);
283 // j+=2;
284 // }
285 // }
286 // }
287
288 // /// Left eigenvectors V stores V
289 // if (is_UL) {
290 // SerialLeftEigenvectorFromSchurInternal
291 // ::invoke(m,
292 // A, as0, as1,
293 // V, vs0, vs1,
294 // ww,
295 // blks);
296
297 // /// V^-1 (QZ)^H
298 // SerialGemmInternal<Algo::Gemm::Unblocked>::
299 // invoke(m, m, m,
300 // one,
301 // V, vs0, vs1,
302 // QZ, qzs1, qzs0,
303 // zero,
304 // UL, uls0, uls1);
305
306 // int i=0;
307 // for (;i<m;) {
308 // /// normalize row vectors
309 // if (ats::abs(ei[i*eis]) < tol) {
310 // /// a real eigenvalue
311 // SerialNormalizeInternal::invoke(m,
312 // UL+i*uls0, uls1);
313 // i+=1;
314 // } else {
315 // /// a complex pair of eigenvalues
316 // SerialNormalizeInternal::invoke(m,
317 // UL+(i )*uls0, uls1,
318 // UL+(i+1)*uls0, uls1);
319 // i+=2;
320 // }
321 // }
322 // }
323 // w_now -= (m*m+2*m); wlen_now += (m*m+2*m);
324 // }
325 // // deallocate blks
326 // w_now -= m; wlen_now += m;
327 // }
328 // /// deallocate QZ
329 // w_now -= (m*m); wlen_now += (m*m);
330
331 // assert( (w == w_now) && "Eigendecomposition: workspace tracking
332 // fails"); assert( (wlen == wlen_now) && "Eigendecomposition:
333 // workspace counting fails");
334 return 0;
335 }
336
337 template <typename RealType>
338 inline static int host_invoke(const int m, RealType* A, const int as0, const int as1, RealType* er, const int ers,
339 RealType* ei, const int eis, RealType* UL, const int uls0, const int uls1, RealType* UR,
340 const int urs0, const int urs1, RealType* w, const int wlen) {
341 #if defined(__KOKKOSBATCHED_ENABLE_LAPACKE__) || defined(KOKKOSBATCHED_IMPL_ENABLE_INTEL_MKL)
342 int matrix_layout(0), lda(0), uls(0), urs(0);
343 if (as0 == 1) {
344 assert(uls0 == 1 && "UL is not column major");
345 assert(urs0 == 1 && "UL is not column major");
346
347 matrix_layout = LAPACK_COL_MAJOR;
348 lda = as1;
349 uls = uls1;
350 urs = urs1;
351 }
352
353 if (as1 == 1) {
354 matrix_layout = LAPACK_ROW_MAJOR;
355 assert(uls1 == 1 && "UR is not row major");
356 assert(urs1 == 1 && "UR is not row major");
357 lda = as0;
358 uls = uls0;
359 urs = urs0;
360 }
361 assert(matrix_layout != 0 && "Either stride of A is not unit");
362 if (std::is_same<RealType, float>::value) {
363 LAPACKE_sgeev(matrix_layout, 'V', 'V', m, (float*)A, lda, (float*)er, (float*)ei, (float*)UL, uls, (float*)UR,
364 urs);
365 } else if (std::is_same<RealType, double>::value) {
366 LAPACKE_dgeev(matrix_layout, 'V', 'V', m, (double*)A, lda, (double*)er, (double*)ei, (double*)UL, uls,
367 (double*)UR, urs);
368 } else {
369 // no complex is needed for this moment
370 assert(false && "complex type is not supported");
371 }
372 #else
373 device_invoke(m, A, as0, as1, er, ers, ei, eis, UL, uls0, uls1, UR, urs0, urs1, w, wlen);
374
375 #endif
376 return 0;
377 }
378
379 template <typename RealType>
380 KOKKOS_INLINE_FUNCTION static int invoke(const int m, RealType* A, const int as0, const int as1, RealType* er,
381 const int ers, RealType* ei, const int eis, RealType* UL, const int uls0,
382 const int uls1, RealType* UR, const int urs0, const int urs1, RealType* w,
383 const int wlen) {
384 KOKKOS_IF_ON_HOST((host_invoke(m, A, as0, as1, er, ers, ei, eis, UL, uls0, uls1, UR, urs0, urs1, w, wlen);))
385 KOKKOS_IF_ON_DEVICE((device_invoke(m, A, as0, as1, er, ers, ei, eis, UL, uls0, uls1, UR, urs0, urs1, w, wlen);))
386 return 0;
387 }
388 };
389
390 } // namespace KokkosBatched
391
392 #endif