sparse-interp
Basic polynomial arithmetic, multi-point evaluation, and sparse interpolation.
This crate is very limited so far in its functionality and under active development. The current functionality isi mostly geared towards sparse interpolation with a known set of possible exponents. Expect frequent breaking changes as things get started.
The [Poly
] type is used to represent dense polynomials along with traits for
algorithm choices. The [ClassicalPoly
] type alias specifies classical arithmetic
algorithms via the [ClassicalTraits
] trait.
use ClassicalPoly;
// f represents 4 + 3x^2 - x^3
let f = new;
// g prepresents 2x
let g = new;
// basic arithmetic is supported
let h = f + g;
assert_eq!;
Evaluation
Single-point and multi-point evaluation work as follows.
type CP = ;
let h = CP new;
assert_eq!;
assert_eq!;
assert_eq!;
let eval_info = CP mp_eval_prep;
assert_eq!;
Sparse interpolation
Sparse interpolation should work over any type supporting field operations of addition, subtration, multiplication, and division.
For a polynomial f with at most t terms, sparse interpolation requires eactly 2t evaluations at consecutive powers of some value θ, starting with θ0 = 1.
This value θ must have sufficiently high order in the underlying field; that is, all powers of θ up to the degree of the polynomial must be distinct.
Calling [Poly::sparse_interp()
] returns on success a vector of (exponent, coefficient)
pairs, sorted by exponent, corresponding to the nonzero terms of the
evaluated polynomial.
type CP = ;
let f = CP new;
let t = 2;
let = sparse_interp_prep;
let evals = f.mp_eval.unwrap;
let mut result = CP sparse_interp.unwrap;
// round the coefficients to nearest 0.1
for in result.iter_mut
assert_eq!;
Current version: 0.0.3
License
This software was written by Daniel S. Roche in 2021, as part of their job as a U.S. Government employee. The source code therefore belongs in the public domain in the United States and is not copyrightable.
Otherwise, the 0-clause BSD license applies.