Structured FFT and TFT: symmetric and lattice polynomials

Joris van der Hoeven; Romain Lebreton; Eric Schost

doi:10.1145/2465506.2465526

Retour

Structured FFT and TFT: symmetric and lattice polynomials

Acte de colloque

Open Access

Structured FFT and TFT: symmetric and lattice polynomials

Joris van der Hoeven, Romain Lebreton et Eric Schost

ISSAC '13: Proceedings of the 38th International Symposium on Symbolic and Algebraic Computation, pp.355-362

ISSAC 2013 - 38th International Symposium on Symbolic and Algebraic Computation (Boston, United States, 26/06/2013–29/06/2013)

2013

DOI: https://doi.org/10.1145/2465506.2465526

Résumé

complexity

TFT

symmetric polynomial

FFT

MSC 42-02, 68W25, 42B99, 30B10, 68W30

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

Fichiers et liens (1)

url

Find in HALAfficher

Indicateurs

1 Consultations de la notice

Détails

Titre: Structured FFT and TFT: symmetric and lattice polynomials
Créateurs - sans rôle: Joris van der Hoeven - Laboratoire d'Informatique de l'École Polytechnique
Romain Lebreton - Université de Montpellier
Eric Schost - Western University
Détails de publication: ISSAC '13: Proceedings of the 38th International Symposium on Symbolic and Algebraic Computation, pp.355-362
Colloque: ISSAC 2013 - 38th International Symposium on Symbolic and Algebraic Computation (Boston, United States, 26/06/2013–29/06/2013)
Identifiants: 99151224909311
Unité académique: Laboratoire d'Informatique de Robotique et de Microélectronique de Montpellier - LIRMM
Langue: English
Type de ressource: Conference proceeding
Champs locaux: hal-00780431