schubmult.mult._shadow

Probabilistic zero testing for the multiplication kernels (probabilistic=True).

The double kernels are layered dynamic programs whose states carry unexpanded partial sums. The signed terms cancel, and a state whose sum is zero as a polynomial -- but not structurally -- keeps fanning out: every descendant is dead work and its leaves are output terms with coefficient zero (6496 of them in a product of two S_8 classes with 246 nonzero coefficients). Nothing short of expanding can see this exactly; polynomial identity testing is only known in randomized form.

The kernels therefore carry a shadow of every partial sum: its value at points random points of \mathbb{F}_p, p = 2^{61} - 1, computed from the children's shadows as each node is built (two modular multiplications per term, no tree walks). A state whose shadow vanishes at every point is dropped at the end of its level. By Schwartz-Zippel a nonzero polynomial of total degree d vanishes at a random point with probability at most d / p, so with the default two points a product of N states is wrong with probability at most N (d / p)^2 -- around 10^{-26} for anything the kernels can finish. The sample points are drawn afresh for every call.

:class:ShadowEvaluator evaluates the inputs of a kernel (the coefficients of perm_dict and the factorial elementary symmetric polynomials, both small) and is what the C++ kernel calls back.

ShadowEvaluator Objects

class ShadowEvaluator()

Evaluate SymEngine expressions at points random points of \mathbb{F}_p, memoized by node.

Calling it returns a tuple of points integers. Symbols get their random values on first sight and keep them for the lifetime of the evaluator; expressions must be built from integers, rationals, symbols, +, * and integer powers (a negative power whose base vanishes at a sample point raises ZeroDivisionError).