Coordinate-aligned sparse algebra

Sparse algebra combines tensors by coordinate values. The row index is an ordering detail; the coordinate row is the key.

Join model

Let \(A\) and \(B\) be coordinate sets. The supported joins are:

\[A_{\text{inner}} = A \cap B,\qquad A_{\text{outer}} = A \cup B,\]
\[A_{\text{left}} = A,\qquad A_{\text{right}} = B.\]

The alignment result stores output coordinates plus gather rows for both operands. Missing rows are encoded as -1 and filled by the operation.

Operation defaults

Operation

Default join

Reason

sparse_add

outer

Preserve contributions from either side.

sparse_sub

outer

Preserve left-only and right-only support with fill values.

sparse_mul

inner

Multiplication is usually meaningful only where both sides exist.

sparse_maximum / sparse_minimum

inner

Avoid introducing filled comparison values by default.

cat

inner

Concatenate feature channels on shared support unless a join is supplied.

Operator shortcuts

SparseTensor defines shortcuts for the common defaults:

  • x + y uses sparse_add with an outer join;

  • x - y uses sparse_sub with an outer join;

  • x * y and x & y use sparse_mul with an inner join.

Use the named functions when a branch merge requires explicit left, right, or custom fill semantics.

Identity fast path

If two tensors share coordinate identity, algebra can operate directly on features:

\[Z_i = f(X_i, Y_i).\]

If identity differs, alignment builds gather maps:

\[Z_j = f(X_{\ell_j}, Y_{r_j}),\]

where \(\ell_j\) and \(r_j\) may be missing-row sentinels.

Row-changing utilities

prune, prune_mask, crop, and topk_rows produce row subsets. They must transform coordinates, features, active-row metadata, and coordinate identity together. replace_feature is the feature-only counterpart and preserves coordinate identity when row count is unchanged.

Pruning keeps caller row order and carries declared per-batch counts forward, including empty batches. A mask may only select active sparse rows.

reindex_sparse(source, target) is the exact-support counterpart to a join. It preserves target row order and coordinate identity, discards source-only rows, and fills target-only rows. Use it when a decoder branch must return to a known geometry rather than relying on an incidental coordinate ordering.

Collation

sparse_collate accepts unbatched (N,3) coordinate arrays, prepends a batch column, concatenates features, and records batch_counts. This is the preferred entry point for building a batched sparse tensor from individual samples.

Use duplicate_reduction='mean' in sparse_collate or sparse_from_coordinates when input coordinates may repeat. It performs an unweighted feature mean for each exact integer coordinate, matching MinkowskiEngine’s UNWEIGHTED_AVERAGE construction mode. The default 'none' path assumes the caller already provides unique support. Reduced coordinates retain their first-occurrence order.