Auteur/autrice : Matthieu Halard

Selon Wikipedia, la dérivation automatique est algorithmique!

En mathématique et en calcul formel, la dérivation automatique (DA), également appelé dérivation algorithmique, dérivation formelle^1,2, ou auto-dérivation est un ensemble de techniques d’évaluation de la dérivée d’une fonction par un programme informatique.
https://fr.wikipedia.org/wiki/Dérivation_automatique

Relevons d’abord une faute par rapport à l’anglais qui parle de la dérivée d’une fonction spécifiée par un programme informatique. Le mot “spécifiée” étant absent de la version française, le programme informatique s’entend comme l’outil contenant les techniques d’évaluation de la dérivée. La différence est de taille, mais dans les deux versions l’incohérence règne.

S’il s’agit de calcul formel au sens usuel, la fonction est donnée non sous la forme d’un programme impératif mais d’une expression formelle et on parle de dérivation symbolique. Sinon, il s’agit de la dérivation d’un programme, c’est-à-dire de dérivation algorithmique. Cependant, un programme peut être vu comme une expression particulière de type procédure, prenant comme entrées les paramètres et le corps de la fonction; et réciproquement, une expression peut être transformée en procédure selon un mécanisme d’évaluation (cf. l’article Computer_algebra de Wikipedia, section Expressions, paragraphe 2).

Pour résumer:

la dérivation algorithmique est une dérivation formelle opérant sur les expressions que constituent les éléments d’un programme.
la dérivation symbolique est une dérivation formelle opérant sur les expressions mathématiques classiques.

… et synonyme de dérivation formelle !!!

L’article se restreint aux mathématiques et au calcul formel. Ne sachant pas ce qu’est une dérivation automatique en mathématiques, on arrive au calcul formel et dans ce cadre, certes, la dérivation automatique est formelle! La boucle est-elle bouclée? Non, on y adjoint le terme auto-dérivation. L’auto-dérision serait-elle une dérision automatique? Décidément, ce premier paragraphe est à revoir. Hélas, le deuxième le conforte en une auto-satisfaction ~~automatique~~.

…mais différente de la dérivation symbolique et de la dérivation numérique

La dérivation automatique est distincte de la dérivation symbolique et de la dérivation numérique (méthode des différences finies).

La dérivation symbolique est une dérivation automatique: sinon, je ne sais pas de quoi on parle, si ce n’est du lycéen sur ses exercices.

La dérivation numérique n’est pas automatiquement automatique mais sans doute la méthode la plus facilement automatisable. Et même elle devient, en abusant quelque peu, une dérivation algorithmique au grain le plus grossier…

Ces deux méthodes ne sont définies que par leurs défauts

La dérivation symbolique peut conduire à un code inefficace et se heurte à la difficulté de convertir un programme informatique en une seule expression, tandis que la dérivation numérique peut introduire des erreurs d’arrondi lors de la discrétisation et de l’annulation. Ces deux méthodes classiques ont par ailleurs des problèmes lors du calcul de dérivées d’ordre plus élevées, car la complexité et/ou les erreurs augmentent. Enfin, ces deux méthodes sont lentes pour calculer les dérivées partielles d’une fonction lorsque cette dernière dépend de nombreuses variables, comme cela est nécessaire pour les algorithmes d’optimisation par descente de gradient.
Idem

En quoi ces défauts empêchent-ils une méthode d’être automatique? Conduire à un code inefficace, c’est déjà arriver à un code!

Les idées présentées mériteraient d’être développées.

… et la dérivation automatique résout tous ces problèmes (sic)

Tout est dit dans ce titre, qui est la conclusion du deuxième paragraphe!

Ma conclusion: une entrée Wikipedia pour la dérivation algorithmique

Il faut redonner au terme automatique son sens usuel: automatique ne signifie pas algorithmique, sauf abusivement dans un contexte spécial. La dérivation algorithmique est une dérivation automatique de code. Il faut présenter les autres dérivations automatiques et montrer en quoi elles se distinguent, notamment leurs avantages et leurs inconvénients, et renvoyer à un article spécial pour la dérivation algorithmique, en évitant donc ce double biais: une équivalence usurpée avec une méthode et la relégation des méthodes concurrentes.

L’article n’est pas seul en cause: rechercher “algorithmic differentiation” ou “computational differentiation” sur Wikipedia donne “Automatic_differentiation”. C’est équivalent, vous dit-on.

On doit s’appuyer sur le schéma pertinent faisant intervenir la dérivation symbolique et la dérivation algorithmique et le détailler. Cf. bouton ci-dessous.

simulation numérique et dérivation automatique

Les opérateurs associatifs du C++ sont asociaux

Le C++ a le défaut d’être un peu binaire… dans sa façon de traiter les opérations n-aires qui se moque bien de l’intention associative du programmeur. Faut-il attendre un compilateur quantique avec états non-binaires pour traiter ensemble les opérandes associées par les parenthèses? 😉

Le problème

Bien que les opérateurs + et * soient associatifs du point de vue mathématique, le C++ traite leurs opérandes 2 par 2 de gauche à droite. Ainsi a+b+c+d est vu comme: ((a+b)+c)+d.

sans qu’il y ait moyen de spécifier que l’on veut une somme de quatre opérandes autrement que par l’appel, moins expressif, d’une fonction comme sum(a,b,c,d), Certes, par le moyen classique des expression-templates, on pourrait aboutir au résultat voulu, mais au prix de perdre le respect des parenthèses. Par exemple, dans le cas où le programmeur écrirait (a+b+c)+d, une expression-template pourrait grouper les trois premiers termes, mais finirait par y agréger le quatrième. A moins d’ajouter au standard C++ un opérateur d’appel externe (static operator ()), qui opérerait sur le résultat de a+b+c, il n’y a aucun moyen de garder trace des parenthèses.

Ceci est un problème sérieux pour une interface de programmation, car il est important de respecter l’intention exprimée par l’utilisateur.

Proposition pour le C++

Soit un type Expr sur lequel nous proposons la possibilité de définir l’opérateur + suivant:

enum ExprOperator { ..., OpSum, ... OpProduct, ...};
struct Expr { ExprOperator; std::vector<Expr> operands;};
std::vector<Expr> to_vector(Expr... ee);

Expr operator+(Expr e, Expr... ee) // <- proposition
{
    return Expr { OpSum, to_vector(e,ee...) };
}

A noter: ce programme compile, mais l’opérateur+ n’est compris qu’avec deux arguments, ce qui est un peu limité pour un deuxième argument variadique. Nous voulons qu’il soit accepté pour ce qu’il est. Avec ceci, nous sommes capables de traduire (a+b+c)+d en Expr{OpSum,{Expr{OpSum,{a,b,c}},d} respectant l’original.

Bien sûr, toutes les variantes prenant const Expr& et Expr&& sont possibles.

Conversions implicites ou opérations avec d’autres types

Bien souvent, ayant une variable a de type Expr, nous voulons lui ajouter un type numérique, par exemple 1, comme dans a+1 ou 1+a sans préciser a+Expr(1) ou Expr(1)+a, ce qui ruinerait l’élégance de notre expression. L’opérateur + binaire permet classiquement de traiter cela. Comment le généraliser à une somme à opérandes multiples, comme dans 1+a+b ou a+1+b?

Nous proposons d’utiliser les concepts en permettant d’écrire:

Expr operator+(Expr e, auto convertible_to<Expr>... ee)

Le problème est que nous n’avons pas toujours un type Expr en première position, comme dans le cas 1+a+b. Nous proposons donc que le C++ interprète cette définition comme: opérandes multiples dont un de type Expr et les autres de type convertible_to<Expr>.

Une façon peut-être plus acceptable pour les compilateurs serait d’écrire:

Expr operator+(auto convertible_to<Expr>... ee1, Expr e, auto convertible_to<Expr>... ee2)

dans lequel e serait la première parmi les opérandes qui soit de type Expr.

Cette possibilité serait réservée aux opérateurs associatifs non booléens (+,*,…). Pour les opérateurs booléens, une meilleure proposition est envisagée.

Présentation au congrès SIA Simulation numérique

Naupacte était présent avec un intervenant au congrès Simulation numérique de la Société des Ingénieurs de l’Automobile, lors d’une session Data & Optimisation. Ce fut l’occasion de montrer ce qu’on peut attendre en terme d’automatisation des calculs lorsqu’on se lance dans la modélisation et la simulation multiphysiques non-linéaires.

Automatisation des calculs

L’automatisation des calculs entraîne l’optimisation du développeur d’applications, de l’exécution des calculs, ainsi que de l’objet étudié, grâce aux algorithmes de conception optimale.

Le développeur formule son couplage multiphysique, tandis que Navpactos se charge du reste, c’est-à-dire de la construction de la matrice et du second membre obtenus par assemblage éléments finis. Il suffit même de spécifier la construction du second membre, si l’on veut la matrice tangente, car elle s’en déduit par dérivation … par rapport aux degrés de liberté. Navpactos se charge de tout.

Conception optimale automatisée

Navpactos se charge même de plus: des exemples d’optimisation à l’ordre 2, c’est-à-dire reposant sur la jacobienne des équations d’optimalité, i.e. la hessienne du lagrangien, ont été montrés. Par rapport à la programmation du problème direct, il suffit de préciser les paramètres à optimiser et à formuler la fonction coût à minimiser. Tout le reste est automatique, ce qui comprend une différentiation de la matrice tangente! Et aussi une recherche linéaire remplacée par une recherche sur un arc parabolique osculateur de la courbe d’état.

Cas d’étude et convergence

Le cas montré était tiré de l’élasticité non-linéaire avec comme paramètres les deux coefficients du polynôme donnant les déplacements imposés sur une face.

Exemple judicieusement choisi (ah! le hasard) car il illustre une conséquence d’un mauvais conditionnement: la direction de descente estimée par la hessienne quasiment orthogonale au gradient. Le gain en itérations est colossal par rapport à une méthode de plus grande pente.

La convergence du résidu du gradient dans l’espace des paramètres est très rapide. Il s’agit d’un cas favorable: un problème inverse où la fonction coût mesure l’écart sur des résultats avec ceux de paramètres cibles. Ce type de cas valide a posteriori le calcul des dérivées.

Naupacte aux Trophées de la simulation et de l’IA…

Trois catégories sont présentes: start-up, innovation et co-design. La sélection des trois “nommés” par catégorie a été rendue publique, avec leur descriptif.

Naupacte est sélectionnée dans la catégorie innovation

Catégorie Start-up

On trouve deux projets de détection de défauts ou de précurseurs de défauts, et un projet un peu à part: un microprocesseur pour viser l’indépendance européenne.

Catégorie Innovation

On y trouve deux logiciels, l’un typé recherche, l’autre résultant d’une intégration “industrielle”, et LA bibliothèque généraliste pour les calculs: NAVPACTOS:

Descriptif public de Navpactos

Navpactos est une bibliothèque C++ constituant un langage et une boîte à outils pour la modélisation et l’exécution des calculs de simulation numérique. Il unifie et simplifie la description des calculs, connaît les éléments finis, les maillages et les matrices creuses, les fonctions et les champs; il construit et optimise « à l’exécution » les chaînes de calcul correspondantes et sait les dériver. Pour parvenir à ce résultat, Naupacte a conçu une expression tensorielle dont la richesse des opérateurs permet de procéder aux analyses formelles nécessaires aux contrôles, à l’optimisation, à la dérivation, pour fournir l’indispensable « calculateur virtuel ». Sa richesse fait du tenseur, associé à la performance de son calculateur, un objet communicable à tous les niveaux supérieurs de la boîte à outils pour assurer l’unité des programmes et leur simplicité par masquage des calculs. Ergonomie et puissance de développement, fiabilité, performance et maintenabilité du code résultant sont les atouts donnés à l’ambition des concepteurs comme à l’optimisation des compétences personnelles et des ressources matérielles. Sa phase de commercialisation commence, le produit basé sur plus de 3000 règles algébriques ayant été longuement testé par des dizaines de milliers de tests unitaires pour les tenseurs, et des centaines de cas applicatifs.
NAUPACTE pour le projet NAVPACTOS (sur le site de l’Usine Nouvelle)

Liens:

Forum Teratec 2022/Trophées

Cf page 19 du PDF: Catalogue du forum Teratec 2022.

Catégorie co-design

Deux projets impliquent l’IA mais de façons très différentes, tandis qu’un autre ne propose pas moins que de jumeler la Terre… numériquement bien entendu.

Grand prix du public

Il est désigné par vote du public parmi les 9 nommés.

Votez ici!

Qu’est-ce que la différentiation automatique?

Les modèles mathématiques de la physique regorgent de gradients, divergences, laplaciens, rotationnels, qui sont des dérivées en espace. On y trouve aussi des dérivées en temps pour les problèmes instationnaires. La dérivation est omniprésente.

Ce dont nous allons parler maintenant est plus général et vise jusqu’à la dérivation des modèles eux-mêmes par rapport à des variables diverses.

Motivation

Une telle dérivation intervient dès l’établissement des équations lorsque celles-ci dérivent d’un potentiel, ou bien pour leur résolution basée sur les informations données par le jacobien: le modèle est linéarisé.

Au-delà de la résolution de l’équation, l’optimisation des paramètres en vue d’un critère sur la solution tirera profit de la connaissance des dérivées de celle-ci par rapport à ceux-là, appelés encore sensibilité de la solution par rapport aux paramètres.

Entrons dans les détails bien connus des spécialistes de l’optimisation. Pour l’optimisation d’ordre 1, on observe que seule la variation efficace vis-à-vis du critère compte, c’est-à-dire la contraction de la variation de la solution avec le gradient du critère par rapport à la solution. Mais la variation de la solution résulte de la résolution d’un système linéaire que l’on peut choisir de transposer mathématiquement sur le gradient du critère. C’est la méthode adjointe, plus performante dès que le nombre de critères à optimiser est inférieur au nombre de paramètres de dérivation… En optimisation d’ordre supérieur, la combinaison de l’adjoint et des sensibilités sera utile.

Des méthodes très différentes

Qu’il s’agisse de variables inconnues ou de données, une fois discrétisées, le problème consiste à dériver une formule mathématique par rapport à une liste de ses entrées de calcul. Partant d’un code de calcul produisant le résultat de la formule mathématique à dériver, il existe trois méthodes pour développer le code fournissant la dérivée.

1. Différence finie

C’est la plus simple des méthodes: elle consiste à réutiliser le code original en faisant varier légèrement le paramètre d’entrée considéré et à faire la différence entre les deux résultats, que l’on divise par l’écart de paramètre. Avec un deuxième calcul pris en une valeur avec l’écart opposé, on obtient un résultat précis non plus au premier ordre mais au second.

Hélas les mathématiques sont contredites par l’informatique dont les arrondis vont empêcher les différences de se montrer précises, car les décimales en jeu seront de plus en plus faibles mais toujours relatives à la même valeur centrale. La précision est donc nécessairement limitée. De plus, le choix de l’écart -le fameux epsilon- pourra parfois n’être jamais satisfaisant si la quantité à dériver est une somme dont les termes sont d’ordre de grandeur différent sans relation avec l’ordre de grandeur de leurs variations… Le petit terme de variation importante sera écrasé et la dérivée perdra sa pertinence.

La méthode semi-analytique

Lorsque la solution provient de la résolution d’un système linéaire, plutôt que de faire la différence entre les solutions, il est préférable de la faire sur les seconds membres et de résoudre le système correspondant. C’est plus rapide et plus performant. Il faut bien sûr soit avoir une matrice constante soit être arrivé à convergence dans le cas linéarisé d’un algorithme de Newton. Voilà ce que dit l’analyse: on peut reporter la dérivation sur le second membre. Si celui-ci est calculé par différence finie, la méthode est dite semi-analytique.

Encore faut-il que le code ne soit plus tout-à-fait une boîte noire: il faut accéder au résultat du second membre avant la résolution du système linéaire. On reste donc à haut-niveau. La méthode de calcul de sensibilité dite semi-analytique est proposée par certains éditeurs.

2. La différentiation de code ligne-à-ligne (algorithmique)

C’est théoriquement le plus simple d’usage, grâce aux outils de différentiation automatique de code: on fournit le code, dont on précise la sortie et l’entrée, et l’outil génère le code calculant la dérivée. Pour cela, ligne après ligne, l’outil écrit le code contenant valeur et dérivée – car on sait dériver les fonctions de base – par chaînage direct ou inverse (adjoint). D’abord réservé au Fortran pour son absence de pointeurs, la méthode a été étendue au C++ par d’autres outils qui ont tiré profit de la surcharge d’opérateurs du langage pour minimiser la ré-ingénierie du code original. Les opérations sont en effet surchargées pour produire valeur et chaînage de dérivée au lieu de la valeur seule.

La méthode de différentiation algorithmique a tout son intérêt dans le cas de codes hérités complexes car, s’appuyant sur les mêmes calculs, elle évite le débogage d’un code nouveau. Elle demande néanmoins une assistance humaine experte pour être opérationnelle et efficace.

Le principe de la méthode semi-analytique doit absolument être employé pour éviter la dérivation ligne-à-ligne de la résolution du système linéaire. Voilà un exemple d’assistance humaine indispensable.

3. Dérivation symbolique de la formule

Dans l’idéal, on voudrait dériver symboliquement la formule et coder son calcul. Le faire à la main conduit à s’octroyer un temps de développement qu’on s’interdisait, tandis que passer par un logiciel de calcul formel a quelques inconvénients majeurs.

D’une part, il est difficile d’exprimer la formule quand elle s’appuie sur des concepts complexes comme les éléments finis et les maillages.
D’autre part, le résultat développé perd la structure tensorielle dont elle est issue et ne donne pas les performances optimales. L’optimisation de la génération de code par ces outils repose en effet sur l’identification de la répétition d’opérations de base comme les multiplications et les sommes de variables scalaires, alors qu’il y a mieux à faire, algébriquement parlant.

Selon les auteurs de la journée Algorithmic Differentiation Workshop organisée par le Groupe de Recherche GDR-Calcul du CNRS le 24 janvier 2019 à Paris, cela peut conduire à une explosion de la complexité des expressions.

C’est donc un défi…

La dérivation avec Navpactos

Moderniser son code de simulation?

L’occasion d’entreprendre la modernisation des processus de développements peut être provoquée par

la volonté d’accroître sa productivité, de réduire sa maintenance, de se focaliser sur ses atouts, de capitaliser sur ses développements
les besoins en nouvelles formulations et les calculs de sensibilité
les besoins en assemblages très rapides.

C’est sans doute l’occasion de considérer l’utilisation de NAVPACTOS, langage spécialement développé par Naupacte pour ces besoins-là. En effet, en débarrassant les codes de leur partie calculatoire, NAVPACTOS allège considérablement leur mise au point. Qu’en est-il alors de la performance? Loin d’être dégradées, les vitesses d’assemblage notamment sont inédites.

La programmation d’un assemblage par Éléments Finis est un exemple où NAVPACTOS brille par sa simplicité et sa performance.

La simplification de la réécriture n’est pas le seul atout de ce langage, car il ouvre la voie d’une programmation générique avec une grande réutilisabilité. En effet, sa puissance vient de ce qu’il est capable de transférer des formulations – ou définitions de calcul – grâce à son moteur de calcul formel tensoriel. Que l’on songe aux fonctionnalités qui manient de telles formulations: l’assemblage, les champs, les maillages, les algorithmes comme celui de Newton… et par conséquent les modules de plus haut niveau qui les utilisent. Tout le code basé sur NAVPACTOS bénéficie du concept de calcul formel.

Une ouverture possible permise par la réécriture avec NAVPACTOS est le développement d’un algorithme d’optimisation paramétrique utilisant les gradients de manière automatique.

NAVPACTOS est donc un outil à considérer lorsque la question se pose de moderniser son code de calcul.

Avec NAVPACTOS, vous pourrez, à partir des spécifications d’un modèle numérique, lues par exemple sur un fichier de commandes, composer facilement sa formulation et la construction du système correspondant, pour ensuite les calculer puis les mettre à jour au moyen d’un simple appel. Un langage dédié écrit en C++ simple et expressif vous permet de suivre le modèle mathématique.

Il suffit de compiler comme d’habitude votre programme de construction et de résolution faisant appel à NAVPACTOS. La performance exceptionnelle des calculs demandés est délivrée automatiquement grâce à une méthode inédite basée sur quelques milliers de règles internes.