A reckoner seed: sparse's column-stored matrices, as a dict — machines/seeds/seedsparse.shoddy
seedsparse bridges sparse into the
calculator: thirteen words for matrices that are mostly zeros. A sparse
matrix at the keyboard is a dict — a list of name-and-value
pairs — not a cell of its own. That is the same call
seedsimplex made for a problem and its
solution, and for the same reason. cuttle's
Cell carries a MATRIX because a dense grid — every
cell written out, zeros included — is the beginner-facing form, and every
seed that touches one speaks it. A second matrix cell would put a choice in
front of a reader at the moment they least want one. So a sparse matrix
arrives and leaves as
Shoddy · The Machines{ ( "rows" 4 ) ( "cols" 3 )
( "colix" { { 2 4 } { 1 } { 3 4 } } )
( "colvs" { { 5 1 } { 2 } { 7 3 } } ) }DGET reads that like any other dict. It also shows what the
storage actually is: a row index and a value per stored entry, and
nothing at all for the gaps.
The keyboard's MATRIX is the right thing for a grid you are
going to look at. It stops being the right thing when the grid is large and
nearly empty: a constraint matrix out of an MPS file, an adjacency table, a
transition matrix over states that only step to their neighbours. In a dense
grid, every zero costs the same to keep and to read as a real number does.
SPARSE crosses a MATRIX over. SPNNZ
tells you what that saved. SPDENSE brings it back when you want
to look at it.
The other reason: the sparse form is what the solver actually walks.
simplex prices a linear program one column at a
time. A session that can inspect those columns — SPCOLIX,
SPCOLVS, SPCOLDOT — can watch the arithmetic the
solver is doing, rather than take its word for the answer.
sparse refuses a malformed column at
construction: indices and values that do not pair up, an index outside the
stated rows, indices that do not ascend. Those are the right refusals for a
program. They are the wrong ones for a keyboard, where an abort ends the
session and takes the stack — the calculator's working pile — with it. So
every one of those questions is asked here first, by SpsRead.
It either hands back a matrix known to be well formed, or says which rule was
broken. Nothing past it can fail.
The same goes for the dimension checks SpMatVec and
SpVecMat make, and for every column index. Reaching a column is
a bare Nth by design, and Nth aborts past the end
of an array. So SPCOLIX 9 on a three-column matrix is the seed's
own question to answer.
Two of the checks have no counterpart in the machine at all: a triplet of
the wrong length, and a fractional row or column index.
SpFromEnts would not notice either, and neither names a cell
anybody meant to type.
A four-by-three grid with five numbers in it, crossed over, inspected, and multiplied:
> 4 3 { 0 2 0 5 0 0 0 0 7 1 0 3 } MAT SPARSE
x: { ( "rows" 4 ) ( "cols" 3 ) ( "colix" { { 2 4 } { 1 } { 3 4 } } ) ... 1 more }
> DUP SPNNZ
x: 5
> DUP 1 SPCOLIX
x: { 2 4 }
> DUP 1 1 SPGET
x: 0
> { 1 2 3 } SPMATVEC
x: { 4 5 21 10 }Or built straight from triplets — one { row col value } trio per entry. That is how a matrix arrives when you are reading it off something rather than typing it out:
> 2 2 { { 1 1 3 } { 1 1 4 } { 2 2 5 } } SPENTS SPNNZ
x: 2Two triplets naming one cell are added together — three and four make seven. A cell adding up to zero is not stored at all, because a zero here is an absence rather than a number.
A malformed one gets a reason, in place of an ended session:
?: SPADDCOL: COLUMN 1 NAMES A ROW OUTSIDE 1 TO 3
?: SPADDCOL: COLUMN 1 DOES NOT HAVE ITS ROW INDICES IN ASCENDING ORDER
?: SPCOLIX: THERE IS NO COLUMN 9 — THIS MATRIX HAS 3
?: SPMATVEC: THE VECTOR HAS 2 NUMBERS AND THE MATRIX IS 3 WIDE
?: SPENTS: TRIPLET 1 NAMES ROW 1.5, AND THE ROWS ARE 1 TO 2| Word | Description |
|---|---|
| SPARSE ( matrix -- sparse ) | The same matrix stored by column, keeping only its nonzero cells. Worth it when the zeros outnumber the numbers and the grid is big; for a small full one the MATRIX is cheaper and clearer. |
| SPDENSE ( sparse -- matrix ) | Back to an ordinary MATRIX, zeros and all. Exact: across and back changes nothing. |
| SPENTS ( rows cols list -- sparse ) | Build from a LIST of { row col value } triplets. Two triplets naming one cell are added together, and a cell adding up to zero is not stored at all. |
| SPNNZ ( sparse -- n ) | How many numbers are actually stored, as against how many cells the grid has. |
| SPGET ( sparse r c -- n ) | The number in row r, column c — zero if nothing is stored there, which is what a gap means. |
| SPCOLIX ( sparse j -- list ) | Which rows column j fills, ascending. |
| SPCOLVS ( sparse j -- list ) | The values column j holds, in the positions SPCOLIX names. |
| SPCOLDOT ( sparse j list -- n ) | Column j against a vector, touching only what is stored. This is the kernel the simplex method spends most of its time in. |
| SPMATVEC ( sparse list -- list ) | The matrix times a vector, one number per row. The vector must be as long as the matrix is wide. |
| SPVECMAT ( list sparse -- list ) | A vector times the matrix, one number per column. The vector must be as long as the matrix is tall. |
| SPTRANSP ( sparse -- sparse ) | The transpose: rows become columns, in one pass over what is stored. |
| SPADDROW ( sparse list list -- sparse ) | A new row on the bottom, holding the given values in the given columns. Only the columns named are touched, so a row with one number in it — a bound, a branch — costs almost nothing. |
| SPADDCOL ( sparse list list -- sparse ) | A new column on the end, holding the given values in the given rows, ascending. |
| User | How | |
|---|---|---|
 | halifax | The calculator's sparse-matrix words, under their own WORDS heading. |
 | sparky | Sparky folds it too, so a model calling eval reaches the same words halifax puts at a prompt. |
A mill — a complete Shoddy program — claims this seed by folding
RckSeedSparse over its reckoner state. That is all halifax
does.
| Machine | Why | |
|---|---|---|
 | cuttle | The Cell type every bridged word reads its arguments from and answers into. |
 | matrix | The Matrix cell SPARSE reads and SPDENSE answers. |
 | reckoner | RckReg and the argument readers every registered word is built from. |
 | seq | All asks a column's three shape questions, and Append gathers the lists the dict converters build. |
 | sparse | The domain this seed bridges: the Sparse type and every kernel over it. |