| 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_QR_WITH_COLUMNPIVOTING_TEAMVECTOR_INTERNAL_HPP |
| 17 |
#define KOKKOSBATCHED_QR_WITH_COLUMNPIVOTING_TEAMVECTOR_INTERNAL_HPP |
| 18 |
|
| 19 |
/// \author Kyungjoo Kim ([email protected]) |
| 20 |
|
| 21 |
#include "KokkosBatched_Util.hpp" |
| 22 |
|
| 23 |
#include "KokkosBatched_FindAmax_Internal.hpp" |
| 24 |
#include "KokkosBatched_Dot.hpp" |
| 25 |
#include "KokkosBatched_ApplyPivot_Internal.hpp" |
| 26 |
|
| 27 |
#include "KokkosBatched_Householder_TeamVector_Internal.hpp" |
| 28 |
#include "KokkosBatched_ApplyHouseholder_TeamVector_Internal.hpp" |
| 29 |
|
| 30 |
namespace KokkosBatched { |
| 31 |
|
| 32 |
/// |
| 33 |
/// TeamVector Internal |
| 34 |
/// =================== |
| 35 |
/// |
| 36 |
/// this impl follows the flame interface of householder transformation |
| 37 |
/// |
| 38 |
struct TeamVectorUpdateColumnNormsInternal { |
| 39 |
template <typename MemberType, typename ValueType> |
| 40 |
KOKKOS_INLINE_FUNCTION static int invoke(const MemberType &member, const int n, const ValueType *KOKKOS_RESTRICT a, |
| 41 |
const int as0, |
| 42 |
/* */ ValueType *KOKKOS_RESTRICT norm, const int ns0) { |
| 43 |
using ats = Kokkos::ArithTraits<ValueType>; |
| 44 |
Kokkos::parallel_for(Kokkos::TeamVectorRange(member, n), [&](const int &j) { |
| 45 |
const int idx_a = j * as0, idx_n = j * ns0; |
| 46 |
norm[idx_n] -= ats::conj(a[idx_a]) * a[idx_a]; |
| 47 |
}); |
| 48 |
return 0; |
| 49 |
} |
| 50 |
}; |
| 51 |
|
| 52 |
struct TeamVectorQR_WithColumnPivotingInternal { |
| 53 |
template <typename MemberType, typename ValueType, typename IntType> |
| 54 |
KOKKOS_INLINE_FUNCTION static int invoke(const MemberType &member, |
| 55 |
const int m, // m = NumRows(A) |
| 56 |
const int n, // n = NumCols(A) |
| 57 |
/* */ ValueType *A, const int as0, const int as1, |
| 58 |
/* */ ValueType *t, const int ts0, |
| 59 |
/* */ IntType *p, const int ps0, |
| 60 |
/* */ ValueType *w, |
| 61 |
/* */ int &matrix_rank) { |
| 62 |
using value_type = ValueType; |
| 63 |
using int_type = IntType; |
| 64 |
using ats = Kokkos::ArithTraits<value_type>; |
| 65 |
|
| 66 |
/// Given a matrix A, it computes QR decomposition of the matrix |
| 67 |
/// - t is to store tau and w is for workspace |
| 68 |
|
| 69 |
// partitions used for loop iteration |
| 70 |
Partition2x2<value_type> A_part2x2(as0, as1); |
| 71 |
Partition3x3<value_type> A_part3x3(as0, as1); |
| 72 |
|
| 73 |
// column vector of tau (size of min_mn) |
| 74 |
Partition2x1<value_type> t_part2x1(ts0); |
| 75 |
Partition3x1<value_type> t_part3x1(ts0); |
| 76 |
|
| 77 |
// row vector for norm and p (size of n) |
| 78 |
Partition1x2<int_type> p_part1x2(ps0); |
| 79 |
Partition1x3<int_type> p_part1x3(ps0); |
| 80 |
|
| 81 |
Partition1x2<value_type> norm_part1x2(1); |
| 82 |
Partition1x3<value_type> norm_part1x3(1); |
| 83 |
|
| 84 |
// loop size |
| 85 |
const int min_mn = m < n ? m : n; |
| 86 |
|
| 87 |
// workspace (norm and householder application, 2*max(m,n) is needed) |
| 88 |
value_type *norm = w; |
| 89 |
w += n; |
| 90 |
|
| 91 |
// initial partition of A where ATL has a zero dimension |
| 92 |
A_part2x2.partWithATL(A, m, n, 0, 0); |
| 93 |
t_part2x1.partWithAT(t, min_mn, 0); |
| 94 |
|
| 95 |
p_part1x2.partWithAL(p, n, 0); |
| 96 |
norm_part1x2.partWithAL(norm, n, 0); |
| 97 |
|
| 98 |
// compute initial column norms (replaced by dot product) |
| 99 |
TeamVectorDotInternal::invoke(member, m, n, A, as0, as1, A, as0, as1, norm, 1); |
| 100 |
member.team_barrier(); |
| 101 |
|
| 102 |
const bool finish_when_rank_found = (matrix_rank == -1); |
| 103 |
|
| 104 |
matrix_rank = min_mn; |
| 105 |
value_type max_diag(0); |
| 106 |
for (int m_atl = 0; m_atl < min_mn; ++m_atl) { |
| 107 |
const int n_AR = n - m_atl; |
| 108 |
|
| 109 |
// part 2x2 into 3x3 |
| 110 |
A_part3x3.partWithABR(A_part2x2, 1, 1); |
| 111 |
const int m_A22 = m - m_atl - 1; |
| 112 |
const int n_A22 = n - m_atl - 1; |
| 113 |
|
| 114 |
t_part3x1.partWithAB(t_part2x1, 1); |
| 115 |
value_type *tau = t_part3x1.A1; |
| 116 |
|
| 117 |
p_part1x3.partWithAR(p_part1x2, 1); |
| 118 |
int_type *pividx = p_part1x3.A1; |
| 119 |
|
| 120 |
norm_part1x3.partWithAR(norm_part1x2, 1); |
| 121 |
|
| 122 |
/// ----------------------------------------------------- |
| 123 |
// find max location |
| 124 |
TeamVectorFindAmaxInternal::invoke(member, n_AR, norm_part1x2.AR, 1, pividx); |
| 125 |
member.team_barrier(); |
| 126 |
|
| 127 |
// apply pivot |
| 128 |
TeamVectorApplyPivotVectorForwardInternal::invoke(member, *pividx, norm_part1x2.AR, 1); |
| 129 |
TeamVectorApplyPivotMatrixForwardInternal::invoke(member, m, *pividx, A_part2x2.ATR, as1, as0); |
| 130 |
member.team_barrier(); |
| 131 |
|
| 132 |
// perform householder transformation |
| 133 |
TeamVectorLeftHouseholderInternal::invoke(member, m_A22, A_part3x3.A11, A_part3x3.A21, as0, tau); |
| 134 |
member.team_barrier(); |
| 135 |
|
| 136 |
// left apply householder to A22 |
| 137 |
TeamVectorApplyLeftHouseholderInternal::invoke(member, m_A22, n_A22, tau, A_part3x3.A21, as0, A_part3x3.A12, as1, |
| 138 |
A_part3x3.A22, as0, as1, w); |
| 139 |
member.team_barrier(); |
| 140 |
|
| 141 |
// break condition |
| 142 |
if (matrix_rank == min_mn) { |
| 143 |
if (m_atl == 0) max_diag = ats::abs(A[0]); |
| 144 |
const value_type val_diag = ats::abs(A_part3x3.A11[0]), threshold(10 * max_diag * ats::epsilon()); |
| 145 |
if (val_diag < threshold) { |
| 146 |
matrix_rank = m_atl; |
| 147 |
if (finish_when_rank_found) break; |
| 148 |
} |
| 149 |
} |
| 150 |
|
| 151 |
// norm update |
| 152 |
TeamVectorUpdateColumnNormsInternal::invoke(member, n_A22, A_part3x3.A12, as1, norm_part1x3.A2, 1); |
| 153 |
member.team_barrier(); |
| 154 |
/// ----------------------------------------------------- |
| 155 |
A_part2x2.mergeToATL(A_part3x3); |
| 156 |
t_part2x1.mergeToAT(t_part3x1); |
| 157 |
p_part1x2.mergeToAL(p_part1x3); |
| 158 |
norm_part1x2.mergeToAL(norm_part1x3); |
| 159 |
} |
| 160 |
|
| 161 |
return 0; |
| 162 |
} |
| 163 |
}; |
| 164 |
|
| 165 |
} // end namespace KokkosBatched |
| 166 |
|
| 167 |
#endif |