Homotopy techniques for multiplication modulo triangular sets

Abstract : We study the cost of multiplication modulo triangular families of polynomials. Following previous work by Li et al. (2007), we propose an algorithm that relies on homotopy and fast evaluation-interpolation techniques. We obtain a quasi-linear time complexity for substantial families of examples, for which no such result was known before. Applications are given notably to additions of algebraic numbers in small characteristic.
Type de document :
Article dans une revue
Journal of Symbolic Computation, Elsevier, 2011, 46 (12), pp.1378-1402. 〈http://www.sciencedirect.com/science/article/pii/S0747717111001271〉. 〈10.1016/j.jsc.2011.08.015〉
Liste complète des métadonnées

https://hal.inria.fr/hal-00819155
Contributeur : Hélène Lowinger <>
Soumis le : mardi 30 avril 2013 - 11:45:07
Dernière modification le : jeudi 10 mai 2018 - 02:06:06
Document(s) archivé(s) le : mardi 4 avril 2017 - 01:48:17

Fichiers

BoChHoSc11.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

Collections

Citation

Alin Bostan, Muhammad F. I. Chowdhury, Joris Van Der Hoeven, Éric Schost. Homotopy techniques for multiplication modulo triangular sets. Journal of Symbolic Computation, Elsevier, 2011, 46 (12), pp.1378-1402. 〈http://www.sciencedirect.com/science/article/pii/S0747717111001271〉. 〈10.1016/j.jsc.2011.08.015〉. 〈hal-00819155〉

Partager

Métriques

Consultations de la notice

363

Téléchargements de fichiers

615