Comment identifier les calculs en virgule flottante instables?

15

En numérique, il est très important de pouvoir identifier des schémas instables et d'améliorer leur stabilité. Comment identifier les calculs en virgule flottante instables?

Je travaille sur une simulation très complexe où de nombreux schémas numériques fonctionnent ensemble et je recherche une méthodologie pour identifier ses points faibles. Je travaille sur un modèle physique impliquant des équations différentielles. Une vue d'ensemble du processus global est:

  1. (Étape préliminaire) Recueillir les observations physiques P .

  2. Déterminez les paramètres initiaux de la simulation. Cela utilise un algorithme d'optimisation, où nous marchons dans un espace de paramètres et recherchons des paramètres C tels que certaines fonctions d'erreur E (F (C), P) soient minimisées, où F est une quantité dérivée des paramètres.

  3. Branchez C dans le moteur de simulation. Il s'agit d'un schéma d'Euler de l'EDP, de sorte qu'à chaque pas de temps, nous calculons les termes entraînant la dynamique (chacun d'eux est une fonction complexe, potentiellement sujette à l'instabilité) et alimentons le schéma d'Euler avec ces termes dynamiques pour calculer le prochain Etat. Cela continue pendant des milliers de points dans le temps.

  4. À la fin de la simulation, nous calculons une fonction Proof (S) de l'état final S et la comparons à certaines quantités Require (P) déduites des quantités observées. Ce n'est pas une preuve formelle du résultat, mais plutôt un contrôle de plausibilité.

Aussi, je vois une tour d'opérations complexes (calcul de termes dynamiques, dans le schéma d'Euler, dans le Proof ). Et je voudrais reconnaître les «mauvaises pièces» et les corriger.

Je suppose que l'utilisation d'une implémentation logicielle de nombres à virgule flottante avec une précision réduite amplifierait l'instabilité des schémas numériques, facilitant ainsi la comparaison entre les différentes implémentations. Est-ce une technique courante pour enquêter sur cette question? Est-il possible d'utiliser une machine virtuelle, comme Bochs, pour y parvenir sans altérer le programme?

Pour traiter correctement la question de stabilité, il est parfois acceptable de cibler l'entrée typique de la procédure numérique, afin qu'elle puisse être réglée pour bien fonctionner sur cette entrée et peut-être moins bien sur d'autres entrées valides, mais peu probables. Étant donné un échantillon d'entrées typiques, il est possible de fouiner certains résultats intermédiaires et de préparer un profil statistique pour eux. Encore une fois, est-ce une technique courante pour étudier les problèmes de stabilité? Une machine virtuelle est-elle utile pour cela?

user40989
la source
peut-être aurez-vous des réponses plus intéressantes sur math.stackexchange.com
Simon Bergot
@Simon Vous avez peut-être raison, mais c'est certainement une question interdomaine. J'imagine que les personnes capables de répondre sont inscrites aux mathématiques et aux programmeurs ou à aucune… Attendons un peu pour voir si cette question trouve sa réponse ici!
user40989
1
Arithmétique d'intervalle?
SK-logic
2
Utiliser Euler pour propager l'état n'est pas nécessairement mauvais; l'optimisation n'est pas non plus, mais vous devez vraiment diviser le problème en sous-tâches. L'instabilité numérique est peut-être le moindre de vos malheurs - la convergence vers un faux maximum et les problèmes liés à la rigidité des ODE / PDE sont plus importants que cela. Et oui, n'utilisez jamais la simple précision :)
Deer Hunter

Réponses:

6

L'étude de la stabilité du calcul en virgule flottante fait partie de l'analyse numérique et si vous voulez vraiment un résultat solide, vous voulez vraiment que quelqu'un de compétent dans ce domaine fasse l'analyse des algorithmes utilisés.

Il y a certaines choses qui peuvent aider à identifier expérimentalement des algorithmes instables. Exécution avec arrondi réglé sur différents modes (haut / bas / aléatoire) ou avec une précision différente et en vérifiant que le résultat ne varie pas trop. Répondre est-ce trop? n'est pas simple du tout et même lorsque la réponse est non, cela ne signifie pas que l'algorithme est stable, juste qu'il n'a pas été détecté instable sur l'ensemble de données que vous avez utilisé.

L'arithmétique des intervalles a été proposée dans les commentaires. Quand je l'ai regardé, même le partisan le plus enragé de l'arithmétique d'intervalle a admis qu'il fonctionnait bien avec des algorithmes conçus pour l'arithmétique d'intervalle mais que passer à celui-ci sans analyser l'algorithme et s'assurer qu'il n'avait pas de modèles connus pour ne pas bien fonctionner ne le ferait pas être utile (les opposants semblaient d'avis que les conditions préalables à l'arithmétique des intervalles étaient utiles lorsqu'elles étaient trop restrictives pour avoir un intérêt pratique)

AProgrammer
la source
3

La conception d'algorithmes à virgule flottante stables est très simple. Ceux qui sont plus doués en mathématiques que moi suggèrent d'utiliser des bibliothèques réputées dans la mesure du possible plutôt que d'essayer de lancer les vôtres. La référence standard dans le domaine semble être:

NJ Higham. Précision et stabilité des algorithmes numériques. Society for Industrial and Applied Mathematics, Philadelphie, PA, États-Unis, deuxième édition, 2002. ISBN 0-89871-521-0

Ne pas en savoir plus sur les types de calculs, de langues, etc., il est difficile de donner une réponse concrète. Il y a une bonne conférence ici: http://introcs.cs.princeton.edu/java/91float/ cela peut être un peu basique, mais c'est une bonne introduction si vous utilisez java.

WPrecht
la source
1

Comment identifier les calculs en virgule flottante instables? Est-ce une technique courante pour enquêter sur cette question?

Je pense que si vous n'avez pas besoin de montrer des statistiques sur les erreurs, vous n'avez pas vraiment besoin de collecter des échantillons. Ce dont vous avez besoin, c'est d'une analyse numérique , qui relève également des sujets des méthodes numériques, de l'algèbre linéaire numérique, etc.

Quoi qu'il en soit, dans la programmation générale, la plupart des problèmes sont faciles à repérer étant donné une compréhension de base du fonctionnement des virgules flottantes et des méthodes numériques de base. Mais des problèmes encore plus complexes sont «plus faciles» à résoudre aujourd'hui avec la disponibilité de flottants 128 bits, encore moins de raisons de produire des échantillons d'erreur. Voici quelques exemples de problèmes pour montrer mon point:

  1. en virgule flottante pour le calcul des valeurs monétaires.
  2. en virgule flottante pour les grands nombres.
  3. ne pas faire de divisions avant d'autres opérations quand il est possible de le faire. (pour rapprocher la valeur de 0).
  4. calcul long sans traitement particulier pour la propagation des erreurs.

Il existe également un exemple d'algorithme naïf et d'algorithme à compensation d'erreur ici pour calculer la variance . Dans l'exemple, en regardant la version naïve, vous pouvez juste sentir que faire un calcul en boucle entraînera des erreurs et n'est pas compensé.

imel96
la source
Merci pour votre réponse, je recherche cependant des informations plus détaillées. J'ai un très gros calcul et je veux identifier ses parties faibles. J'ai modifié la question en conséquence.
user40989
Je ne sais pas exactement quelle est votre situation lorsque vous dites que vous avez un gros calcul et que vous souhaitez identifier les parties faibles. Les calculs numériques contiennent intrinsèquement des erreurs, même une simple opération d'ajout. Donc, à moins que votre grand calcul ne soit compensé par une erreur, alors ils doivent être corrigés dans leur ensemble. L'amélioration des points faibles pourrait ne pas être suffisante. Si vous êtes maintenant le "epsilon" de votre modèle à virgule flottante, une simple analyse montrera l'ampleur de l'erreur alors qu'elle se propage à travers le long calcul.
imel96
0

Vous pouvez éviter les erreurs numériques en utilisant les types de données appropriés (comme, par exemple, les fractions continues). Si vous avez besoin ou souhaitez utiliser l'arithmétique à virgule flottante, vous devez appliquer un savoir-faire numérique pour connaître les erreurs.

Ingo
la source
Je ne veux pas éviter les erreurs numériques, je veux trouver quelles parties du calcul sont instables. Cela revient à localiser les goulots d'étranglement de la vitesse lors de l'optimisation de la vitesse. Je veux donc optimiser la précision et donc trouver des goulots d'étranglement de précision. (Les fractions continues ne sont pas utiles ici.)
user40989
1
@ user40989, alors vous avez certainement besoin de l'arithmétique d'intervalle.
SK-logic