Sparse polynomial arrays¶
Use poly.sparse for (power, coefficient) terms. Operands share a power
shape: Int for one variable, or a tuple of Int powers for several variables.
Axis numbers start at zero, and output terms use increasing lexicographic order.
Every computational function accepts max_steps= instead of the explicit
shared budget shown below. See array conventions for inference
and errors, or exact array algebra for worked examples.
Construction and interoperability¶
Array¶
struct Array[P: Copyable & Deinitable, k: Int](Copyable, Movable, Iterable, Sized, _WithModulus, _Record)
An immutable polynomial sharing its canonical term storage.
Parameters.
P: The power shape: Int or a tuple of Int powers.k: The inferred coefficient kind: 0 for ZZ, 1 for QQ, 2 for QQi, 3 for a prime field, 4 for AA, or 5 for QQbar.
Defined in src/poly/sparse.mojo.
Array.IteratorType¶
comptime IteratorType[iterable_mut: Bool, //, iterable_origin: Origin[mut=iterable_mut]]: Iterator = _ArrayIterator[Self.P, Self.k, ImmOrigin(iterable_origin)]
A borrowing iterator over the shared storage.
Parameters.
iterable_mut: Whether the borrowing origin is mutable.iterable_origin: The lifetime of the borrowed array.
Array.__init__¶
def __init__(out self, var core: SparsePoly[_Ring[Self.k]], mut budget: Budget) raises PolyError
Take ownership of canonical storage; use asarray for coefficient inputs.
Arguments.
core: An owned canonical core polynomial in the array's variable layout and domain.budget: The caller-owned work allowance, shared through preparation and computation.
Raises.
PolyError: LIMIT on exhausted work, CAPACITY on unrepresentable sizes, or DOMAIN for incompatible input.
Array.to_list¶
def to_list(self, mut budget: Budget) raises PolyError -> List[Tuple[Self.P, _Scalar[Self.k]]]
Return an independent mutable list, charging allocation and coefficient work.
Arguments.
budget: The caller-owned work allowance, shared through preparation and computation.
Returns. An independent mutable list in the current entry order.
Raises.
PolyError: LIMIT on exhausted work, CAPACITY on unrepresentable sizes, or DOMAIN for incompatible input.
Array.to_list¶
def to_list(self, *, max_steps: UInt64 = UInt64.MAX) raises PolyError -> List[Tuple[Self.P, _Scalar[Self.k]]]
Return an independent mutable list, charging allocation and coefficient work.
Arguments.
max_steps: The complete call's work allowance; defaults to UInt64.MAX.
Returns. An independent mutable list in the current entry order.
Raises.
PolyError: LIMIT on exhausted work, CAPACITY on unrepresentable sizes, or DOMAIN for incompatible input.
Array.modulus¶
def modulus(self) -> UInt64
Return the retained prime modulus, or zero outside a prime field.
Returns. The prime modulus for modular data, or zero otherwise.
Array.domain¶
def domain(self) -> String
Return ZZ, QQ, QQi, GF(p), AA, or QQbar, including for an empty result.
Returns. ZZ, QQ, QQi, GF(p), AA, or QQbar, including for an empty result.
asarray¶
def asarray[I: Iterable, P: Copyable & Deinitable, C: Copyable & Deinitable](values: I, mut budget: Budget) raises PolyError -> Array[P, _Kind[C]] where _Element[I] == Tuple[P, C]
Normalize one pass over terms, or share a prepared sparse array.
Parameters.
I: The inferred input iterable type.P: The power shape: Int or a tuple of Int powers.C: The inferred input coefficient type.
Arguments.
values: The coefficient sequence, sparse terms, or prepared array.budget: The caller-owned work allowance, shared through preparation and computation.
Returns. An immutable canonical polynomial that retains its exact domain and modulus.
Raises.
PolyError: LIMIT on exhausted work, CAPACITY on unrepresentable sizes, or DOMAIN for incompatible input.
Defined in src/poly/sparse.mojo.
astype¶
def astype[dtype: AnyType, I: Iterable, Context: Copyable & Deinitable, P: Copyable & Deinitable, C: Copyable & Deinitable](values: I, mut budget: Budget, *, context: Context) raises PolyError -> NumericArray[P, _num._StoredDomain[dtype]] where _Element[I] == Tuple[P, C]
Convert every coefficient to an explicit numerical type and precision.
Unlike asarray on a prepared array, this also converts within the same domain. Real destinations require exactly zero imaginary bounds; point destinations require certain rounding. Inputs remain unchanged.
Parameters.
dtype: Float, Complex, Ball, or ComplexBall.I: The inferred term iterable type.Context: The matching explicit precision context.P: The common sparse power shape.C: The first or homogeneous coefficient type.
Arguments.
values: Raw sparse terms or a prepared sparse array.budget: The shared conversion allowance.context: ArithmeticContext for Float, ComplexContext for Complex, or BallContext for balls.
Returns. An immutable array with rounded points or enclosing balls in the requested type.
Raises.
PolyError: DOMAIN for nonreal or uncertain point conversion, or LIMIT/CAPACITY.
Defined in src/poly/sparse.mojo.
to_core¶
def to_core[I: Iterable, P: Copyable & Deinitable, C: Copyable & Deinitable](values: I, mut budget: Budget, *, variables: List[Int64] = List[Int64]()) raises PolyError -> SparsePoly[_Ring[_Kind[C]]] where (_Element[I] == Tuple[P, C] and _Kind[C] >= 0)
Return an independent mutable core polynomial with an explicit axis-to-ID map.
An empty map uses IDs 0 through the number of axes minus one. Output uses lexicographic priority in array-axis order, even when IDs are not increasing.
Changing the returned core storage cannot affect a prepared input. Sparse export uses lexicographic order with the supplied IDs in axis-priority order.
Parameters.
I: The inferred input iterable type.P: The power shape: Int or a tuple of Int powers.C: The inferred input coefficient type.
Arguments.
values: The coefficient sequence, sparse terms, or prepared array.budget: The caller-owned work allowance, shared through preparation and computation.variables: Core variable IDs in array-axis order. An empty list selects 0, 1, and so on.
Returns. An independent mutable core polynomial with the requested variable IDs and the same exact domain.
Raises.
PolyError: LIMIT on exhausted work, CAPACITY on unrepresentable sizes, DOMAIN for invalid input, or UNSUPPORTED for a documented domain restriction.
Defined in src/poly/sparse.mojo.
from_core¶
def from_core[C: CoefficientRing, *, ndim: Int = 1](values: SparsePoly[C], mut budget: Budget, *, variables: List[Int64] = List[Int64]()) raises PolyError -> Array[_Shape[ndim], _CoreKind[C]]
Validate and copy a core polynomial into a fixed number of array axes.
Use from_core[ndim=2] for two variables. The optional map lists core IDs in array axis order; its default is 0, 1, and so on. Unknown variables are rejected. One axis produces integer powers; several axes produce power tuples.
Checks core invariants and modular residues, then copies storage. Mutating the core afterwards cannot affect the result. Dense import normalizes the sole variable to zero. Sparse import rejects used IDs absent from the map and normalizes term order to lexicographic.
Parameters.
C: The supported core ring: ZZ, QQ, QQi, ModInt, AA, or QQbar.ndim: The nonnegative number of sparse axes, including unused axes; zero accepts constants only.
Arguments.
values: The mutable core SparsePoly to validate and copy.budget: The caller-owned work allowance, shared through preparation and computation.variables: Core variable IDs in array-axis order. An empty list selects 0, 1, and so on.
Returns. An independent immutable array in the core coefficient domain, with normalized variable IDs.
Raises.
PolyError: LIMIT on exhausted work, CAPACITY on unrepresentable sizes, DOMAIN for invalid input, or UNSUPPORTED for a documented domain restriction.
Defined in src/poly/sparse.mojo.
format¶
def format[I: Iterable, P: Copyable & Deinitable, C: Copyable & Deinitable](values: I, mut budget: Budget, *, variables: List[String] = List[String]()) raises PolyError -> String where (_Element[I] == Tuple[P, C] and _Kind[C] >= 0 and _Kind[C] <= 3)
Display an exact polynomial with readable variable names.
Supports ZZ, QQ, QQi, and prime fields. Coefficients remain exact; terms appear in decreasing lexicographic order. This is display text, not an archive carrying domain or axis metadata.
Parameters.
I: The inferred input iterable.P: The scalar or tuple power shape.C: The inferred coefficient type.
Arguments.
values: Polynomial coefficients, terms, or a prepared exact array.budget: The shared work allowance.variables: One ASCII identifier per axis; defaults to x or x0, x1, and so on.
Returns. A named-variable expression, or 0 for the zero polynomial.
Raises.
PolyError: DOMAIN for invalid or duplicate names (i is reserved over QQi), LIMIT on exhaustion, or CAPACITY for excessive sizes.
Defined in src/poly/sparse.mojo.
to_kernel_bytes¶
def to_kernel_bytes[I: Iterable, P: Copyable & Deinitable, C: Copyable & Deinitable](values: I, mut budget: Budget, *, variables: List[Int64] = List[Int64]()) raises PolyError -> List[UInt8] where (_Element[I] == Tuple[P, C] and _Kind[C] >= 0 and _Kind[C] <= 1)
Encode integer or rational coefficients as a canonical kernel literal.
Zero and one use separate kernel atoms and cannot be encoded here. For application archives, use poly.io instead.
Parameters.
I: The inferred input iterable.P: The scalar or tuple power shape.C: The inferred coefficient type.
Arguments.
values: Exact integer or rational polynomial input.budget: The shared work allowance.variables: Core IDs in array-axis order; empty selects 0, 1, and so on.
Returns. Canonical little-endian kernel bytes, at most 1 MiB.
Raises.
PolyError: ENCODING for zero or one, DOMAIN for invalid maps, LIMIT on exhaustion, or CAPACITY beyond the kernel size ceiling.
Defined in src/poly/sparse.mojo.
from_kernel_bytes¶
def from_kernel_bytes[*, ndim: Int = 1](data: Span[UInt8, _], mut budget: Budget, *, variables: List[Int64] = List[Int64]()) raises PolyError -> Array[_Shape[ndim], 1]
Decode and validate a kernel literal into rational coefficient storage.
Malformed or noncanonical bytes are rejected, never silently repaired. The variable map supplies axis metadata absent from the wire format.
Parameters.
ndim: The number of output axes.
Arguments.
data: The kernel literal payload.budget: The shared work allowance.variables: Core IDs in array-axis order; empty selects 0, 1, and so on.
Returns. A canonical polynomial over QQ with array axes starting at zero.
Raises.
PolyError: ENCODING for malformed bytes, DOMAIN for unmapped variables, LIMIT on exhaustion, or CAPACITY for excessive input or output size.
Defined in src/poly/sparse.mojo.
Arithmetic and calculus¶
add¶
def add[A: Iterable, B: Iterable, P: Copyable & Deinitable, C: Copyable & Deinitable, D: Copyable & Deinitable](a: A, b: B, mut budget: Budget) raises PolyError -> Array[P, _Join[_Kind[C], _Kind[D]]] where (_Element[A] == Tuple[P, C] and _Element[B] == Tuple[P, D])
Add polynomials, promoting their coefficients together.
Parameters.
A: The first inferred iterable type.B: The second inferred iterable type.P: The power shape: Int or a tuple of Int powers.C: The inferred input coefficient type.D: The second inferred coefficient type.
Arguments.
a: The first polynomial.b: The second polynomial.budget: The caller-owned work allowance, shared through preparation and computation.
Returns. The canonical sum in the common exact domain.
Raises.
PolyError: LIMIT on exhausted work, CAPACITY on unrepresentable sizes, or DOMAIN for incompatible input.
Defined in src/poly/sparse.mojo.
subtract¶
def subtract[A: Iterable, B: Iterable, P: Copyable & Deinitable, C: Copyable & Deinitable, D: Copyable & Deinitable](a: A, b: B, mut budget: Budget) raises PolyError -> Array[P, _Join[_Kind[C], _Kind[D]]] where (_Element[A] == Tuple[P, C] and _Element[B] == Tuple[P, D])
Subtract polynomials, promoting their coefficients together.
Parameters.
A: The first inferred iterable type.B: The second inferred iterable type.P: The power shape: Int or a tuple of Int powers.C: The inferred input coefficient type.D: The second inferred coefficient type.
Arguments.
a: The first polynomial.b: The second polynomial.budget: The caller-owned work allowance, shared through preparation and computation.
Returns. The canonical first polynomial minus the second.
Raises.
PolyError: LIMIT on exhausted work, CAPACITY on unrepresentable sizes, or DOMAIN for incompatible input.
Defined in src/poly/sparse.mojo.
negative¶
def negative[I: Iterable, P: Copyable & Deinitable, C: Copyable & Deinitable](values: I, mut budget: Budget) raises PolyError -> Array[P, _Kind[C]] where _Element[I] == Tuple[P, C]
Negate every coefficient, preserving the domain and power shape.
Parameters.
I: The inferred input iterable type.P: The power shape: Int or a tuple of Int powers.C: The inferred input coefficient type.
Arguments.
values: The coefficient sequence, sparse terms, or prepared array.budget: The caller-owned work allowance, shared through preparation and computation.
Returns. The polynomial with every coefficient negated.
Raises.
PolyError: LIMIT on exhausted work, CAPACITY on unrepresentable sizes, or DOMAIN for incompatible input.
Defined in src/poly/sparse.mojo.
multiply¶
def multiply[A: Iterable, B: Iterable, P: Copyable & Deinitable, C: Copyable & Deinitable, D: Copyable & Deinitable](a: A, b: B, mut budget: Budget) raises PolyError -> Array[P, _Join[_Kind[C], _Kind[D]]] where (_Element[A] == Tuple[P, C] and _Element[B] == Tuple[P, D])
Multiply polynomials, promoting their coefficients together.
Parameters.
A: The first inferred iterable type.B: The second inferred iterable type.P: The power shape: Int or a tuple of Int powers.C: The inferred input coefficient type.D: The second inferred coefficient type.
Arguments.
a: The first polynomial.b: The second polynomial.budget: The caller-owned work allowance, shared through preparation and computation.
Returns. The canonical product in the common exact domain.
Raises.
PolyError: LIMIT on exhausted work, CAPACITY on unrepresentable sizes, or DOMAIN for incompatible input.
Defined in src/poly/sparse.mojo.
divide¶
def divide[I: Iterable, S: Copyable & Deinitable, P: Copyable & Deinitable, C: Copyable & Deinitable](values: I, scalar: S, mut budget: Budget) raises PolyError -> Array[P, _FieldKind[_Join[_Kind[C], _Kind[S]]]] where (_Element[I] == Tuple[P, C] and _Kind[C] >= 0 and _Kind[S] >= 0)
Divide every coefficient by a nonzero scalar.
Exact domains promote together; integer division returns rationals. Modular inputs must have the same prime. Inputs remain unchanged.
Parameters.
I: The inferred polynomial iterable.S: The scalar operand type.P: The retained sparse power shape.C: The input coefficient type.
Arguments.
values: Sparse terms or a prepared array.scalar: The scalar constant; division requires a nonzero value.budget: The shared work allowance, including conversion and storage.
Returns. A new polynomial in the common exact domain.
Raises.
PolyError: DOMAIN for incompatible scalars or zero divisors; LIMIT/CAPACITY on resource limits.
Defined in src/poly/sparse.mojo.
power¶
def power[I: Iterable, P: Copyable & Deinitable, C: Copyable & Deinitable](values: I, exponent: Int, mut budget: Budget) raises PolyError -> Array[P, _Kind[C]] where _Element[I] == Tuple[P, C]
Raise a polynomial to a nonnegative power by repeated squaring.
Zero to power zero returns the constant one. Negative exponents raise DOMAIN.
Parameters.
I: The inferred input iterable type.P: The power shape: Int or a tuple of Int powers.C: The inferred input coefficient type.
Arguments.
values: The coefficient sequence, sparse terms, or prepared array.exponent: A nonnegative integer exponent; zero returns one, including for a zero input.budget: The caller-owned work allowance, shared through preparation and computation.
Returns. The canonical power in the input domain.
Raises.
PolyError: LIMIT on exhausted work, CAPACITY on unrepresentable sizes, or DOMAIN for incompatible input.
Defined in src/poly/sparse.mojo.
degree¶
def degree[I: Iterable, P: Copyable & Deinitable, C: Copyable & Deinitable](values: I, mut budget: Budget, *, axis: Int = -1) raises PolyError -> Int where _Element[I] == Tuple[P, C]
Return total degree, or degree in one axis; the zero polynomial has degree -1.
The default axis=-1 selects total degree. Other axes are numbered from zero.
Parameters.
I: The inferred input iterable type.P: The power shape: Int or a tuple of Int powers.C: The inferred input coefficient type.
Arguments.
values: The coefficient sequence, sparse terms, or prepared array.budget: The caller-owned work allowance, shared through preparation and computation.axis: The zero-based variable index; -1 selects total degree.
Returns. The degree, or -1 for the zero polynomial.
Raises.
PolyError: LIMIT on exhausted work, CAPACITY on unrepresentable sizes, or DOMAIN for incompatible input.
Defined in src/poly/sparse.mojo.
leading_term¶
def leading_term[I: Iterable, P: Copyable & Deinitable, C: Copyable & Deinitable](values: I, mut budget: Budget, *, order: String = "lex", axes: List[Int] = List[Int]()) raises PolyError -> Tuple[P, _Scalar[_Kind[C]]] where (_Element[I] == Tuple[P, C] and _Kind[C] >= 0)
Return the greatest stored term under the requested monomial order.
Parameters.
I: The inferred sparse input iterable.P: The common sparse power shape.C: The inferred exact coefficient type.
Arguments.
values: Sparse terms or a prepared array.budget: The shared query allowance.order: One of lex, grlex, or grevlex; defaults to lex.axes: All axes in descending priority; empty uses tuple order.
Returns. The power and coefficient, leaving input storage unchanged.
Raises.
PolyError: DOMAIN for zero or invalid order settings, or LIMIT/CAPACITY.
Defined in src/poly/sparse.mojo.
variables¶
def variables[I: Iterable, P: Copyable & Deinitable, C: Copyable & Deinitable](values: I, mut budget: Budget) raises PolyError -> List[Int] where (_Element[I] == Tuple[P, C] and _Kind[C] >= 0)
Return the sorted axes occurring in stored nonzero terms.
Parameters.
I: The inferred sparse input iterable.P: The common sparse power shape.C: The inferred exact coefficient type.
Arguments.
values: Sparse terms or a prepared array.budget: The shared query allowance.
Returns. Occurring axis numbers; constants and zero return an empty list.
Raises.
PolyError: DOMAIN for invalid input, or LIMIT/CAPACITY.
Defined in src/poly/sparse.mojo.
derivative¶
def derivative[I: Iterable, P: Copyable & Deinitable, C: Copyable & Deinitable](values: I, mut budget: Budget, *, axis: Int = 0) raises PolyError -> Array[P, _Kind[C]] where _Element[I] == Tuple[P, C]
Differentiate along the selected variable, numbered from zero.
Parameters.
I: The inferred input iterable type.P: The power shape: Int or a tuple of Int powers.C: The inferred input coefficient type.
Arguments.
values: The coefficient sequence, sparse terms, or prepared array.budget: The caller-owned work allowance, shared through preparation and computation.axis: The zero-based variable index.
Returns. The derivative, retaining the exact coefficient domain.
Raises.
PolyError: LIMIT on exhausted work, CAPACITY on unrepresentable sizes, or DOMAIN for incompatible input.
Defined in src/poly/sparse.mojo.
integral¶
def integral[I: Iterable, P: Copyable & Deinitable, C: Copyable & Deinitable](values: I, mut budget: Budget, *, axis: Int = 0) raises PolyError -> Array[P, _FieldKind[_Kind[C]]] where _Element[I] == Tuple[P, C]
Integrate along an axis with zero constant, promoting integers to rationals.
Other domains are retained. In a prime field, a nonzero coefficient that requires division by zero raises DOMAIN. Axis numbers start at zero.
Parameters.
I: The inferred input iterable type.P: The power shape: Int or a tuple of Int powers.C: The inferred input coefficient type.
Arguments.
values: The coefficient sequence, sparse terms, or prepared array.budget: The caller-owned work allowance, shared through preparation and computation.axis: The zero-based variable index.
Returns. The zero-constant antiderivative; integer coefficients promote to QQ.
Raises.
PolyError: LIMIT on exhausted work, CAPACITY on unrepresentable sizes, or DOMAIN for incompatible input.
Defined in src/poly/sparse.mojo.
definite_integral¶
def definite_integral[I: Iterable, P: Copyable & Deinitable, C: Copyable & Deinitable, T: Copyable & Deinitable, U: Copyable & Deinitable](values: I, low: T, high: U, mut budget: Budget, *, axis: Int = 0) raises PolyError -> Array[P, _FieldKind[_Join[_Kind[C], _Join[_Kind[T], _Kind[U]]]]] where _Element[I] == Tuple[P, C]
Integrate out one axis between exact scalar endpoints; integers promote to QQ.
Integer coefficients and endpoints promote to QQ. In a prime field, a nonzero term needing a noninvertible antiderivative denominator raises DOMAIN. Sparse integration retains all axes, with exponent zero on the integrated axis.
Parameters.
I: The inferred input iterable type.P: The power shape: Int or a tuple of Int powers.C: The inferred input coefficient type.T: The sequence's exact scalar type.U: The inferred type of the second exact scalar.
Arguments.
values: The coefficient sequence, sparse terms, or prepared array.low: The exact lower integration endpoint.high: The exact upper integration endpoint.budget: The caller-owned work allowance, shared through preparation and computation.axis: The zero-based variable index.
Returns. The exact endpoint difference of an antiderivative; a scalar for dense input or an array retaining the sparse power shape.
Raises.
PolyError: LIMIT on exhausted work, CAPACITY on unrepresentable sizes, DOMAIN for invalid input, or UNSUPPORTED for a documented domain restriction.
Defined in src/poly/sparse.mojo.
compose¶
def compose[A: Iterable, B: Iterable, P: Copyable & Deinitable, C: Copyable & Deinitable, D: Copyable & Deinitable](a: A, b: B, mut budget: Budget) raises PolyError -> Array[P, _Join[_Kind[C], _Kind[D]]] where _Element[A] == Tuple[P, C] and _Element[B] == Tuple[P, D]
Compose univariate polynomials as a(b(x)); use substitute for several axes.
Parameters.
A: The first inferred iterable type.B: The second inferred iterable type.P: The power shape: Int or a tuple of Int powers.C: The inferred input coefficient type.D: The second inferred coefficient type.
Arguments.
a: The first polynomial.b: The second polynomial.budget: The caller-owned work allowance, shared through preparation and computation.
Returns. The outer polynomial evaluated at the inner polynomial.
Raises.
PolyError: LIMIT on exhausted work, CAPACITY on unrepresentable sizes, DOMAIN for invalid input, or UNSUPPORTED for a documented domain restriction.
Defined in src/poly/sparse.mojo.
substitute¶
def substitute[A: Iterable, B: Iterable, P: Copyable & Deinitable, C: Copyable & Deinitable, D: Copyable & Deinitable](values: A, replacements: B, mut budget: Budget, *, axes: List[Int] = List[Int]()) raises PolyError -> Array[P, _Join[_Kind[C], _Kind[D]]] where _Element[A] == Tuple[P, C] and _Element[_Nested[B]] == Tuple[P, D]
Replace axes simultaneously; replacements retain the same power shape.
Replacements are evaluated in the original variables; they are not recursively substituted into one another. By default there must be one replacement per axis. Explicit axes select a subset; duplicates and invalid axes raise DOMAIN.
Parameters.
A: The first inferred iterable type.B: The second inferred iterable type.P: The power shape: Int or a tuple of Int powers.C: The inferred input coefficient type.D: The second inferred coefficient type.
Arguments.
values: The coefficient sequence, sparse terms, or prepared array.replacements: A finite iterable of replacement polynomials of one Mojo input type and the same power shape.budget: The caller-owned work allowance, shared through preparation and computation.axes: Distinct zero-based axes to replace; an empty list assigns every axis in order.
Returns. The simultaneously substituted polynomial in the common exact domain, with unchanged power shape.
Raises.
PolyError: LIMIT on exhausted work, CAPACITY on unrepresentable sizes, DOMAIN for invalid input, or UNSUPPORTED for a documented domain restriction.
Defined in src/poly/sparse.mojo.
affine_transform¶
def affine_transform[I: Iterable, P: Copyable & Deinitable, C: Copyable & Deinitable, T: Copyable & Deinitable, U: Copyable & Deinitable](values: I, scale: T, shift: U, mut budget: Budget, *, axis: Int = 0) raises PolyError -> Array[P, _Join[_Kind[C], _Join[_Kind[T], _Kind[U]]]] where _Element[I] == Tuple[P, C]
Substitute scale*x + shift along one axis, retaining the power shape.
Parameters.
I: The inferred input iterable type.P: The power shape: Int or a tuple of Int powers.C: The inferred input coefficient type.T: The sequence's exact scalar type.U: The inferred type of the second exact scalar.
Arguments.
values: The coefficient sequence, sparse terms, or prepared array.scale: The exact multiplier of the selected variable.shift: The exact constant added to the scaled variable.budget: The caller-owned work allowance, shared through preparation and computation.axis: The zero-based variable index.
Returns. The polynomial with the selected variable replaced by scale*x + shift.
Raises.
PolyError: LIMIT on exhausted work, CAPACITY on unrepresentable sizes, DOMAIN for invalid input, or UNSUPPORTED for a documented domain restriction.
Defined in src/poly/sparse.mojo.
taylor_shift¶
def taylor_shift[I: Iterable, P: Copyable & Deinitable, C: Copyable & Deinitable, T: Copyable & Deinitable](values: I, point: T, mut budget: Budget, *, axis: Int = 0) raises PolyError -> Array[P, _Join[_Kind[C], _Kind[T]]] where _Element[I] == Tuple[P, C]
Shift one axis by an exact scalar, retaining the power shape.
Parameters.
I: The inferred input iterable type.P: The power shape: Int or a tuple of Int powers.C: The inferred input coefficient type.T: The sequence's exact scalar type.
Arguments.
values: The coefficient sequence, sparse terms, or prepared array.point: An exact scalar for one variable, or a coordinate tuple in variable order.budget: The caller-owned work allowance, shared through preparation and computation.axis: The zero-based variable index.
Returns. The polynomial with the selected variable replaced by x + point.
Raises.
PolyError: LIMIT on exhausted work, CAPACITY on unrepresentable sizes, DOMAIN for invalid input, or UNSUPPORTED for a documented domain restriction.
Defined in src/poly/sparse.mojo.
Exact algebra¶
Use method="modular" on gcd or gcd_checked to select sparse modular
reconstruction over ZZ or QQ. The default "auto" preserves core dispatch.
Exact divmod, divide_many, and their checked counterparts accept order=
and axes=. These select the reduction order; returned arrays still use
canonical increasing lexicographic storage. See the worked
examples.
divmod¶
def divmod[A: Iterable, B: Iterable, P: Copyable & Deinitable, C: Copyable & Deinitable, D: Copyable & Deinitable](a: A, b: B, mut budget: Budget, *, order: String = "lex", axes: List[Int] = List[Int]()) raises PolyError -> Tuple[Array[P, _FieldKind[_Join[_Kind[C], _Kind[D]]]], Array[P, _FieldKind[_Join[_Kind[C], _Kind[D]]]]] where (_Element[A] == Tuple[P, C] and _Element[B] == Tuple[P, D])
Return quotient and remainder in the requested monomial order.
Integer inputs promote to QQ. A zero divisor raises DOMAIN. For several variables, the remainder is reduced by the divisor's leading monomial; order defaults to lex with axis zero first. Returned arrays keep canonical storage order.
Parameters.
A: The first inferred iterable type.B: The second inferred iterable type.P: The power shape: Int or a tuple of Int powers.C: The inferred input coefficient type.D: The second inferred coefficient type.
Arguments.
a: The first polynomial.b: The second polynomial.budget: The caller-owned work allowance, shared through preparation and computation.order: One of lex, grlex, or grevlex; defaults to lex.axes: All axes in descending priority; empty uses tuple order.
Returns. A pair (quotient, remainder); integer coefficients promote to QQ.
Raises.
PolyError: LIMIT on exhausted work, CAPACITY on unrepresentable sizes, or DOMAIN for incompatible input.
Defined in src/poly/sparse.mojo.
divide_exact¶
def divide_exact[A: Iterable, B: Iterable, P: Copyable & Deinitable, C: Copyable & Deinitable, D: Copyable & Deinitable](a: A, b: B, mut budget: Budget) raises PolyError -> Optional[Array[P, _Join[_Kind[C], _Kind[D]]]] where _Element[A] == Tuple[P, C] and _Element[B] == Tuple[P, D]
Return a quotient in the inferred ring, or None when division is not exact.
Integer inputs stay in ZZ unless another operand widens the domain. Use divmod for field division or an explicit Rational coefficient to request QQ.
Parameters.
A: The first inferred iterable type.B: The second inferred iterable type.P: The power shape: Int or a tuple of Int powers.C: The inferred input coefficient type.D: The second inferred coefficient type.
Arguments.
a: The first polynomial.b: The second polynomial.budget: The caller-owned work allowance, shared through preparation and computation.
Returns. A quotient in the inferred coefficient ring, or None if that ring contains no exact quotient.
Raises.
PolyError: LIMIT on exhausted work, CAPACITY on unrepresentable sizes, DOMAIN for invalid input, or UNSUPPORTED for a documented domain restriction.
Defined in src/poly/sparse.mojo.
pseudo_divmod¶
def pseudo_divmod[A: Iterable, B: Iterable, P: Copyable & Deinitable, C: Copyable & Deinitable, D: Copyable & Deinitable](a: A, b: B, mut budget: Budget) raises PolyError -> Tuple[_Scalar[_Join[_Kind[C], _Kind[D]]], Array[P, _Join[_Kind[C], _Kind[D]]], Array[P, _Join[_Kind[C], _Kind[D]]]] where _Element[A] == Tuple[P, C] and _Element[B] == Tuple[P, D]
Return univariate (scale, q, r) with scalea = qb + r in the inferred ring.
The remainder has smaller degree than the divisor. Sparse input must have one axis and is converted to dense storage; use a finite work limit for large sparse powers.
Parameters.
A: The first inferred iterable type.B: The second inferred iterable type.P: The power shape: Int or a tuple of Int powers.C: The inferred input coefficient type.D: The second inferred coefficient type.
Arguments.
a: The first polynomial.b: The second polynomial.budget: The caller-owned work allowance, shared through preparation and computation.
Returns. The tuple (scale, q, r), where scale = lc(b)*max(deg(a)-deg(b)+1, 0) and scalea = q*b + r.
Raises.
PolyError: LIMIT on exhausted work, CAPACITY on unrepresentable sizes, DOMAIN for invalid input, or UNSUPPORTED for a documented domain restriction.
Defined in src/poly/sparse.mojo.
divide_many¶
def divide_many[A: Iterable, B: Iterable, P: Copyable & Deinitable, C: Copyable & Deinitable, D: Copyable & Deinitable](values: A, divisors: B, mut budget: Budget, *, order: String = "lex", axes: List[Int] = List[Int]()) raises PolyError -> Tuple[List[Array[P, _FieldKind[_Join[_Kind[C], _Kind[D]]]]], Array[P, _FieldKind[_Join[_Kind[C], _Kind[D]]]]] where _Element[A] == Tuple[P, C] and _Element[_Nested[B]] == Tuple[P, D]
Return ordered quotients and a remainder; integer coefficients promote to QQ.
Sparse reduction uses the requested monomial order; lex with axis zero first is the default. Returned arrays keep canonical storage order. Changing divisor order can change quotients and remainder; this is not a Groebner-basis computation. An empty divisor collection returns no quotients and the promoted input as remainder. A zero divisor raises DOMAIN.
Parameters.
A: The first inferred iterable type.B: The second inferred iterable type.P: The power shape: Int or a tuple of Int powers.C: The inferred input coefficient type.D: The second inferred coefficient type.
Arguments.
values: The coefficient sequence, sparse terms, or prepared array.divisors: A finite iterable of polynomials of one Mojo input type, tried in the supplied order.budget: The caller-owned work allowance, shared through preparation and computation.order: One of lex, grlex, or grevlex; defaults to lex.axes: All axes in descending priority; empty uses tuple order.
Returns. A quotient list in divisor order and a remainder, with input = sum(quotient_i * divisor_i) + remainder.
Raises.
PolyError: LIMIT on exhausted work, CAPACITY on unrepresentable sizes, DOMAIN for invalid input, or UNSUPPORTED for a documented domain restriction.
Defined in src/poly/sparse.mojo.
content¶
def content[I: Iterable, P: Copyable & Deinitable, C: Copyable & Deinitable](values: I, mut budget: Budget, *, axis: Int = 0) raises PolyError -> Array[P, _Kind[C]] where _Element[I] == Tuple[P, C]
Return the coefficient content in the other axes.
Integer content is nonnegative. Field content is monic; a nonzero univariate field polynomial has content one. Zero has content zero.
Parameters.
I: The inferred input iterable type.P: The power shape: Int or a tuple of Int powers.C: The inferred input coefficient type.
Arguments.
values: The coefficient sequence, sparse terms, or prepared array.budget: The caller-owned work allowance, shared through preparation and computation.axis: The zero-based variable index.
Returns. The normalized coefficient GCD; a scalar for dense input or a polynomial in the remaining sparse axes.
Raises.
PolyError: LIMIT on exhausted work, CAPACITY on unrepresentable sizes, DOMAIN for invalid input, or UNSUPPORTED for a documented domain restriction.
Defined in src/poly/sparse.mojo.
primitive_part¶
def primitive_part[I: Iterable, P: Copyable & Deinitable, C: Copyable & Deinitable](values: I, mut budget: Budget, *, axis: Int = 0) raises PolyError -> Array[P, _Kind[C]] where _Element[I] == Tuple[P, C]
Remove the content with respect to one axis.
Parameters.
I: The inferred input iterable type.P: The power shape: Int or a tuple of Int powers.C: The inferred input coefficient type.
Arguments.
values: The coefficient sequence, sparse terms, or prepared array.budget: The caller-owned work allowance, shared through preparation and computation.axis: The zero-based variable index.
Returns. The input divided by its content, or zero for a zero input.
Raises.
PolyError: LIMIT on exhausted work, CAPACITY on unrepresentable sizes, DOMAIN for invalid input, or UNSUPPORTED for a documented domain restriction.
Defined in src/poly/sparse.mojo.
gcd¶
def gcd[A: Iterable, B: Iterable, P: Copyable & Deinitable, C: Copyable & Deinitable, D: Copyable & Deinitable](a: A, b: B, mut budget: Budget, *, method: String = "auto") raises PolyError -> Array[P, _Join[_Kind[C], _Kind[D]]] where _Element[A] == Tuple[P, C] and _Element[B] == Tuple[P, D]
Return a positive-leading integer GCD or a monic field GCD.
Parameters.
A: The first inferred iterable type.B: The second inferred iterable type.P: The power shape: Int or a tuple of Int powers.C: The inferred input coefficient type.D: The second inferred coefficient type.
Arguments.
a: The first polynomial.b: The second polynomial.budget: The caller-owned work allowance, shared through preparation and computation.method: Use auto for existing dispatch or modular for sparse reconstruction over ZZ or QQ.
Returns. The positive-leading integer GCD, including integer content, or the monic field GCD. GCD(0, 0) is zero.
Raises.
PolyError: LIMIT on exhausted work, CAPACITY on unrepresentable sizes, DOMAIN for invalid input, or UNSUPPORTED for a documented domain restriction.
Defined in src/poly/sparse.mojo.
extended_gcd¶
def extended_gcd[A: Iterable, B: Iterable, P: Copyable & Deinitable, C: Copyable & Deinitable, D: Copyable & Deinitable](a: A, b: B, mut budget: Budget) raises PolyError -> Tuple[Array[P, _FieldKind[_Join[_Kind[C], _Kind[D]]]], Array[P, _FieldKind[_Join[_Kind[C], _Kind[D]]]], Array[P, _FieldKind[_Join[_Kind[C], _Kind[D]]]]] where _Element[A] == Tuple[P, C] and _Element[B] == Tuple[P, D]
Return univariate (g, u, v) with ua + vb = g; integers promote to QQ.
Sparse input must have one axis and is converted to dense storage. For several variables, use gcd or the core certificate API.
Parameters.
A: The first inferred iterable type.B: The second inferred iterable type.P: The power shape: Int or a tuple of Int powers.C: The inferred input coefficient type.D: The second inferred coefficient type.
Arguments.
a: The first polynomial.b: The second polynomial.budget: The caller-owned work allowance, shared through preparation and computation.
Returns. The tuple (g, u, v) with ua + vb = g and monic nonzero g; integers promote to QQ.
Raises.
PolyError: LIMIT on exhausted work, CAPACITY on unrepresentable sizes, DOMAIN for invalid input, or UNSUPPORTED for a documented domain restriction.
Defined in src/poly/sparse.mojo.
resultant¶
def resultant[A: Iterable, B: Iterable, P: Copyable & Deinitable, C: Copyable & Deinitable, D: Copyable & Deinitable](a: A, b: B, mut budget: Budget, *, axis: Int = 0) raises PolyError -> Array[P, _Join[_Kind[C], _Kind[D]]] where _Element[A] == Tuple[P, C] and _Element[B] == Tuple[P, D]
Eliminate the variable using the Sylvester sign convention.
Two nonzero constants in the elimination variable raise DOMAIN; a zero operand returns zero. Sparse output retains the eliminated axis with exponent zero.
Parameters.
A: The first inferred iterable type.B: The second inferred iterable type.P: The power shape: Int or a tuple of Int powers.C: The inferred input coefficient type.D: The second inferred coefficient type.
Arguments.
a: The first polynomial.b: The second polynomial.budget: The caller-owned work allowance, shared through preparation and computation.axis: The zero-based variable index.
Returns. The Sylvester-convention resultant; a scalar for dense input or an array retaining the sparse power shape.
Raises.
PolyError: LIMIT on exhausted work, CAPACITY on unrepresentable sizes, DOMAIN for invalid input, or UNSUPPORTED for a documented domain restriction.
Defined in src/poly/sparse.mojo.
subresultants¶
def subresultants[A: Iterable, B: Iterable, P: Copyable & Deinitable, C: Copyable & Deinitable, D: Copyable & Deinitable](a: A, b: B, mut budget: Budget, *, axis: Int = 0) raises PolyError -> List[Array[P, _Join[_Kind[C], _Kind[D]]]] where _Element[A] == Tuple[P, C] and _Element[B] == Tuple[P, D]
Return the indexed subresultants, retaining zero entries.
Parameters.
A: The first inferred iterable type.B: The second inferred iterable type.P: The power shape: Int or a tuple of Int powers.C: The inferred input coefficient type.D: The second inferred coefficient type.
Arguments.
a: The first polynomial.b: The second polynomial.budget: The caller-owned work allowance, shared through preparation and computation.axis: The zero-based variable index.
Returns. The list S_0 through S_(min(deg(a), deg(b))-1), including zeros; empty when the smaller degree is nonpositive.
Raises.
PolyError: LIMIT on exhausted work, CAPACITY on unrepresentable sizes, DOMAIN for invalid input, or UNSUPPORTED for a documented domain restriction.
Defined in src/poly/sparse.mojo.
Factorization keeps the inferred domain and supports several variables over
AA and QQbar. Tuple powers retain unused axes. Univariate factors have degree
at most two over AA and one over QQbar; multivariate irreducibles can have
higher degree in either field. See
algebraic factorization
for a complete example.
factor¶
def factor[I: Iterable, P: Copyable & Deinitable, C: Copyable & Deinitable](values: I, mut budget: Budget, *, seed: UInt64 = 0) raises PolyError -> Tuple[_Scalar[_Kind[C]], List[Tuple[Array[P, _Kind[C]], Int]]] where _Element[I] == Tuple[P, C]
Return a scalar and irreducible factors in the inferred exact domain.
ZZ factors are primitive with positive leading coefficient; factors over fields are monic. Zero and constants have no factors. Repeated factors retain their exact multiplicities, including inseparable prime-field inputs. Factors retain deterministic ordering. AA and QQbar support any number of active variables and preserve the full power shape. In one variable, AA factors have degree one or two and QQbar factors are linear; multivariate irreducibles can have higher degree. Multivariate algebraic factors sort by total degree, then compare term lists from greatest monomial to least, comparing each monomial before its coefficient (real component before imaginary component). Their greatest stored coefficient is one. Multivariable QQi, prime-field, AA and QQbar factorization uses budgeted dense Kronecker images and potentially exponential recombination. Algebraic inputs first remove coordinate factors, repeated factors, and coefficient content; dense storage is charged before allocation.
Parameters.
I: The inferred input iterable type.P: The power shape: Int or a tuple of Int powers.C: The inferred input coefficient type.
Arguments.
values: The coefficient sequence, sparse terms, or prepared array.budget: The caller-owned work allowance, shared through preparation and computation.seed: The deterministic finite-field splitting seed; defaults to zero and is ignored outside finite fields.
Returns. The tuple (scalar, factors), where each entry is (irreducible polynomial, positive multiplicity) and their powered product times the scalar equals the input.
Raises.
PolyError: LIMIT on exhausted work, CAPACITY on unrepresentable sizes, DOMAIN for invalid input, or UNSUPPORTED for a documented domain restriction.
Defined in src/poly/sparse.mojo.
squarefree¶
def squarefree[I: Iterable, P: Copyable & Deinitable, C: Copyable & Deinitable](values: I, mut budget: Budget) raises PolyError -> Tuple[_Scalar[_FieldKind[_Kind[C]]], List[Tuple[Array[P, _FieldKind[_Kind[C]]], Int]]] where _Element[I] == Tuple[P, C]
Return monic multiplicity blocks for a sparse polynomial in any number of variables.
Blocks group irreducible factors with the same multiplicity and need not themselves be irreducible. ZZ inputs promote to QQ; QQ, QQi and prime fields retain their domains. Zero and constants have no blocks. Prime-field decomposition includes inverse Frobenius when derivatives vanish. All power shapes are supported; ordinary decomposition operates directly on sparse terms.
Parameters.
I: The inferred input iterable type.P: The power shape: Int or a tuple of Int powers.C: The inferred input coefficient type.
Arguments.
values: The coefficient sequence, sparse terms, or prepared array.budget: The caller-owned work allowance, shared through preparation and computation.
Returns. The tuple (leading scalar, blocks), where each entry is (monic block, positive multiplicity), ordered by multiplicity.
Raises.
PolyError: LIMIT on exhausted work, CAPACITY on unrepresentable sizes, DOMAIN for invalid input, or UNSUPPORTED for a documented domain restriction.
Defined in src/poly/sparse.mojo.
Evaluation¶
evaluate¶
def evaluate[I: Iterable, P: Copyable & Deinitable, C: Copyable & Deinitable, *Ts: Copyable & Deinitable](values: I, point: Tuple[*Ts], mut budget: Budget) raises PolyError -> _Evaluation[C, Tuple[*Ts]] where _Element[I] == Tuple[P, C]
Evaluate at exact coordinates in variable order.
Parameters.
I: The inferred input iterable type.P: The power shape: Int or a tuple of Int powers.C: The inferred input coefficient type.Ts: The inferred element types of the input tuple.
Arguments.
values: The coefficient sequence, sparse terms, or prepared array.point: An exact scalar for one variable, or a coordinate tuple in variable order.budget: The caller-owned work allowance, shared through preparation and computation.
Returns. The exact scalar after joint promotion, or an algebraic Real for algebraic coordinates.
Raises.
PolyError: LIMIT on exhausted work, CAPACITY on unrepresentable sizes, or DOMAIN for incompatible input.
Defined in src/poly/sparse.mojo.
evaluate_many¶
def evaluate_many[I: Iterable, X: Iterable, P: Copyable & Deinitable, C: Copyable & Deinitable](values: I, points: X, mut budget: Budget) raises PolyError -> Values[_Scalar[_Join[_Kind[C], _Kind[_Element[X]]]], _Join[_Kind[C], _Kind[_Element[X]]]] where (_Element[I] == Tuple[P, C] and _Kind[_Element[X]] >= 0)
Evaluate at each point, returning values in input order, including zeros.
Multivariate points are coordinate tuples. The polynomial is prepared and promoted once; every point must use the same exact coefficient domain.
Parameters.
I: The inferred input iterable type.X: The inferred point or point-sequence type.P: The power shape: Int or a tuple of Int powers.C: The inferred input coefficient type.
Arguments.
values: The coefficient sequence, sparse terms, or prepared array.points: A one-dimensional sequence of exact points, in output order.budget: The caller-owned work allowance, shared through preparation and computation.
Returns. An immutable Values sequence, preserving every input point and returned zero.
Raises.
PolyError: LIMIT on exhausted work, CAPACITY on unrepresentable sizes, or DOMAIN for incompatible input.
Defined in src/poly/sparse.mojo.
Roots and polynomial systems¶
See root workflows and the Gröbner and CAD tutorials for complete examples.
real_roots¶
def real_roots[I: Iterable, P: Copyable & Deinitable, C: Copyable & Deinitable](values: I, mut budget: Budget) raises PolyError -> _roots.ExactRoots where _Element[I] == Tuple[P, C]
Find every distinct real root of a univariate sparse polynomial.
Parameters.
I: The inferred input type.P: The inferred power shape.C: The inferred input type.
Arguments.
values: Univariate integer or rational sparse terms, or a prepared array.budget: The shared work allowance for preparation and computation.
Returns. The computed result, with its evidence retained.
Raises.
PolyError: DOMAIN for incompatible input, UNSUPPORTED for an unavailable operation, or LIMIT/CAPACITY on resource limits.
Defined in src/poly/sparse.mojo.
complex_roots¶
def complex_roots[I: Iterable, P: Copyable & Deinitable, C: Copyable & Deinitable](values: I, mut budget: Budget, *, axis: Int = 0) raises PolyError -> _roots.ComplexRoots where _Element[I] == Tuple[P, C]
Find every distinct exact complex root, with multiplicities.
Results use lexicographic real-part then imaginary-part order. Nonzero constants return no roots. Integer, rational, Gaussian-rational, AA, and QQbar coefficients are accepted; no numerical precision is needed.
Parameters.
I: The inferred input iterable type.P: The sparse power shape.C: The exact coefficient type.
Arguments.
values: Exact sparse terms or a prepared sparse array.budget: The shared work allowance, including preparation and verification.axis: The zero-based root variable; all other axes must be absent.
Returns. Exact algebraic.Complex values with multiplicities and completeness evidence.
Raises.
PolyError: DOMAIN for zero or incompatible input, or LIMIT/CAPACITY on resource limits.
Defined in src/poly/sparse.mojo.
root_between¶
def root_between[I: Iterable, P: Copyable & Deinitable, C: Copyable & Deinitable, L: Copyable & Deinitable, H: Copyable & Deinitable](values: I, low: L, high: H, mut budget: Budget) raises PolyError -> _algebraic.Real where _Element[I] == Tuple[P, C]
Count or select roots between exact endpoints.
Parameters.
I: The inferred input type.P: The inferred power shape.C: The inferred input type.L: The inferred input type.H: The inferred input type.
Arguments.
values: Univariate integer or rational terms.low: The lower exact endpoint.high: The upper exact endpoint.budget: The shared work allowance for preparation and computation.
Returns. The computed result, with its evidence retained.
Raises.
PolyError: DOMAIN for incompatible input, UNSUPPORTED for an unavailable operation, or LIMIT/CAPACITY on resource limits.
Defined in src/poly/sparse.mojo.
count_roots¶
def count_roots[I: Iterable, P: Copyable & Deinitable, C: Copyable & Deinitable, L: Copyable & Deinitable, H: Copyable & Deinitable](values: I, low: L, high: H, mut budget: Budget) raises PolyError -> _dense._Count[C, L, H] where _Element[I] == Tuple[P, C]
Count or select roots between exact endpoints.
Parameters.
I: The inferred input type.P: The inferred power shape.C: The inferred input type.L: The inferred input type.H: The inferred input type.
Arguments.
values: Univariate integer or rational terms.low: The lower exact endpoint.high: The upper exact endpoint.budget: The shared work allowance for preparation and computation.
Returns. The computed result, with its evidence retained.
Raises.
PolyError: DOMAIN for incompatible input, UNSUPPORTED for an unavailable operation, or LIMIT/CAPACITY on resource limits.
Defined in src/poly/sparse.mojo.
sturm_sequence¶
def sturm_sequence[I: Iterable, P: Copyable & Deinitable, C: Copyable & Deinitable](values: I, mut budget: Budget, *, axis: Int = 0) raises PolyError -> _sturm.SturmPlan where _Element[I] == Tuple[P, C]
Prepare a reusable rational Sturm chain for root and sign-variation queries.
Parameters.
I: The inferred polynomial iterable.P: The sparse power shape.C: The integer or rational coefficient type.
Arguments.
values: Nonzero sparse polynomial terms over ZZ or QQ.budget: The shared preparation allowance.axis: The only axis allowed to have nonzero powers.
Returns. An immutable plan retaining the polynomial, chain, and quotient witnesses.
Raises.
PolyError: DOMAIN for zero or an invalid axis, or LIMIT/CAPACITY.
Defined in src/poly/sparse.mojo.
sign_on_interval¶
def sign_on_interval[I: Iterable, P: Copyable & Deinitable, C: Copyable & Deinitable, L: Copyable & Deinitable, H: Copyable & Deinitable](values: I, low: L, high: H, mut budget: Budget) raises PolyError -> Optional[Int] where _Element[I] == Tuple[P, C]
Determine the strict sign throughout a closed exact interval.
Parameters.
I: The inferred input type.P: The inferred power shape.C: The inferred input type.L: The inferred input type.H: The inferred input type.
Arguments.
values: Univariate integer or rational terms.low: The lower exact endpoint.high: The upper exact endpoint, possibly equal to low.budget: The shared work allowance for preparation and computation.
Returns. Positive or negative one on a root-free closed interval; None if a root occurs, including either endpoint. The zero polynomial returns None.
Raises.
PolyError: DOMAIN for incompatible input, UNSUPPORTED for an unavailable operation, or LIMIT/CAPACITY on resource limits.
Defined in src/poly/sparse.mojo.
real_root_cover¶
def real_root_cover[I: Iterable, P: Copyable & Deinitable, C: Copyable & Deinitable](values: I, mut budget: Budget, *, options: NumericOptions = NumericOptions(), complete_only: Bool = False) raises PolyError -> _dense._RealCover[_Kind[C]] where _Element[I] == Tuple[P, C]
Prepare a real root cover.
The sparse polynomial is converted to dense storage under the shared budget. Only one-variable power shapes are accepted.
Parameters.
I: The inferred input type.P: The inferred power shape.C: The inferred input type.
Arguments.
values: A univariate sparse polynomial with exact coefficients.budget: The shared work allowance for preparation and computation.options: The precision and root-cover settings.complete_only: Raise unless all requested properties succeed.
Returns. The computed result, with its evidence retained.
Raises.
PolyError: DOMAIN for incompatible input, UNSUPPORTED for an unavailable operation, or LIMIT/CAPACITY on resource limits.
Defined in src/poly/sparse.mojo.
complex_root_cover¶
def complex_root_cover[I: Iterable, P: Copyable & Deinitable, C: Copyable & Deinitable](values: I, mut budget: Budget, *, options: NumericOptions = NumericOptions(), complete_only: Bool = False) raises PolyError -> _dense._ComplexCover[_Kind[C]] where _Element[I] == Tuple[P, C]
Prepare a complex root cover.
The sparse polynomial is converted to dense storage under the shared budget. Only one-variable power shapes are accepted.
Parameters.
I: The inferred input type.P: The inferred power shape.C: The inferred input type.
Arguments.
values: A univariate sparse polynomial with exact coefficients.budget: The shared work allowance for preparation and computation.options: The precision and root-cover settings.complete_only: Raise unless all requested properties succeed.
Returns. The computed result, with its evidence retained.
Raises.
PolyError: DOMAIN for incompatible input, UNSUPPORTED for an unavailable operation, or LIMIT/CAPACITY on resource limits.
Defined in src/poly/sparse.mojo.
real_root_cover_to¶
def real_root_cover_to[I: Iterable, P: Copyable & Deinitable, C: Copyable & Deinitable, S: RealRootSink](values: I, mut sink: S, mut budget: Budget, *, options: NumericOptions = NumericOptions(), complete_only: Bool = False) raises PolyError -> RootStreamReceipt where _Element[I] == Tuple[P, C]
Prepare a real root cover stream.
The sparse polynomial is converted to dense storage under the shared budget. Only one-variable power shapes are accepted.
Parameters.
I: The inferred input type.P: The inferred power shape.C: The inferred input type.S: The inferred input type.
Arguments.
values: A univariate sparse polynomial with exact coefficients.sink: The incremental witness consumer.budget: The shared work allowance for preparation and computation.options: The precision and root-cover settings.complete_only: Raise unless all requested properties succeed.
Returns. The computed result, with its evidence retained.
Raises.
PolyError: DOMAIN for incompatible input, UNSUPPORTED for an unavailable operation, or LIMIT/CAPACITY on resource limits.
Defined in src/poly/sparse.mojo.
complex_root_cover_to¶
def complex_root_cover_to[I: Iterable, P: Copyable & Deinitable, C: Copyable & Deinitable, S: ComplexRootSink](values: I, mut sink: S, mut budget: Budget, *, options: NumericOptions = NumericOptions(), complete_only: Bool = False) raises PolyError -> RootStreamReceipt where _Element[I] == Tuple[P, C]
Prepare a complex root cover stream.
The sparse polynomial is converted to dense storage under the shared budget. Only one-variable power shapes are accepted.
Parameters.
I: The inferred input type.P: The inferred power shape.C: The inferred input type.S: The inferred input type.
Arguments.
values: A univariate sparse polynomial with exact coefficients.sink: The incremental witness consumer.budget: The shared work allowance for preparation and computation.options: The precision and root-cover settings.complete_only: Raise unless all requested properties succeed.
Returns. The computed result, with its evidence retained.
Raises.
PolyError: DOMAIN for incompatible input, UNSUPPORTED for an unavailable operation, or LIMIT/CAPACITY on resource limits.
Defined in src/poly/sparse.mojo.
real_root_checker¶
def real_root_checker[I: Iterable, P: Copyable & Deinitable, C: Copyable & Deinitable](values: I, mut budget: Budget, *, options: NumericOptions = NumericOptions()) raises PolyError -> _dense._RealChecker[_Kind[C]] where _Element[I] == Tuple[P, C]
Prepare a real root stream checker.
The sparse polynomial is converted to dense storage under the shared budget. Only one-variable power shapes are accepted.
Parameters.
I: The inferred input type.P: The inferred power shape.C: The inferred input type.
Arguments.
values: A univariate sparse polynomial with exact coefficients.budget: The shared work allowance for preparation and computation.options: The precision and root-cover settings.
Returns. The computed result, with its evidence retained.
Raises.
PolyError: DOMAIN for incompatible input, UNSUPPORTED for an unavailable operation, or LIMIT/CAPACITY on resource limits.
Defined in src/poly/sparse.mojo.
complex_root_checker¶
def complex_root_checker[I: Iterable, P: Copyable & Deinitable, C: Copyable & Deinitable](values: I, mut budget: Budget, *, options: NumericOptions = NumericOptions()) raises PolyError -> _dense._ComplexChecker[_Kind[C]] where _Element[I] == Tuple[P, C]
Prepare a complex root stream checker.
The sparse polynomial is converted to dense storage under the shared budget. Only one-variable power shapes are accepted.
Parameters.
I: The inferred input type.P: The inferred power shape.C: The inferred input type.
Arguments.
values: A univariate sparse polynomial with exact coefficients.budget: The shared work allowance for preparation and computation.options: The precision and root-cover settings.
Returns. The computed result, with its evidence retained.
Raises.
PolyError: DOMAIN for incompatible input, UNSUPPORTED for an unavailable operation, or LIMIT/CAPACITY on resource limits.
Defined in src/poly/sparse.mojo.
Basis¶
@fieldwise_init
struct Basis[P: Copyable & Deinitable, k: Int](Copyable, Movable, Iterable, Sized)
A reusable reduced monic basis with original generator order retained.
Its polynomials use the usual canonical array storage. The retained core basis keeps the chosen computational monomial order. Copies share storage.
Parameters.
P: The sparse power shape.k: The inferred coefficient field kind.
Defined in src/poly/sparse.mojo.
Basis.IteratorType¶
comptime IteratorType[iterable_mut: Bool, //, iterable_origin: Origin[mut=iterable_mut]]: Iterator = _BasisIterator[Self.P, Self.k, ImmOrigin(iterable_origin)]
An iterator borrowing the prepared basis.
Parameters.
iterable_mut: Whether the source origin is mutable.iterable_origin: The source lifetime.
Basis.evidence¶
def evidence(self) -> ref[ImmOrigin(origin_of(self._data[].basis))] _CoreBasis[_Field[Self.k]]
Borrow the basis and optional original-generator cofactor rows.
Returns. Immutable core basis data in the requested monomial order.
groebner¶
def groebner[I: Iterable, P: Copyable & Deinitable, C: Copyable & Deinitable](generators: I, mut budget: Budget, *, order: String = "grevlex", axes: List[Int] = List[Int](), witnesses: Bool = True, certify: Bool = True) raises PolyError -> Basis[P, _FieldKind[_Kind[C]]] where _Element[_Nested[I]] == Tuple[P, C]
Compute a reusable reduced monic Groebner basis from sparse polynomials.
Integer coefficients promote to QQ. QQi and prime fields remain in their own fields. Set witnesses=False when only reduction or Boolean membership is needed.
Parameters.
I: The inferred input type.P: The inferred power shape.C: The inferred input type.
Arguments.
generators: A finite iterable of sparse term iterables or prepared arrays with one power shape.budget: The shared work allowance for preparation and computation.order: One of lex, grlex, or grevlex; defaults to grevlex.axes: Variable priority, highest first; defaults to increasing axis order.witnesses: Retain cofactor rows for membership witnesses and basis verification.certify: Over QQ without witnesses, prove the basis computed from modular images exactly; False skips the proof, and the result is then the reduced basis with high probability.
Returns. The computed result, with its evidence retained.
Raises.
PolyError: DOMAIN for incompatible input, UNSUPPORTED for an unavailable operation, or LIMIT/CAPACITY on resource limits.
Defined in src/poly/sparse.mojo.
reduce¶
def reduce[I: Iterable, P: Copyable & Deinitable, C: Copyable & Deinitable, k: Int](values: I, basis: Basis[P, k], mut budget: Budget) raises PolyError -> Array[P, k] where _Element[I] == Tuple[P, C]
Return the unique normal form modulo a prepared Groebner basis.
Parameters.
I: The inferred input type.P: The inferred power shape.C: The inferred input type.k: The inferred coefficient kind.
Arguments.
values: The sparse polynomial to reduce.basis: A prepared basis in the same field and power shape.budget: The shared work allowance for preparation and computation.
Returns. A canonical sparse polynomial array in the basis field.
Raises.
PolyError: DOMAIN for incompatible input, UNSUPPORTED for an unavailable operation, or LIMIT/CAPACITY on resource limits.
Defined in src/poly/sparse.mojo.
contains¶
def contains[I: Iterable, P: Copyable & Deinitable, C: Copyable & Deinitable, k: Int](values: I, basis: Basis[P, k], mut budget: Budget) raises PolyError -> Bool where _Element[I] == Tuple[P, C]
Test ideal membership using a prepared basis.
Parameters.
I: The inferred input type.P: The inferred power shape.C: The inferred input type.k: The inferred coefficient kind.
Arguments.
values: The sparse polynomial to test.basis: The prepared basis; cofactor tracking is not required.budget: The shared work allowance for preparation and computation.
Returns. True exactly when the normal form is zero. Exhausted work raises instead of returning False.
Raises.
PolyError: DOMAIN for incompatible input, UNSUPPORTED for an unavailable operation, or LIMIT/CAPACITY on resource limits.
Defined in src/poly/sparse.mojo.
Membership¶
@fieldwise_init
struct Membership[P: Copyable & Deinitable, k: Int](Copyable, Movable)
A checked-identity candidate against the original ordered generators.
Parameters.
P: The sparse power shape.k: The prepared coefficient field.
Defined in src/poly/sparse.mojo.
| Field | Type | |
|---|---|---|
cofactors |
Values[Array[Self.P, Self.k], Self.k] |
Multipliers in original generator order, with canonical array storage. |
Membership.evidence¶
def evidence(self) -> ref[ImmOrigin(origin_of(self._data[].certificate))] MembershipCertificate[_Field[Self.k]]
Borrow the exact membership identity certificate.
Returns. Immutable multipliers in original generator order.
membership¶
def membership[I: Iterable, P: Copyable & Deinitable, C: Copyable & Deinitable, k: Int](values: I, basis: Basis[P, k], mut budget: Budget) raises PolyError -> Optional[Membership[P, k]] where _Element[I] == Tuple[P, C]
Express a polynomial as a combination of the original generators.
Parameters.
I: The inferred input type.P: The inferred power shape.C: The inferred input type.k: The inferred coefficient kind.
Arguments.
values: The proposed ideal member.basis: A basis constructed with witnesses=True.budget: The shared work allowance for preparation and computation.
Returns. A membership witness, or None for a nonmember. Budget exhaustion raises.
Raises.
PolyError: DOMAIN for incompatible input, UNSUPPORTED for an unavailable operation, or LIMIT/CAPACITY on resource limits.
Defined in src/poly/sparse.mojo.
check_membership¶
def check_membership[P: Copyable & Deinitable, k: Int](result: Membership[P, k], mut budget: Budget) raises PolyError -> Bool
Verify the retained identity against the original generators.
Parameters.
P: The inferred power shape.k: The inferred coefficient kind.
Arguments.
result: The membership result, including its visible cofactor arrays.budget: The shared work allowance for preparation and computation.
Returns. Whether the multipliers prove the original membership identity.
Raises.
PolyError: DOMAIN for incompatible input, UNSUPPORTED for an unavailable operation, or LIMIT/CAPACITY on resource limits.
Defined in src/poly/sparse.mojo.
check_groebner¶
def check_groebner[P: Copyable & Deinitable, k: Int](basis: Basis[P, k], mut budget: Budget) raises PolyError -> Bool
Verify the Groebner property and equality with the original ideal.
This checks ideal equality and the Groebner property independently of the producer. It does not certify the reducedness or ordering of the basis.
Parameters.
P: The inferred power shape.k: The inferred coefficient kind.
Arguments.
basis: A basis produced with witnesses=True.budget: The shared work allowance for preparation and computation.
Returns. Whether both ideal containments and every Buchberger pair check succeed.
Raises.
PolyError: DOMAIN for incompatible input, UNSUPPORTED for an unavailable operation, or LIMIT/CAPACITY on resource limits.
Defined in src/poly/sparse.mojo.
dumps¶
def dumps[I: Iterable, P: Copyable & Deinitable, C: Copyable & Deinitable](values: I, mut budget: Budget) raises PolyError -> String where _Element[I] == Tuple[P, C]
Write canonical versioned polynomial text.
AA and QQbar retain their exact root witnesses, which are validated on load. Arithmetic history is not serialized. Other exact domains keep their existing format.
Parameters.
I: The inferred input iterable type.P: The sparse power shape or retained source array type, inferred from the input.C: The input coefficient type.
Arguments.
values: Input coefficients, sparse terms, or prepared values as required by this overload.budget: The shared work allowance, including preparation, computation, and result storage.
Returns. Canonical text including the final newline.
Raises.
PolyError: ENCODING for malformed or incompatible records, DOMAIN for invalid settings, or LIMIT/CAPACITY on resource limits.
Defined in src/poly/sparse.mojo.
loads¶
def loads[T: Copyable & Deinitable, *, ndim: Int = 1](text: String, mut budget: Budget, *, modulus: UInt64 = 0) raises PolyError -> Array[_Shape[ndim], _Kind[T]]
Read canonical text into an exact array; the scalar type selects the expected domain.
AA and QQbar retain their exact root witnesses, which are validated on load. Arithmetic history is not serialized. Other exact domains keep their existing format.
Parameters.
T: The scalar or batch item type.ndim: The expected sparse axis count, including unused axes; defaults to one.
Arguments.
text: One canonical versioned polynomial record.budget: The shared work allowance, including preparation, computation, and result storage.modulus: The expected prime modulus for ModInt records; zero outside that domain.
Returns. An exact array in the requested scalar domain.
Raises.
PolyError: ENCODING for malformed or incompatible records, DOMAIN for invalid settings, or LIMIT/CAPACITY on resource limits.
Defined in src/poly/sparse.mojo.
dump¶
def dump[I: Iterable, P: Copyable & Deinitable, C: Copyable & Deinitable, S: PolynomialTextSink](values: I, mut sink: S, mut budget: Budget) raises PolyError where _Element[I] == Tuple[P, C] and _Kind[C] >= 0
Write canonical versioned polynomial text in bounded chunks.
AA and QQbar retain their exact root witnesses, which are validated on load. Arithmetic history is not serialized. Other exact domains keep their existing format.
Parameters.
I: The inferred input iterable type.P: The sparse power shape or retained source array type, inferred from the input.C: The input coefficient type.S: The text transport implementation.
Arguments.
values: Input coefficients, sparse terms, or prepared values as required by this overload.sink: The destination for ordered text chunks.budget: The shared work allowance, including preparation, computation, and result storage.
Raises.
PolyError: ENCODING for malformed or incompatible records, DOMAIN for invalid settings, or LIMIT/CAPACITY on resource limits.
Defined in src/poly/sparse.mojo.
load¶
def load[T: Copyable & Deinitable, S: PolynomialTextSource, *, ndim: Int = 1](var source: S, mut budget: Budget, *, modulus: UInt64 = 0, max_field_bytes: Int = 16777216) raises PolyError -> Array[_Shape[ndim], _Kind[T]]
Read canonical text into an exact array; the scalar type selects the expected domain.
AA and QQbar retain their exact root witnesses, which are validated on load. Arithmetic history is not serialized. Other exact domains keep their existing format.
Parameters.
T: The scalar or batch item type.S: The text transport implementation.ndim: The expected sparse axis count, including unused axes; defaults to one.
Arguments.
source: An owned source of arbitrary text chunks.budget: The shared work allowance, including preparation, computation, and result storage.modulus: The expected prime modulus for ModInt records; zero outside that domain.max_field_bytes: Maximum bytes in one input field; defaults to 16 MiB.
Returns. An exact array decoded from the text stream.
Raises.
PolyError: ENCODING for malformed or incompatible records, DOMAIN for invalid settings, or LIMIT/CAPACITY on resource limits.
Defined in src/poly/sparse.mojo.
loads_numeric¶
def loads_numeric[T: Copyable & Deinitable, *, ndim: Int = 1](text: String, mut budget: Budget) raises PolyError -> NumericArray[_Shape[ndim], _num._StoredDomain[T]]
Restore stored numerical values exactly; subsequent arithmetic takes an explicit context.
Parameters.
T: The scalar or batch item type.ndim: The expected sparse axis count, including unused axes; defaults to one.
Arguments.
text: One canonical versioned polynomial record.budget: The shared work allowance, including preparation, computation, and result storage.
Returns. A numerical array preserving the encoded scalar precision and enclosures.
Raises.
PolyError: ENCODING for malformed or incompatible records, DOMAIN for invalid settings, or LIMIT/CAPACITY on resource limits.
Defined in src/poly/sparse.mojo.
degree_bound¶
def degree_bound[P: Copyable & Deinitable, D: NumericDomain](values: NumericArray[P, D], mut budget: Budget) raises PolyError -> Int
Return the stored degree bound.
Parameters.
P: The sparse power shape or retained source array type, inferred from the input.D: The APN numerical domain associated with the stored scalars.
Arguments.
values: Input coefficients, sparse terms, or prepared values as required by this overload.budget: The shared work allowance, including preparation, computation, and result storage.
Returns. The largest possible degree, or minus one for zero.
Raises.
PolyError: DOMAIN for invalid or incompatible input, or LIMIT/CAPACITY on resource limits.
Defined in src/poly/sparse.mojo.
certified_degree¶
def certified_degree[P: Copyable & Deinitable, D: NumericDomain](values: NumericArray[P, D], mut budget: Budget) raises PolyError -> Optional[Int]
Return a common degree for every represented polynomial, or None when uncertain.
Parameters.
P: The sparse power shape or retained source array type, inferred from the input.D: The APN numerical domain associated with the stored scalars.
Arguments.
values: Input coefficients, sparse terms, or prepared values as required by this overload.budget: The shared work allowance, including preparation, computation, and result storage.
Returns. A common degree for every represented polynomial, or None if uncertain.
Raises.
PolyError: DOMAIN for invalid or incompatible input, or LIMIT/CAPACITY on resource limits.
Defined in src/poly/sparse.mojo.
specialize¶
def specialize[I: Iterable, A: Iterable, P: Copyable & Deinitable, C: Copyable & Deinitable, X: Copyable & Deinitable](values: I, assignments: A, mut budget: Budget) raises PolyError -> _Specialized[P, C, X] where (_Element[I] == Tuple[P, C] and _Element[A] == Tuple[Int, X])
Assign exact values to selected axes, retaining the remaining power shape.
Parameters.
I: The inferred input iterable type.A: The first input type.P: The sparse power shape or retained source array type, inferred from the input.C: The input coefficient type.X: The evaluation point or seed type.
Arguments.
values: Input coefficients, sparse terms, or prepared values as required by this overload.assignments: An iterable of (axis, exact real value) pairs; axes must be unique and in range.budget: The shared work allowance, including preparation, computation, and result storage.
Returns. For rational or AA inputs and real assignments, retained coefficient-group proofs. Complex coefficients or assignments return a sparse array in the promoted field.
Raises.
PolyError: DOMAIN for invalid or incompatible input, or LIMIT/CAPACITY on resource limits.
Defined in src/poly/sparse.mojo.
evaluate_algebraic¶
def evaluate_algebraic[I: Iterable, P: Copyable & Deinitable, C: Copyable & Deinitable, *Ts: Copyable & Deinitable](values: I, point: Tuple[*Ts], mut budget: Budget) raises PolyError -> _alg.Real where _Element[I] == Tuple[P, C]
Evaluate exactly at a coordinate tuple containing rational or algebraic values.
Parameters.
I: The inferred input iterable type.P: The sparse power shape or retained source array type, inferred from the input.C: The input coefficient type.Ts: The inferred tuple element types.
Arguments.
values: Input coefficients, sparse terms, or prepared values as required by this overload.point: The evaluation scalar or ordered coordinate tuple.budget: The shared work allowance, including preparation, computation, and result storage.
Returns. An exact real value retaining the sparse evaluation certificate.
Raises.
PolyError: DOMAIN for invalid or incompatible input, or LIMIT/CAPACITY on resource limits.
Defined in src/poly/sparse.mojo.
enclose¶
def enclose[I: Iterable, P: Copyable & Deinitable, C: Copyable & Deinitable, *Ts: Copyable & Deinitable](values: I, point: Tuple[*Ts], mut budget: Budget, *, context: BallContext) raises PolyError -> _evaluation.Enclosure[_Ring[_Kind[C]], _evaluation._Domain[C, _num._TupleScalar[Tuple[*Ts]]], False, True] where (_Element[I] == Tuple[P, C] and _Kind[C] >= 0)
Evaluate with an independently checkable enclosure.
Inputs remain unchanged. Exact algebraic coefficients and points retain root witnesses for independent conversion checks. Adaptive calls refine exact algebraic coefficients while preserving supplied numerical uncertainty.
Parameters.
I: Inferred from the input types.P: Inferred from the input types.C: Inferred from the input types.Ts: Inferred from the input types.
Arguments.
values: Coefficients, terms, or a prepared value.point: A scalar for one variable, or a tuple in sparse axis order.budget: The shared work allowance.context: Explicit output precision and rounding or enclosure settings.
Returns. An enclosing value with the original inputs, proof trace, and any requested accuracy outcome.
Raises.
PolyError: DOMAIN for invalid input, or LIMIT/CAPACITY on resource limits.
Defined in src/poly/sparse.mojo.
adaptive_evaluate¶
def adaptive_evaluate[I: Iterable, P: Copyable & Deinitable, C: Copyable & Deinitable, *Ts: Copyable & Deinitable](values: I, point: Tuple[*Ts], mut budget: Budget, *, options: NumericOptions) raises PolyError -> _evaluation.Enclosure[_Ring[_Kind[C]], _evaluation._Domain[C, _num._TupleScalar[Tuple[*Ts]]], False, True] where (_Element[I] == Tuple[P, C] and _Kind[C] >= 0)
Evaluate with an independently checkable enclosure and a requested accuracy.
Inputs remain unchanged. Exact algebraic coefficients and points retain root witnesses for independent conversion checks. Adaptive calls refine exact algebraic coefficients while preserving supplied numerical uncertainty.
Parameters.
I: Inferred from the input types.P: Inferred from the input types.C: Inferred from the input types.Ts: Inferred from the input types.
Arguments.
values: Coefficients, terms, or a prepared value.point: A scalar for one variable, or a tuple in sparse axis order.budget: The shared work allowance.options: Initial and maximum precision, and absolute or relative width targets.
Returns. An enclosing value with the original inputs, proof trace, and any requested accuracy outcome.
Raises.
PolyError: DOMAIN for invalid input, or LIMIT/CAPACITY on resource limits.
Defined in src/poly/sparse.mojo.
jet_evaluate¶
def jet_evaluate[P: Copyable & Deinitable, D: NumericDomain, X: Copyable & Deinitable](values: NumericArray[P, D], point: X, order: Int, mut budget: Budget, *, context: D.Context) raises PolyError -> _num.Values[D]
Return consecutive Taylor coefficients of a univariate sparse polynomial.
Conversion charges the complete dense extent before allocation.
Parameters.
P: Inferred from the input types.D: The numerical coefficient domain.X: Inferred from the input types.
Arguments.
values: Coefficients, terms, or a prepared value.point: The evaluation or expansion point.order: The number of retained coefficients.budget: The shared work allowance.context: Explicit output precision and rounding or enclosure settings.
Returns. A numerical sequence retaining every entry, including zeros.
Raises.
PolyError: DOMAIN for invalid input, or LIMIT/CAPACITY on resource limits.
Defined in src/poly/sparse.mojo.
roots_at¶
def roots_at[I: Iterable, A: Iterable, P: Copyable & Deinitable, C: Copyable & Deinitable, X: Copyable & Deinitable](values: I, assignments: A, mut budget: Budget, *, axis: Int = 0) raises PolyError -> _RootsAt[P, C, X] where (_Element[I] == Tuple[P, C] and _Element[A] == Tuple[Int, X])
Specialize all other occurring variables and find the remaining real roots.
Parameters.
I: Inferred from the input types.A: Inferred from the input types.P: Inferred from the input types.C: Inferred from the input types.X: Inferred from the input types.
Arguments.
values: Coefficients, terms, or a prepared value.assignments: Distinct axis and exact-real-value pairs; leave the root axis unassigned.budget: The shared work allowance.axis: The zero-based variable axis.
Returns. All distinct real roots in increasing order, with specialization and completeness evidence.
Raises.
PolyError: DOMAIN for invalid input, or LIMIT/CAPACITY on resource limits.
Defined in src/poly/sparse.mojo.
Retained exact evidence¶
See checked exact results for functional accessors and the precise claim each checker establishes.
gcd_checked¶
def gcd_checked[A: Iterable, B: Iterable, P: Copyable & Deinitable, C: Copyable & Deinitable, D: Copyable & Deinitable](a: A, b: B, mut budget: Budget, *, method: String = "auto") raises PolyError -> _exact.Result[_Join[_Kind[C], _Kind[D]], P, True, GcdResult[_Ring[_Join[_Kind[C], _Kind[D]]]]] where _Element[A] == Tuple[P, C] and _Element[B] == Tuple[P, D]
Compute a GCD and retain independent maximality evidence.
Independent checking proves greatest-common-divisor status up to a unit; the producer returns the usual normalized representative.
Parameters.
A: Inferred from the input types unless explicitly supplied.B: Inferred from the input types unless explicitly supplied.P: Inferred from the input types unless explicitly supplied.C: Inferred from the input types unless explicitly supplied.D: Inferred from the input types unless explicitly supplied.
Arguments.
a: The first polynomial.b: The second polynomial.budget: The shared work allowance, including preparation and output storage.method: Use auto for existing dispatch or modular for sparse reconstruction over ZZ or QQ.
Returns. A retained GCD with maximality evidence for exact.value and exact.check.
Raises.
PolyError: DOMAIN for incompatible input, UNSUPPORTED for an unavailable coefficient domain, or LIMIT/CAPACITY on resource limits.
Defined in src/poly/sparse.mojo.
coprimality¶
def coprimality[A: Iterable, B: Iterable, P: Copyable & Deinitable, C: Copyable & Deinitable, D: Copyable & Deinitable](a: A, b: B, mut budget: Budget) raises PolyError -> Optional[_exact.Result[_Join[_Kind[C], _Kind[D]], P, True, CoprimalityCertificate[_Ring[_Join[_Kind[C], _Kind[D]]]]]] where _Element[A] == Tuple[P, C] and _Element[B] == Tuple[P, D]
Produce a coprimality witness when the inputs have no common nonunit factor.
None means the producer did not establish coprimality.
Parameters.
A: Inferred from the input types unless explicitly supplied.B: Inferred from the input types unless explicitly supplied.P: Inferred from the input types unless explicitly supplied.C: Inferred from the input types unless explicitly supplied.D: Inferred from the input types unless explicitly supplied.
Arguments.
a: The first polynomial.b: The second polynomial.budget: The shared work allowance, including preparation and output storage.
Returns. A retained result for exact.check, or None for an unsuccessful coprimality request.
Raises.
PolyError: DOMAIN for incompatible input, UNSUPPORTED for an unavailable coefficient domain, or LIMIT/CAPACITY on resource limits.
Defined in src/poly/sparse.mojo.
resultant_checked¶
def resultant_checked[A: Iterable, B: Iterable, P: Copyable & Deinitable, C: Copyable & Deinitable, D: Copyable & Deinitable](a: A, b: B, mut budget: Budget, *, axis: Int = 0) raises PolyError -> _exact.Result[_Join[_Kind[C], _Kind[D]], P, True, ResultantResult[_Ring[_Join[_Kind[C], _Kind[D]]]]] where _Element[A] == Tuple[P, C] and _Element[B] == Tuple[P, D]
Compute a resultant and retain its ideal-membership identity.
The checker proves ua + vb = result; it does not independently prove the determinant definition of the resultant.
Parameters.
A: Inferred from the input types unless explicitly supplied.B: Inferred from the input types unless explicitly supplied.P: Inferred from the input types unless explicitly supplied.C: Inferred from the input types unless explicitly supplied.D: Inferred from the input types unless explicitly supplied.
Arguments.
a: The first polynomial.b: The second polynomial.budget: The shared work allowance, including preparation and output storage.axis: The zero-based polynomial axis.
Returns. A retained resultant with an ideal-membership identity for exact.value and exact.check.
Raises.
PolyError: DOMAIN for incompatible input, UNSUPPORTED for an unavailable coefficient domain, or LIMIT/CAPACITY on resource limits.
Defined in src/poly/sparse.mojo.
resultant_certified¶
def resultant_certified[A: Iterable, B: Iterable, P: Copyable & Deinitable, C: Copyable & Deinitable, D: Copyable & Deinitable](a: A, b: B, mut budget: Budget, *, axis: Int = 0) raises PolyError -> _exact.Result[_FieldKind[_Join[_Kind[C], _Kind[D]]], P, True, _exact._Determinant[_FieldKind[_Join[_Kind[C], _Kind[D]]]]] where _Element[A] == Tuple[P, C] and _Element[B] == Tuple[P, D]
Compute an exact resultant with a complete determinant certificate.
Integer coefficients promote to rationals. exact.check verifies the Sylvester determinant transcript. The result retains the original power shape.
Parameters.
A: Inferred from the input types unless explicitly supplied.B: Inferred from the input types unless explicitly supplied.P: Inferred from the input types unless explicitly supplied.C: Inferred from the input types unless explicitly supplied.D: Inferred from the input types unless explicitly supplied.
Arguments.
a: The first polynomial.b: The second polynomial.budget: The shared work allowance, including preparation and output storage.axis: The zero-based polynomial axis.
Returns. A retained exact resultant and determinant evidence for exact.value and exact.check.
Raises.
PolyError: DOMAIN for incompatible input, UNSUPPORTED for an unavailable coefficient domain, or LIMIT/CAPACITY on resource limits.
Defined in src/poly/sparse.mojo.
divide_checked¶
def divide_checked[A: Iterable, B: Iterable, P: Copyable & Deinitable, C: Copyable & Deinitable, D: Copyable & Deinitable](a: A, b: B, mut budget: Budget, *, order: String = "lex", axes: List[Int] = List[Int]()) raises PolyError -> _exact.Result[_FieldKind[_Join[_Kind[C], _Kind[D]]], P, True, ListDivision[_Ring[_FieldKind[_Join[_Kind[C], _Kind[D]]]]]] where _Element[A] == Tuple[P, C] and _Element[B] == Tuple[P, D]
Divide exact polynomials and retain the inputs and division evidence.
Integer inputs promote to QQ. Sparse checking proves the reduction identity without claiming a unique remainder.
Parameters.
A: Inferred from the input types unless explicitly supplied.B: Inferred from the input types unless explicitly supplied.P: Inferred from the input types unless explicitly supplied.C: Inferred from the input types unless explicitly supplied.D: Inferred from the input types unless explicitly supplied.
Arguments.
a: The first polynomial.b: The second polynomial.budget: The shared work allowance, including preparation and output storage.order: One of lex, grlex, or grevlex; defaults to lex.axes: All axes in descending priority; empty uses tuple order.
Returns. A retained division for exact.quotient, exact.remainder and exact.check.
Raises.
PolyError: DOMAIN for incompatible input, UNSUPPORTED for an unavailable coefficient domain, or LIMIT/CAPACITY on resource limits.
Defined in src/poly/sparse.mojo.
divide_many_checked¶
def divide_many_checked[A: Iterable, B: Iterable, P: Copyable & Deinitable, C: Copyable & Deinitable, D: Copyable & Deinitable](values: A, divisors: B, mut budget: Budget, *, order: String = "lex", axes: List[Int] = List[Int]()) raises PolyError -> _exact.Result[_FieldKind[_Join[_Kind[C], _Kind[D]]], P, True, ListDivision[_Ring[_FieldKind[_Join[_Kind[C], _Kind[D]]]]]] where _Element[A] == Tuple[P, C] and _Element[_Nested[B]] == Tuple[P, D]
Divide by ordered polynomials and retain the exact recomposition identity.
Sparse reduction uses the requested monomial order; lex with axis zero first is the default. Returned arrays keep canonical storage order. Changing divisor order can change quotients and remainder; this is not a Groebner-basis computation. An empty divisor collection returns no quotients and the promoted input as remainder. A zero divisor raises DOMAIN.
Parameters.
A: The first inferred iterable type.B: The second inferred iterable type.P: The power shape: Int or a tuple of Int powers.C: The inferred input coefficient type.D: The second inferred coefficient type.
Arguments.
values: The coefficient sequence, sparse terms, or prepared array.divisors: A finite iterable of polynomials of one Mojo input type, tried in the supplied order.budget: The caller-owned work allowance, shared through preparation and computation.order: One of lex, grlex, or grevlex; defaults to lex.axes: All axes in descending priority; empty uses tuple order.
Returns. A retained result for exact.quotients, exact.remainder and exact.check; the check establishes the identity, not a unique reduced remainder.
Raises.
PolyError: LIMIT on exhausted work, CAPACITY on unrepresentable sizes, DOMAIN for invalid input, or UNSUPPORTED for a documented domain restriction.
Defined in src/poly/sparse.mojo.
factor_checked¶
def factor_checked[I: Iterable, P: Copyable & Deinitable, C: Copyable & Deinitable](values: I, mut budget: Budget, *, seed: UInt64 = 0) raises PolyError -> _exact.Result[_Kind[C], P, True, MultivariateFactorization[_Ring[_Kind[C]]]] where _Element[I] == Tuple[P, C]
Factor the polynomial and retain independently checkable evidence.
exact.check verifies recomposition. Over AA and QQbar it also verifies monicity, ordering, distinct factors, and irreducibility. Multivariate results retain auxiliary univariate image factorizations; the checker verifies those certificates and exhausts possible proper divisors without calling the factorization producer. Checking can require exponential work. evidence() exposes the core product certificate; retain the complete Result for the stronger check. Other coefficient domains retain the product-only claim.
Parameters.
I: Inferred from the input types unless explicitly supplied.P: Inferred from the input types unless explicitly supplied.C: Inferred from the input types unless explicitly supplied.
Arguments.
values: Input coefficients, sparse terms, or a prepared array.budget: The shared work allowance, including preparation and output storage.seed: The deterministic finite-field factorization seed.
Returns. A retained factorization for exact.unit, exact.factors and exact.check.
Raises.
PolyError: DOMAIN for incompatible input, UNSUPPORTED for an unavailable coefficient domain, or LIMIT/CAPACITY on resource limits.
Defined in src/poly/sparse.mojo.
squarefree_checked¶
def squarefree_checked[I: Iterable, P: Copyable & Deinitable, C: Copyable & Deinitable](values: I, mut budget: Budget) raises PolyError -> _exact.Result[_FieldKind[_Kind[C]], P, True, _SquarefreeProof[P, _FieldKind[_Kind[C]]]] where _Element[I] == Tuple[P, C]
Decompose by multiplicity and retain the product identity.
The checker verifies recomposition. It does not certify irreducibility or squarefreeness of the factors.
Parameters.
I: Inferred from the input types unless explicitly supplied.P: Inferred from the input types unless explicitly supplied.C: Inferred from the input types unless explicitly supplied.
Arguments.
values: Input coefficients, sparse terms, or a prepared array.budget: The shared work allowance, including preparation and output storage.
Returns. A retained factorization for exact.unit, exact.factors and exact.check.
Raises.
PolyError: DOMAIN for incompatible input, UNSUPPORTED for an unavailable coefficient domain, or LIMIT/CAPACITY on resource limits.
Defined in src/poly/sparse.mojo.
Incremental enclosure and numerical transport¶
enclose_stream¶
def enclose_stream[I: Iterable, P: Copyable & Deinitable, C: Copyable & Deinitable, *Ts: Copyable & Deinitable](values: I, point: Tuple[*Ts], mut budget: Budget, *, context: BallContext) raises PolyError -> _evaluation._Stream[_Ring[_Kind[C]], _evaluation._Domain[C, _num._TupleScalar[Tuple[*Ts]]], False, True, False, _evaluation._AlgebraicTuple[Tuple[*Ts]]] where (_Element[I] == Tuple[P, C] and _Kind[C] >= 0)
Prepare an enclosure producer that emits one witness event at a time.
Use the same inputs and context for producer and checker. Algebraic inputs are refined automatically at the requested precision, with root evidence before the arithmetic events. The receipt alone does not certify evaluation.
Parameters.
I: Inferred from the input types.P: Inferred from the input types.C: Inferred from the input types.Ts: Inferred from the input types.
Arguments.
values: Coefficients, terms, or a prepared value.point: A scalar for one variable, or a tuple in sparse axis order.budget: The shared work allowance.context: Explicit output precision and rounding or enclosure settings.
Returns. A producer owning its evaluation state without retaining emitted witnesses.
Raises.
PolyError: DOMAIN for invalid input, or LIMIT/CAPACITY on resource limits.
Defined in src/poly/sparse.mojo.
enclose_checker¶
def enclose_checker[I: Iterable, P: Copyable & Deinitable, C: Copyable & Deinitable, *Ts: Copyable & Deinitable](values: I, point: Tuple[*Ts], mut budget: Budget, *, context: BallContext) raises PolyError -> _evaluation._Stream[_Ring[_Kind[C]], _evaluation._Domain[C, _num._TupleScalar[Tuple[*Ts]]], False, True, True, _evaluation._AlgebraicTuple[Tuple[*Ts]]] where (_Element[I] == Tuple[P, C] and _Kind[C] >= 0)
Prepare independent incremental enclosure checking.
Use the same inputs and context for producer and checker. Algebraic inputs are refined automatically at the requested precision, with root evidence before the arithmetic events. The receipt alone does not certify evaluation.
Parameters.
I: Inferred from the input types.P: Inferred from the input types.C: Inferred from the input types.Ts: Inferred from the input types.
Arguments.
values: Coefficients, terms, or a prepared value.point: A scalar for one variable, or a tuple in sparse axis order.budget: The shared work allowance.context: Explicit output precision and rounding or enclosure settings.
Returns. A checker accepting events in order and validating the completion receipt.
Raises.
PolyError: DOMAIN for invalid input, or LIMIT/CAPACITY on resource limits.
Defined in src/poly/sparse.mojo.
load_numeric¶
def load_numeric[T: Copyable & Deinitable, S: PolynomialTextSource, *, ndim: Int = 1](var source: S, mut budget: Budget, *, max_field_bytes: Int = 16777216) raises PolyError -> NumericArray[_Shape[ndim], _num._StoredDomain[T]]
Restore stored numerical values exactly; subsequent arithmetic takes an explicit context.
Parameters.
T: The expected numerical scalar type.S: The text source type.ndim: The expected sparse axis count, including unused axes; defaults to one.
Arguments.
source: The owned text source, consumed through end of input.budget: The shared work allowance, including preparation, computation, and result storage.max_field_bytes: Positive maximum encoded field size in bytes.
Returns. A numerical array preserving the encoded scalar precision and enclosures.
Raises.
PolyError: ENCODING for malformed or incompatible records, DOMAIN for invalid settings, or LIMIT/CAPACITY on resource limits.
Defined in src/poly/sparse.mojo.
complex_roots_to¶
def complex_roots_to[I: Iterable, S: _roots.ExactComplexRootSink, P: Copyable & Deinitable, C: Copyable & Deinitable](values: I, mut sink: S, mut budget: Budget, *, axis: Int = 0) raises PolyError -> _roots.ExactComplexRootReceipt where _Element[I] == Tuple[P, C]
Stream exact complex roots with multiplicities and a completion receipt.
Parameters.
I: The inferred coefficient iterable.S: The event consumer type.P: The sparse power shape.C: The exact coefficient type.
Arguments.
values: Exact coefficients or terms over ZZ, QQ, QQi, AA, or QQbar.sink: A consumer of owned ExactComplexRootEvent values.budget: The shared preparation, production, and checking allowance.axis: The root variable; other axes must be absent.
Returns. A receipt to verify with checker.finish. Events follow deterministic factor and coordinate traversal order, which need not be sorted. Output witnesses are not collected; algebraic working state is retained.
Raises.
PolyError: DOMAIN for zero or invalid input, consumer failures, or LIMIT/CAPACITY on resource limits. Partial streams are not complete results.
Defined in src/poly/sparse.mojo.
complex_roots_checker¶
def complex_roots_checker[I: Iterable, P: Copyable & Deinitable, C: Copyable & Deinitable](values: I, mut budget: Budget, *, axis: Int = 0) raises PolyError -> _roots.ExactComplexRootChecker where _Element[I] == Tuple[P, C]
Prepare independent incremental checking of exact complex roots.
Parameters.
I: The inferred coefficient iterable.P: The sparse power shape.C: The exact coefficient type.
Arguments.
values: Exact coefficients or terms over ZZ, QQ, QQi, AA, or QQbar.budget: The shared preparation, production, and checking allowance.axis: The root variable; other axes must be absent.
Returns. A checker accepting root events; finish verifies complete reconstruction.
Raises.
PolyError: DOMAIN for zero or invalid input, consumer failures, or LIMIT/CAPACITY on resource limits. Partial streams are not complete results.
Defined in src/poly/sparse.mojo.