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

CREATORNick Fischer, Melvin Kallmayer, Leo Wennmann
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE29 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2507-00196

Browse the full library · About the Tower of Babel