Sparse Operations | NumKong for C++

Sparse helpers cover sorted-index intersection and weighted sparse dot products.

nk_u32_t a_idx[] = {1, 3, 5, 7}, b_idx[] = {3, 4, 5, 8};
nk_u32_t intersection[4];
nk_size_t count = 0;
nk_sparse_intersect_u32_best(a_idx, b_idx, 4, 4, intersection, &count, capabilities, NULL);
assert(count == 2 && "indices 3 and 5");

nk_f32_t a_weights[] = {1.0f, 2.0f, 3.0f, 4.0f};
nk_f32_t b_weights[] = {5.0f, 6.0f, 7.0f, 8.0f};
nk_f64_t result = 0;
nk_sparse_dot_u32f32_best(a_idx, b_idx, a_weights, b_weights, 4, 4, &result, capabilities, NULL);
assert(result > 0 && "weighted dot over shared indices");

This family deserves explicit mention because it is not just sparse dot. Set intersection itself is often the workload.

API

Functions

sparse_intersectCount intersection of two sorted index arrays.

sparse.hpp:33 ↗

template <numeric_dtype index_type_>
status_t sparse_intersect(
    index_type_ const *a,
    index_type_ const *b,
    std::size_t a_length,
    std::size_t b_length,
    index_type_ *result,
    std::size_t *count,
    nk_capability_t capabilities = default_capabilities(),
    nk_stream_t stream = nullptr) noexcept;

template <numeric_dtype index_type_, vector_of<index_type_> a_type_, vector_of<index_type_> b_type_>
expected<std::size_t> sparse_intersect(
    a_type_ const & a,
    b_type_ const & b,
    nk_capability_t capabilities = default_capabilities()) noexcept;

Counts the indices two sorted index runs share; unexpected_dimensions_k for a strided run or one ending mid-value.

Parameters

`a`	in	First sorted index array (ascending, unique elements)
`b`	in	Second sorted index array (ascending, unique elements)
`a_length`	in	Number of elements in `a`
`b_length`	in	Number of elements in `b`
`result`	out	Optional buffer for matches, at least min( `a_length`, `b_length`) long
`count`	out	Output intersection count
`capabilities`	in	Capabilities to pick from, or zero for the C++ template
`stream`	in	Null on the CPU, or the stream of the device `capabilities` describes

sparse_dotSparse weighted dot product: Σ aₖ × bₖ over shared indices.

sparse.hpp:92 ↗

template <numeric_dtype index_type_, numeric_dtype weight_t, numeric_dtype result_type_ = typename weight_t::dot_result_t>
status_t sparse_dot(
    index_type_ const *a,
    index_type_ const *b,
    weight_t const *a_weights,
    weight_t const *b_weights,
    std::size_t a_length,
    std::size_t b_length,
    result_type_ *product,
    nk_capability_t capabilities = default_capabilities(),
    nk_stream_t stream = nullptr) noexcept;

template <numeric_dtype index_type_, numeric_dtype weight_t, numeric_dtype result_type_ = typename weight_t::dot_result_t, vector_of<index_type_> a_type_, vector_of<index_type_> b_type_, vector_of<weight_t> a_weights_type_, vector_of<weight_t> b_weights_type_>
expected<result_type_> sparse_dot(
    a_type_ const & a,
    b_type_ const & b,
    a_weights_type_ const & a_weights,
    b_weights_type_ const & b_weights,
    nk_capability_t capabilities = default_capabilities()) noexcept;

Σ of weight products over the indices two sorted runs share; unexpected_dimensions_k when a weight run's size differs from its index run's, or any run is strided or ends mid-value.

Parameters

`a`	in	First sorted index array (ascending, unique elements)
`b`	in	Second sorted index array (ascending, unique elements)
`a_weights`	in	Weights corresponding to indices of `a`
`b_weights`	in	Weights corresponding to indices of `b`
`a_length`	in	Number of elements in `a`
`b_length`	in	Number of elements in `b`
`product`	out	Output dot product
`capabilities`	in	Capabilities to pick from, or zero for the C++ template
`stream`	in	Null on the CPU, or the stream of the device `capabilities` describes

Notes

Computes sum of a_weights[i] * b_weights[j] for all i,j where a[i] == b[j]