Le calcul formel, ou parfois calcul symbolique, est le domaine des mathématiques et de l’informatique qui s’intéresse aux algorithmes opérant sur des objets de nature mathématique par le biais de représentations finies et exactes.
Ainsi, un nombre entier est représenté de manière finie et exacte par la suite des chiffres de son écriture en base 2. Étant donné les représentations de deux nombres entiers, le calcul formel se pose par exemple la question de calculer celle de leur produit.
Sur le plan théorique, on s’attache en calcul formel à donner des algorithmes avec la démonstration qu’ils terminent en temps fini et la démonstration que le résultat est bien la représentation d’un objet mathématique défini préalablement. Autant que possible, on essaie de plus d’estimer la complexité des algorithmes que l'on décrit, c'est-à-dire le nombre total d’opérations élémentaires qu'ils effectuent. Cela permet d’avoir une idée a priori du temps d’exécution d’un algorithme, de comparer l’efficacité théorique de différents algorithmes ou encore d’éclairer la nature même du problème.
Historique
Les premiers calculs symboliques sur ordinateur ont été réalisés dans les années 1950. Il s'agissait alors d'opérations spécifiques, comme le calcul de dérivées de fonctions. Les tout premiers systèmes étaient en général spécialisés et écrits par une ou deux personnes (Alpak par Brown en 1964, Formac(en) par Bond et Tobey en 1964). Ces systèmes ont disparu depuis, faute de moyens humains et de développement. Sont apparus ensuite Reduce(en) en 1968, MATLAB en 1968 qui a donné Macsyma en 1970, et Scratchpad, développé par IBM dès le milieu des années soixante, qui est devenu Scratchpad II en 1975,
pour n'être diffusé officiellement qu'en 1991 sous le nom d'Axiom. Ces trois systèmes (Reduce, Macsyma et Scratchpad) ont été écrits en Lisp. On a longtemps pensé que ce langage était préférable pour développer un système de calcul formel, jusqu'à l'apparition vers le milieu des années 1970 du langage C, dans lequel ont été écrits Maple (1980) et Mathematica (1988), successeur de SMP (1982).
Le calcul formel a acquis une notoriété considérable depuis 1988 avec l'arrivée de Mathematica, dont le concepteur, Stephen Wolfram, a mené une campagne de publicité partout dans le monde. Cette publicité a fait mieux connaître le calcul formel dans le milieu industriel.
Les systèmes de calcul formel les plus répandus actuellement sont Maple et Mathematica, et dans une moindre mesure Magma et SageMath. Il s'agit de systèmes généraux, c'est-à-dire qu'ils savent manipuler des nombres en précision arbitraire, factoriser ou développer des polynômes et fractions à nombre quelconque de variables, dériver — et intégrer lorsque c'est possible — des expressions construites à l'aide de fonctions élémentaires, résoudre des équations, différentielles ou non, de façon exacte ou à défaut numérique, effectuer des développements limités à un ordre quelconque, manipuler
des matrices à coefficients symboliques, tracer des graphiques en deux ou trois dimensions. Ces systèmes évoluent sans cesse, au rythme par exemple d'une nouvelle version tous les ans environ en ce qui concerne Maple.
Il existe aussi des logiciels spécialisés pour certains calculs symboliques. Ces logiciels ne fournissent pas tous les outils que
propose un système général, mais ils disposent de fonctionnalités spécifiques à un domaine qu'ils sont souvent les seuls à offrir. En
outre, dans leur domaine, ces logiciels sont souvent plus efficaces que les logiciels généraux. C'est le cas de PARI/GP et Kant(en) en théorie des nombres, de Cayley (devenu Magma) et Gap en théorie des groupes, de Macaulay(en) pour les manipulations d'idéaux, de FGb(en) pour les calculs de bases de Gröbner.
Les objets du calcul formel
Pour chaque type d'objet que le calcul formel appréhende, il faut définir une représentation, propre à être manipulée par un ordinateur, et ensuite concevoir des algorithmes travaillant sur ces représentations.
Les nombres
Les entiers
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 2B, 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 264) 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, 264 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 entiers modulo p de l'arithmétique modulaire sont représentés par un élément de . 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.
Les polynômes
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) = 5X5 + 3X3 – X2 + 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 2X100 000 – X1 000 + 4X10 avec les deux tableaux [2 ;-1; 4] et [100 000; 1 000; 10] qu'avec un tableau de taille 100 001.
Les matrices
Cette section est vide, insuffisamment détaillée ou incomplète. Votre aide est la bienvenue ! Comment faire ?
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 à ? Aujourd'hui la borne atteinte par l'algorithme de Coppersmith-Winograd est de .
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)2 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.
Alin Bostan, Frédéric Chyzak, Marc Giusti, Romain Lebreton, Bruno Salvy et Éric Schost, Algorithmes efficaces en calcul formel, Palaiseau, Frédéric Chyzak (auto-édit.), , 686 p. (ISBN979-10-699-0947-2, lire en ligne)
James Davenport, Yvon Siret et Évelyne Tournier, Calcul formel : Systèmes et algorithmes de manipulation algébrique, Paris/New York/Barcelone, Masson, , 263 p. (ISBN2-225-80990-9)
(en) Joachim von zur Gathen et Jürgen Gerhard, Modern computer algebra, New York, Cambridge University Press, , 2e éd., 785 p. (ISBN0-521-82646-2, lire en ligne)
(en) Keith O. Geddes, Stephen R. Czapor et George Labahn, Algorithms for Computer Algebra, Boston/Dordrecht/London, Kluwer Academic Publishers, , 585 p. (ISBN0-7923-9259-0, lire en ligne)
![{\displaystyle [\![0,p-1]\!]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/808fb46ba7dd8f96171a7c6961ecde50c35d4054)
