Fast polynomial evaluation and composition
Résumé
The library \emph{fast\_polynomial} for Sage compiles multivariate polynomials for subsequent fast evaluation. Several evaluation schemes are handled, such as Hörner, divide and conquer and new ones can be added easily. Notably, a new scheme is introduced that improves the classical divide and conquer scheme when the number of terms is not a pure power of two. Natively, the library handles polynomials over gmp big integers, boost intervals, python numeric types. And any type that supports addition and multiplication can extend the library thanks to the template design. Finally, the code is parallelized for the divide and conquer schemes, and memory allocation is localized and optimized for the different evaluation schemes. This extended abstract presents the concepts behind the \emph{fast\_polynomial} library. The sage package can be downloaded at \url{http://trac.sagemath.org/sage_trac/ticket/13358}.
La bibliothèque \emph{fast\_polynomial} permet de compiler des polynômes multivariés sage pour les évaluer ensuite rapidement en Sage. Plusieurs schémas d'évaluation sont disponibles, comme Hörner, scindage binaire, ou d'autres qui peuvent être ajoutés facilement. La bibliothèque peut manipuler des polynômes à coefficients de type entier long gmp, interval boost, objet python. Par un système de template, elle est facilement extensible à d'autres types qui peuvent être ajoutés et multipliés entre eux. Enfin l'évaluation peut être parallélisée et l'espace mêmoire est optimisé pour chaque schéma d'évaluation. Ce rapport présente les concepts sous-jacents à la bibliothèque \emph{fast\_polynomial}. Le paquet Sage est téléchargeable à l'adresse \url{http://trac.sagemath.org/sage_trac/ticket/13358}.
Domaines
Calcul formel [cs.SC]
Origine : Fichiers produits par l'(les) auteur(s)
Loading...