boundlab.polysp.PolySp

final class boundlab.polysp.PolySp

Bases: Expr

A polynomial expression component with sparse representation.

One generator stores mixed-order monomials with -1-padded indices; all monomials index error symbols through one shared span table.

Methods

__init__
absub	Bound on the magnitude: \(\max(|lb|, ub) \ge \sup |x|\).
add	Same-class addition; __add__ dispatches here when classes match and otherwise groups the addends in an ExprGroup.
align_fill_zeros
broadcast_to
chw	Center/halfwidth form: c = (ub + lb) / 2, w = (ub - lb) / 2.
classset	The set of component classes present in this value.
compress	Re-express the value over at most nterms - 1 fresh symbols, with a certified residual, via lasso.lad.admm_dict_learning() (LAD-lasso dictionary learning from the pytorch-lasso package).
convert_from	Lift an Error/Noise symbol or a dense Zono into a sparse polynomial.
convert_to	Hook: convert self into expr_type, or None when this class does not know how.
einsum	Apply the linear map described by an integer-label einsum.
error	Diagonal polynomial scaling each component of err by amplitude.
expanded_to_table
from_exprlike	Lift a tensor/scalar into a broadcast Bias; pass Expr through.
from_zono	Reinterpret a dense zonotope as an order-1 sparse polynomial.
full_abs
lb	Sound elementwise lower bound on every concrete value represented.
lbub	(lb, ub) in one call; components override it when computing both at once is cheaper than two passes.
make	Build a PolySp, padding and merging its generators.
matmul
mean
numel
reasons_breakdown
reshape
rmatmul
sparse_applypoly	Apply a concrete quadratic a x^2 + b x + c elementwise via the sparse pair product, with the same eps / order truncation.
sparse_matmul	Matrix product with sound truncation.
split	Split into (matching, rest) so that matching + rest == self.
squeeze
sum
to	Convert to another component class, exactly.
to_intervals	Collapse to the box hull Bias(c) + Noise(w).
torch_print	Diagnostics as a TensorFormat.
transpose
ub	Sound elementwise upper bound on every concrete value represented.
unsqueeze
zeros

table: SpanTable[Error]

gens: Generator

__init__(table, gens)

property shape_dtype: ShapeDtype

Allocation-free (shape, dtype) metadata of the value.

property by_order: dict[int, Generator]

property nbytes

Estimated memory of all generators’ data and indices, in bytes.

static make(table, *gens)

Build a PolySp, padding and merging its generators.

classmethod convert_from(expr)

Lift an Error/Noise symbol or a dense Zono into a sparse polynomial.

Bias has no polynomial counterpart, so an Intervals group keeps its center outside the PolySp and only its Noise part converts.

static error(err, amplitude=1.0)

Diagonal polynomial scaling each component of err by amplitude.

static zeros(shape_dtype, table=None, order=1)

static from_zono(zono)

Reinterpret a dense zonotope as an order-1 sparse polynomial.

full_abs()

ub()

Sound elementwise upper bound on every concrete value represented.

lb()

Sound elementwise lower bound on every concrete value represented.

lbub()

(lb, ub) in one call; components override it when computing both at once is cheaper than two passes.

einsum(subscripts, *operands)

Apply the linear map described by an integer-label einsum.

subscripts holds one label tuple per input followed by the output labels (see boundlab.utils.einsum_parser()). This is the single linear primitive: __mul__, __matmul__, sum and mean all lower to it, so implementing it soundly makes every derived linear operation sound.

align_fill_zeros(other)

expanded_to_table(table)

add(other)

Same-class addition; __add__ dispatches here when classes match and otherwise groups the addends in an ExprGroup.

reshape(*shape)

transpose(*perm)

broadcast_to(*shape)

sparse_matmul(other, eps=0.001, order=2)

Matrix product with sound truncation.

Every pair of monomials multiplies exactly — \((d_r \prod_{k \in I_r} \varepsilon_k)(d_s \prod_{k \in I_s} \varepsilon_k)\) is a monomial of degree \(|I_r| + |I_s|\) — and the result keeps those whose degree fits order and whose magnitude clears eps; everything discarded is enclosed by the returned Noise (each dropped monomial contributes at most its coefficient magnitude, since every \(\varepsilon\) factor lies in \([-1, 1]\)).

sparse_applypoly(poly, eps=0.001, order=2)

Apply a concrete quadratic a x^2 + b x + c elementwise via the sparse pair product, with the same eps / order truncation.

reasons_breakdown()

torch_print(group='reason')

Diagnostics as a TensorFormat.

The result is safe to hand to Torch diagnostic output under tracing: only plain arrays cross the callback boundary, never expression metadata (which may hold tracers, e.g. reason weights).

compress(nterms, lam=0.5, max_iter=20, tol=0.001, max_cols=None)

Re-express the value over at most nterms - 1 fresh symbols, with a certified residual, via lasso.lad.admm_dict_learning() (LAD-lasso dictionary learning from the pytorch-lasso package).

Warning

Not fully tested: soundness is covered by sampling unit tests and the defaults were tuned on real barrier matrices, but no complete end-to-end verified run has exercised compression yet.

Every non-constant monomial \(\mu_r = \prod_{k \in I_r} \varepsilon_k\) ranges in \([-1, 1]\), so the value is a linear map of the monomial vector: \(x = d_0 + A \mu\) with \(A \in \mathbb{R}^{p \times R}\) holding one flattened coefficient column per monomial. LAD-LASSO factorizes \(A \approx D S\) with \(k' = nterms - 1\) dictionary atoms; each row of \(S\), rescaled into the dictionary, defines a fresh symbol

\[\varepsilon'_j = \frac{S_{j\cdot}\,\mu}{\|S_{j\cdot}\|_1} \in [-1, 1],\]

sound when treated as a new independent symbol (the true \(\varepsilon'\) set is a subset of the box). The factorization error is enclosed coefficient-wise — element \(i\) of the returned Noise is \(\sum_r |A - DS|_{ir}\) — which is exactly the LAD fit term the solver minimizes, while the L1 penalty keeps \(\|S_{j\cdot}\|_1\), and with it the new symbols’ amplitudes, from inflating.

The fresh symbols carry the value’s blended Reasons; the residual is tagged "compress". Correlation with other live values is severed — the compressed value no longer references the old symbols (see the cross-value correlation caveat in docs/guide/polysp-plan.md).

Only the max_cols (default 16 * nterms) largest monomials by coefficient l1 mass are handed to the solver; the tail joins the residual noise directly. Coefficient mass is heavily concentrated in practice (on the SST barrier matrices the tail beyond 16 * 1024 columns carries ~0.2% of the mass), and this keeps the solve tractable — LAD-LASSO on all 350k+ monomials of a real attention barrier would take hours.

The solver runs with init="topk" (dictionary seeded with the heaviest monomials, codes warm-started with the matching diagonal, so iteration 0 is exactly the top-k truncation solution and the iterations move tail mass from the residual into the atoms), the ISTA inner lasso solver and the vectorized least-squares + projection dictionary update (dict_update="lstsq"); tol is accepted for interface stability but the ADMM loop runs a fixed max_iter steps. This matters because residual Noise propagates through downstream linear layers as |W| h (no sign cancellation) while generator rows propagate as W d: on the real barrier-0 matrix, cold-started solves leave ~90% of the mass in the residual and inflate downstream width ~7.7x, whereas the warm-started defaults (lam=0.5, max_iter=20) reach ~1.02x mean / ~1.4x worst-element with 0.6% of the mass in Noise in ~12 s — an order of magnitude below plain truncation’s 3.8%.

Returns:

The compressed PolySp (constant row plus at most nterms - 1 order-1 rows over one fresh Error) and the certified residual Noise.

Return type:

tuple[PolySp, Noise]

property T: Self

__add__(other)

__mul__(other)

absub()

Bound on the magnitude: \(\max(|lb|, ub) \ge \sup |x|\).

chw()

Center/halfwidth form: c = (ub + lb) / 2, w = (ub - lb) / 2.

classset()

The set of component classes present in this value.

A single component reports {type(self)}, an ExprGroup its member classes, and Zeros the empty set. Handlers use this to decide which part of a value they know how to transform.

convert_to(expr_type)

Hook: convert self into expr_type, or None when this class does not know how. The other half of to().

property dtype: dtype

static from_exprlike(expr, shape)

Lift a tensor/scalar into a broadcast Bias; pass Expr through.

matmul(other)

mean(axis, keepdims=False)

property ndim: int

numel()

rmatmul(other)

property shape: Sequence[Any]

split(ty)

Split into (matching, rest) so that matching + rest == self.

The main way handlers peel off the component class they transform while passing the remainder through untouched.

squeeze(axes=None)

sum(axis, keepdims=False)

to(expr_type)

Convert to another component class, exactly.

Identity short-circuits; otherwise the target’s convert_from is tried, then this class’s convert_to. Raises TypeError when neither side knows the conversion — conversions never approximate.

to_intervals(name='')

Collapse to the box hull Bias(c) + Noise(w).

Sound but lossy: every correlation between error symbols is dropped, so downstream cancellation (x - x = 0) no longer happens.

unsqueeze(axes)