Amortized multi-point evaluation of multivariate polynomials |
| |
| Institution: | 1. Department of Computer Science, The University of Tokyo, Bunkyo-ku, Tokyo 113-8656, Japan;2. Dept. IV Computer Science, Universität Trier, 54286 Trier, Germany;3. Department of Mathematics, TU Darmstadt, Schlossgartenstr. 7, 64289 Darmstadt, Germany;1. Computer Science Department, Facultad de Ciencias Exactas y Naturales, University of Buenos Aires, Pabellón 0+Infinito, Ciudad Universitaria (C1428), Ciudad Autónoma de Buenos Aires, Argentina;2. Departamento de Matemáticas, Estadística y Computación, Facultad de Ciencias, Universidad de Cantabria, 39071 Santander, Spain;3. Facultad de Ingeniería, University of Buenos Aires, Av. Paseo Colón 850 (C1063) Ciudad Autónoma de Buenos Aires, Argentina;4. Instituto de Ciencias, Universidad Nacional de General Sarmiento, J. M. Gutiérrez 1150 (B1613GSX) Los Polvorines, Provincia de Buenos Aires, Argentina;1. Institute of Mathematics and Scientific Computing, Universität Graz, Heinrichstraße 36, 8010 Graz, Austria;2. Institut für Finanzmathematik und Angewandte Zahlentheorie, Johannes Kepler Universität Linz, Altenbergerstraße 69, 4040 Linz, Austria;3. Johann Radon Institute for Computational and Applied Mathematics (RICAM), Austrian Academy of Sciences, Altenbergerstraße 69, 4040 Linz, Austria |
| |
| Abstract: | 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. |
| |
| Keywords: | Multi-point evaluation Multivariate polynomial Gröbner bases Complexity |
| 本文献已被 ScienceDirect 等数据库收录！ |
|
