Calcul formel

Page d'aide sur les redirections « Calcul symbolique » redirige ici. Pour l'autre signification, voir Calcul ombral.

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ées les représentations de deux nombres entiers, le calcul formel se pose par exemple la question de calculer celle de leur produit.

Le calcul formel est en général considéré comme un domaine distinct du calcul scientifique, cette dernière appellation faisant référence au calcul numérique approché à l'aide de nombres en virgule flottante, là où le calcul formel met l'accent sur les calculs exacts sur des expressions pouvant contenir des variables ou des nombres en précision arbitraire  (en). Comme exemples d'opérations de calcul formel, on peut citer le calcul de dérivées ou de primitives, la simplification d'expressions, la décomposition en facteurs irréductibles de polynômes, la mise sous formes normales de matrices, ou encore la résolution des systèmes polynomiaux.

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.