Somme par paires - Pairwise summation

Dans l'analyse numérique , la sommation par paires , également appelée sommation en cascade , est une technique pour additionner une séquence de nombres à virgule flottante de précision finie qui réduit considérablement l' erreur d'arrondi accumulée par rapport à l'accumulation naïve de la somme en séquence. Bien qu'il existe d'autres techniques telles que la sommation de Kahan qui ont généralement des erreurs d'arrondi encore plus petites, la sommation par paires est presque aussi bonne (ne différant que par un facteur logarithmique) tout en ayant un coût de calcul beaucoup plus faible - elle peut être mise en œuvre de manière à avoir près de même coût (et exactement le même nombre d'opérations arithmétiques) que la sommation naïve.

En particulier, la sommation par paires d'une séquence de n nombres x _n fonctionne en divisant récursivement la séquence en deux moitiés, en additionnant chaque moitié et en ajoutant les deux sommes: un algorithme de division et de conquête . Ses erreurs d'arrondi dans le pire des cas croissent asymptotiquement comme au plus O (ε log  n ), où ε est la précision de la machine (en supposant un nombre de condition fixe , comme discuté ci-dessous). En comparaison, la technique naïve d'accumuler la somme en séquence (en ajoutant chaque x _i un à la fois pour i  = 1, ...,  n ) a des erreurs d'arrondi qui croissent au pire comme O (ε n ). La sommation de Kahan a une erreur dans le pire des cas d'environ O (ε), indépendante de n , mais nécessite plusieurs fois plus d'opérations arithmétiques. Si les erreurs d'arrondi sont aléatoires, et en particulier ont des signes aléatoires, elles forment alors une marche aléatoire et la croissance des erreurs est réduite à une moyenne de pour une sommation par paires. ${\ displaystyle O (\ varepsilon {\ sqrt {\ log n}})}$

Une structure de sommation récursive très similaire se trouve dans de nombreux algorithmes de transformée de Fourier rapide (FFT) et est responsable de la même accumulation lente d'arrondi de ces FFT.

L'algorithme

En pseudo - code , l'algorithme de sommation par paire pour un tableau x de longueur n > 0 peut s'écrire:

s = pairwise(x[1…n])
      if n ≤ N     base case: naive summation for a sufficiently small array
          s = x[1]
          for i = 2 to n
              s = s + x[i]
      else         divide and conquer: recursively sum two halves of the array
          m = floor(n / 2)
          s = pairwise(x[1…m]) + pairwise(x[m+1…n])
      end if

Pour certains N suffisamment petits , cet algorithme passe à une sommation naïve basée sur une boucle comme cas de base , dont la borne d'erreur est O (Nε). La somme entière a une erreur du pire des cas qui croît asymptotiquement comme O (ε log  n ) pour un grand n , pour un nombre de condition donné (voir ci-dessous).

Dans un algorithme de ce type (comme pour les algorithmes de division et de conquête en général), il est souhaitable d'utiliser un cas de base plus large afin d' amortir la surcharge de la récursivité. Si N  = 1, alors il y a à peu près un appel de sous - récursif pour chaque entrée, mais plus généralement il y a un appel récursif pour ( à peu près) tous les N / 2 entrées si la récursion arrête à exactement  n  =  N . En rendant N suffisamment grand, le surcoût de la récursivité peut être rendu négligeable (précisément cette technique d'un grand cas de base pour la sommation récursive est utilisée par les implémentations FFT haute performance).

Indépendamment de N , exactement n −1 additions sont effectuées au total, comme pour la sommation naïve, donc si le surcoût de récursivité est rendu négligeable, alors la sommation par paires a essentiellement le même coût de calcul que pour la sommation naïve.

Une variante de cette idée est de diviser la somme en b blocs à chaque étape récursive, en additionnant chaque bloc de manière récursive, puis en additionnant les résultats, ce qui a été surnommé un algorithme de «superbloc» par ses proposants. Les ci - dessus correspond l' algorithme de paire à b  = 2 pour chaque étape , sauf pour la dernière étape , qui est  b  =  N .

Précision

Supposons que l'on additionne n valeurs x _i , pour i  = 1, ...,  n . La somme exacte est:

${\ displaystyle S_ {n} = \ sum _ {i = 1} ^ {n} x_ {i}}$

(calculé avec une précision infinie).

Avec la somme par paires pour un cas de base N  = 1, on obtient à la place , où l'erreur est limitée ci-dessus par: ${\ displaystyle S_ {n} + E_ {n}}$${\ displaystyle E_ {n}}$

${\ displaystyle | E_ {n} | \ leq {\ frac {\ varepsilon \ log _ {2} n} {1- \ varepsilon \ log _ {2} n}} \ sum _ {i = 1} ^ {n } | x_ {i} |}$

où ε est la précision machine de l'arithmétique employée (par exemple ε ≈ 10 ^-16 pour une virgule flottante double précision standard ). Habituellement, la quantité d'intérêt est l' erreur relative , qui est donc bornée ci-dessus par: ${\ displaystyle | E_ {n} | / | S_ {n} |}$

${\ displaystyle {\ frac {| E_ {n} |} {| S_ {n} |}} \ leq {\ frac {\ varepsilon \ log _ {2} n} {1- \ varepsilon \ log _ {2} n}} \ left ({\ frac {\ sum _ {i = 1} ^ {n} | x_ {i} |} {\ left | \ sum _ {i = 1} ^ {n} x_ {i} \ droite |}} \ droite).}$

Dans l'expression de la borne d'erreur relative, la fraction (Σ | x _i | / | Σ x _i |) est le numéro de condition du problème de sommation. Essentiellement, le numéro de condition représente la sensibilité intrinsèque du problème de sommation aux erreurs, quelle que soit la façon dont il est calculé. La borne d'erreur relative de chaque méthode de sommation ( stable en arrière ) par un algorithme fixe à précision fixe (c'est-à-dire pas ceux qui utilisent l'arithmétique de précision arbitraire , ni les algorithmes dont les exigences de mémoire et de temps changent en fonction des données), est proportionnelle à ce nombre de condition . Un problème de sommation mal conditionné est celui dans lequel ce rapport est grand, et dans ce cas, même une sommation par paires peut avoir une grande erreur relative. Par exemple, si les sommations x _i sont des nombres aléatoires non corrélés avec une moyenne nulle, la somme est une marche aléatoire et le nombre de conditions croîtra proportionnellement à . D'autre part, pour les entrées aléatoires avec une valeur différente de zéro, le nombre de conditions asymptotes à une constante finie comme . Si les entrées sont toutes non négatives , le numéro de condition est 1. ${\ displaystyle {\ sqrt {n}}}$${\ Displaystyle n \ to \ infty}$

On notera que le dénominateur est effectivement 1 en pratique, puisqu'il est beaucoup plus petit que 1 jusqu'à ce que n devienne d'ordre 2 ^{1 / ε} , soit environ 10 ^{10 15} en double précision. ${\ displaystyle 1- \ varepsilon \ log _ {2} n}$${\ displaystyle \ varepsilon \ log _ {2} n}$

En comparaison, l'erreur relative liée à la sommation naïve (simplement en ajoutant les nombres en séquence, en arrondissant à chaque étape) augmente lorsqu'elle est multipliée par le numéro de condition. En pratique, il est beaucoup plus probable que les erreurs d'arrondi aient un signe aléatoire, avec une moyenne nulle, de sorte qu'elles forment une marche aléatoire; dans ce cas, la somme naïve a une racine carrée moyenne erreur relative qui augmente à mesure que et sommation a une erreur par paire qui croît en moyenne. ${\ displaystyle O (\ varepsilon n)}$${\ displaystyle O (\ varepsilon {\ sqrt {n}})}$${\ displaystyle O (\ varepsilon {\ sqrt {\ log n}})}$

Implémentations logicielles

La sommation par paires est l'algorithme de sommation par défaut dans NumPy et le langage de calcul technique Julia , où dans les deux cas il s'est avéré avoir une vitesse comparable à la sommation naïve (grâce à l'utilisation d'un grand cas de base).

D' autres implémentations logicielles comprennent la bibliothèque HPCsharp pour le C de Sharp langue et la sommation bibliothèque standard dans D .

Les références