Párový součet - Pairwise summation

V numerické analýze je párový součet , nazývaný také kaskádový součet , technika k součtu posloupnosti čísel s plovoucí desetinnou čárkou s konečnou přesností, která podstatně snižuje akumulovanou chybu zaokrouhlování ve srovnání s naivní akumulací součtu v sekvenci. Ačkoli existují i ​​jiné techniky, jako je Kahanův součet, které mají obvykle ještě menší chyby zaokrouhlování, párový součet je téměř stejně dobrý (liší se pouze logaritmickým faktorem) a má mnohem nižší výpočetní náklady - lze jej implementovat tak, aby měl téměř stejné náklady (a přesně stejný počet aritmetických operací) jako naivní součet.

Zejména párový součet sekvence n čísel x n funguje tak, že rekurzivně rozdělí sekvenci na dvě poloviny, sčítá každou polovinu a přidá dvě součty: algoritmus rozděl a panuj . Jeho nejhorší případy zaokrouhlovací chyby rostou asymptoticky jako nanejvýš O (ε log  n ), kde ε je přesnost stroje (za předpokladu čísla pevné podmínky , jak je popsáno níže). Ve srovnání má naivní technika hromadění součtu v pořadí (přidávání každého x i jeden po druhém pro i  = 1, ...,  n ) chyby zaokrouhlování, které rostou v nejhorším případě jako O (ε n ). Kahanova sumace má nejhorší chybu zhruba O (ε), nezávislou na n , ale vyžaduje několikrát více aritmetických operací. Pokud jsou chyby zaokrouhlení náhodné a zejména mají náhodné znaky, tvoří náhodnou procházku a nárůst chyb se sníží na průměrnou hodnotu pro párový součet.

Velmi podobná rekurzivní struktura součtu se nachází v mnoha algoritmech rychlé Fourierovy transformace (FFT) a je zodpovědná za stejnou pomalou akumulaci těchto FFT.

Algoritmus

V pseudokódu lze zapsat algoritmus párového součtu pro pole x délky n > 0: 

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

U nějakého dostatečně malého N se tento algoritmus přepne na naivní smyčkový součet jako základní případ , jehož chyba je O (Nε). Celá suma má nejhorší chybu, která roste asymptoticky jako O (ε log  n ) pro velké n , pro dané číslo podmínky (viz níže).

V algoritmu tohoto druhu ( obecně pro algoritmy dělení a dobývání ) je žádoucí použít větší základní případ, aby se amortizovala režie rekurze. V případě N  = 1, pak je zde zhruba rekurzivní volání podprogramu pro každý vstup, ale obecně je tam jeden rekurzivní volání pro (zhruba) každý N / 2 vstupy v případě, že rekurze se zastaví v přesně  n  =  N . Tím, že N dostatečně velký, může být režie rekurze zanedbatelná (právě tato technika velkého základního případu pro rekurzivní součet je využívána vysoce výkonnými implementacemi FFT).

Bez ohledu na N se provádí celkem přesně n −1 sčítání, stejně jako u naivního součtu, takže pokud je režie rekurze zanedbatelná, pak má párový součet v zásadě stejné výpočetní náklady jako u naivního součtu.

Variací této myšlenky je rozdělit součet na b bloky v každé rekurzivní fázi, rekurzivně sčítat každý blok a poté sečíst výsledky, které jeho navrhovatelé nazvali algoritmem „superbloku“. Výše uvedené párové algoritmus odpovídá b  = 2, pro každou fázi, s výjimkou posledního stupně, který je  b  =  N .

Přesnost

Předpokládejme, že se sečte n hodnot x i , pro i  = 1, ...,  n . Přesná částka je:

(počítáno s nekonečnou přesností).

S párovým součtem pro základní případ N  = 1 místo toho získá jeden , kde je chyba ohraničena výše:

kde ε je strojová přesnost použité aritmetiky (např. ε ≈ 10 −16 pro standardní plovoucí desetinnou čárku s dvojitou přesností ). Obvykle je množství zájmu relativní chybou , která je proto výše omezena:

Ve výrazu pro relativní vázanou chybu je zlomek (Σ | x i | / | Σ x i |) číslem podmínky úlohy součtu. Číslo podmínky v podstatě představuje vnitřní citlivost součtového problému na chyby, bez ohledu na to, jak je vypočítán. Relativní chyba vázaná na každou ( zpětně stabilní ) metodu sčítání pevným algoritmem s pevnou přesností (tj. Ne těmi, které používají aritmetiku s libovolnou přesností , ani algoritmy, jejichž požadavky na paměť a čas se na základě dat mění), je úměrná tomuto počtu podmínek . Špatně podmíněné součet Problém je ten, ve kterém je tento poměr je velký, a v tomto případě i po dvou sčítání může mít velkou relativní chybu. Například pokud jsou summandy x i nekorelovaná náhodná čísla s nulovým průměrem, je součet náhodným procházením a počet podmínek bude úměrný . Na druhou stranu pro náhodné vstupy s nenulovou hodnotou znamená počet podmínek asymptoty na konečnou konstantu jako . Pokud jsou všechny vstupy nezáporné , pak je číslo podmínky 1.

Všimněte si, že jmenovatel je v praxi 1, protože je mnohem menší než 1, dokud se n nestane řádem 2 1 / ε , což je zhruba 10 10 15 s dvojitou přesností.

Ve srovnání relativní chyba vázaná na naivní součet (jednoduché přidávání čísel v pořadí, zaokrouhlování v každém kroku) roste vynásobením číslem podmínky. V praxi je mnohem pravděpodobnější, že chyby zaokrouhlování mají náhodné znaménko s nulovým průměrem, takže tvoří náhodnou procházku; v tomto případě má naivní součet relativní chybu s odmocninou, která roste, a párová sumace má chybu, která roste jako průměr.

Softwarové implementace

Pairwise summation is the default summation algorithm in NumPy and the Julia technical-computing language , where in both cases it was found to have compared speed to naive summation (thanks to the use of a large base case).

Jiné implementace softwaru patří HPCsharp knihovnu pro C Sharp jazyka a standardní knihovny sčítání v D .

Reference