Попарное суммирование

В численном анализе парное суммирование , также называемое каскадным суммированием , представляет собой метод суммирования последовательности чисел с плавающей точкой конечной точности , который существенно уменьшает накопленную ошибку округления по сравнению с наивным накоплением суммы в последовательности. ^[1] Хотя существуют и другие методы, такие как суммирование Кахана , которые обычно имеют еще меньшие ошибки округления, парное суммирование почти так же хорошо (отличаясь только логарифмическим множителем), имея при этом гораздо меньшие вычислительные затраты — его можно реализовать так, чтобы иметь почти такую ​​же стоимость (и точно такое же количество арифметических операций), как и наивное суммирование.

В частности, попарное суммирование последовательности из n чисел x _n работает путем рекурсивного разбиения последовательности на две половины, суммирования каждой половины и сложения двух сумм: алгоритм «разделяй и властвуй» . Его худшие ошибки округления растут асимптотически как максимум O (ε log  n ), где ε — точность машины (предполагая фиксированное число условий , как обсуждается ниже). ^[1] Для сравнения, наивный метод накопления суммы в последовательности (добавление каждого x _i по одному за раз для i  = 1, ...,  n ) имеет ошибки округления, которые растут в худшем случае как O (ε n ). ^[1] Суммирование Кахана имеет худшую ошибку примерно O (ε), независимо от n , но требует в несколько раз больше арифметических операций. ^[1] Если ошибки округления случайны и, в частности, имеют случайные знаки, то они образуют случайное блуждание , и рост ошибки уменьшается до среднего для попарного суммирования. ^[2]${\displaystyle O(\varepsilon {\sqrt {\log n}})}$

Очень похожая рекурсивная структура суммирования встречается во многих алгоритмах быстрого преобразования Фурье (БПФ) и отвечает за такое же медленное округление накопления этих БПФ. ^{[2] [3]}

На псевдокоде алгоритм попарного суммирования для массива x длины n ≥ 0 можно записать:

s = попарно ( x [1... n ]), если  n ≤ N  базовый случай: наивное суммирование для достаточно малого массива  s = 0 для  i = 1 до n  s = s + x [ i ] иначе  разделяй и властвуй: рекурсивно суммируй две половины массива  m = floor ( n / 2) s = попарно ( x [1... m ]) + попарно ( x [ m +1... n ]) конец если

Для некоторого достаточно малого N этот алгоритм переключается на наивное суммирование на основе цикла в качестве базового случая , чья граница ошибки равна O(Nε). ^[4] Вся сумма имеет наихудшую ошибку, которая растет асимптотически как O (ε log  n ) для больших n , для заданного числа условий (см. ниже).

В алгоритме такого рода (как и для алгоритмов «разделяй и властвуй» в целом ^[5] ) желательно использовать больший базовый случай, чтобы амортизировать накладные расходы рекурсии. Если N  = 1, то есть примерно один рекурсивный вызов подпрограммы для каждого входа, но в более общем случае есть один рекурсивный вызов для (примерно) каждых N /2 входов, если рекурсия останавливается точно на  n  =  N. Сделав N достаточно большим, накладные расходы рекурсии можно сделать пренебрежимо малыми (именно эта техника большого базового случая для рекурсивного суммирования используется высокопроизводительными реализациями БПФ ^[3] ).

Независимо от N , в общей сложности выполняется ровно n −1 сложений, как и при наивном суммировании, поэтому, если сделать накладные расходы рекурсии незначительными, то попарное суммирование будет иметь по сути те же вычислительные затраты, что и при наивном суммировании.

Разновидностью этой идеи является разбиение суммы на b блоков на каждом рекурсивном этапе, суммирование каждого блока рекурсивно, а затем суммирование результатов, что было названо авторами алгоритмом «суперблока». ^[6] Вышеуказанный парный алгоритм соответствует b  = 2 для каждого этапа, за исключением последнего этапа, который  равен b  =  N.

Dalton, Wang & Blainey (2014) описывают итеративную формулировку "сдвиг-уменьшение" для парного суммирования. Ее можно развернуть и ускорить с помощью инструкций SIMD . Неразвернутая версия выглядит так: ^[7]

double shift_reduce_sum ( double ∗ x , size_t n ) { double stack [ 64 ], v ; size_t p = 0 ; for ( size_t i = 0 ; i < n ; ++ i ) { v = x [ i ]; // сдвиг for ( size_t b = 1 ; i & b ; b <<= 1 , −− p ) // уменьшение v += stack [ p − 1 ]; stack [ p ++ ] = v ; } double sum = 0.0 ; while ( p ) sum += stack [ −− p ]; return sum ; }                                                         

Предположим, что суммируется n значений x _i , для i  = 1, ...,  n . Точная сумма:

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

(вычислено с бесконечной точностью).

При попарном суммировании для базового случая N  = 1 вместо этого получается , где ошибка ограничена сверху: ^[1]${\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}|}$

где ε — машинная точность используемой арифметики (например, ε ≈ 10 ⁻¹⁶ для стандартной двойной точности с плавающей точкой). Обычно интересующей величиной является относительная погрешность , которая, следовательно, ограничена сверху:${\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}\right|}}\right).}$

В выражении для относительной границы погрешности дробь (Σ| x _i |/|Σ x _i |) является числом условий задачи суммирования. По сути, число условий представляет внутреннюю чувствительность задачи суммирования к ошибкам, независимо от того, как она вычисляется. ^[8] Относительная граница погрешности каждого ( обратно устойчивого ) метода суммирования фиксированным алгоритмом с фиксированной точностью (т. е. не тех, которые используют арифметику произвольной точности , и не алгоритмов, чьи требования к памяти и времени изменяются в зависимости от данных), пропорциональна этому числу условий. ^[1] Плохо обусловленная задача суммирования — это задача, в которой это отношение велико, и в этом случае даже попарное суммирование может иметь большую относительную ошибку. Например, если слагаемые x _i являются некоррелированными случайными числами с нулевым средним, сумма является случайным блужданием , а число условий будет расти пропорционально . С другой стороны, для случайных входных данных с ненулевым средним число условий асимптотируется к конечной константе как . Если все входные данные неотрицательны , то число условий равно 1.${\displaystyle {\sqrt {n}}}$${\displaystyle n\to \infty }$

Обратите внимание, что на практике знаменатель фактически равен 1, поскольку он намного меньше 1, пока n не станет порядка 2 ^1/ε , что примерно равно 10 ^{10 15} в двойной точности.${\displaystyle 1-\varepsilon \log _{2}n}$${\displaystyle \varepsilon \log _{2}n}$

Для сравнения, относительная погрешность, связанная с наивным суммированием (простое последовательное сложение чисел с округлением на каждом шаге), растет как умножение на число условий. ^[1] На практике гораздо более вероятно, что ошибки округления имеют случайный знак с нулевым средним значением, так что они образуют случайное блуждание; в этом случае наивное суммирование имеет среднеквадратичную относительную погрешность, которая растет как , а попарное суммирование имеет погрешность, которая растет как в среднем. ^[2]${\displaystyle O(\varepsilon n)}$${\displaystyle O(\varepsilon {\sqrt {n}})}$${\displaystyle O(\varepsilon {\sqrt {\log n}})}$

Попарное суммирование является алгоритмом суммирования по умолчанию в NumPy ^[9] и языке технических вычислений Julia ^[10] , где в обоих случаях было обнаружено, что оно имеет сравнимую скорость с наивным суммированием (благодаря использованию большого базового случая).

Другие программные реализации включают библиотеку HPCsharp ^[11] для языка C# и стандартную библиотеку суммирования ^[12] на языке D.