Structured FFT and TFT: Symmetric and lattice polynomials

Joris Van Der Hoeven; Romain Lebreton; Éric Schost

doi:10.1145/2465506.2465526

Structured FFT and TFT: Symmetric and lattice polynomials

Joris Van Der Hoeven
, Romain Lebreton
, Éric Schost

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

Abstract

In this paper, we consider the problem of efficient computa- tions with structured polynomials. We provide complexity results for computing Fourier Transform and Truncated Fourier Transform of symmetric polynomials, and for mul- tiplying polynomials supported on a lattice.

Original language	English
Title of host publication	ISSAC 2013 - Proceedings of the 38th International Symposium on Symbolic and Algebraic Computation
Pages	355-362
Number of pages	8
DOIs	https://doi.org/10.1145/2465506.2465526
Publication status	Published - 23 Aug 2013
Event	38th International Symposium on Symbolic and Algebraic Computation, ISSAC 2013 - Boston, MA, United States Duration: 26 Jun 2013 → 29 Jun 2013

Publication series

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

Conference

Conference	38th International Symposium on Symbolic and Algebraic Computation, ISSAC 2013
Country/Territory	United States
City	Boston, MA
Period	26/06/13 → 29/06/13

Keywords

Lattice FFT
Symmetric FFT
TFT

Access to Document

10.1145/2465506.2465526

Cite this

@inproceedings{0e758afdbb08434b99d156473c757053,

title = "Structured FFT and TFT: Symmetric and lattice polynomials",

abstract = "In this paper, we consider the problem of efficient computa- tions with structured polynomials. We provide complexity results for computing Fourier Transform and Truncated Fourier Transform of symmetric polynomials, and for mul- tiplying polynomials supported on a lattice.",

keywords = "Lattice FFT, Symmetric FFT, TFT",

author = "\{Van Der Hoeven\}, Joris and Romain Lebreton and {\'E}ric Schost",

year = "2013",

month = aug,

day = "23",

doi = "10.1145/2465506.2465526",

language = "English",

isbn = "9781450320597",

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

pages = "355--362",

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

note = "38th International Symposium on Symbolic and Algebraic Computation, ISSAC 2013 ; Conference date: 26-06-2013 Through 29-06-2013",

}

Van Der Hoeven, J, Lebreton, R & Schost, É 2013, Structured FFT and TFT: Symmetric and lattice polynomials. in ISSAC 2013 - Proceedings of the 38th International Symposium on Symbolic and Algebraic Computation. Proceedings of the International Symposium on Symbolic and Algebraic Computation, ISSAC, pp. 355-362, 38th International Symposium on Symbolic and Algebraic Computation, ISSAC 2013, Boston, MA, United States, 26/06/13. https://doi.org/10.1145/2465506.2465526

Structured FFT and TFT: Symmetric and lattice polynomials. / Van Der Hoeven, Joris; Lebreton, Romain; Schost, Éric.
ISSAC 2013 - Proceedings of the 38th International Symposium on Symbolic and Algebraic Computation. 2013. p. 355-362 (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 - Structured FFT and TFT

T2 - 38th International Symposium on Symbolic and Algebraic Computation, ISSAC 2013

AU - Van Der Hoeven, Joris

AU - Lebreton, Romain

AU - Schost, Éric

PY - 2013/8/23

Y1 - 2013/8/23

N2 - In this paper, we consider the problem of efficient computa- tions with structured polynomials. We provide complexity results for computing Fourier Transform and Truncated Fourier Transform of symmetric polynomials, and for mul- tiplying polynomials supported on a lattice.

AB - In this paper, we consider the problem of efficient computa- tions with structured polynomials. We provide complexity results for computing Fourier Transform and Truncated Fourier Transform of symmetric polynomials, and for mul- tiplying polynomials supported on a lattice.

KW - Lattice FFT

KW - Symmetric FFT

KW - TFT

U2 - 10.1145/2465506.2465526

DO - 10.1145/2465506.2465526

M3 - Conference contribution

AN - SCOPUS:84882257932

SN - 9781450320597

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

SP - 355

EP - 362

BT - ISSAC 2013 - Proceedings of the 38th International Symposium on Symbolic and Algebraic Computation

Y2 - 26 June 2013 through 29 June 2013

ER -

Structured FFT and TFT: Symmetric and lattice polynomials

Abstract

Publication series

Conference

Keywords

Access to Document

Fingerprint

Cite this