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( extend reconstructor adding zeros at positions in li)li.
chinese_update(v, pt, r) informs r that evaluation at pt gave vector of values v
empty(n, p) initializes reconstructor with n slots working modulo p
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. Returns "failed" when such r/s does not exist.
rational_reconstruction(r) reconstructs vector of rational functions based on information stored in reconstructor.
reconstruct(n, bo, po, ev, nums, dens, p) reconstructs polynomials in n + 1 variables from result of rational reconstruction.
reconstruct(r, n, bo, po, ev) reconstructs polynomials in n + 1 variables using information stored in r.
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(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.