| 1 |
/* |
| 2 |
* (C) Crown Copyright 2025 Met Office |
| 3 |
* |
| 4 |
* This software is licensed under the terms of the Apache Licence Version 2.0 |
| 5 |
* which can be obtained at http://www.apache.org/licenses/LICENSE-2.0. |
| 6 |
*/ |
| 7 |
|
| 8 |
#pragma once |
| 9 |
|
| 10 |
#include <algorithm> |
| 11 |
#include <cstring> |
| 12 |
#include <memory> |
| 13 |
#include <tuple> |
| 14 |
#include <type_traits> |
| 15 |
#include <vector> |
| 16 |
|
| 17 |
#include "atlas/linalg/sparse/SparseMatrixStorage.h" |
| 18 |
#include "atlas/linalg/sparse/SparseMatrixView.h" |
| 19 |
|
| 20 |
namespace atlas::linalg { |
| 21 |
|
| 22 |
/// @brief A triplet which represents a non-zero entry in a sparse matrix. |
| 23 |
template <typename Value, typename Index> |
| 24 |
class Triplet { |
| 25 |
static_assert(std::is_integral_v<Index>, "Index must be an integral type"); |
| 26 |
|
| 27 |
public: |
| 28 |
Triplet() = default; |
| 29 |
Triplet(Index row, Index column, Value value): row_{row}, column_{column}, value_{value} {} |
| 30 |
Index row() const { return row_; } |
| 31 |
Index col() const { return column_; } |
| 32 |
Value value() const { return value_; } |
| 33 |
|
| 34 |
/// @brief Less-than operator for sorting triplets. |
| 35 |
bool operator<(const Triplet& other) const { return std::tie(row_, column_) < std::tie(other.row_, other.column_); } |
| 36 |
|
| 37 |
private: |
| 38 |
Index row_{}; |
| 39 |
Index column_{}; |
| 40 |
Value value_{}; |
| 41 |
}; |
| 42 |
|
| 43 |
namespace detail { |
| 44 |
// SFINAE types/variables in place of C++20 concepts. |
| 45 |
template <typename T> |
| 46 |
struct is_triplet : std::false_type {}; |
| 47 |
|
| 48 |
template <typename Value, typename Index> |
| 49 |
struct is_triplet<Triplet<Value, Index>> : std::true_type {}; |
| 50 |
|
| 51 |
template <typename Iter> |
| 52 |
constexpr bool is_triplet_iterator = is_triplet<typename std::iterator_traits<Iter>::value_type>::value; |
| 53 |
|
| 54 |
template <typename Iter> |
| 55 |
constexpr bool is_random_access_iterator = |
| 56 |
std::is_base_of_v<typename std::iterator_traits<Iter>::iterator_category, std::random_access_iterator_tag>; |
| 57 |
|
| 58 |
template <typename Iter> |
| 59 |
constexpr bool is_mutable_iterator = |
| 60 |
!std::is_const_v<typename std::remove_reference_t<typename std::iterator_traits<Iter>::reference>>; |
| 61 |
|
| 62 |
template <typename Iter> |
| 63 |
constexpr bool is_sortable_iterator = is_random_access_iterator<Iter> && is_mutable_iterator<Iter>; |
| 64 |
} // namespace detail |
| 65 |
|
| 66 |
/// @brief Construct a SparseMatrixStorage from a range of triplets. |
| 67 |
template <typename Iter> |
| 68 |
std::enable_if_t<detail::is_triplet_iterator<Iter>, SparseMatrixStorage> make_sparse_matrix_storage_from_triplets( |
| 69 |
std::size_t n_rows, std::size_t n_cols, Iter triplets_begin, Iter triplets_end) { |
| 70 |
using TripletType = typename std::iterator_traits<Iter>::value_type; |
| 71 |
using Index = decltype(std::declval<TripletType>().row()); |
| 72 |
using Value = decltype(std::declval<TripletType>().value()); |
| 73 |
|
| 74 |
const std::size_t n_non_zero = std::distance(triplets_begin, triplets_end); |
| 75 |
auto outer_array = std::unique_ptr<array::Array>(array::Array::create<Index>(n_rows + 1)); |
| 76 |
auto inner_array = std::unique_ptr<array::Array>(array::Array::create<Index>(n_non_zero)); |
| 77 |
auto values_array = std::unique_ptr<array::Array>(array::Array::create<Value>(n_non_zero)); |
| 78 |
auto outer_view = array::make_view<Index, 1>(*outer_array); |
| 79 |
auto inner_view = array::make_view<Index, 1>(*inner_array); |
| 80 |
auto values_view = array::make_view<Value, 1>(*values_array); |
| 81 |
|
| 82 |
std::size_t index = 0; |
| 83 |
Iter triplet_iter = triplets_begin; |
| 84 |
TripletType previous_triplet = *triplet_iter; |
| 85 |
for (std::size_t row = 0; row < n_rows; ++row) { |
| 86 |
outer_view(row) = index; |
| 87 |
for (; triplet_iter != triplets_end && triplet_iter->row() == static_cast<Index>(row); |
| 88 |
++index, ++triplet_iter) { |
| 89 |
ATLAS_ASSERT(!(triplet_iter->row() < previous_triplet.row()), "Triplets must be sorted per row."); |
| 90 |
ATLAS_ASSERT(static_cast<std::size_t>(triplet_iter->col()) < n_cols, "Triplet column index out of bounds."); |
| 91 |
inner_view(index) = triplet_iter->col(); |
| 92 |
values_view(index) = triplet_iter->value(); |
| 93 |
previous_triplet = *triplet_iter; |
| 94 |
} |
| 95 |
} |
| 96 |
ATLAS_ASSERT(index == n_non_zero, "Triplet row index out of bounds."); |
| 97 |
outer_view(n_rows) = n_non_zero; |
| 98 |
|
| 99 |
return SparseMatrixStorage::make(n_rows, n_cols, n_non_zero, std::move(values_array), std::move(inner_array), |
| 100 |
std::move(outer_array), std::any()); |
| 101 |
} |
| 102 |
|
| 103 |
/// @brief Construct a SparseMatrixStorage from a random-access range of triplets, sorting if necessary. |
| 104 |
template <typename Iter> |
| 105 |
std::enable_if_t<detail::is_triplet_iterator<Iter> && detail::is_sortable_iterator<Iter>, SparseMatrixStorage> |
| 106 |
make_sparse_matrix_storage_from_triplets(std::size_t n_rows, std::size_t n_cols, std::size_t n_non_zero, |
| 107 |
Iter triplets_begin, bool is_sorted = false) { |
| 108 |
if (!is_sorted) { |
| 109 |
std::sort(triplets_begin, triplets_begin + n_non_zero); |
| 110 |
} |
| 111 |
return make_sparse_matrix_storage_from_triplets(n_rows, n_cols, triplets_begin, triplets_begin + n_non_zero); |
| 112 |
} |
| 113 |
|
| 114 |
/// @brief Construct a SparseMatrixStorage from a vector of triplets, sorting if necessary. |
| 115 |
template <typename Value, typename Index> |
| 116 |
SparseMatrixStorage make_sparse_matrix_storage_from_triplets(std::size_t n_rows, std::size_t n_cols, |
| 117 |
std::vector<Triplet<Value, Index>>& triplets, |
| 118 |
bool is_sorted = false) { |
| 119 |
return make_sparse_matrix_storage_from_triplets(n_rows, n_cols, triplets.size(), triplets.begin(), is_sorted); |
| 120 |
} |
| 121 |
|
| 122 |
/// @brief For-each iteration over all non-zero triplets in row. |
| 123 |
template <typename Value, typename Index, typename Functor> |
| 124 |
std::enable_if_t<std::is_invocable_v<Functor, Index, Index, Value>> sparse_matrix_for_each_row( |
| 125 |
std::size_t row, const SparseMatrixView<Value, Index>& matrix, Functor&& functor) { |
| 126 |
const Index* outer = matrix.outer(); |
| 127 |
const Index* inner = matrix.inner(); |
| 128 |
const Value* values = matrix.value(); |
| 129 |
|
| 130 |
for (Index index = outer[row]; index < outer[row + 1]; ++index) { |
| 131 |
const Index column = inner[index]; |
| 132 |
const Value value = values[index]; |
| 133 |
functor(static_cast<Index>(row), column, value); |
| 134 |
} |
| 135 |
} |
| 136 |
|
| 137 |
/// @brief For-each iteration over all non-zero triplets in matrix. |
| 138 |
template <typename Value, typename Index, typename Functor> |
| 139 |
std::enable_if_t<std::is_invocable_v<Functor, Index, Index, Value>> sparse_matrix_for_each( |
| 140 |
const SparseMatrixView<Value, Index>& matrix, Functor&& functor) { |
| 141 |
for (std::size_t row = 0; row < matrix.rows(); ++row) { |
| 142 |
sparse_matrix_for_each_row(row, matrix, functor); |
| 143 |
} |
| 144 |
} |
| 145 |
|
| 146 |
} // namespace atlas::linalg |