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

extend reconstructor adding zeros at specified positions.

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)

reconstruct vector of rational functions based on information stored in reconstructor.

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

reconstruct rational function

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

reconstruct polynomials in n + 1 variables

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

reconstruct 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)

convert 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