GV

GeezerVison

The World Wide Web, restored to 800 pixels of glory.

Home|About|Gaming cabinet|Archives|How it works|Starter sites

On this site

  • Sign in
  • ActionsCI/CD and automation
  • CodespacesCloud development environments
  • All Features
  • Documentation
  • Training
  • Certifications
  • Build with Copilot
  • Customize Copilot
  • Integrations
  • Trending repos
  • GitHub Sponsors
  • Developer articles
  • Enterprises

This view

  • Original page
  • New address

GeezerVison is showing github.com — Add an experimental n-dimensional Tensor (gb.Tensor, gb.einsum) by eriknw · Pull Request #651 · python-graphblas/python-graphblas

Conversation

@eriknw

@eriknw eriknw commented Oct 27, 2026 •
edited
Loading

Uh oh!

There was an error while loading. Please reload this page.

Copy link
Copy Markdown
Member

An experimental n-dimensional sparse array, gb.Tensor, and gb.einsum, built on the
existing Matrix machinery. Both are marked experimental in their docstrings and docs, and the
API may change. They need the SuiteSparse backend and SuiteSparse:GraphBLAS 10 or later (the
Container API); elsewhere a Tensor raises NotImplementedError and the Tensor tests skip.
import graphblas imports neither the Tensor nor Numba; both load on first use.

Data model. A Tensor is one Matrix, stored by row, plus a layout: an ordered partition of
the logical axes into a row group and a column group, each raveled in C order into one
dimension of the Matrix. Hypersparse storage keeps the raveled dimensions cheap. Shape
operations (permute_dims, .T, expand_dims, squeeze, and reshape where the layout
allows) change only metadata, with copy-on-write between views. An operation that needs
another layout gets it from a planner, which prices reshape, transpose, permutation and
rebuild steps and takes the cheapest sequence.

Semantics. GraphBLAS missing-value semantics (no fill value), with numpy / Array API rules
for shapes, axes and broadcasting, and python-graphblas's lazy expressions, masks,
accumulators and <<. When a Matrix, Vector, Scalar or ndarray meets a Tensor in an infix
operator, Tensor rules apply. Matrix and Vector methods still refuse a Tensor operand, with a
hint.

What it covers

  • construction and conversion: from_coo, from_dense, from and to Matrix and Vector, and
    pydata/sparse and scipy n-d arrays in both directions (n-d scipy arrays need scipy 1.15);
  • element-wise operations with broadcasting, apply, select, comparisons;
  • reductions with monoids and aggregators;
  • contractions: tensordot, matmul / @ with batch axes, einsum with any semiring, TTV,
    TTM and MTTKRP. TTM and MTTKRP have selectable engines: GraphBLAS products, generated Numba
    kernels, and an array-UDT engine that uses the SuiteSparse JIT;
  • outer indexing, index assignment, take, take_along_axis and vindex;
  • reshape / ravel / flatten, relayout, unfold.

Changes outside the Tensor, each in its own commit (candidates to split into their own PRs):

  • Core hooks. Infix operators on Matrix, Vector and Scalar return NotImplemented for a
    Tensor operand, so Python tries the Tensor's reflected operator. Masks combine across kinds.
    Operator calls (binary.plus(A | T), unary.abs(T), agg.sum(T)) dispatch to the Tensor.
    A Tensor given to a Matrix or Vector method, as a mask of one, or to << raises with a hint.
    Core modules see the Tensor only through utils._tensor_types, which stays empty until
    graphblas.core.tensor is imported.
  • Matrix.isequal / isclose and Vector.isequal / isclose accept a Tensor.
  • The gb.Tensor and gb.einsum exports (lazy, as for Matrix, Vector and Scalar), and a
    tensor_max_expansion config key (default 1e9 entries): a broadcast in a union that would
    expand past it raises unless called with allow_expansion=True.
  • CI: the notebook job runs the Tensor notebooks only on SuiteSparse:GraphBLAS 10 or later.

Two changes that began in this PR now live in #652, below it: JIT C definitions for lifted ops on
a scalar and a UDT or on two UDT types (the Tensor's array-UDT engine uses them), and
ss.fix_jit_config finding a conda compiler on Windows.

Also here: a user-guide page (docs/user_guide/tensor.rst, with doctested examples) and the
API reference; ai-notes/, a new directory of curated notes for contributors and reviewers
(design, decisions, verification, limitations and roadmap, benchmarks, and a SuiteSparse
wishlist); asv benchmarks (benchmarks/tensor_ops.py); a portable comparison kit
(scripts/tensor_bench/: pydata/sparse, scipy, torch and Numba, plus optional SPLATT, TACO and
Finch builds); and two notebooks.

Where to start reviewing. The user-guide page shows the API. ai-notes/tensor/design.md
explains the data model, the planner and the engines, and has a map of the modules. The parts
that deserve the hardest look:

  • copy-on-write between O(1) views (_Owners, _Store in tensor.py);
  • the Container surgery in tensor_layout.py, which edits SuiteSparse's arrays in place;
  • arrays from the Numba kernels handed to SuiteSparse without a check (matrix_from_arrays),
    and, with suitesparse-graphblas before 10.5.1.1, handed over by utils._give_buffer's
    fallback, which follows the ss pack methods;
  • the planner's cost constants, fitted on one machine (an Apple M5 Pro).

Verification. The unit tests compare with dense numpy throughout (test_tensor.py,
test_tensor_io.py). Randomized oracles, each with a check that a planted error is caught, run
as slow tests (test_tensor_oracles.py, --runslow). ai-notes/tensor/verification.md has
the recipes for running without Numba and with the JIT off.

Local runs (macOS arm64, --runslow, cold JIT and kernel caches) found five problems that CI
would have hit, and CI's first runs found more: scipy before 1.15 (no n-d arrays) and before
1.13 (no coords), pydata/sparse 0.14, a test that checked the wrong backend, a CI draw with no
Numba, Windows' 32-bit default int in doctest output, and a dataset whose server rebuilt its
zip. The branch's last commits, from "Tensor tests: skip the Numba tests on any ImportError" on,
fix them, and CI is green. With those commits, these pass locally: the full suite
with suitesparse-graphblas 10.5.1.1 and with 10.3.1.0, each also with CI's C-scalar second
pass; the full suite without Numba, on both backends; the Tensor modules with the JIT off;
Python 3.11 with numpy 1.24 and no C compiler; scipy 1.13 with pydata/sparse 0.14; the Tensor modules in two shuffled orders; the
user guide's doctests; the Quickstart notebook; and pre-commit run --all-files. Three tests
from the base branch fail in some of those environments, as they do without this PR (one with
the JIT forced off, one with no C compiler, one without installed package metadata). The
oracles take about 90 s with cold caches here, and the Tensor modules about 4.5 minutes of an
11-minute run. Not run locally: Linux, Windows, x86, and SuiteSparse:GraphBLAS before 10 (CI covers them). On
CI's slowest runner (macos-15-intel) the Tensor modules take about 20-35 minutes, mostly Numba and
JIT compiles.

Review and coverage since the first CI runs. An adversarial review looked for what CI and the
oracles miss and found 18 issues: crashes (take_along_axis over a broadcast size-1 axis read out
of bounds; Container work on a Matrix with pending work; Numba kernels with 64-bit row pointers),
wrong results (C << T.T when C shares T's storage; reductions of an empty region of an iso
Tensor, from a long-standing SuiteSparse bug that Matrix also has; einsum and MTTKRP regrouping
with non-distributive or non-commutative semirings; broadcast integer pow), shapes past 2^60 and
2^63 positions (broadcasting, TTV, extraction and gather costs), and smaller API gaps (-T,
abs(T), ~T, string select, GCXS with repeated columns, a C-name collision with a user UDT).
Each fix has a regression test that fails before it, and the oracles now draw the cases they
missed. A second review, by an agent that wrote none of the fixes, checked them (all correct; its
notes are fixed in the last commits). A coverage pass then brought the Tensor's source lines to
about 99.8% covered locally (over the suitesparse, no-Numba, JIT-off and vanilla runs), with tests
first, 17 unreachable branches removed, and pragmas only on the Numba kernels' definitions and two
safety guards. A performance round followed (each change reviewed the same way): extraction is priced
by the rows it visits, a row becomes a Vector without an extract, a column range of sparse rows
is filtered without an extract, one planner search prices many targets (a new 5-d MTTKRP shape
plans in 12 ms, not 163), and unsigned sums use a precompiled kernel. Uber's slices went from
0.52x to 1.19x of the fastest of pydata/sparse, scipy and torch at 1 thread (1.68x at 8). Two
choices from it are recorded in ai-notes/tensor/decisions.md (24, 25): wait() keeps
building SuiteSparse's row hash, as Matrix.wait does (wait("complete") defers it), and
there are no per-mode copies for TTM; an explicit relayout() before a loop does that job.

Not tested yet, and known gaps (ai-notes/tensor/limitations-and-roadmap.md): before this
PR's CI, the Tensor had run only on macOS (arm64) with SuiteSparse:GraphBLAS 10.5.1 and 10.3.1,
so Linux, Windows and other SuiteSparse versions are new to it; the planner's constants are unmeasured on x86;
TTM over axes off the stored order is 2-7x behind TACO, which keeps a copy per mode. The
comparisons with pydata/sparse, scipy, torch, SPLATT, TACO and Finch are in
ai-notes/tensor/benchmarks.md.

History. The commits are the development history, kept as written. This repository's squash
merge puts every commit message into the merge commit by default, so the merge message wants
replacing with a summary.

🤖 Generated with Claude Code

Sorry, something went wrong.

Uh oh!

There was an error while loading. Please reload this page.

rtbs-dev reacted with hooray emoji
All reactions
  • 🎉 1 reaction
@eriknw
eriknw added this pull request to stack #650 October 27, 2026 04:30
@codecov

codecov Bot commented Oct 27, 2026 •
edited
Loading

Uh oh!

There was an error while loading. Please reload this page.

Copy link
Copy Markdown

Codecov Report

❌ Patch coverage is 99.29101% with 43 lines in your changes missing coverage. Please review.
✅ Project coverage is 99.34%. Comparing base (bc9c687) to head (fd813a2).

Additional details and impacted files
@@                 Coverage Diff                 @@
##           57-udt-cleanups     #651      +/-   ##
===================================================
- Coverage            99.43%   99.34%   -0.10%     
===================================================
  Files                  109      125      +16     
  Lines                35806    46932   +11126     
  Branches              4083     5556    +1473     
===================================================
+ Hits                 35605    46623   +11018     
- Misses                 117      186      +69     
- Partials                84      123      +39     
🚀 New features to boost your workflow:
  • ❄️ Test Analytics: Detect flaky tests, report on failures, and find test suite problems.
All reactions

Sorry, something went wrong.

Uh oh!

There was an error while loading. Please reload this page.

@eriknw
eriknw force-pushed the 50-tensor branch from cda7f58 to dff2457 Compare October 28, 2026 04:29
@eriknw
eriknw removed this pull request from stack #650 October 28, 2026 04:29
@eriknw eriknw mentioned this pull request Oct 28, 2026
Set the SuiteSparse JIT control from config, and JIT-compile lifted UDT ops on mixed operand types #652
Merged
@eriknw
eriknw added this pull request to stack #653 October 28, 2026 04:30
@eriknw
eriknw removed this pull request from stack #653 October 28, 2026 04:31
@eriknw
eriknw added this pull request to stack #655 October 28, 2026 04:32
@eriknw
eriknw removed this pull request from stack #655 October 28, 2026 04:33
@eriknw eriknw mentioned this pull request Oct 28, 2026
Test what main's coverage misses, and exclude what no input reaches #656
Open
@eriknw
eriknw changed the base branch from 16-asv-benchmarks to 51-coverage-main-gaps October 28, 2026 04:33
@eriknw
eriknw added this pull request to stack #657 October 28, 2026 04:33
@eriknw
eriknw force-pushed the 50-tensor branch from 3e322d4 to 6275ed1 Compare October 28, 2026 13:21
@eriknw eriknw mentioned this pull request Oct 28, 2026
Add Python 3.15; routine maintenance; zizmor in pre-commit and CI #636
Merged
@eriknw
eriknw force-pushed the 50-tensor branch from c59e717 to 6f0ebd6 Compare October 29, 2026 02:01
@eriknw
eriknw force-pushed the 50-tensor branch 2 times, most recently from feb51aa to baa3b46 Compare November 3, 2026 16:44
@eriknw
eriknw removed this pull request from stack #657 November 3, 2026 16:44
@eriknw
eriknw changed the base branch from 51-coverage-main-gaps to 54-jit-on-windows-cmake November 3, 2026 16:44
@eriknw
eriknw added this pull request to stack #660 November 3, 2026 16:45
@eriknw
eriknw force-pushed the 50-tensor branch from baa3b46 to 8f19f4e Compare November 3, 2026 20:07
@eriknw
eriknw removed this pull request from stack #660 November 3, 2026 23:09
@eriknw
eriknw force-pushed the 50-tensor branch from 8f19f4e to 38ad1e7 Compare November 3, 2026 23:09
@eriknw
eriknw added this pull request to stack #662 November 3, 2026 23:09
eriknw added 29 commits November 12, 2026 11:25
@eriknw
ai-notes: the row hash that the Tensor's internal waits build, as a r…
01af497
…oadmap idea

The perf round found that the Tensor's operations finish their operands with wait()
(materialize) before Container work, which also builds SuiteSparse's hyper hash of a
hypersparse Matrix's rows, even where the operation would not use it (SuiteSparse's own
extract of a short row list does not build it). On NELL-2's TTM output that hash is
0.68-0.97 s at 1 thread and 86-116 ms at 8 (about 45 ns a row), and after
wait("complete") a 1-3 ms row extract took 0.68-0.96 s because its own wait built it.
Internal waits cannot use "complete", which does no work at all, since Container work needs
pending work finished (stored_format). limitations-and-roadmap.md now lists this as a known
performance gap with those numbers and the idea of a per-Matrix GxB_HYPER_HASH setting
around the wait (with the caveat that GB_wait frees an existing hash while it is off), and
adds it to the performance item of the roadmap. No code change.
@eriknw
Tensor: X | Y and X & Y on their own follow Matrix: BOOL only
0672309
On non-BOOL Tensors, (X | Y).new() and (X & Y).new() computed the default operator (plus,
times), where Matrix raises "Bad dtypes for `x | y`!"; and the other ways of using the
expression on its own fared differently: C << (X | Y) refused (de6bd07), while passing it
to a method, using it as an operand or calling to_dense raised AttributeError ("no
attribute '_shape'"), BOOL included. The coordinator decided (on Erik's instruction) to
align with Matrix: the user guide says infix operators work "as for Matrix"; with numpy,
| on integers is bitwise or and on floats raises, so computing plus surprises; + and *
already give plus and times; and nothing recorded a reason for the old default.

- _TensorEwiseInfixExpr._to_expr gives lor / land on BOOL and raises Matrix's own "Bad
  dtypes" TypeError (its text, from infix._ewise_add_to_expr) for other dtypes. C << takes
  it directly (no separate _assigned).
- _compute turns an infix expression into its expression first, so as an operand (ewise,
  infix, einsum, region values through _region_value) it raises for other dtypes, and on
  BOOL it is computed with autocompute or refused with the ".new() first" hint without, as
  for Matrix.
- An infix expression forwards TensorExpression's methods (to_dense, ...), so with
  autocompute they compute on BOOL and raise for other dtypes, as Matrix's do.
- shape no longer needs the expression (the broadcast of the operands' shapes), so
  (X | Y).shape works for any dtype, as Matrix's nrows does.
- With an operator (binary.plus(X | Y), monoid.max(X & Y)) every dtype works as before.

The user guide's infix paragraph and the infix class's docstring say so, and decisions.md
records it as 27 (who, why, revisit if users ask for a default operator). The Tensor's own
code, oracles, notebooks, docs examples, benchmarks/tensor_ops.py and the benchmark kit use
| and & only on BOOL or with an operator; one test assigned (B | B) of FP64 to a region and
now checks the refusal and assigns binary.plus(B | B).

A new test checks, for FP64 and INT64, | and & refused with Matrix's message through
.new(), C <<, a region, ewise_add, +, einsum and to_dense, with autocompute off and on,
the same refusal from Matrix, shape still right, binary.plus / binary.times results against
numpy, and BOOL unchanged against Matrix.
@eriknw
Tensor: broadcast onto nonempty rows finds values by search, not a de…
4ffab66
…nse table

A broadcast ewise_mult that puts the small side on the nonempty rows of a hypersparse row
group (_bcast_mult's "diagonal rows, nonempty rows" option, _expand_on_rows) looked the
small side's values up in two dense numpy tables as long as its Vector: np.zeros(v._size)
for the values and for a presence mask. That is sized by the small side's axes, not by its
entries: for an axis of 2^40 it asks for 9 TiB. CI's Linux and Windows jobs failed so in
test_broadcast_mult_past_2_60_no_flip (Y.ewise_mult(X, pow), Y of shape (1, 2^40, 1, 1));
macOS hands out zeroed memory lazily, so it passed there.

The values are now found by a binary search of the small side's sorted indices
(tl.lookup_sorted, new): O((entries + nonempty rows) log entries), with the same results,
dtype included, and positions without a value left out as before.

The new test (test_broadcast_on_nonempty_rows_sized_by_entries) bounds the peak with
tracemalloc, which counts numpy's lazily zeroed allocations too: before the fix the peak
was 9895604665746 bytes on macOS (the test fails), after it is under 2^24.
@eriknw
Tensor: size four more paths by the entries, not by a long axis or group
3af14de
A sweep of the Tensor modules for the hazard 5fb13f9 fixed (dense numpy allocations sized
by an axis, a group, a Vector or a Matrix dimension rather than by entries), with numpy's
constructors made to refuse large sizes while operations ran on Tensors of 2^40 axes and
past 2^60 positions, found four more that a huge but sparse operand reaches:

- A broadcast ewise_mult with the small side's axes inside a wider group expanded it
  through a selector over every position of the group (tl.selector: an arange of them).
  Past 2^60 positions in total that may be the one option left, over 2^60 columns: numpy
  refuses outright ("array is too big"). A group of more positions than max(4 * nnz, 4096)
  (_perm_matrix's rule) now takes the small side onto its nonempty rows or columns
  (_expand_on_ids; tl.nonempty_col_ids, new), as a hypersparse row group already did. The
  costs are as before; the census labels the option "diagonal rows/cols, nonempty
  rows/cols".
- A TTV along an axis inside a hypersparse row group filled a dense table and a presence
  mask over the whole axis (9 TiB for 2^40). rows_selector now takes w's sorted indices and
  values and finds them by tl.lookup_sorted.
- The Numba MTTKRP kernel's owner and column-block modes fill a dense (mode x R) output
  whatever the data (only per-thread buffers were bounded): 24 TiB for a mode of 2^40 at
  R = 3. It now declines past the per-thread bound, max(R * nnz, 2^22), and the GraphBLAS
  products, sized by the entries, take it.
- take_along_axis listed every point of the broadcast shape for the gather, so indices
  that broadcast over a long axis of the Tensor listed all of it (64 TiB per coordinate
  array for 2^40). Past max(4 * (nnz + indices), 4096) points it now joins the entries
  with the indices (_along_by_entries), sized by them and the result. It also computes the
  broadcast shape itself: numpy's broadcast_shapes refuses one past 2^63 positions, which
  read as indices that do not broadcast.

The other allocations the sweep found are sized by entries, by the operands' own storage
(a sparse Matrix's row pointers, full factors), by the user's index arrays, or are
selectors priced against an option sized by the entries that always exists; the report
lists each.

Each new test bounds the peak with tracemalloc (it counts numpy's lazily zeroed
allocations) and fails before this commit on macOS: the broadcast past 2^60 by numpy's
refusal; the TTV at 9895604658905 bytes; MTTKRP at 8858887824 for a mode of 2^28 (the test
runs 2^40 after it); take_along_axis at 411238565 for an axis of 2^20 (likewise). The
broadcast and take_along_axis tests also check the new ways against numpy at moderate
sizes, forced or past their threshold.
@eriknw
Tensor: keep the cached selector where it fits, and find values witho…
ca2a8b6
…ut a search where cheap

Round 5's sweep moved broadcasts over a group wider than max(4 * nnz, 4096)
positions onto its nonempty rows or columns, and looked the small side's
values up by a binary search instead of a dense table. At ordinary sizes
both cost time:

- The wide-group limit is now max(4 * nnz, 4096, the selector cache's
  bound of 2^25). Below it the selector is shape-only and cached, so a
  repeated broadcast pays one product over the group, where the nonempty
  columns are found again on every call. Past it (and past 2^60 positions,
  the case round 5 fixed) the nonempty rows or columns run as before.
- nonempty_col_ids sorts the column indices and masks the changes instead
  of np.unique: 22 against 146-153 ms for 1e6 indices.
- The nonempty-columns option is priced per entry (C_NONEMPTY_COLS, fitted
  forced on hyper and Zipf), not by the selector's per-position price; no
  kit decision changes (320 rows, census).
- lookup_sorted indexes a full vector directly and uses a dense table while
  the vector is within max(4 * (entries + positions), 4096); the binary
  search, whose memory follows the data, runs only past that.

Against 7ebce90, interleaved, 3 reps (load 3.3-5.9; ms, 8 / 1 threads):
NELL-2 mul_vec0 39.3 -> 36.0 / 174 -> 171, mul_vec1 39.3 -> 36.2 /
177 -> 174, ttv0 86.6 -> 83.6, ttv1 74.3 -> 70.9 (1 thread within 1%).
Forced broadcast over a column group of G positions, 1e6 entries (2 reps):
G = 8-32 x nnz, 156-170 -> 6.3-20.4 (8t), 259-315 -> 18-62 (1t), the cached
selector again; G = 128 x nnz, past the cache, 161-200 -> 56 and 269-323
-> 163, by the faster distinct columns. Results are the same.

Tests pin the choices: the forced wide-group cases keep the selector under
the cache's bound and take the nonempty ids with it lowered; lookup_sorted's
three ways are checked against each other and its search's memory with
tracemalloc. The round 5 tracemalloc tests still pass.
@eriknw
Tensor: say what a GCXS export's row pointer costs
3517f55
to_pydata_sparse's docstring and the user guide now say that a "gcxs"
export holds a row pointer with one slot per position of its compressed
axes, so its memory follows the product of their lengths whatever the
entries (two compressed axes of 2^20 make 2^40 slots), and to choose
compressed_axes to keep it small; "coo" (and "dok") follow the entries.
Documented rather than refused: any threshold would be arbitrary, and the
user asked for GCXS.
@eriknw
Tensor: reshape in place past 2^31 on SuiteSparse 10.5.2
a2889b1
reshape_owned copied instead of reshaping in place past 2^31 rows or
columns because SuiteSparse 10.5.1's in-place reshape kept 32-bit
indices that cannot hold the new ones (Issue 462). 10.5.2 fixed that,
so on 10.5.2 and later it now always reshapes in place, which skips a
copy of the values; older versions still copy. Results do not change.

Checked against the library: in-place and copying reshapes of 8 shapes
crossing 2^31 or 2^32 (hypersparse and sparse, rowwise and columnwise
order) all agree with numpy on 10.5.2. On 10.5.1, 14 of the 32
in-place reshapes are wrong, and 10 columnwise copies are wrong or raise
InvalidValue, all with a dimension past 2^32.

test_reshape_owned_past_2_32 runs reshape_owned both ways where the
library allows it (copy only before 10.5.2): (4, 2^31) to (1, 2^33),
whose last entry 10.5.1 put at column 2^32 - 1.
@eriknw
Tensor: reshape notes say 2^31, as the code does; drop a no-op resize…
51cc519
… in its test

From the independent review of the SuiteSparse 10.5.2 reshape commit: the module comment said
2^32 where _RESHAPE_IN_PLACE_PAST_2_31 and reshape_owned use 2^31, and the test resized a Matrix
to the shape from_coo had already given it.
@eriknw
Tensor: size the GCXS export by its row pointer, and refuse a huge one
19062ef
to_pydata_sparse("gcxs") took the Tensor's layout when GCXS could hold it,
else the cheapest move to any layout GCXS could hold, and nothing weighed
the row pointer, which has one int64 per position of the compressed axes.
A 2-entry Tensor of shape (2, 2**30, 2**31) compressed (0, 1): a 16 GiB
pointer and a 26 GB peak, which killed GitHub's 16 GB runners. No Matrix
layout of that shape does better, since a Matrix dimension stops at 2**60
and every split has at least 2**30 groups; GCXS needs 3 slots for (0,)
because it only ravels the columns into int64.

The export now keeps a layout whose pointer is small (2**20 groups, or two
per entry, where it costs what the entries do and a move would cost more),
else moves to one, else compresses the axes with the fewest groups, building
the arrays from the sorted coordinates when no Matrix can hold that split.
compressed_axes= gets that coordinate route too, so asking for a split the
default would have picked no longer raises.

A pointer past 2**28 groups and past two per entry raises, naming "coo",
for both the default and compressed_axes=: such an array's memory follows
the shape and not the data. (2**40, 2**40) with 2 entries started an 8 TiB
allocation.
@eriknw
Tensor: make the JIT-only tests count in the pytest_jit job
3a22480
The Tensor tests that need the SuiteSparse JIT skipped without it even under
GRAPHBLAS_REQUIRE_JIT, so a pytest_jit job that had stopped compiling would
have stayed green having run none of them. Use skip_without_jit from conftest
for the TTM engine's guard and for the two scripts that report "no JIT
compiler" from a subprocess, and likewise for the oracle when the udt engine
never ran. test_ttm_engine_choice skipped its UDT half with a plain if, so it
now fails when the JIT is required.
@eriknw
Tensor: read a GCXS export back past 2^63 positions
6a56438
Past 2^63 positions in all, with columns past 2^60, from_pydata_sparse could
not read the array to_pydata_sparse had just written: no Matrix holds those
columns, so it went through pydata's asformat("coo"), and pydata cannot ravel
a shape that large. It now decodes indptr and indices itself, combining
repeated columns as the Matrix route does.

The coordinate route held two row pointers at once, bincount's and cumsum's,
for 4.4 GB at the 2**28 limit where the comment promised about 3 GiB. Summing
in place holds one, for 2.2 GB.

The to_pydata_sparse docstring said GCXS could hold these arrays, but pydata's
own tocoo, sum, indexing and transpose raise on them, so it now says so.
@eriknw
Tensor: import a GCXS whose indptr is uint64
a2abb48
pydata's GCXS.from_coo(..., idx_dtype=np.uint64) stores indptr as uint64, and
np.repeat will not take uint64 counts, so from_pydata_sparse raised TypeError
for such an array with columns past 2^60 (fb11e4fe8's decode route) or with
unsorted or repeated columns (the Matrix route, already broken before). The
counts are now cast to int64, which holds any count an indptr can have.
@eriknw
Tensor: take bool, integer and FP32 tensors into the FP64 TTM and MTT…
4ee5c57
…KRP kernels

The Numba TTM and MTTKRP kernels and the array-UDT TTM engine took only FP64
tensor values. FROSTT's count tensors load as INT64 or BOOL, so with FP64
factors (an FP64 result under plus_times) they took the GraphBLAS products:
the SAPS pilot measured CP-ALS 13-18x slower per sweep than after a cast.

They now take a tensor of any real built-in type (BOOL, INT8-64, UINT8-64,
FP32, FP64) under plus_times[FP64] with FP64 factors. The Numba kernels read
the values in their stored type (Numba compiles each kernel per type), and
the UDT engine's SuiteSparse kernel casts them as it reads them. Numba's
conversion to float64 is C's (double) cast, which is SuiteSparse's typecast,
so the results are the products'. Integer results (which wrap), complex
results, UDTs and other semirings still take the products.

Reading in place rather than casting once per call, on Uber (3.3e6 entries,
R = 10, 18 threads): an MTTKRP takes 1.7-2.1 ms for INT64, INT8 or FP64
values and 2.0-2.5 ms for BOOL, where a cast to FP64 would add 1.2-1.3 ms to
every call. A new value type compiles its kernels once (about 0.3 s each),
then loads them from the disk cache.

The pilot's reproducer: an INT64 MTTKRP over 4 modes 161.2 -> 3.5 ms, a TTM
16.3 -> 3.2 ms (FP64: 3.7 and 3.0). CP-ALS on Uber as SAPS loads it (INT64):
125.3 -> 7.5 ms per sweep, the same as after a cast to FP64 (7.6).

test_kernels_take_real_value_types runs every TTM and MTTKRP of a 4-d tensor
of each type through each engine and the products, in and out of the stored
layout and iso, and asserts the engine ran and the results are equal; for
INT64 and UINT64 also values past 2^53 (2^53 + 3 rounds to 2^53 + 4), and
INT64 factors, whose wrapping INT64 result takes the products. The kernel
path tests now use integer factors and complex values for "another dtype".
@eriknw
Tensor: say "pass shape=" when from_coo gets a shape where dtype goes
a19ba34
numpy, scipy.sparse and pydata/sparse take the shape as the third argument
of their COO constructors; Tensor.from_coo takes dtype there, and
Tensor.from_coo(coords, values, (3, 3, 3)) raised "ValueError: Unknown
dtype: (3, 3, 3)", which does not say what went wrong (the SAPS pilot's
friction 6). A tuple or list of integers is never a dtype, so it now raises
a TypeError that names the argument and says to pass shape=(3, 3, 3). A
numpy subarray spec such as (np.float64, (2,)) is not all integers and
stays a dtype. Matrix.from_coo and Vector.from_coo are unchanged.

test_from_coo_shape_passed_as_dtype: tuples, lists, numpy integers and ()
raise the TypeError with the shape= hint; a dtype, a subarray spec and
Matrix.from_coo behave as before.
@eriknw
Tensor: name to_dense(fill_value=0) when np.asarray refuses a Tensor
a1f0ad3
np.asarray(T) refuses, as for Matrix, since a missing entry has no value,
and the message (from BaseType) offered only T.to_coo(). The SAPS pilot's
ports hand MTTKRP and projection results to dense numpy algorithms (pinv,
svd), which want the missing entries as zeros, and reached for to_dense
twice (friction 5). Tensor's own __array__ now also names
T.to_dense(fill_value=0), for a Tensor small enough to hold densely. Only
the message changes; Matrix and Vector keep theirs.

test_no_implicit_dense_conversion_names_to_dense: np.asarray, np.array and
np.linalg.norm raise with both hints, and to_dense(fill_value=0) gives zeros.
@eriknw
Tensor: notes and user guide take in the SAPS pilot's findings
4fe7ba9
The SAPS pilot (HOOI and CP-ALS on FROSTT data, 2026-10-28) left findings
for the notes; each entry points at runs/2026-10-28-saps-pilot/report.md in
the grblas-ai repo.

- decisions.md, 25 (no per-mode copies): the pilot ran the HOOI and Tucker
  sweeps the decision said to revisit for, and it stands. Copies saved 1-19%
  on HOOI and made CP-ALS 1.6-6x slower per sweep; relayout() already gives
  users the copies where they help.
- limitations-and-roadmap.md: a chain of TTMs has no einsum route or kernel
  of its own (moving the intermediates cost 187 ms per sweep on Chicago, and
  einsum's dense-size order is 1.4x behind the best route on Uber), with a
  TTMc kernel as the fix; a ttm(U, mode) method that keeps the axis in
  place, as an API proposal, not done; per-call overhead on tiny problems
  (CP-ALS on 20^3, 48.7 ms against NumPy's 17.2). The roadmap lists them.
- The user guide's Engines section and design.md: the MTTKRP and TTM
  engines take bool, integer, FP32 and FP64 values with FP64 factors under
  plus_times (the previous commit), so count data need not be cast first;
  integer and complex results take the products.
@eriknw
Tensor: ewise_mult's expansion refusal gives advice that works for ew…
896828e
…ise_mult

When both operands of ewise_mult broadcast, the result is an outer product,
and past tensor_max_expansion it raised with the union methods' advice: "use
ewise_mult for the intersection, pass allow_expansion=True". ewise_mult is
the intersection already and takes no allow_expansion, so neither suggestion
could help. It now says the intersection is an outer product and names the
one thing that raises the limit, the config option. The union methods keep
their message, where both suggestions apply.
@eriknw
Tensor: select and apply take a 0-d Tensor as their scalar operand
af396e2
A full reduction is a 0-d Tensor (decision 2) and ewise_mult already
broadcasts one, but Tensor.select's thunk and Tensor.apply's left and right
went straight to the Matrix probe. It refused them with "Bad type for keyword
argument thunk= in Matrix.select" and the hint "Matrix methods do not take
Tensor operands", though the call was Tensor.select, so a threshold from a
reduction needed a to_scalar() that no other operand needs.

A 0-d Tensor (with autocompute, a 0-d expression) now converts with
to_scalar() when the expression is built, so it behaves as the Scalar it
stands for: an empty one raises EmptyObject, as an empty Scalar does, since
these operators need a value. Anything else goes through as before. Decision
28 records this and the narrower alternative.
@eriknw
Tensor: drop the two flags that unify ignores from ewise_union
017fdce
unify takes is_left_scalar and is_right_scalar only for code that still
passes them and ignores both, so passing them here suggested a scalar rule
that no longer exists. Behavior does not change.
@eriknw
Tensor: build the BOOL GCXS from arrays in the uint64 import test
b72d95a
sparse 0.14's GCXS.astype converts through from_coo, whose bincount cannot
take uint64 indices, so the test failed inside sparse on CI's ubuntu
notebooks job (numpy 2.1, sparse 0.14) before reaching from_pydata_sparse.
Building the BOOL array from the same arrays also keeps the repeated and
unsorted columns, which astype merged in every sparse version, so the BOOL
import now sees them; a mix of True and False checks that it ORs them.
@eriknw
Tensor: permute float rows with any_second, which keeps NaN and -0.0
0a475e7
A row permutation or row pick (P @ M, tensor_layout._perm_semiring) used
min_second for the 32- and 64-bit types, on the claim that its monoid never
combines two values. SuiteSparse's saxpy does combine the one term with the
monoid's identity when an output column has every row (GB_COMPUTE_DENSE_C_j
in 10.5.1 and 10.5.2, factory and JIT kernels), and fmin(+inf, NaN) is +inf.
A hypersparse row group stored out of order whose rows are full (as the TTM
engines' results are) returned +inf for NaN through relayout, to_coo and an
extract's row pick, with no error. Complex used plus_second, which returned
+0.0 for a -0.0 real or imaginary part the same way.

The selector expansions in a TTV (tensor_contract) and in a broadcast
(tensor_ewise) use the same semiring for St @ v. With the small side stored
full or bitmap, SuiteSparse runs that product as a dot product, which starts
from the first term; stored sparse with every entry, it runs saxpy, and a
NaN came back +inf there too.

Floats and complex now use any_second, which writes the term, so every value
comes back bit for bit, a signaling NaN included. Integers keep min_second,
which is exact for them and keeps iso. SuiteSparse 10 has no factory
ANY_SECOND kernels for the real types except where the build adds them back
(conda-forge's 10.5.2), and none for complex, so without the JIT it runs
generic: on 10.5.1, FP64 is 2x slower than min_second for 1e7 entries in 1e6
sparse rows and 1.1-1.25x in hypersparse rows; on conda-forge's 10.5.2,
complex is 1.5x slower than plus_second in sparse rows and 1.04-1.11x in
hypersparse rows.
@eriknw
Tensor: use any for a broadcast's diagonal product of floats, keeping…
634f631
… -0.0

A broadcast through a diagonal product (D @ M or M @ D, one term per output
entry) used plus as the monoid for every type but BOOL and UDTs. Where an
output column had every row, SuiteSparse's saxpy added the term to 0.0 (the
mechanism in "Tensor: permute float rows with any_second, which keeps NaN
and -0.0"), so a -0.0 came back +0.0 and a signaling NaN came back quiet
when the small side was expanded onto the nonempty rows of a hypersparse row
group with full rows. Floats and complex now use any, which writes the term;
integers keep plus, which is exact for them. Without the JIT, any_times and
most other any semirings run generic, 0-15% slower than plus for 1e6
hypersparse rows.
@eriknw
Tensor: reduce through a selector with no identity seed, keeping NaN
5c8c7b5
Tensor.reduce over part of a group multiplies by a selector (S @ M for
row axes, M @ S.T for column axes) under the caller's monoid. Where a
row of that product had an entry in every column, SuiteSparse's saxpy
started it from the monoid's identity and added each term
(GB_COMPUTE_DENSE_C_j, 10.5.1 and 10.5.2), and that identity is not
exact for every float: under min a fiber of NaNs came back +inf (-inf
under max), under plus a fiber of -0.0 came back +0.0, and a lone
signaling NaN came back quiet under plus and times (and complex times
turned NaN+0j into nan+nanj). Matrix.reduce_rowwise returns the NaN. The
monoid is the caller's, so unlike the row permutations in "Tensor:
permute float rows with any_second, which keeps NaN and -0.0" it cannot
be swapped for any.

On sparse data the product is now padded with one column that nothing
fills, so no row of it is complete and saxpy starts every row from its
first term. The column selector gets the extra column itself. For a row
selector the data needs it: tensor_layout.padded_view loads the data's
arrays and hyper hash GxB_IS_READONLY into a new Matrix with one more
column, in O(1) with no copy. The padding column is dropped through the
Container without waiting, so jumbled rows stay jumbled as the product
left them. saxpy is forced, since the dot method folds terms under plus
from 0; SuiteSparse 10.5 would not pick dot for these products, so that
costs nothing today. This holds for every monoid, user monoids included;
built-in monoids on integers and BOOL, and any, have exact identities
and are not padded. On bitmap or full data SuiteSparse runs the product
as a dot product from the first term, so nothing changes there; under
plus, full data still folds a fiber of -0.0 to +0.0, as
Matrix.reduce_rowwise does.

Two paths keep Matrix's behavior, as comments now say: a whole column
group goes through Matrix.reduce_rowwise, whose dot kernels fold plus
from 0, so a fiber of two or more -0.0 sums to +0.0 on sparse and full
data; and a reduction over every axis goes through Matrix.reduce_scalar,
which on bitmap data starts from the identity, so entries all NaN reduce
to +inf under min (-inf under max) and all -0.0 to +0.0 under plus.

Cost against no padding (AC, 18 threads, fresh JIT cache; 10.5.1 and
10.5.2, JIT at run and off): a column selector on sparse data,
0.95-1.05x; a row selector over hypersparse rows of 16 columns,
0.92-1.14x; over 1e7 entries in wide sparse rows, 0.97-1.05x under min
and 1.16-1.23x under plus. Bitmap and full data are not padded
(0.93-1.13x, noise on 2 ms runs). Peak memory reducing a group of 2^50
positions with 4e4 entries into 2^40: 100 MB, against 105 MB without the
padding.
@eriknw
Tensor: restore a test comment lost in an unrelated edit
98bda2e
"Tensor: permute float rows with any_second, which keeps NaN and -0.0"
dropped the "(along axis 1)" note on yd in
test_broadcast_on_nonempty_rows_sized_by_entries.
@eriknw
Tensor: raise what Matrix raises for an index out of range
50d088f
Outer indexing of a Tensor raised IndexOutOfBound for every index out
of range, which is not an IndexError, so `except IndexError` around
`T[i]` missed it, and Matrix raises otherwise. The Tensor now raises
what the same Matrix call raises, decided over the whole key, with the
Tensor's own message (which names the axis and its size):

- IndexError when an int (Python or numpy) is out of range, or any
  index of any kind is below -size, on whatever axis, as Matrix checks
  those itself;
- otherwise, for an assignment (=, <<, with or without accum, and del),
  InvalidIndex where the region is one element (every index an int, a
  Scalar or a one-element list or array), else IndexOutOfBound;
- otherwise, for an extraction, InvalidIndex where a Scalar index is
  out of range, else IndexOutOfBound.

As for Matrix, only the IndexError cases are raised when T[key] is
built; the others when the extraction is computed, or when it is
assigned to (T[key] << v), as GraphBLAS reports them for Matrix. take,
take_along_axis and vindex keep numpy's IndexError, and
Tensor.from_coo keeps IndexOutOfBound for coordinates past the shape.

A new test applies each key (ints, Scalars and lists, above and below
the range, one element or a region, and mixed) and each operation (get,
=, <<, accum <<, del) to a Matrix and a 2-d Tensor of it, a Vector and
a 1-d Tensor, and a 3-d Tensor with the key on each pair of axes, and
checks that the Tensor raises what Matrix raises.
@eriknw
ai-notes: decisions 29-31, NaN and -0.0 against an identity, and inde…
8473f09
…x errors

29: a float fiber's NaN or -0.0 is no longer replaced by a monoid's
identity in row permutations, a broadcast's diagonal product or a
partial-group reduce, with what each fix costs; where a reduction calls
a Matrix method it keeps Matrix's result, including a sum of two or
more -0.0 coming back +0.0.

30: a reduction over every axis returns what Matrix.reduce_scalar
returns, including +inf for entries all NaN under min on bitmap data.

31: an index out of range raises what the same Matrix call raises.
@eriknw
Tensor: let the NaN TTM test's numpy model make NaN from +inf and -inf
17452d5
test_ttm_engine_results_keep_nan puts +inf and -inf in one fiber, and
its numpy reference (_ttm_model, np.tensordot) sums them to NaN, as
intended. numpy's dot reports that as "invalid value encountered in
dot" where the BLAS sets the floating-point flag (OpenBLAS on Linux,
x86-64 and arm64, and MKL on Windows; not OpenBLAS on macOS), and CI
turns warnings into errors, so the test failed there for both engines.
The model now runs under np.errstate(invalid="ignore"). numpy's own dot
loop gives the same warning on macOS (longdouble operands), and errstate
silences it.
@eriknw
Ignore any_atan2 and any_pow in test_operator_types, made by Tensor t…
f427f34
…ests

test_semiring_types takes the names it expects from dir(semiring) at
import, so a semiring that a test later creates by name fails it unless
IGNORE lists it, as plus_atan2 has been listed. A float Tensor broadcast
through a diagonal product now uses the any monoid ("Tensor: use any for
a broadcast's diagonal product of floats, keeping -0.0"), so the
broadcasts with atan2 and pow in test_tensor.py create any_atan2 and
any_pow, and test_semiring_types failed whenever test_tensor.py ran
before it in the same process.
@eriknw
Ignore any_rpow in test_operator_types, made from the Tensor tests' a…
67f19c6
…ny_pow

test_op.py::test_commutes reads commutes_to on every semiring in
dir(semiring), and any_pow's is any_rpow, which get_semiring creates by
name. So when test_tensor.py made any_pow first ("Ignore any_atan2 and
any_pow in test_operator_types, made by Tensor tests"), test_commutes
then made any_rpow, and test_semiring_types failed if it ran after both,
as one random order on CI did. The other names the Tensor tests make add
nothing here: atan2 has no commuted op, and max_pow's max_rpow is
already listed.
@eriknw
eriknw force-pushed the 50-tensor branch from 9c60de3 to 67f19c6 Compare November 12, 2026 17:36
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment

Reviewers

No reviews

Uh oh!

There was an error while loading. Please reload this page.

Assignees

No one assigned

Labels

None yet

Projects

None yet

Milestone

No milestone

Development

Successfully merging this pull request may close these issues.

Uh oh!

There was an error while loading. Please reload this page.

1 participant

@eriknw
Add this suggestion to a batch that can be applied as a single commit.This suggestion is invalid because no changes were made to the code.Suggestions cannot be applied while the pull request is closed.Suggestions cannot be applied while viewing a subset of changes.Only one suggestion per line can be applied in a batch.Add this suggestion to a batch that can be applied as a single commit.Applying suggestions on deleted lines is not supported.You must change the existing code in this line in order to create a valid suggestion.Outdated suggestions cannot be applied.This suggestion has been applied or marked resolved.Suggestions cannot be applied from pending reviews.Suggestions cannot be applied on multi-line comments.Suggestions cannot be applied while the pull request is queued to merge.Suggestion cannot be applied right now. Please check back later.
You are visitor 01402503 — GeezerVison does not store the pages you look up.
Best viewed with Netscape Navigator 4.7 or Internet Explorer 6 at 800×600. No cookies required.