VectorModularReconstructor

vecrec.spad line 7 [edit on github]

This domain supports modular methods based on evaluation and rational reconstruction. All computation are done on polynomials modulo machine sized prime p -- p must be chosen small enough to avoid overflow in intermediate calculations. Each evaluation is supposed to produce vector of values. Once enough evaluations are known rational reconstruction produces vector of rational functions or multivariate polynomials.

add_slots: (List Integer, %) -> Void

add_slots(li) extend reconstructor adding zeros at positions in li.

chinese_update: (U32Vector, Integer, %) -> Void

chinese_update(v, pt, r) informs r that evaluation at pt gave vector of values v

empty: (Integer, Integer) -> %

empty(n, p) initializes reconstructor with n slots working modulo p

rational_reconstruction: % -> Union(Record(numers: PrimitiveArray U32Vector, denoms: PrimitiveArray U32Vector), failed)

rational_reconstruction(r) reconstructs vector of rational functions based on information stored in reconstructor.

rational_reconstruction: (U32Vector, U32Vector, Integer, Integer) -> Union(Record(numer: U32Vector, denom: U32Vector), failed)

rational_reconstruction(x, y, i, j) finds rational function r/s such that r/s = y modulo x, degre(r) <= i, degree(s) \leq j. Returs “failed” when such r/s does not exist.

reconstruct: (%, Integer, Vector Integer, Vector Integer, SortedExponentVector) -> Union(Record(nvars: Integer, offsetdata: Vector Integer, expdata: SortedExponentVector, coeffdata: U32Vector), failed)

reconstruct(r, n, bo, po, ev) reconstructs polynomials in n + 1 variables using information stored in r.

reconstruct: (Integer, Vector Integer, Vector Integer, SortedExponentVector, PrimitiveArray U32Vector, PrimitiveArray U32Vector, Integer) -> Record(nvars: Integer, offsetdata: Vector Integer, expdata: SortedExponentVector, coeffdata: U32Vector)

reconstruct(n, bo, po, ev, nums, dens, p) reconstructs polynomials in n + 1 variables from result of rational reconstruction.

remove_denoms: (Vector Integer, PrimitiveArray U32Vector, PrimitiveArray U32Vector, Integer) -> PrimitiveArray U32Vector

remove_denoms(offsets, nums, denoms, p) removes common denominator from vectors of rational functions. Several vectors of rational functions are packed into nums (storing numerators) and dens (storing denominators) Vector i starts at position offsets(i). Computations are done modulo p.

repack_polys: (Integer, Vector Integer, SortedExponentVector, PrimitiveArray U32Vector) -> Record(nvars: Integer, offsetdata: Vector Integer, expdata: SortedExponentVector, coeffdata: U32Vector)

repack_polys(k, offsets, exponents, coefficients) converts polynomials represented as parallel vector of exponents in k variables and vector of univariate polynomials to parallel vector of exponents in k+1 variables and coefficients.