| http://dbpedia.org/ontology/abstract
|
In numerical analysis, pairwise summation, … In numerical analysis, pairwise summation, also called cascade summation, is a technique to sum a sequence of finite-precision floating-point numbers that substantially reduces the accumulated round-off error compared to naively accumulating the sum in sequence. Although there are other techniques such as Kahan summation that typically have even smaller round-off errors, pairwise summation is nearly as good (differing only by a logarithmic factor) while having much lower computational cost—it can be implemented so as to have nearly the same cost (and exactly the same number of arithmetic operations) as naive summation. In particular, pairwise summation of a sequence of n numbers xn works by recursively breaking the sequence into two halves, summing each half, and adding the two sums: a divide and conquer algorithm. Its worst-case roundoff errors grow asymptotically as at most O(ε log n), where ε is the machine precision (assuming a fixed condition number, as discussed below). In comparison, the naive technique of accumulating the sum in sequence (adding each xi one at a time for i = 1, ..., n) has roundoff errors that grow at worst as O(εn). Kahan summation has a worst-case error of roughly O(ε), independent of n, but requires several times more arithmetic operations. If the roundoff errors are random, and in particular have random signs, then they form a random walk and the error growth is reduced to an average of for pairwise summation. A very similar recursive structure of summation is found in many fast Fourier transform (FFT) algorithms, and is responsible for the same slow roundoff accumulation of those FFTs. slow roundoff accumulation of those FFTs.
, In analisi numerica, la sommatoria ricorsi … In analisi numerica, la sommatoria ricorsiva a coppie (pairwise summation in inglese), chiamata anche sommatoria a cascata (cascade summation), è una tecnica per sommare una sequenza di numeri in virgola mobile di precisione finita che, sostanzialmente, riduce l'errore di arrotondamento accumulato in confronto a quello accumulato dalla semplice sommatoria in sequenza. Sebbene ci siano anche altre tecniche, come l'algoritmo di sommatoria di Kahan, le quali, tipicamente, presentano anche errori di arrotondamento più piccoli, la sommatoria ricorsiva a coppie è quasi altrettanto buona (differendo soltanto di un fattore logaritmico), pur avendo un costo computazionale molto più basso; essa può essere implementata in modo da avere quasi lo stesso costo (e esattamente lo stesso numero di operazioni aritmetiche) della sommatoria semplice. In particolare, la sommatoria ricorsiva a coppie di una sequenza di n numeri xn funziona dividendo ricorsivamente la sequenza in due metà, sommando ogni metà e addizionando le due somme: un algoritmo di tipo divide et impera. I suoi errori di arrotondamento nel peggiore dei casi crescono asintoticamente al massimo come O(ε log n), dove ε è la precisione di macchina (assumendo un numero di condizionamento fissato, come discusso sotto). In compenso, la semplice tecnica di accumulare la somma in sequenza (addizionando ogni xi uno alla volta per i = 1, ..., n) ha errori di arrotondamento che crescono nel peggiore dei casi come O(εn). La sommatoria di Kahan ha un errore nel peggiore dei casi approssimativamente di O(ε), indipendente da n, ma richiede un numero di operazioni aritmetiche molte volte maggiore. Se gli errori di arrotondamento sono casuali e, in particolare, hanno segni casuali, allora essi danno luogo ad una passeggiata aleatoria e, per la sommatoria ricorsiva a coppie, la crescita dell'errore è ridotta a una media di . Una struttura ricorsiva molto simile di sommatoria si trova in molti algoritmi di trasformata di Fourier veloce (FFT) ed è responsabile dello stesso accumulo lento di errori di arrotondamento in tali FFT. La sommatoria ricorsiva a coppie è l'algoritmo di sommatoria predefinito nel NumPy e nel linguaggio di calcolo tecnico Julia, dove in entrambi i casi si trova che esso ha velocità confrontabile con la sommatoria semplice (grazie all'utilizzo di un ampio modello di base).all'utilizzo di un ampio modello di base).
|
| rdfs:comment |
In numerical analysis, pairwise summation, … In numerical analysis, pairwise summation, also called cascade summation, is a technique to sum a sequence of finite-precision floating-point numbers that substantially reduces the accumulated round-off error compared to naively accumulating the sum in sequence. Although there are other techniques such as Kahan summation that typically have even smaller round-off errors, pairwise summation is nearly as good (differing only by a logarithmic factor) while having much lower computational cost—it can be implemented so as to have nearly the same cost (and exactly the same number of arithmetic operations) as naive summation.arithmetic operations) as naive summation.
, In analisi numerica, la sommatoria ricorsi … In analisi numerica, la sommatoria ricorsiva a coppie (pairwise summation in inglese), chiamata anche sommatoria a cascata (cascade summation), è una tecnica per sommare una sequenza di numeri in virgola mobile di precisione finita che, sostanzialmente, riduce l'errore di arrotondamento accumulato in confronto a quello accumulato dalla semplice sommatoria in sequenza. Sebbene ci siano anche altre tecniche, come l'algoritmo di sommatoria di Kahan, le quali, tipicamente, presentano anche errori di arrotondamento più piccoli, la sommatoria ricorsiva a coppie è quasi altrettanto buona (differendo soltanto di un fattore logaritmico), pur avendo un costo computazionale molto più basso; essa può essere implementata in modo da avere quasi lo stesso costo (e esattamente lo stesso numero di operazioe esattamente lo stesso numero di operazio
|
