Párový součet - Pairwise summation

v numerická analýza, párový součet, také zvaný kaskádový součet, je technika pro součet posloupnosti konečnýchpřesnost plovoucí bod čísla, která podstatně snižují nahromaděné chyba zaokrouhlení ve srovnání s naivním hromaděním součtu postupně.^[1] I když existují i ​​jiné techniky, jako je Kahanův součet které mají obvykle ještě menší chyby zaokrouhlování, je párový součet 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é operace) jako naivní součet.

Zejména párový součet posloupnosti n čísla X_n díla od rekurzivně rozdělení sekvence na dvě poloviny, sečtení každé poloviny a přidání dvou součtů: a algoritmus rozděl a panuj. Jeho nejhorší případy zaokrouhlovací chyby rostou asymptoticky jako nanejvýš Ó(ε logn), kde ε je přesnost stroje (za předpokladu pevné číslo podmínky, jak je uvedeno níže).^[1] Ve srovnání je naivní technika hromadění součtu v pořadí (přidání každého X_i jeden po druhém pro i = 1, ..., n) má chyby zaokrouhlení, které rostou v nejhorším případě jako Ó(εn).^[1] Kahanův součet má nejhorší chyba zhruba Ó(ε), nezávisle na n, ale vyžaduje několikrát více aritmetických operací.^[1] Pokud jsou chyby zaokrouhlování náhodné a zejména mají náhodné znaky, tvoří a náhodná procházka a růst chyb se sníží na průměrnou hodnotu ${ displaystyle O ( varepsilon { sqrt { log n}})}$ pro párový součet.^[2]

Velmi podobná rekurzivní struktura součtu se nachází v mnoha rychlá Fourierova transformace (FFT) a je zodpovědný za stejné pomalé zaokrouhlování těchto FFT.^[2][3]

Algoritmus

v pseudo kód, algoritmus párového součtu pro pole X délky n > 0 lze napsat:

s = po párech(X[1…n])      -li n ≤ N                    základní případ: naivní součet pro dostatečně malé pole          s = X[1]          pro i = 2 až n              s = s + X[i]      jiný                        rozděl a panuj: rekurzivně sečte dvě poloviny pole          m = podlaha (n / 2)          s = po párech(X[1…m]) + po párech(X[m+1…n])      skončit, pokud

Nerekurzivní verze algoritmu používá a zásobník hromadit dílčí částky:

partials = nový Zásobníkpro i = 1 až n    partials.push (X[i]) j = i zatímco is_even (j) j = podlaha (j / 2) p = částečné. pop () q = částečné. pop () částečné. tlačit (p + q) celkem = 0,0zatímco partials.size> 0 celkem = celkem + partials.pop ()vrátit se celkový

Pro některé dostatečně malé N, tento algoritmus přepne na naivní smyčkový součet jako a základní případ, jehož chyba je vázána na O (Nε).^[4] Celá částka má chybu v nejhorším případě, která roste asymptoticky jako Ó(ε logn) pro velké n, pro dané číslo podmínky (viz níže).

V algoritmu tohoto druhu (jako pro algoritmy rozděl a panuj obecně^[5]), je žádoucí použít větší základní případ, aby amortizovat režie rekurze. Li N = 1, pak existuje zhruba jedno rekurzivní volání podprogramu pro každý vstup, ale obecněji existuje jedno rekurzivní volání pro (zhruba) každý N/ 2 vstupy, pokud se rekurze zastaví přesněn = N. Děláním N dostatečně velká, režie rekurze může být 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^[3]).

Bez ohledu na N, přesně n−1 sčítání se provádí celkem, 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.

Varianta této myšlenky je rozdělit součet na b bloky v každé rekurzivní fázi, rekurzivní sčítání každého bloku a následné sčítání výsledků, které jeho navrhovatelé nazvali „superblokovým“ algoritmem.^[6] Výše uvedený párový algoritmus odpovídá b = 2 pro každou fázi s výjimkou poslední fáze, která jeb = N.

Přesnost

Předpokládejme, že jeden sčítá n hodnoty X_i, pro i = 1, ..., n. Přesná částka je:

${ displaystyle S_ {n} = součet _ {i = 1} ^ {n} x_ {i}}$

(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 ${ displaystyle S_ {n} + E_ {n}}$, kde došlo k chybě ${ displaystyle E_ {n}}$ je omezen výše:^[1]

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

kde ε je přesnost stroje použité aritmetiky (např. ε ≈ 10⁻¹⁶ pro standard dvojnásobná přesnost plovoucí bod). Obvykle je množství zájmu relativní chyba ${ displaystyle | E_ {n} | / | S_ {n} |}$, který je tedy výše omezen:

${ 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} vpravo |}} vpravo).}$

Ve výrazu pro relativní vázanou chybu zlomek (Σ |X_i| / | ΣX_i|) je číslo podmínky součtové úlohy. Číslo podmínky v zásadě představuje vnitřní citlivost součtového problému na chyby, bez ohledu na to, jak je vypočítán.^[7] Relativní chyba vázaná na každý (dozadu stabilní ) metoda součtu pevným algoritmem s pevnou přesností (tj. ne těmi, které používají.) aritmetika s libovolnou přesností, ani algoritmy, jejichž požadavky na paměť a čas se mění na základě dat), jsou úměrné tomuto počtu podmínek.^[1] An špatně podmíněný součtový problém je takový, ve kterém je tento poměr velký, a v tomto případě může mít i párová sumace velkou relativní chybu. Například pokud sčítá X_i jsou nekorelovaná náhodná čísla s nulovým průměrem, součet je a náhodná procházka a počet podmínek bude úměrný ${ displaystyle { sqrt {n}}}$. Na druhou stranu pro náhodné vstupy s nenulovou hodnotou znamená počet podmínek asymptoty na konečnou konstantu jako ${ displaystyle n to infty}$. Pokud jsou všechny vstupy nezáporné, pak je číslo podmínky 1.

Všimněte si, že ${ displaystyle 1- varepsilon log _ {2} n}$ jmenovatel je v praxi prakticky 1, protože ${ displaystyle varepsilon log _ {2} n}$ je mnohem menší než 1 do n stane se řádu 2^{1 / ε}, což je zhruba 10¹⁰¹⁵ ve dvojité přesnosti.

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, jak ${ displaystyle O ( varepsilon n)}$ vynásobeno číslem podmínky.^[1] 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 a střední kvadratická relativní chyba, která roste jako ${ displaystyle O ( varepsilon { sqrt {n}})}$ a párový součet má chybu, která roste jako ${ displaystyle O ( varepsilon { sqrt { log n}})}$ v průměru.^[2]

Softwarové implementace

Pairwise summation is the default summation algorithm in NumPy^[8] a Julia technicko-výpočetní jazyk,^[9] kde v obou případech bylo zjištěno, že má srovnatelnou rychlost s naivním sčítáním (díky použití velkého základního případu).

Mezi další softwarové implementace patří knihovna HPCsharp^[10] pro Cis Jazyk.

Reference