Debian Codegraph @

packages/kokkos-kernels/batched/dense/impl/KokkosBatched_HessenbergQR_WithShift_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_HESSENBERG_QR_WITH_SHIFT_SERIAL_INTERNAL_HPP
17 #define KOKKOSBATCHED_HESSENBERG_QR_WITH_SHIFT_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 SerialHessenbergQR_WithShiftInternal {
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, const ValueType shift,
37 /* */ Kokkos::pair<ValueType, ValueType> *GG, const bool request_schur) {
38 typedef ValueType value_type;
39 // typedef Kokkos::ArithTraits<value_type> ats;
40
41 const int hs = hs0 + hs1;
42 const value_type zero(0), one(1);
43 const Kokkos::pair<value_type, value_type> identity(one, zero);
44
45 /// redefine variables
46 const int m = mend - mbeg, mbeg_mult_hs0 = mbeg * hs0;
47 value_type *H = HH + mbeg * hs;
48
49 /// initialize Gs
50 Kokkos::pair<value_type, value_type> *Gs = NULL;
51 if (request_schur) {
52 for (int i = 0; i < morg; ++i) GG[i] = identity;
53 Gs = GG + mbeg;
54 }
55
56 /// Given a strict Hessenberg matrix H (m x m),
57 /// it computes a single implicit QR step with a given shift
58 /// - it assumes H has zeros on subdiagonal entries (
59 /// givens rotation is defined as G = [gamma -sigma
60 /// sigma gamma]
61 /// G' [chi1 chi2]^t = [alpha 0]^T
62 /// where G is stored as a pair of gamma and sigma
63 Kokkos::pair<value_type, value_type> G;
64
65 /// 0. compute the first givens rotation that introduces a bulge
66 {
67 const value_type chi1 = H[0] - shift;
68 const value_type chi2 = H[hs0];
69 /* */ value_type alpha;
70 SerialGivensInternal::invoke(chi1, chi2, &G, &alpha);
71 // record G
72 if (request_schur) Gs[0] = G;
73
74 value_type *h11 = H;
75 value_type *h21 = H + hs0;
76 value_type *h12 = H + hs1;
77
78 // apply G' from left
79 G.second = -G.second; // transpose G
80 const int nn = m;
81 SerialApplyLeftGivensInternal::invoke(G, nn + (morg - mend), h11, hs1, h21, hs1);
82
83 // apply (G')' from right
84 const int mm = m < 3 ? m : 3;
85 SerialApplyRightGivensInternal::invoke(G, mm + mbeg, h11 - mbeg_mult_hs0, hs0, h12 - mbeg_mult_hs0, hs0);
86 }
87
88 /// 1. chase the bulge
89
90 // partitions used for loop iteration
91 Partition2x2<value_type> H_part2x2(hs0, hs1);
92 Partition3x3<value_type> H_part3x3(hs0, hs1);
93
94 // initial partition of A where ATL has a zero dimension
95 H_part2x2.partWithATL(H, m, m, 1, 1);
96
97 for (int m_htl = 1; m_htl < (m - 1); ++m_htl) {
98 // part 2x2 into 3x3
99 H_part3x3.partWithABR(H_part2x2, 1, 1);
100 // const int n_hbr = m - m_htl;
101 /// -----------------------------------------------------
102 value_type *chi1 = H_part3x3.A11 - hs1;
103 value_type *chi2 = H_part3x3.A21 - hs1;
104 SerialGivensInternal::invoke(*chi1, *chi2, &G, chi1);
105 *chi2 = zero;
106 // record G
107 if (request_schur) Gs[m_htl] = G;
108
109 G.second = -G.second; // transpose G
110
111 const int nn = m - m_htl;
112 SerialApplyLeftGivensInternal::invoke(G, nn + (morg - mend), H_part3x3.A11, hs1, H_part3x3.A21, hs1);
113
114 const int mtmp = m_htl + 3, mm = mtmp < m ? mtmp : m;
115 SerialApplyRightGivensInternal::invoke(G, mm + mbeg, H_part3x3.A01 - mbeg_mult_hs0, hs0,
116 H_part3x3.A02 - mbeg_mult_hs0, hs0);
117 /// -----------------------------------------------------
118 H_part2x2.mergeToATL(H_part3x3);
119 }
120 return 0;
121 }
122
123 template <typename ValueType>
124 KOKKOS_FORCEINLINE_FUNCTION static int invoke(const int mbeg, const int mend, const int morg,
125 /* */ ValueType *HH, const int hs0, const int hs1,
126 const ValueType shift) {
127 return invoke(mbeg, mend, morg, HH, hs0, hs1, shift, (Kokkos::pair<ValueType, ValueType> *)NULL, false);
128 }
129 };
130
131 } // end namespace KokkosBatched
132
133 #endif