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

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

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

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

Алгоритм

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

s = pairwise(x[1...n])
      if n ≤ N     base case: naive summation for a sufficiently small array
          s = 0
          for i = 1 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

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

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

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

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

Точность

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

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

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

При попарном суммировании для базового случая N = 1 вместо этого получается $S_{n}+E_{n}$, где ошибка $E_{n}$ ограничено сверху:

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

где ε — машинная точность используемой арифметики (например, ε ≈ 10 ⁻¹⁶ для стандартной двойной точности с плавающей запятой). Обычно интересующей величиной является относительная ошибка $|E_{n}|/|S_{n}|$, который, следовательно, ограничен сверху:

${\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 |) является числом обусловленности задачи суммирования. По сути, число обусловленности представляет собой внутреннюю чувствительность задачи суммирования к ошибкам, независимо от того, как оно вычисляется. Относительная граница ошибки для каждого ( обратно стабильного ) метода суммирования с использованием фиксированного алгоритма с фиксированной точностью (т.е. не тех, которые используют арифметику произвольной точности или алгоритмов, требования к памяти и времени которых меняются в зависимости от данных), пропорциональна этому числу обусловленности. . Плохо обусловленная задача суммирования — это задача, в которой это отношение велико, и в этом случае даже попарное суммирование может иметь большую относительную ошибку. Например, если слагаемые x _i представляют собой некоррелированные случайные числа с нулевым средним значением, сумма представляет собой случайное блуждание , и число обусловленности будет расти пропорционально ${\sqrt {n}}$. С другой стороны, для случайных входных данных с ненулевым значением число обусловленности асимптотируется до конечной константы как $n\to \infty$. Если все входные данные неотрицательны , то номер условия равен 1.

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

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

Реализации программного обеспечения

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

Другие реализации программного обеспечения включают библиотеку HPCsharp. для языка C# и суммирования стандартной библиотеки в Д. ​