Calcul formel

Les nombres entiers sont une des briques de base du calcul formel : ils servent à représenter d'autres objets plus complexes, et beaucoup de calcul se réduisent in fine à la manipulation d'entiers. La notion d'entier en informatique est significativement différente de la notion mathématique. En informatique, un entier est une valeur que peut prendre un mot machine ; cette valeur est bornée par 2^B, où B est le nombre de bits d'un mot machine, selon l'ordinateur. Tant que cette limite n'est pas atteinte, un entier machine se comporte comme un entier idéal. En calcul formel, de grands entiers (bien plus grands que 2⁶⁴) apparaissent fréquemment, que ce soit dans des calculs intermédiaires ou dans un résultat final. Une branche du calcul formel est celle des calculs en arithmétique multiprécision, c'est-à-dire des calculs où il n'y a aucune limite sur la taille des entiers manipulés autre que celle de la disponibilité mémoire, du temps de calcul et de l'affichage des résultats. En ce sens, la notion d'entier en précision arbitraire (également appelée précision infinie) coïncide avec celle d'entier des mathématiques.

Un entier n est généralement représenté par la suite des chiffres de n dans une certaine base, 2⁶⁴ par exemple. Le processeur ne peut pas manipuler directement les entiers dépassant le mot machine ; il faut alors développer des algorithmes spécialisés. Pour l'addition et la soustraction les algorithmes naïfs (ceux qui sont enseignés à l'école, en base 10, pour les calculs à la main) sont bons. En revanche, la multiplication pose un problème de taille : l'algorithme naïf est terriblement lent. La découverte d'algorithmes rapides a été essentielle pour le développement du calcul formel.

La bibliothèque GNU MP, en langage C, est utilisée par la plupart des systèmes de calcul formel pour gérer la manipulation des entiers.

Les nombres rationnels sont représentés par un couple numérateur-dénominateur, à l'instar de la construction formelle des rationnels. Les opérations sur les rationnels se réduisent à des opérations sur les entiers.

Les entiers modulo p de l'arithmétique modulaire sont représentés par un élément de ${\displaystyle [\![0,p-1]\!]}$. Les opérations de base se réduisent aux opérations sur les entiers (addition, multiplication, division euclidienne, etc.) Si p n'est pas trop grand, les entiers modulaires peuvent être représentés par un mot machine. Les opérations de bases sont alors particulièrement rapides. Les algorithmes efficaces du calcul formel essaient autant que possible de se ramener à la manipulation des entiers modulaires.

Un polynôme est une expression formée uniquement de produits et de sommes de constantes et d'indéterminées, habituellement notées X, Y, Z…. Les polynômes interviennent partout en calcul formel. Ils sont par exemple utilisés pour représenter des approximations de fonctions régulières, faire du dénombrement, représenter l'écriture d'un entier dans une base, ou encore représenter les corps finis. Les opérations sur les polynômes, tels que la multiplication, l'inversion ou l'évaluation, sont des questions centrales en calcul formel.

Ils sont souvent représentés sous la forme d'un tableau à n + 1 composantes dans l'ordre de ses puissances croissantes. Par exemple le polynôme P(X) = 5X⁵ + 3X³ – X² + X + 4 sera représenté par le tableau [4;1;-1;3;0;5]. D'autres représentations sont possibles, on peut par exemple représenter un polynôme par un tableau contenant ses coefficients non nuls et un deuxième tableau contenant les exposants des monômes auxquels les coefficients sont multipliés. Pour notre polynôme P, cela donne les deux tableaux [4;1;-1;3;5] et [0;1;2;3;5]. Une telle représentation prend tout son intérêt pour des polynômes creux, c'est-à-dire pour des polynômes ayant peu de coefficients non nuls et dont le monôme dominant est grand. Par exemple, il vaut mieux stocker le polynôme 2X^{100 000} – X^{1 000} + 4X¹⁰ avec les deux tableaux [2 ;-1; 4] et [100 000; 1 000; 10] qu'avec un tableau de taille 100 001.

Une matrice est un tableau d'objets qui sert à interpréter, en termes calculatoires, les résultats théoriques de l'algèbre linéaire. Les entrées de ces tableaux peuvent être de diverses natures, par exemple un corps fini, ou un anneau (de polynômes par exemple). Outre leur intérêt théorique avéré pour étudier le comportement de phénomènes (y compris non linéaires), leur étude algorithmique est centrale en calcul formel.

Ainsi, une question de complexité majeure est ouverte depuis les années 1960, et très dynamique : peut-on calculer un produit (non commutatif) de matrices aussi efficacement que le produit (commutatif) de polynômes ? Autrement dit, peut-on multiplier deux matrices carrées (n, n) en temps proportionnel à ${\displaystyle n^{2}}$ ? Aujourd'hui la borne atteinte par l'algorithme de Coppersmith-Winograd est de ${\displaystyle O(n^{2,3737})\!\ }$.

L'ubiquité des matrices dans de nombreux domaines scientifiques (physique, géologie, mathématiques expérimentales) amène à rechercher des algorithmes très performants sur des applications ciblées. Ainsi, calculer les racines d'un polynôme peut s'effectuer en résolvant un système linéaire, dit de Toeplitz, dont la matrice (n + 1, n + 1) peut être décrite avec seulement n + 1 coefficients (et non (n + 1)² comme dans le cas général). On peut alors mettre au point des algorithmes spécifiques bien plus rapides que les algorithmes génériques sur ces entrées.