Implementing the Tangent Graeffe Root Finding Method

Joris van der Hoeven; Michael Monagan

doi:10.1007/978-3-030-52200-1_48

Implementing the Tangent Graeffe Root Finding Method

Joris van der Hoeven
, Michael Monagan

Simon Fraser University

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

Abstract

The tangent Graeffe method has been developed for the efficient computation of single roots of polynomials over finite fields with multiplicative groups of smooth order. It is a key ingredient of sparse interpolation using geometric progressions, in the case when blackbox evaluations are comparatively cheap. In this paper, we improve the complexity of the method by a constant factor and we report on a new implementation of the method and a first parallel implementation.

Original language	English
Title of host publication	Mathematical Software – ICMS 2020 - 7th International Conference, Proceedings
Editors	Anna Maria Bigatti, Jacques Carette, James H. Davenport, Michael Joswig, Timo de Wolff
Publisher	Springer
Pages	482-492
Number of pages	11
ISBN (Print)	9783030521998
DOIs	https://doi.org/10.1007/978-3-030-52200-1_48
Publication status	Published - 1 Jan 2020
Event	7th International Congress on Mathematical Software, ICMS 2020 - Braunschweig, Germany Duration: 13 Jul 2020 → 16 Jul 2020

Publication series

Name	Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume	12097 LNCS
ISSN (Print)	0302-9743
ISSN (Electronic)	1611-3349

Conference

Conference	7th International Congress on Mathematical Software, ICMS 2020
Country/Territory	Germany
City	Braunschweig
Period	13/07/20 → 16/07/20

Access to Document

10.1007/978-3-030-52200-1_48

Cite this

van der Hoeven, J., & Monagan, M. (2020). Implementing the Tangent Graeffe Root Finding Method. In A. M. Bigatti, J. Carette, J. H. Davenport, M. Joswig, & T. de Wolff (Eds.), Mathematical Software – ICMS 2020 - 7th International Conference, Proceedings (pp. 482-492). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 12097 LNCS). Springer. https://doi.org/10.1007/978-3-030-52200-1_48

van der Hoeven, Joris ; Monagan, Michael. / Implementing the Tangent Graeffe Root Finding Method. Mathematical Software – ICMS 2020 - 7th International Conference, Proceedings. editor / Anna Maria Bigatti ; Jacques Carette ; James H. Davenport ; Michael Joswig ; Timo de Wolff. Springer, 2020. pp. 482-492 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).

@inproceedings{d75ec28ffc374806bf8db716af5b79f3,

title = "Implementing the Tangent Graeffe Root Finding Method",

abstract = "The tangent Graeffe method has been developed for the efficient computation of single roots of polynomials over finite fields with multiplicative groups of smooth order. It is a key ingredient of sparse interpolation using geometric progressions, in the case when blackbox evaluations are comparatively cheap. In this paper, we improve the complexity of the method by a constant factor and we report on a new implementation of the method and a first parallel implementation.",

author = "\{van der Hoeven\}, Joris and Michael Monagan",

note = "Publisher Copyright: {\textcopyright} 2020, Springer Nature Switzerland AG.; 7th International Congress on Mathematical Software, ICMS 2020 ; Conference date: 13-07-2020 Through 16-07-2020",

year = "2020",

month = jan,

day = "1",

doi = "10.1007/978-3-030-52200-1\_48",

language = "English",

isbn = "9783030521998",

series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

publisher = "Springer",

pages = "482--492",

editor = "Bigatti, \{Anna Maria\} and Jacques Carette and Davenport, \{James H.\} and Michael Joswig and \{de Wolff\}, Timo",

booktitle = "Mathematical Software – ICMS 2020 - 7th International Conference, Proceedings",

}

van der Hoeven, J & Monagan, M 2020, Implementing the Tangent Graeffe Root Finding Method. in AM Bigatti, J Carette, JH Davenport, M Joswig & T de Wolff (eds), Mathematical Software – ICMS 2020 - 7th International Conference, Proceedings. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 12097 LNCS, Springer, pp. 482-492, 7th International Congress on Mathematical Software, ICMS 2020, Braunschweig, Germany, 13/07/20. https://doi.org/10.1007/978-3-030-52200-1_48

Implementing the Tangent Graeffe Root Finding Method. / van der Hoeven, Joris; Monagan, Michael.
Mathematical Software – ICMS 2020 - 7th International Conference, Proceedings. ed. / Anna Maria Bigatti; Jacques Carette; James H. Davenport; Michael Joswig; Timo de Wolff. Springer, 2020. p. 482-492 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 12097 LNCS).

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

TY - GEN

T1 - Implementing the Tangent Graeffe Root Finding Method

AU - van der Hoeven, Joris

AU - Monagan, Michael

PY - 2020/1/1

Y1 - 2020/1/1

N2 - The tangent Graeffe method has been developed for the efficient computation of single roots of polynomials over finite fields with multiplicative groups of smooth order. It is a key ingredient of sparse interpolation using geometric progressions, in the case when blackbox evaluations are comparatively cheap. In this paper, we improve the complexity of the method by a constant factor and we report on a new implementation of the method and a first parallel implementation.

AB - The tangent Graeffe method has been developed for the efficient computation of single roots of polynomials over finite fields with multiplicative groups of smooth order. It is a key ingredient of sparse interpolation using geometric progressions, in the case when blackbox evaluations are comparatively cheap. In this paper, we improve the complexity of the method by a constant factor and we report on a new implementation of the method and a first parallel implementation.

UR - https://www.scopus.com/pages/publications/85088523250

U2 - 10.1007/978-3-030-52200-1_48

DO - 10.1007/978-3-030-52200-1_48

M3 - Conference contribution

AN - SCOPUS:85088523250

SN - 9783030521998

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 482

EP - 492

BT - Mathematical Software – ICMS 2020 - 7th International Conference, Proceedings

A2 - Bigatti, Anna Maria

A2 - Carette, Jacques

A2 - Davenport, James H.

A2 - Joswig, Michael

A2 - de Wolff, Timo

PB - Springer

T2 - 7th International Congress on Mathematical Software, ICMS 2020

Y2 - 13 July 2020 through 16 July 2020

ER -

van der Hoeven J, Monagan M. Implementing the Tangent Graeffe Root Finding Method. In Bigatti AM, Carette J, Davenport JH, Joswig M, de Wolff T, editors, Mathematical Software – ICMS 2020 - 7th International Conference, Proceedings. Springer. 2020. p. 482-492. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). doi: 10.1007/978-3-030-52200-1_48

Implementing the Tangent Graeffe Root Finding Method

Abstract

Publication series

Conference

Access to Document

Other files and links

Fingerprint

Cite this