Calcul formel

Un article de Wikipédia, l'encyclopédie libre.
Aller à : navigation, rechercher

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. 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[modifier | modifier le code]

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 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 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 Sage. 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 théorie des nombres, de Cayley (devenu Magma) et Gap en théorie des groupes, de Macaulay pour les manipulations d'idéaux, de FGb pour les calculs de bases de Gröbner.

Les objets du calcul formel[modifier | modifier le code]

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[modifier | modifier le code]

Les entiers[modifier | modifier le code]

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.

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ème de calcul formel pour gérer la manipulation des entiers.

Les rationnels[modifier | modifier le code]

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 modulaires[modifier | modifier le code]

Les entiers modulo p de l'arithmétique modulaire sont représentés par un élément de \{0,\dotsc,p-1\}. Les opérations de bases 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[modifier | modifier le code]

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 F_q. Les opérations sur les polynômes, tels que la multiplication, l'inversion ou l'évaluation sont des questions centrales en calcul formel.

Ils 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^5+3x^3-x^2+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 suivants : [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ˆome dominant est grand. Par exemple, il vaut mieux stocker le polynôme Q(X) = 2X^{100000} - X^{1000} + 4X^{10} avec les deux tableaux [2 ;-1; 4] et [100000; 1000; 10] qu'avec un tableau de taille 100001.

Les matrices[modifier | modifier le code]

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 le produit (commutatif) de polynôme? Son écriture usuelle est \omega > 2 (\omega désigne l'exposant en n de la complexité du produit de matrices carrée (n,n).

L'ubiquité des matrices dans de nombreux domaines scientifiques (physique, géologie, mathématiques expérimentales) amènent à 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.

Voir aussi[modifier | modifier le code]

Références[modifier | modifier le code]

Bibliographie[modifier | modifier le code]

  • Alin Bostan, Frédéric Chyzak, Marc Giusti, Romain Lebreton, Bruno Salvy et Éric Schost, Algorithmes efficaces en calcul formel (support de cours, Master parisien de recherche en informatique) [lire en ligne]
  • James Davenport, Yvon Siret et Évelyne Tournier, Calcul formel : Systèmes et algorithmes de manipulation algébrique, Masson,‎ 1987 (ISBN 2225809909)
  • (en) Joachim von zur Gathen et Jürgen Gerhard, Modern computer algebra, Cambridge University Press,‎ 2003, 2e éd. (ISBN 0-521-82646-2)
  • (en) Keith O. Geddes, Stephen R. Czapor et George Labahn, Algorithms for Computer Algebra, Kluwer Academic Publishers,‎ 1992 (ISBN 0-7923-9259-0)