Amortized Bivariate Multi-point Evaluation

Joris Van Der Hoeven; Grégoire Lecerf

doi:10.1145/3452143.3465531

Amortized Bivariate Multi-point Evaluation

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

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. Efficient algorithms for this kind of "amortized"multi-point evaluation were recently developed for the special case when the set of evaluation points is sufficiently generic. In this paper, we design a new algorithm for arbitrary sets of points, while restricting ourselves to bivariate polynomials.

Original language	English
Title of host publication	ISSAC 2021 - Proceedings of the 2021 International Symposium on Symbolic and Algebraic Computation
Publisher	Association for Computing Machinery
Pages	179-185
Number of pages	7
ISBN (Electronic)	9781450383820
DOIs	https://doi.org/10.1145/3452143.3465531
Publication status	Published - 18 Jul 2021
Event	46th International Symposium on Symbolic and Algebraic Computation, ISSAC 2021 - Virtual, Online, Russian Federation Duration: 18 Jul 2021 → 23 Jul 2021

Publication series

Name	Proceedings of the International Symposium on Symbolic and Algebraic Computation, ISSAC

Conference

Conference	46th International Symposium on Symbolic and Algebraic Computation, ISSAC 2021
Country/Territory	Russian Federation
City	Virtual, Online
Period	18/07/21 → 23/07/21

Keywords

bivariate polynomial
complexity
multi-point evaluation

Access to Document

10.1145/3452143.3465531

Cite this

@inproceedings{90cace0d9cf7453e8ee30c9b7a7df768,

title = "Amortized Bivariate Multi-point Evaluation",

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. Efficient algorithms for this kind of {"}amortized{"}multi-point evaluation were recently developed for the special case when the set of evaluation points is sufficiently generic. In this paper, we design a new algorithm for arbitrary sets of points, while restricting ourselves to bivariate polynomials.",

keywords = "bivariate polynomial, complexity, multi-point evaluation",

author = "\{Van Der Hoeven\}, Joris and Gr{\'e}goire Lecerf",

note = "Publisher Copyright: {\textcopyright} 2021 ACM.; 46th International Symposium on Symbolic and Algebraic Computation, ISSAC 2021 ; Conference date: 18-07-2021 Through 23-07-2021",

year = "2021",

month = jul,

day = "18",

doi = "10.1145/3452143.3465531",

language = "English",

series = "Proceedings of the International Symposium on Symbolic and Algebraic Computation, ISSAC",

publisher = "Association for Computing Machinery",

pages = "179--185",

booktitle = "ISSAC 2021 - Proceedings of the 2021 International Symposium on Symbolic and Algebraic Computation",

}

Van Der Hoeven, J & Lecerf, G 2021, Amortized Bivariate Multi-point Evaluation. in ISSAC 2021 - Proceedings of the 2021 International Symposium on Symbolic and Algebraic Computation. Proceedings of the International Symposium on Symbolic and Algebraic Computation, ISSAC, Association for Computing Machinery, pp. 179-185, 46th International Symposium on Symbolic and Algebraic Computation, ISSAC 2021, Virtual, Online, Russian Federation, 18/07/21. https://doi.org/10.1145/3452143.3465531

Amortized Bivariate Multi-point Evaluation. / Van Der Hoeven, Joris ; Lecerf, Grégoire.
ISSAC 2021 - Proceedings of the 2021 International Symposium on Symbolic and Algebraic Computation. Association for Computing Machinery, 2021. p. 179-185 (Proceedings of the International Symposium on Symbolic and Algebraic Computation, ISSAC).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

TY - GEN

T1 - Amortized Bivariate Multi-point Evaluation

AU - Van Der Hoeven, Joris

AU - Lecerf, Grégoire

PY - 2021/7/18

Y1 - 2021/7/18

N2 - 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. Efficient algorithms for this kind of "amortized"multi-point evaluation were recently developed for the special case when the set of evaluation points is sufficiently generic. In this paper, we design a new algorithm for arbitrary sets of points, while restricting ourselves to bivariate polynomials.

AB - 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. Efficient algorithms for this kind of "amortized"multi-point evaluation were recently developed for the special case when the set of evaluation points is sufficiently generic. In this paper, we design a new algorithm for arbitrary sets of points, while restricting ourselves to bivariate polynomials.

KW - bivariate polynomial

KW - complexity

KW - multi-point evaluation

U2 - 10.1145/3452143.3465531

DO - 10.1145/3452143.3465531

M3 - Conference contribution

AN - SCOPUS:85111103546

T3 - Proceedings of the International Symposium on Symbolic and Algebraic Computation, ISSAC

SP - 179

EP - 185

BT - ISSAC 2021 - Proceedings of the 2021 International Symposium on Symbolic and Algebraic Computation

PB - Association for Computing Machinery

T2 - 46th International Symposium on Symbolic and Algebraic Computation, ISSAC 2021

Y2 - 18 July 2021 through 23 July 2021

ER -

Amortized Bivariate Multi-point Evaluation

Abstract

Publication series

Conference

Keywords

Access to Document

Fingerprint

Cite this