Pairwise summation とは

数値解析では、カスケード加算とも呼ばれるペアワイズ加算は、積和演算の丸め誤差を実質的に減少させる一連の有限精度浮動小数点数を加算する手法であり、典型的にはより小さな丸め誤差を有するカハン和のような他の技法もあるが、ペアワイズ加算は対数ファクタだけでほぼ同等でありながら、はるかに低い計算コストを有している。純粋な合計と同じコスト(正確に同じ算術演算の数)。
特に、n個の数列x nの対の和は、シーケンスを2つの半分に再帰的に分割し、各半分を合計し、2つの合計を加算することによって作用する:分割および征服アルゴリズム。その最悪ケースの丸め誤差は、最大でもO(εlog n)のように漸近的に増加します。ここで、εはマシンの精度です(後述のように固定の条件数を仮定します)。これとは対照的に、和を累積する単純な手法(各x iをi = 1、…、nに対して一度に加える)は、O(εn)として最悪で成長する丸め誤差を有する。カハン和は、nとは無関係におおよそO(ε)の最悪ケース誤差を有するが、数倍の算術演算を必要とする。丸め誤差がランダムであり、特にランダムな符号がある場合、それらはランダムウォークを形成し、エラーの増加はペアごとの合計の平均 O ( ε log n ) {\displaystyle O(\varepsilon {\sqrt {\log n}})} に減少します。
加算の非常に類似した再帰的構造は、多くの高速フーリエ変換(FFT)アルゴリズムで見られ、それらのFFTの同じ遅い丸め積分の原因となります。
NumPyとJuliaテクニカルコンピューティング言語のデフォルトの加算アルゴリズムは、ペアワイズ加算です(どちらの場合も、大きな基底ケースを使用したため、単純な合計と同等のスピードを持つことがわかりました)。