sparse-interp

基本的代数运算、多点评估和稀疏插值。

该 crate 目前在功能上非常有限，正在积极开发中。当前功能主要针对具有已知可能指数的稀疏插值。随着项目的开展，预期将会有频繁的破坏性更改。

Poly 类型用于表示密集的多项式，并包含算法选择的特性。通过 ClassicalTraits 特性，ClassicalPoly 类型别名指定了经典算术算法。

use sparse_interp::ClassicalPoly;

// f represents 4 + 3x^2 - x^3
let f = ClassicalPoly::<f32>::new(vec![4., 0., 3., -1.]);

// g prepresents 2x
let g = ClassicalPoly::<f32>::new(vec![0., 2.]);

// basic arithmetic is supported
let h = f + g;
assert_eq!(h, ClassicalPoly::new(vec![4., 2., 3., -1.]));

评估

单点和多点评估工作如下。

type CP = ClassicalPoly<f32>;
let h = CP::new(vec![4., 2., 3., -1.]);
assert_eq!(h.eval(&0.), Ok(4.));
assert_eq!(h.eval(&1.), Ok(8.));
assert_eq!(h.eval(&-1.), Ok(6.));
let eval_info = CP::mp_eval_prep([0., 1., -1.].iter().copied());
assert_eq!(h.mp_eval(&eval_info).unwrap(), [4.,8.,6.]);

稀疏插值

稀疏插值应在支持加、减、乘、除运算的任何类型的域上工作。

对于最多有 t 项的多项式 f，稀疏插值需要在某个值 θ 的连续幂上恰好进行 2t 次评估，从 θ⁰ = 1 开始。

该值 θ 必须在基础域中有足够高的阶数；也就是说，θ 的所有幂直到多项式的次数都必须是不同的。

调用 [Poly::sparse_interp()] 在成功时返回一个按指数排序的 (指数，系数) 对的向量，对应于评估多项式的非零项。

type CP = ClassicalPoly<f64>;
let f = CP::new(vec![0., -2.5, 0., 0., 0., 7.1]);
let t = 2;
let (eval_info, interp_info) = ClassicalPoly::sparse_interp_prep(
    t,          // upper bound on nonzero terms
    0..8,       // iteration over possible exponents
    &f64::MAX,  // upper bound on coefficient magnitude
);
let evals = f.mp_eval(&eval_info).unwrap();
let mut result = CP::sparse_interp(&evals, &interp_info).unwrap();

// round the coefficients to nearest 0.1
for (_,c) in result.iter_mut() {
    *c = (*c * 10.).round() / 10.;
}

assert_eq!(result, [(1, -2.5), (5, 7.1)]);

当前版本：0.0.3

许可证

本软件由 Daniel S. Roche 于 2021 年编写，作为其作为美国政府雇员工作的一部分。因此，源代码属于美国公共领域，不受版权保护。

否则，适用 0-clause BSD 许可证。