Amortized multi-point evaluation of multivariate polynomials

van der Hoeven J.; Lecerf G.

首页> 外文期刊>Journal of complexity >Amortized multi-point evaluation of multivariate polynomials

【24h】

Amortized multi-point evaluation of multivariate polynomials

机译：Amortized multi-point evaluation of multivariate polynomials

获取原文

获取原文并翻译 | 示例

掌桥外文数据库（机构版） >>

开具论文收录证明 >>

文献代查 >>

页面导航

摘要
著录项
相关主题

摘要

? 2022 Elsevier Inc.The evaluation of a polynomial at several points is called the problem of multi-point evaluation. Sometimes, the set of evaluation points is fixed and several polynomials need to be evaluated at this set of points. Several efficient algorithms for this kind of “amortized” multi-point evaluation have been developed recently for the special cases of bivariate polynomials or when the set of evaluation points is generic. In this paper, we extend these results to the evaluation of polynomials in an arbitrary number of variables at an arbitrary set of points. We prove a softly linear complexity bound when the number of variables is fixed. Our method relies on a novel quasi-reduction algorithm for multivariate polynomials, that operates simultaneously with respect to several orderings on the monomials.

著录项

来源
《Journal of complexity》 |2023年第2期|101693.1-101693.17|共17页
作者
van der Hoeven J.; Lecerf G.;
展开▼
作者单位

CNRS école polytechnique Institut Polytechnique de Paris Laboratoire d'informatique de l'école polytechnique (LIX UMR 7161);

展开▼
收录信息
原文格式 PDF
正文语种英语
中图分类
关键词
Complexity; Gr?bner bases; Multi-point evaluation; Multivariate polynomial;

Amortized multi-point evaluation of multivariate polynomials

摘要

著录项

相关主题

期刊订阅