On the sign of a trigonometric expression

Abstract : We propose a set of simple and fast algorithms for evaluating and using trigonometric expressions in the form $F=\sum_{k=0}^df_k\cos k\frac{\pi}{n}$, $f_k\in\ZZ$, $d0}$: computing the sign of such an expression, evaluating it numerically and computing its minimal polynomial in $\QQ[x]$. As critical byproducts, we propose simple and efficient algorithms for performing arithmetic operations (multiplication, division, gcd) on polynomials expressed in a Chebyshev basis (with the same bit-complexity as in the monomial basis) and for computing the minimal polynomial of $2 \cos \frac{\pi}{n}$ in $\tcO(n_0^2)$ bit operations with $n_0 \leq n$ is the odd squarefree part of $n$. Within such a framework, we can decide if $F=0$ in $\tcO(d(\tau+d))$ bit operations, compute the sign of $F$ in $\tcO(d^2\tau)$ bit operations and compute the minimal polynomial of $F$ in $\tcO(n^3\tau)$ bit operations, where $\tau$ denotes the maximum bitsize of the $f_k$'s.
Type de document :
Communication dans un congrès
ISSAC ' 15, Jul 2015, Bath, United Kingdom. 2015, Proceedings of the 2015 ACM on International Symposium on Symbolic and Algebraic Computation. 〈10.1145/2755996.2756664〉
Liste complète des métadonnées

https://hal.inria.fr/hal-01200820
Contributeur : Fabrice Rouillier <>
Soumis le : jeudi 17 septembre 2015 - 11:48:46
Dernière modification le : vendredi 16 novembre 2018 - 02:11:26

Lien texte intégral

Identifiants

Citation

Pierre-Vincent Koseleff, Fabrice Rouillier, Cuong Tran. On the sign of a trigonometric expression. ISSAC ' 15, Jul 2015, Bath, United Kingdom. 2015, Proceedings of the 2015 ACM on International Symposium on Symbolic and Algebraic Computation. 〈10.1145/2755996.2756664〉. 〈hal-01200820〉

Partager

Métriques

Consultations de la notice

183