Suma recursivă în perechi

În analiza numerică , însumarea recursivă în perechi (însumarea pereche în engleză ), numită și summation cascade (sumare în cascadă), este o tehnică pentru însumarea unei secvențe de numere în virgulă mobilă de precizie peste care reduce substanțial „ rotunjirea erorii acumulată în comparație cu aceea acumulat prin însumare simplă în ordine. ^[1] Deși există și alte tehnici, cum ar fi algoritmul de însumare Kahan , care de obicei au și erori de rotunjire mai mici, sumarea recursivă pereche este aproape la fel de bună (diferă doar printr-un factor logaritmic), în ciuda unui cost de calcul mult mai mic; poate fi implementat pentru a avea aproape același cost (și exact același număr de operații aritmetice) ca suma simplă.

În special, însumarea recursivă în perechi a unei secvențe de n numere x _n funcționează împărțind recursiv secvența în două jumătăți, adăugând fiecare jumătate și adăugând cele două sume: un algoritm de împărțire și cucerire . Erorile sale de rotunjire în cel mai rău caz cresc asimptotic cel mult ca O (ε log n ), unde ε este precizia mașinii (presupunând un număr de condiționare fix, așa cum se discută mai jos). ^[1] Pe de altă parte, tehnica simplă de a acumula suma în ordine (adăugând fiecare x _i câte unul pentru i = 1, ..., n ) are erori de rotunjire care cresc cel mai rău ca O (ε n ) . ^[1] Suma Kahan are o eroare de cel mai rău caz de aproximativ O (ε), independent de n , dar necesită de multe ori mai multe operații aritmetice. ^[1] Dacă erorile de rotunjire sunt aleatorii și, în special, au semne aleatorii, atunci dau naștere la o mers aleatoriu și, pentru însumarea recursivă pereche, creșterea erorii este redusă la o medie de $O(\varepsilon {\sqrt {\log n}})$ ${\ displaystyle O (\ varepsilon {\ sqrt {\ log n}})}$ ${\ displaystyle O (\ varepsilon {\ sqrt {\ log n}})}$ . ^[2]

O structură de însumare recursivă foarte similară se găsește în mulți algoritmi de transformare Fourier rapidă (FFT) și este responsabilă pentru aceeași acumulare lentă de erori de rotunjire în astfel de FFT-uri. ^[2] ^[3]

Suma recursivă pereche este algoritmul de însumare implicit în NumPy ^[4] și în limbajul de calcul tehnic Julia , ^[5] unde în ambele cazuri se constată că are o viteză comparabilă cu suma simplă (datorită utilizării unui model de bază larg ).

Algoritmul

În pseudocod , algoritmul de însumare recursivă pereche pentru o matrice x de lungime n > 0 poate fi scris:

 s = pairwise ( x [1 ... n ])
      dacă n ≤ N model de bază: însumare simplă pentru o matrice suficient de mică
          s = x [1]
          pentru i = 2 până la n
              s = s + x [ i ]
      altfel împărțiți și cuceriți : însumați recursiv două jumătăți ale matricei
          m = etaj ( n / 2)
          s = pairwise ( x [1 ... m ]) + pairwise ( x [ m + 1 ... n ])
      endif

Pentru unii N suficient de mici, acest algoritm trece la o sumă simplă de buclă ca model de bază, a cărei limită de eroare este O (Nε). ^[6] Întreaga sumă are o eroare în cel mai rău caz care crește asimptotic ca O (ε log n ) pentru n mare, pentru un număr de condiționare dat (a se vedea mai jos).

Într-un algoritm de acest tip (ca în general pentru un algoritm de împărțire și cucerire ^[7] ), este preferabil să se utilizeze un model de bază mai larg pentru a amortiza cheltuielile generale ale recursivității. Dacă N = 1, atunci există aproximativ un apel recursiv către un subrutin pentru fiecare intrare, dar mai general există un apel recursiv (aproximativ) pentru fiecare N / 2 intrări dacă recursivitatea se oprește exact la n = N. Făcând N suficient de mare, costul recursiv poate fi făcut neglijabil (tocmai această tehnică largă a modelului de bază pentru însumarea recursivă este utilizată de implementările FFT de înaltă performanță ^[3] ).

Indiferent de N , exact, n −1 adunări sunt efectuate în total, atât cât pentru sumarea simplă, deci dacă recursivitatea generală este neglijabilă, atunci suma sumară recursivă în perechi are în esență același cost de calcul ca suma simplă.

O variantă a acestei idei este să împărțiți suma în blocuri b la fiecare fază recursivă, însumând fiecare bloc recursiv și apoi adăugând rezultatele; această variantă a fost numită algoritm de „superbloc” de către susținătorii săi. ^[8] Algoritmul însumării recursive în perechi văzut mai sus corespunde cazului b = 2 pentru fiecare fază, cu excepția ultimei în care b = N.

Precizie

Să presupunem că adăugăm n valori x _i , pentru i = 1, ..., n . Suma exactă este:

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

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

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

(calculat cu o precizie infinită).

Pe de altă parte, cu însumarea recursivă în perechi pentru un model de bază N = 1, obținem $S_{n}+E_{n}$ ${\ displaystyle S_ {n} + E_ {n}}$ ${\ displaystyle S_ {n} + E_ {n}}$ , unde eroarea $E_{n}$ ${\ displaystyle E_ {n}}$ $E_ {n}$ este limitat în partea de sus de: ^[1]

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

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

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

unde ε este precizia mașinii aritmeticii utilizate (de exemplu ε ≈ 10 ⁻¹⁶ pentru formatul standard cu virgulă mobilă de dublă precizie ). În general, valoarea dobânzii este eroarea relativă $|E_{n}|/|S_{n}|$ ${\ displaystyle | E_ {n} | / | S_ {n} |}$ ${\ displaystyle | E_ {n} | / | S_ {n} |}$ , care este, prin urmare, limitat în partea de sus de:

{\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}\right|}}\right).

{\ 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} \ dreapta |}} \ dreapta).}

{\ 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} \ dreapta |}} \ dreapta).}

În expresia pentru limita de eroare relativă, fracția (Σ | x _i | / | Σ x _i |) este numărul condiției problemei corespunzătoare sumării. În esență, numărul condiționat reprezintă sensibilitatea intrinsecă a problemei corespunzătoare sumării la erori, indiferent de ceea ce este calculat. ^[9] Limita de eroare relativă a fiecărei metode de însumare ( stabilă înapoi ) pentru un algoritm fix cu o precizie fixă (deci nu cele care utilizează aritmetică de precizie arbitrară , nici algoritmi ale căror cerințe de memorie și timp se modifică în funcție de date), este proporțională cu această numărul condiționării. ^[1] O problemă de sumare slab condiționată este una în care acest raport este mare și, în acest caz, chiar și suma sumară recursivă în perechi poate avea o eroare relativă mare. De exemplu, dacă aditivele x _i sunt numere aleatorii fără legătură cu medie zero, suma este o plimbare aleatorie și numărul condiționat va crește proporțional cu ${\sqrt {n}}$ ${\ displaystyle {\ sqrt {n}}}$ $\ sqrt {n}$ . Pe de altă parte, pentru intrări aleatorii medii diferite de zero, numărul condiționării tinde spre o constantă finită pentru $n\to \infty$ ${\ displaystyle n \ to \ infty}$ $n \ to \ infty$ . Dacă intrările sunt toate non-negative , atunci numărul de condiționare este 1.

Observăm că numitorul $1-\varepsilon \log _{2}n$ ${\ displaystyle 1- \ varepsilon \ log _ {2} n}$ ${\ displaystyle 1- \ varepsilon \ log _ {2} n}$ în practică este 1, deoarece $\varepsilon \log _{2}n$ ${\ displaystyle \ varepsilon \ log _ {2} n}$ ${\ displaystyle \ varepsilon \ log _ {2} n}$ este mult mai mic de 1 până când n devine de ordinul 2 ^{1 / ε} , care este de aproximativ 10 ^{10 ¹⁵} cu precizie dublă.

În comparație, limita relativă de eroare pentru însumarea simplă (adăugarea simplă a numerelor în ordine, rotunjire la fiecare pas) crește ca $O(\varepsilon n)$ ${\ displaystyle O (\ varepsilon n)}$ ${\ displaystyle O (\ varepsilon n)}$ înmulțit cu numărul de condiționare. ^[1] În practică, erorile de rotunjire sunt mult mai susceptibile de a avea un semn aleatoriu, cu medie zero, astfel încât să dea naștere unei mers aleatorii; în acest caz, suma simplă are o eroare relativă, având în vedere abaterea standard, care crește ca $O(\varepsilon {\sqrt {n}})$ ${\ displaystyle O (\ varepsilon {\ sqrt {n}})}$ ${\ displaystyle O (\ varepsilon {\ sqrt {n}})}$ iar însumarea recursivă pereche are o eroare care crește pe măsură ce $O(\varepsilon {\sqrt {\log n}})$ ${\ displaystyle O (\ varepsilon {\ sqrt {\ log n}})}$ ${\ displaystyle O (\ varepsilon {\ sqrt {\ log n}})}$ in medie. ^[2]

Notă

^ ^a ^b ^c ^d ^e ^f ^g Nicholas J. Higham, The accurate of floating point summation , în SIAM Journal on Scientific Computing , vol. 14, n. 4, 1993, pp. 783–799, DOI : 10.1137 / 0914050 .
^ ^a ^b ^c Manfred Tasche și Hansmartin Zeuner Handbook of Analytic-Computational Methods in Applied Mathematics Boca Raton, FL: CRC Press, 2000).
^ ^a ^b SG Johnson și M. Frigo, „ Implementing FFTs in practice , în Fast Fourier Transforms , editat de C. Sidney Burrus (2008).
^ ENH: implementați sumare pereche , github.com/numpy/numpy pull request # 3685 (septembrie 2013).
^ RFC: utilizați sumarea pereche pentru sumă, cumsum și cumprod , github.com/JuliaLang/julia pull request # 4039 (august 2013).
^ Nicholas Higham, Accuracy and Stability of Numerical Algorithms (2 ed.) , SIAM, 2002, pp. 81-82.
^ Radu Rugina și Martin Rinard, „Recursiederulându-se pentru programe de divizare și cucerire ”, în Limbi și compilatoare pentru calcul paralel , capitolul 3, pp. 34–48. Note de curs în Informatică vol. 2017 (Berlin: Springer, 2001).
^ Anthony M. Castaldo, R. Clint Whaley și Anthony T. Chronopoulos, „Reducerea erorilor în virgulă mobilă în produsul cu puncte folosind familia de algoritmi superbloc”, SIAM J. Sci. Comput. , vol. 32, pp. 1156–1174 (2008).
^ LN Trefethen și D. Bau, Algebra liniară numerică (SIAM: Philadelphia, 1997).

Elemente conexe

Portalul de matematică : accesați intrările Wikipedia care se ocupă de matematică

[Higham93-1] ^ ^a ^b ^c ^d ^e ^f ^g Nicholas J. Higham, The accurate of floating point summation , în SIAM Journal on Scientific Computing , vol. 14, n. 4, 1993, pp. 783–799, DOI : 10.1137 / 0914050 .

[Tasche-2] Manfred Tasche și Hansmartin Zeuner Handbook of Analytic-Computational Methods in Applied Mathematics Boca Raton, FL: CRC Press, 2000).

[JohnsonFrigo08-3] SG Johnson și M. Frigo, „ Implementing FFTs in practice , în Fast Fourier Transforms , editat de C. Sidney Burrus (2008).

[4] ENH: implementați sumare pereche , github.com/numpy/numpy pull request # 3685 (septembrie 2013).

[5] RFC: utilizați sumarea pereche pentru sumă, cumsum și cumprod , github.com/JuliaLang/julia pull request # 4039 (august 2013).

[6] Nicholas Higham, Accuracy and Stability of Numerical Algorithms (2 ed.) , SIAM, 2002, pp. 81-82.

[7] Radu Rugina și Martin Rinard, „Recursiederulându-se pentru programe de divizare și cucerire ”, în Limbi și compilatoare pentru calcul paralel , capitolul 3, pp. 34–48. Note de curs în Informatică vol. 2017 (Berlin: Springer, 2001).

[Castaldo08-8] Anthony M. Castaldo, R. Clint Whaley și Anthony T. Chronopoulos, „Reducerea erorilor în virgulă mobilă în produsul cu puncte folosind familia de algoritmi superbloc”, SIAM J. Sci. Comput. , vol. 32, pp. 1156–1174 (2008).

[9] LN Trefethen și D. Bau, Algebra liniară numerică (SIAM: Philadelphia, 1997).

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]