Debian Codegraph @

packages/kokkos-kernels/batched/dense/impl/KokkosBatched_SVD_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_SVD_SERIAL_INTERNAL_HPP
17 #define KOKKOSBATCHED_SVD_SERIAL_INTERNAL_HPP
18
19 /// \author Brian Kelley ([email protected])
20
21 #include "Kokkos_MathematicalFunctions.hpp"
22 #include "KokkosBatched_SetIdentity_Internal.hpp"
23 #include "KokkosBatched_Givens_Serial_Internal.hpp"
24 #include "KokkosBatched_ApplyGivens_Serial_Internal.hpp"
25 #include "KokkosBatched_Householder_Serial_Internal.hpp"
26 #include "KokkosBatched_ApplyHouseholder_Serial_Internal.hpp"
27
28 // Use this macro to handle raw pointer/stride based 2D indexing in this file
29 // (just for readability) Requires that for pointer X, the corresponding row/col
30 // strides are named Xs0 and Xs1.
31 #define SVDIND(arr, i, j) arr[(i)*arr##s0 + (j)*arr##s1]
32 #define SVDSWAP(a, b) \
33 { \
34 auto tmp = a; \
35 a = b; \
36 b = tmp; \
37 }
38
39 namespace KokkosBatched {
40
41 ///
42 /// Serial Internal Impl
43 /// ====================
44
45 struct SerialSVDInternal {
46 // Find the two eigenvalues of [a11 a21 ; a21 a22] by solving the
47 // characteristic quadratic. Since matrix is symmetric these will be real.
48 // NOTE: this is essentially the Wilkinson shift routine already in Batched,
49 // however this is simpler because it exploits the symmetric structure, and
50 // the realness of the eigenvalues.
51 template <typename value_type>
52 KOKKOS_INLINE_FUNCTION static void symEigen2x2(value_type a11, value_type a21, value_type a22, value_type& e1,
53 value_type& e2) {
54 value_type a = Kokkos::ArithTraits<value_type>::one();
55 value_type b = -a11 - a22;
56 value_type c = a11 * a22 - a21 * a21;
57 value_type sqrtDet = Kokkos::sqrt(b * b - 4 * a * c);
58 e1 = (-b + sqrtDet) / (2 * a);
59 e2 = (-b - sqrtDet) / (2 * a);
60 }
61
62 // B is a square submatrix on the diagonal.
63 // Usub is a subset of columns of U
64 // Vtsub is a subset of rows of Vt
65 //
66 // B22 is nsub * nsub, Usub is m * nsub, and Vtsub is nsub * n
67 template <typename value_type>
68 KOKKOS_INLINE_FUNCTION static void svdStep(value_type* B, value_type* U, value_type* Vt, int um, int vn, int n,
69 int Bs0, int Bs1, int Us0, int Us1, int Vts0, int Vts1) {
70 using KAT = Kokkos::ArithTraits<value_type>;
71 // Compute the eigenvalues of trailing 2x2
72 value_type dn = SVDIND(B, n - 1, n - 1);
73 value_type dm = SVDIND(B, n - 2, n - 2);
74 value_type fm = SVDIND(B, n - 2, n - 1);
75 value_type fmm1 = (n > 2) ? SVDIND(B, n - 3, n - 2) : KAT::zero();
76 value_type target = dn * dn + fm * fm;
77 value_type e1, e2, mu;
78 symEigen2x2(dm * dm + fmm1 * fmm1, dm * fm, target, e1, e2);
79 // the shift is the eigenvalue closer to the last diagonal entry of B^T*B
80 if (Kokkos::abs(e1 - target) < Kokkos::abs(e2 - target))
81 mu = e1;
82 else
83 mu = e2;
84 value_type y = SVDIND(B, 0, 0) * SVDIND(B, 0, 0) - mu;
85 value_type z = SVDIND(B, 0, 0) * SVDIND(B, 0, 1);
86 for (int k = 0; k < n - 1; k++) {
87 // Use Givens to zero out z in [y; z]
88 Kokkos::pair<value_type, value_type> G;
89 value_type discard; // Don't actually write [alpha; 0] anywhere
90 KokkosBatched::SerialGivensInternal::invoke<value_type>(y, z, &G, &discard);
91 // apply the Givens transformation to B on the right, to columns k,k+1
92 // B := BG(k, k+1, theta)
93 int minrow = KOKKOSKERNELS_MACRO_MAX(0, k - 1);
94 int maxrow = KOKKOSKERNELS_MACRO_MIN(n, k + 2);
95 KokkosBatched::SerialApplyRightGivensInternal::invoke<value_type>(G, maxrow - minrow, &SVDIND(B, minrow, k + 1),
96 Bs0, &SVDIND(B, minrow, k), Bs0);
97 if (Vt) {
98 KokkosBatched::SerialApplyLeftGivensInternal::invoke<value_type>(G, vn, &SVDIND(Vt, k + 1, 0), Vts1,
99 &SVDIND(Vt, k, 0), Vts1);
100 }
101 y = SVDIND(B, k, k);
102 z = SVDIND(B, k + 1, k);
103 KokkosBatched::SerialGivensInternal::invoke<value_type>(y, z, &G, &SVDIND(B, k, k));
104 SVDIND(B, k + 1, k) = KAT::zero();
105 int mincol = k + 1;
106 int maxcol = KOKKOSKERNELS_MACRO_MIN(n, k + 3);
107 // apply Givens transformation to B on the left, to rows k, k + 1
108 // B := G(k, k+1, theta)^T * B
109 KokkosBatched::SerialApplyLeftGivensInternal::invoke<value_type>(G, maxcol - mincol, &SVDIND(B, k + 1, mincol),
110 Bs1, &SVDIND(B, k, mincol), Bs1);
111 if (U) {
112 KokkosBatched::SerialApplyRightGivensInternal::invoke<value_type>(G, um, &SVDIND(U, 0, k + 1), Us0,
113 &SVDIND(U, 0, k), Us0);
114 }
115 if (k < n - 2) {
116 y = SVDIND(B, k, k + 1);
117 z = SVDIND(B, k, k + 2);
118 }
119 }
120 }
121
122 // Deal with B(i, i) = 0, by chasing superdiagonal nonzero across row i.
123 // Assumes i is not the last row.
124 // U is m*m, B is n*n
125 template <typename value_type>
126 KOKKOS_INLINE_FUNCTION static void svdZeroRow(int i, value_type* B, int n, int Bs0, int Bs1, value_type* U, int Um,
127 int Us0, int Us1) {
128 Kokkos::pair<value_type, value_type> G;
129 for (int j = i + 1; j < n; j++) {
130 // Zero out B(i, j) against diagonal j, introducing nonzero in B(i, j + 1)
131 KokkosBatched::SerialGivensInternal::invoke<value_type>(SVDIND(B, j, j), SVDIND(B, i, j), &G, &SVDIND(B, j, j));
132 SVDIND(B, i, j) = Kokkos::ArithTraits<value_type>::zero();
133 // Now, only need to apply givens to a single column (if not already at
134 // the end), introducing the next nonzero
135 if (j < n - 1) {
136 KokkosBatched::SerialApplyLeftGivensInternal::invoke<value_type>(G, 1, &SVDIND(B, i, j + 1), Bs1,
137 &SVDIND(B, j, j + 1), Bs1);
138 }
139 if (U) {
140 KokkosBatched::SerialApplyRightGivensInternal::invoke<value_type>(G, Um, &SVDIND(U, 0, i), Us0,
141 &SVDIND(U, 0, j), Us0);
142 }
143 }
144 }
145
146 template <typename value_type>
147 KOKKOS_INLINE_FUNCTION static void svdZeroLastColumn(value_type* B, int n, int Bs0, int Bs1, int vn, value_type* Vt,
148 int Vts0, int Vts1) {
149 // Deal with B(n-1, n-1) = 0, by chasing the superdiagonal nonzero up the last column.
150 Kokkos::pair<value_type, value_type> G;
151 for (int j = n - 2; j >= 0; j--) {
152 KokkosBatched::SerialGivensInternal::invoke<value_type>(SVDIND(B, j, j), SVDIND(B, j, n - 1), &G,
153 &SVDIND(B, j, j));
154 SVDIND(B, j, n - 1) = Kokkos::ArithTraits<value_type>::zero();
155 if (j != 0) {
156 KokkosBatched::SerialApplyRightGivensInternal::invoke<value_type>(G, 1, &SVDIND(B, j - 1, n - 1), Bs0,
157 &SVDIND(B, j - 1, j), Bs0);
158 }
159 if (Vt) {
160 KokkosBatched::SerialApplyLeftGivensInternal::invoke<value_type>(G, vn, &SVDIND(Vt, n - 1, 0), Vts1,
161 &SVDIND(Vt, j, 0), Vts1);
162 }
163 }
164 }
165
166 template <typename value_type>
167 KOKKOS_INLINE_FUNCTION static void bidiagonalize(int m, int n, value_type* A, int As0, int As1, value_type* U,
168 int Us0, int Us1, value_type* Vt, int Vts0, int Vts1,
169 value_type* work) {
170 using KAT = Kokkos::ArithTraits<value_type>;
171 value_type tau;
172 for (int i = 0; i < n; i++) {
173 // Eliminating column i of A below the diagonal
174 KokkosBatched::SerialLeftHouseholderInternal::invoke<value_type>(m - i - 1, &SVDIND(A, i, i),
175 &SVDIND(A, i + 1, i), As0, &tau);
176 if (n - i > 1) {
177 KokkosBatched::SerialApplyLeftHouseholderInternal::invoke<value_type>(
178 m - i - 1, n - i - 1, &tau, &SVDIND(A, i + 1, i), As0, &SVDIND(A, i, i + 1), As1, &SVDIND(A, i + 1, i + 1),
179 As0, As1, work);
180 }
181 if (U) {
182 KokkosBatched::SerialApplyRightHouseholderInternal::invoke<value_type>(
183 m, m - i - 1, &tau, &SVDIND(A, i + 1, i), As0, &SVDIND(U, 0, i), Us0, &SVDIND(U, 0, i + 1), Us0, Us1, work);
184 }
185 // Zero out A subdiag explicitly (NOTE: may not be necessary...)
186 for (int j = i + 1; j < m; j++) {
187 SVDIND(A, j, i) = KAT::zero();
188 }
189 if (i < n - 2) {
190 // Eliminating row i of A to the right of the 1st superdiagonal
191 KokkosBatched::SerialLeftHouseholderInternal::invoke<value_type>(n - i - 2, &SVDIND(A, i, i + 1),
192 &SVDIND(A, i, i + 2), As1, &tau);
193 if (m - i > 1) {
194 KokkosBatched::SerialApplyRightHouseholderInternal::invoke<value_type>(
195 m - i - 1, n - i - 2, &tau, &SVDIND(A, i, i + 2), As1, &SVDIND(A, i + 1, i + 1), As0,
196 &SVDIND(A, i + 1, i + 2), As0, As1, work);
197 }
198 if (Vt) {
199 KokkosBatched::SerialApplyLeftHouseholderInternal::invoke<value_type>(
200 n - i - 2, n, &tau, &SVDIND(A, i, i + 2), As1, &SVDIND(Vt, i + 1, 0), Vts1, &SVDIND(Vt, i + 2, 0), Vts0,
201 Vts1, work);
202 }
203 // Zero out A superdiag row explicitly
204 for (int j = i + 2; j < n; j++) {
205 SVDIND(A, i, j) = KAT::zero();
206 }
207 }
208 }
209 }
210
211 // Compute the SVD of a bidiagonal matrix B. Apply inverse transformations to
212 // U and Vt to maintain the product U*B*Vt. At the end, the singular values
213 // are copied to sigma.
214 template <typename value_type>
215 KOKKOS_INLINE_FUNCTION static void bidiSVD(int m, int n, value_type* B, int Bs0, int Bs1, value_type* U, int Us0,
216 int Us1, value_type* Vt, int Vts0, int Vts1, value_type* sigma, int ss,
217 const value_type& tol) {
218 using KAT = Kokkos::ArithTraits<value_type>;
219 const value_type eps = Kokkos::ArithTraits<value_type>::epsilon();
220 int p = 0;
221 int q = 0;
222 while (true) {
223 // Zero out tiny superdiagonal entries
224 for (int i = 0; i < n - 1; i++) {
225 if (Kokkos::abs(SVDIND(B, i, i + 1)) <
226 eps * (Kokkos::abs(SVDIND(B, i, i)) + Kokkos::abs(SVDIND(B, i + 1, i + 1))) ||
227 Kokkos::abs(SVDIND(B, i, i + 1)) < tol) {
228 SVDIND(B, i, i + 1) = KAT::zero();
229 }
230 }
231 // Find q: first column from the end with nonzero superdiagonal.
232 // If no such columns, will be 0.
233 for (q = n - 1; q > 0; q--) {
234 if (SVDIND(B, q - 1, q) != KAT::zero()) break;
235 }
236 if (q == 0) {
237 // B is completely diagonal, so it contains singular values and we are
238 // done.
239 break;
240 }
241 q++;
242 // now, q is the upper (exclusive) bound of submatrix on which to do SVD
243 // step. Find min p, so that [p, q) x [p, q) submatrix has all nonzero
244 // superdiagonals.
245 for (p = q - 1; p > 0; p--) {
246 if (SVDIND(B, p - 1, p) == KAT::zero()) break;
247 }
248 value_type* Bsub = &SVDIND(B, p, p);
249 value_type* Usub = &SVDIND(U, 0, p);
250 value_type* Vtsub = &SVDIND(Vt, p, 0);
251 int nsub = q - p;
252 // If there are zero diagonals in this range, eliminate the entire row
253 //(effectively decoupling into two subproblems)
254 for (int i = q - 1; i >= p; i--) {
255 if (SVDIND(B, i, i) == KAT::zero()) {
256 if (i == q - 1) {
257 // Last diagonal entry being 0 is a special case.
258 // Zero out the superdiagonal above it.
259 // Deal with B(q-1, q-1) = 0, by chasing the superdiagonal nonzero
260 // B(q-2, q-1) up the last column.
261 //
262 // Once that nonzero reaches B(p, q-1), we are either at the top of B
263 // (if p == 0) or the superdiag above B(p, p) is zero.
264 // In either case, the chase stops after eliminating B(p, q-1) because no
265 // new entry is introduced by the Givens.
266 svdZeroLastColumn(Bsub, nsub, Bs0, Bs1, n, Vtsub, Vts0, Vts1);
267 } else if (SVDIND(B, i, i + 1) != KAT::zero()) {
268 svdZeroRow(i - p, Bsub, nsub, Bs0, Bs1, Usub, m, Us0, Us1);
269 }
270 }
271 }
272 // B22 is nsub * nsub, Usub is m * nsub, and Vtsub is nsub * n
273 svdStep(Bsub, Usub, Vtsub, m, n, nsub, Bs0, Bs1, Us0, Us1, Vts0, Vts1);
274 }
275 for (int i = 0; i < n; i++) {
276 sigma[i * ss] = SVDIND(B, i, i);
277 }
278 }
279
280 // Convert SVD into conventional form: singular values positive and in
281 // descending order
282 template <typename value_type>
283 KOKKOS_INLINE_FUNCTION static void postprocessSVD(int m, int n, value_type* U, int Us0, int Us1, value_type* Vt,
284 int Vts0, int Vts1, value_type* sigma, int ss) {
285 // First step: flip signs on negative singular values
286 for (int i = 0; i < n; i++) {
287 if (sigma[i * ss] < 0) {
288 sigma[i * ss] = -sigma[i * ss];
289 if (Vt) {
290 for (int j = 0; j < n; j++) SVDIND(Vt, i, j) = -SVDIND(Vt, i, j);
291 }
292 }
293 }
294 // Second step: stable selection sort to put singular values in order.
295 // Using selection sort because the quadratic part only applies to sigma
296 // (O(n^2) total), and it minimizes column swaps in U,V (O(mn) total
297 // movement).
298 for (int i = 0; i < n - 1; i++) {
299 // find the proper singular value to go in position i
300 value_type maxval = sigma[i * ss];
301 int maxloc = i;
302 for (int j = i + 1; j < n; j++) {
303 if (sigma[j * ss] > maxval) {
304 maxval = sigma[j * ss];
305 maxloc = j;
306 }
307 }
308 // swap singular values and U/V columns i and maxloc (if maxloc is not
309 // already in the right place)
310 if (i != maxloc) {
311 SVDSWAP(sigma[i * ss], sigma[maxloc * ss]);
312 if (U) {
313 for (int j = 0; j < m; j++) SVDSWAP(SVDIND(U, j, i), SVDIND(U, j, maxloc))
314 }
315 if (Vt) {
316 for (int j = 0; j < n; j++) SVDSWAP(SVDIND(Vt, i, j), SVDIND(Vt, maxloc, j))
317 }
318 }
319 }
320 }
321
322 template <typename value_type>
323 KOKKOS_INLINE_FUNCTION static int invoke(int m, int n, value_type* A, int As0, int As1, value_type* U, int Us0,
324 int Us1, value_type* Vt, int Vts0, int Vts1, value_type* sigma, int ss,
325 value_type* work, value_type tol = Kokkos::ArithTraits<value_type>::zero()) {
326 // First, if m < n, need to instead compute (V, s, U^T) = A^T.
327 // This just means swapping U & Vt, and implicitly transposing A, U and Vt.
328 if (m < n) {
329 // Transpose A
330 SVDSWAP(m, n);
331 SVDSWAP(As0, As1);
332 // Transpose and swap U, Vt
333 SVDSWAP(U, Vt);
334 SVDSWAP(Us0, Vts1);
335 SVDSWAP(Us1, Vts0);
336 }
337 if (U) {
338 KokkosBatched::SerialSetIdentityInternal::invoke<value_type>(m, m, U, Us0, Us1);
339 }
340 if (Vt) {
341 KokkosBatched::SerialSetIdentityInternal::invoke<value_type>(n, n, Vt, Vts0, Vts1);
342 }
343 if (m == 0 || n == 0) {
344 // sigma is length 0, so there's nothing left to compute
345 return 0;
346 }
347 bidiagonalize(m, n, A, As0, As1, U, Us0, Us1, Vt, Vts0, Vts1, work);
348 bidiSVD(m, n, A, As0, As1, U, Us0, Us1, Vt, Vts0, Vts1, sigma, ss, tol);
349 postprocessSVD(m, n, U, Us0, Us1, Vt, Vts0, Vts1, sigma, ss);
350 return 0;
351 }
352 };
353
354 } // namespace KokkosBatched
355
356 #undef SVDIND
357 #undef SVDSWAP
358
359 #endif