# Sparse Operations

> NumKong for C++

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

```c
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.

`#include <numkong/sparse.hpp>`

## sparse_intersect

Count intersection of two sorted index arrays.

```cpp
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;
```

```cpp
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`](https://www.unum.cloud/docs/numkong/cpp/quickstart.md#unexpected_dimensions_k) for a strided run or one ending mid-value.

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

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

```cpp
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;
```

```cpp
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`](https://www.unum.cloud/docs/numkong/cpp/quickstart.md#unexpected_dimensions_k) when a weight run's size differs from its index run's, or any run is strided or ends mid-value.

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