| 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 |