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

nk_sparse_intersect_*_best× 3Set intersection between two sorted u16 arrays.

sparse.h:114 ↗

nk_status_t nk_sparse_intersect_u16_best(
    nk_u16_t const *a,
    nk_u16_t const *b,
    nk_size_t a_length,
    nk_size_t b_length,
    nk_u16_t *result,
    nk_size_t *count,
    nk_capability_t capabilities,
    nk_stream_t stream);

Symbol	`a, b, result`	Backends
`nk_sparse_intersect_u16_best`	`nk_u16_t`	6
`nk_sparse_intersect_u32_best`	`nk_u32_t`	6
`nk_sparse_intersect_u64_best`	`nk_u64_t`	6

Backends

nk_sparse_intersect_u16serialneonsve2icelakehaswellturin
nk_sparse_intersect_u32serialneonsve2icelakehaswellturin
nk_sparse_intersect_u64serialneonsve2icelakehaswellturin

Parameters

`a`	in	The first sorted array of indices.
`b`	in	The second sorted array of indices.
`a_length`	in	The number of elements in the first array.
`b_length`	in	The number of elements in the second array.
`result`	out	Output buffer for intersection elements, or NULL to count only.
`count`	out	The output intersection count.
`capabilities`	in	One device's capabilities, like `nk_cpu_capabilities_enabled` reports.
`stream`	in	Null on the CPU, or the GPU stream of that device to queue on.

Notes

Inputs must be sorted in ascending order and contain unique elements.

Statuses

nk_missing_kernel_k No capability in capabilities has it.

nk_sparse_dot_u16bf16_bestSparse dot-product over u16 indices with bf16 weights.

sparse.h:178 ↗

nk_status_t nk_sparse_dot_u16bf16_best(
    nk_u16_t const *a,
    nk_u16_t const *b,
    nk_bf16_t const *a_weights,
    nk_bf16_t const *b_weights,
    nk_size_t a_length,
    nk_size_t b_length,
    nk_f32_t *product,
    nk_capability_t capabilities,
    nk_stream_t stream);

Backends

nk_sparse_dot_u16bf16serialneonsve2turin

Parameters

`a`	in	The first sorted array of indices.
`b`	in	The second sorted array of indices.
`a_weights`	in	The bf16 weights for the first array.
`b_weights`	in	The bf16 weights for the second array.
`a_length`	in	The number of elements in the first array.
`b_length`	in	The number of elements in the second array.
`product`	out	The output dot product.
`capabilities`	in	One device's capabilities, like `nk_cpu_capabilities_enabled` reports.
`stream`	in	Null on the CPU, or the GPU stream of that device to queue on.

Notes

Inputs must be sorted in ascending order and contain unique elements.

Statuses

nk_missing_kernel_k No capability in capabilities has it.

nk_sparse_dot_u32f32_bestSparse dot-product over u32 indices with f32 weights.

sparse.h:200 ↗

nk_status_t nk_sparse_dot_u32f32_best(
    nk_u32_t const *a,
    nk_u32_t const *b,
    nk_f32_t const *a_weights,
    nk_f32_t const *b_weights,
    nk_size_t a_length,
    nk_size_t b_length,
    nk_f64_t *product,
    nk_capability_t capabilities,
    nk_stream_t stream);

Backends

nk_sparse_dot_u32f32serialneonsve2icelakehaswellturin

Parameters

`a`	in	The first sorted array of indices.
`b`	in	The second sorted array of indices.
`a_weights`	in	The f32 weights for the first array.
`b_weights`	in	The f32 weights for the second array.
`a_length`	in	The number of elements in the first array.
`b_length`	in	The number of elements in the second array.
`product`	out	The output dot product.
`capabilities`	in	One device's capabilities, like `nk_cpu_capabilities_enabled` reports.
`stream`	in	Null on the CPU, or the GPU stream of that device to queue on.

Notes

Inputs must be sorted in ascending order and contain unique elements.

Statuses

nk_missing_kernel_k No capability in capabilities has it.

nk_sparse_dot_output_dtypeReturns the output dtype for sparse dot products.

sparse.h:333 ↗

nk_dtype_t nk_sparse_dot_output_dtype(nk_dtype_t dtype);

nk_sparse_dot_error_boundReturns the error bound of sparse dot products, per nk_accumulation_error_bound of their output.

sparse.h:343 ↗

nk_f64_t nk_sparse_dot_error_bound(nk_dtype_t dtype);

nk_sparse_find_kernelFinds the sparse kernel of kind for dtype, from the best of capabilities.

sparse.h:359 ↗

nk_status_t nk_sparse_find_kernel(
    nk_kernel_kind_t kind,
    nk_dtype_t dtype,
    nk_capability_t capabilities,
    nk_kernel_punned_t *kernel,
    nk_capability_t *capability);

Parameters

`kind`	in	The verb whose kernel to find.
`dtype`	in	The input type the kernel reads.
`capabilities`	in	The mask to pick the best capability from.
`kernel`	out	The kernel, or null when none of `capabilities` has it.
`capability`	out	The capability the kernel belongs to, or zero.

Statuses

nk_missing_kernel_k
nk_missing_library_k Header-only.