A Simple Algorithm for Trimmed Multipoint Evaluation
Nick Fischer, Melvin Kallmayer, Leo Wennmann · 2025
Read A Simple Algorithm for Trimmed Multipoint Evaluation by Nick Fischer, Melvin Kallmayer, Leo Wennmann (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2507-00196.txt.
Description
Computing a polynomial's values at many points is a basic chore in computer algebra, with a harder trimmed variant that sits inside several recent algorithms. Three authors revisit that variant, where the polynomial has many variables with limits on each variable's degree and on the total degree.
A near-linear-time method exists, but it leans on heavy machinery that few can follow. The team's contribution is a plain recursive algorithm that reaches the goal without the specialized apparatus. Simplicity is the point: the method can be readily understood by researchers without a computer algebra background, which matters because the subroutine is showing up in work far from its home field. The authors present the algorithm as the accessible version of a result that others had made forbidding.
Catalog record
| CREATOR | Nick Fischer, Melvin Kallmayer, Leo Wennmann |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 29 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2507-00196