Debian Codegraph @

packages/kokkos-kernels/batched/dense/impl/KokkosBatched_Francis_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_FRANCIS_SERIAL_INTERNAL_HPP
17 #define KOKKOSBATCHED_FRANCIS_SERIAL_INTERNAL_HPP
18
19 /// \author Kyungjoo Kim ([email protected])
20
21 #include "KokkosBatched_Util.hpp"
22 #include "KokkosBatched_Givens_Serial_Internal.hpp"
23 #include "KokkosBatched_ApplyGivens_Serial_Internal.hpp"
24
25 namespace KokkosBatched {
26
27 ///
28 /// Serial Internal Impl
29 /// ====================
30 ///
31 /// this impl follows the flame interface of householder transformation
32 ///
33 struct SerialFrancisInternal {
34 template <typename ValueType>
35 KOKKOS_INLINE_FUNCTION static int invoke(const int mbeg, const int mend, const int morg,
36 /* */ ValueType *HH, const int hs0, const int hs1,
37 const Kokkos::complex<ValueType> lambda1,
38 const Kokkos::complex<ValueType> lambda2, const bool is_complex,
39 /* */ Kokkos::pair<ValueType, ValueType> *GG, const bool request_schur) {
40 typedef ValueType value_type;
41
42 const int hs = hs0 + hs1;
43 const value_type one(1), zero(0);
44 const Kokkos::pair<value_type, value_type> identity(one, zero);
45
46 /// redefine variables
47 const int m = mend - mbeg, mrst = morg - mend, mbeg_mult_hs0 = mbeg * hs0;
48 value_type *H = HH + hs * mbeg;
49
50 /// initialize Gs
51 Kokkos::pair<value_type, value_type> *Gs = NULL;
52 if (request_schur) {
53 Gs = (Kokkos::pair<value_type, value_type> *)(GG + mbeg * 2);
54 for (int i = 0; i < morg; ++i) {
55 GG[2 * i] = identity;
56 GG[2 * i + 1] = identity;
57 }
58 }
59
60 /// Given a strict Hessenberg matrix H (m x m),
61 /// it computes a single implicit QR step with a given shift
62 /// - it assumes H has zeros on subdiagonal entries (
63 /// givens rotation is defined as G = [gamma -sigma
64 /// sigma gamma]
65 /// G' [chi1 chi2]^t = [alpha 0]^T
66 /// where G is stored as a pair of gamma and sigma
67 Kokkos::pair<value_type, value_type> G[2];
68
69 /// 0. compute 1st double shift vector
70 value_type v[3];
71 {
72 // this needs m>=3
73 // v = M e_1 = (H*H - 2 Re(lambda) H + |lambda|^2 I)e_1
74 value_type s, t;
75 const value_type h00 = H[0 * hs0 + 0 * hs1], h01 = H[0 * hs0 + 1 * hs1], h10 = H[1 * hs0 + 0 * hs1],
76 h11 = H[1 * hs0 + 1 * hs1],
77 /* */ h21 = H[2 * hs0 + 1 * hs1];
78 if (is_complex) {
79 s = 2 * lambda1.real();
80 t = lambda1.real() * lambda1.real() + lambda1.imag() * lambda1.imag();
81 } else {
82 const value_type val = H[(m - 1) * hs];
83 const auto dist_lambda1 = Kokkos::ArithTraits<value_type>::abs(lambda1.real() - val);
84 const auto dist_lambda2 = Kokkos::ArithTraits<value_type>::abs(lambda2.real() - val);
85 const value_type lambda = dist_lambda1 < dist_lambda2 ? lambda1.real() : lambda2.real();
86 s = 2 * lambda;
87 t = lambda * lambda;
88 }
89 v[0] = h00 * h00 + h01 * h10 /* H^2 e_1 */ - s * h00 /* 2 Re(lambda) */ + t;
90 v[1] = h10 * h00 + h11 * h10 /* */ - s * h10;
91 v[2] = h21 * h10;
92 }
93
94 /// 1. compute the first two givens rotations that introduces a bulge
95 {
96 SerialGivensInternal::invoke(v[0], v[1], &G[0], &v[0]);
97 SerialGivensInternal::invoke(v[0], v[2], &G[1], &v[0]);
98 // record
99 if (request_schur) {
100 Gs[0] = G[0];
101 Gs[1] = G[1];
102 }
103
104 // apply G' from left and right
105 G[0].second = -G[0].second;
106 G[1].second = -G[1].second;
107
108 const int mm = m < 4 ? m : 4, nn = m;
109 value_type *Hs = H - mbeg_mult_hs0;
110 SerialApplyLeftRightGivensInternal ::invoke(G[0], G[1], mm + mbeg, nn + mrst, H, H + hs0, H + 2 * hs0, Hs,
111 Hs + hs1, Hs + 2 * hs1, hs0, hs1);
112 }
113
114 /// 1. chase the bulge
115
116 // partitions used for loop iteration
117 Partition2x2<value_type> H_part2x2(hs0, hs1);
118 Partition3x3<value_type> H_part3x3(hs0, hs1);
119
120 // initial partition of A where ATL has a zero dimension
121 int m_htl = 1;
122 H_part2x2.partWithATL(H, m, m, m_htl, m_htl);
123 for (; m_htl < (m - 2); ++m_htl) {
124 // part 2x2 into 3x3
125 H_part3x3.partWithABR(H_part2x2, 1, 1);
126 /// -----------------------------------------------------
127 value_type *chi1 = H_part3x3.A11 - hs1;
128 value_type *chi2 = chi1 + hs0;
129 value_type *chi3 = chi2 + hs0;
130
131 SerialGivensInternal::invoke(*chi1, *chi2, &G[0], chi1);
132 *chi2 = zero;
133 SerialGivensInternal::invoke(*chi1, *chi3, &G[1], chi1);
134 *chi3 = zero;
135 // record
136 if (request_schur) {
137 Gs[2 * m_htl] = G[0];
138 Gs[2 * m_htl + 1] = G[1];
139 }
140
141 G[0].second = -G[0].second;
142 G[1].second = -G[1].second;
143
144 const int nn = m - m_htl, mtmp = m_htl + 4, mm = mtmp < m ? mtmp : m;
145 value_type *a1t = H_part3x3.A11;
146 value_type *a2t = a1t + hs0;
147 value_type *a3t = a2t + hs0;
148 value_type *a1 = H_part3x3.A01 - mbeg_mult_hs0;
149 value_type *a2 = a1 + hs1;
150 value_type *a3 = a2 + hs1;
151
152 SerialApplyLeftRightGivensInternal ::invoke(G[0], G[1], mm + mbeg, nn + mrst, a1t, a2t, a3t, a1, a2, a3, hs0,
153 hs1);
154 /// -----------------------------------------------------
155 H_part2x2.mergeToATL(H_part3x3);
156 }
157
158 // last 3x3 block
159 {
160 // part 2x2 into 3x3
161 H_part3x3.partWithABR(H_part2x2, 1, 1);
162 /// -----------------------------------------------------
163 value_type *chi1 = H_part3x3.A11 - hs1;
164 value_type *chi2 = chi1 + hs0;
165 SerialGivensInternal::invoke(*chi1, *chi2, &G[0], chi1);
166 *chi2 = zero;
167 Gs[2 * m_htl] = G[0];
168 Gs[2 * m_htl + 1] = identity;
169
170 G[0].second = -G[0].second;
171
172 const int mm = m, nn = 2;
173 value_type *a1t = H_part3x3.A11;
174 value_type *a2t = a1t + hs0;
175 value_type *a1 = H_part3x3.A01 - mbeg_mult_hs0;
176 value_type *a2 = a1 + hs1;
177 SerialApplyLeftRightGivensInternal ::invoke(G[0], mm + mbeg, nn + mrst, a1t, a2t, a1, a2, hs0, hs1);
178
179 /// -----------------------------------------------------
180 H_part2x2.mergeToATL(H_part3x3);
181 }
182
183 return 0;
184 }
185
186 template <typename ValueType>
187 KOKKOS_FORCEINLINE_FUNCTION static int invoke(const int mbeg, const int mend, const int morg,
188 /* */ ValueType *HH, const int hs0, const int hs1,
189 const Kokkos::complex<ValueType> lambda1,
190 const Kokkos::complex<ValueType> lambda2, const bool is_complex) {
191 return invoke(mbeg, mend, morg, HH, hs0, hs1, lambda1, lambda2, is_complex,
192 (Kokkos::pair<ValueType, ValueType> *)NULL, false);
193 }
194 };
195
196 } // end namespace KokkosBatched
197
198 #endif