쌍집합

수치해석학에서, 캐스케이드 가산이라고도 불리는 쌍방향 합계는 유한정밀 부동소수점수의 시퀀스를 가산하는 기술로,^[1] 누적된 반올림 오차를 순차적으로 누적하는 것에 비해 실질적으로 감소시킵니다.일반적으로 더 작은 반올림 오차를 갖는 Kahan summation과 같은 다른 기법들이 있지만, 쌍별 합계는 훨씬 낮은 계산 비용을 가지면서도 거의 같은 수준(대수 인수에 의해서만 확산됨)이다. 이는 n과 거의 같은 비용(및 정확히 동일한 수의 산술 연산)을 가지도록 구현될 수 있다.aive summary.

특히 n개의 숫자_n x의 시퀀스의 쌍별 합계는 시퀀스를 2개의 반으로 재귀적으로 분할하여 각 반을 합산하고 2개의 합(분할 알고리즘과 정복 알고리즘)을 더함으로써 동작한다.최악의 경우 반올림 오류는 최대 O(' log n)와 같이 점근적으로 증가합니다.여기서 θ는 기계 정밀도입니다(아래에서 ^[1]설명하듯이 고정 조건 수를 가정한 경우).이에 비해, 합계를 순차적으로 누적하는 순진한 기술(i = 1, ..., n에 대해 각_i x를 한 번에 하나씩 누적)에는 O(θn)^[1]만큼 최악의 경우 증가하는 반올림 오차가 있습니다.Kahan summation은 n에 의존하지 않는 대략적인 O(),)의 최악의 오차를 가지지만 몇 배의 산술 ^[1]연산을 필요로 한다.반올림 오차가 랜덤이며 특히 랜덤한 부호가 있는 경우 랜덤 워크를 형성하고 쌍으로 ^[2]합산하기 위해 오차 증가량은 평균 O $(「log」n)$ 로 $O(\varepsilon {\sqrt {\log n}})$ 감소합니다.

매우 유사한 재귀적 합계는 많은 고속 푸리에 변환(FFT) 알고리즘에서 발견되며, 이러한 FFT의 ^[2]^[3]느린 반올림 축적을 담당합니다.

알고리즘

의사 코드에서 어레이의 쌍별 합계 알고리즘 x길쭉한n§ 0을 쓸 수 있다:

s = pairwise(x[1…n]): n ≤ N base case: 충분히 작은 배열 s에 대한 순합 = i = 1 ~ n s = x [ i ] 나누어서 정복: 배열 m = 바닥(n / 2) s = 쌍(x[1…m])의 두 반을 재귀적으로 합한다.

충분히 작은 일부에게는N이 알고리즘은 기본 케이스로서 Naigive 루프 베이스의 합계(오류 바인딩은 O(N'))^[4]로 전환됩니다.전체 합계는 주어진 조건 번호(아래 참조)에 대해 큰 n에 대해 점근적으로 O(θ log n)로 증가하는 최악의 경우 오류를 가집니다.

이러한 종류의 알고리즘에서는(일반적으로^[5] 분할 및 정복 알고리즘의 경우), 재귀의 오버헤드를 상각하기 위해 더 큰 베이스 케이스를 사용하는 것이 바람직하다.N = 1이면 모든 입력에 대해 대략 1개의 재귀 서브루틴 호출이 존재하지만, 보다 일반적으로 재귀가 정확히 n = N에서 멈추면 재귀의 오버헤드가 무시될 수 있습니다(재귀 합계를 위한 큰 기본 사례 기술).n은 고성능 FFT 구현에^[3] 사용됩니다).

N에 관계없이 정확히 n-1의 덧셈이 총합으로 실행되며, 이는 순합과 마찬가지로 재귀 오버헤드가 무시할 수 있는 경우 쌍별 덧셈은 기본적으로 순합과 동일한 계산 비용을 가집니다.

이 아이디어의 변형은 각 재귀 단계에서 합계를 b블록으로 나누어 각 블록을 재귀적으로 합산한 후 그 결과를 합산하는 것입니다.이 결과는 제안자들에 ^[6]의해 "슈퍼블록" 알고리즘이라고 불렸습니다.위의 쌍별 알고리즘은 마지막 단계인 b = N을 제외한 모든 단계에서 b = 2에 해당합니다.

정확성.

i = 1, ..., n에 대해 n개의_i 값 x를 합산한다고 가정합니다. 정확한 합계는 다음과 같습니다.

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

(무한 정밀도로 표시)

베이스 케이스 N = 1에 대한 쌍별 합계를 사용하면 $S_{n}+E_{n}$ S $S_{n}+E_{n}$ + $S_{n}+E_{n}$ n {\ $displaystyle S_{n$ } + $E_{$ n $S_{n}+E_{n}$ 을(를)^[1] $S_{n}+E_{n}$ .여기서 $E_{n}$ $E_{n}$ n \ $displaystyle E_{n}$ 은 $E_{n}$ 위의 값으로 제한됩니다.

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

여기서 θ는 사용 중인 산술의 기계 정밀도이다(예: 표준 2배 정밀도 부동 소수점의 경우 θ for⁻¹⁶ 10).일반적으로 대상 수량은 상대 $|E_{n}|/|S_{n}|$ $|E_{n}|/|S_{n}|$ / $|E_{n}|/|S_{n}|$ n { $displaystyle E_{n}$ / $S_{n}$ $|E_{n}|/|S_{n}|$ 이며, 따라서 위의 항목에 의해 제한됩니다.

{\frac { E_{n} {S_{n}} {leq {1-\varepsilon \log _{2}n} {1-\varepsilon \log _{2}n} \leftfrac {sum _{i=1}^{i} {\sum _{i} {{n}} {\} {\leftsum_n}

상대오차한계식에서는 fraction(δ_i x / δx_i )은 합계문제의 조건번호입니다.본질적으로, 조건 번호는 계산 ^[7]방법에 관계없이 오차에 대한 합산 문제의 본질적인 민감도를 나타낸다.고정 정밀도의 고정 알고리즘(즉 임의 정밀도 산술을 사용하는 알고리즘이나 데이터에 따라 메모리 및 시간 요건이 변화하는 알고리즘이 아님)에 의한 모든 (뒤로 안정적인) 합산 방법의 상대 오차 경계는 이 조건 ^[1]숫자에 비례한다.잘못된 조건의 합계 문제는 이 비율이 큰 문제이며, 이 경우 쌍별 합계에서도 상대 오차가 클 수 있습니다.예를 들어, summands_i x가 평균이 0인 상관없는 난수인 경우, 합계는 랜덤 워크이며 조건 번호는 n $(\$ 에 비례하여 증가한다. 반면, 평균이 0이 아닌 랜덤 입력의 경우 조건 번호는 n $n\to \infty$ $displaystyle$ n $\to\infty$ 로 $n\to \infty$ 상수에 점근한다. $n\to \infty$ 입력이 모두 음이 아닌 경우 조건 번호는 1입니다 $.$

$\varepsilon \log _{2}n$ $1-\varepsilon \log _{2}n$ - $1-\varepsilon \log _{2}n$ $1-\varepsilon \log _{2}n$ 2 $1-\varepsilon \log _{2}n$ n \ $displaystyle$ 1 - \ $varepsilon$ \ $log$ _ { $2$ $1-\varepsilon \log _{2}n$ } n $1-\varepsilon \log _{2}n$ $\varepsilon \log _{2}n$ n $\varepsilon \log _{2}n$ \ $displaystyle$ \ $varepsilon$ \ $log$ _ { $2$ } $n$ is1보다 훨씬 작기 때문에 n은 2배^10¹⁵ 정도2가^1/ε 될 때까지 $1-\varepsilon \log _{2}n$ 는 1입니다.

이에 비해 순진한 합계(순차적으로 숫자를 더해 각 단계에서 반올림)에 대한 상대오차는 O $O(\varepsilon n)$ ( $O(\varepsilon n)$ $)(\displaystyle$ O $(\varepsilon$ n $))$ 에 $O(\varepsilon n)$ 조건번호를 ^[1]곱한 값으로 $O(\varepsilon n)$ .실제로는 반올림 오차는 평균이 0인 랜덤 부호를 가지고 있기 때문에 랜덤 워크를 형성할 가능성이 매우 높아집니다.이 경우 naigive summary는 O $')\displaystyle$ O $(\varepsilon {$ n})\varepsilon { $O(\varepsilon {\sqrt {\log n}})$ ${n})\$ pair $O(\varepsilon {\sqrt {n}})$ summary 에는 O $O(\varepsilon {\sqrt {\log n}})$ n $O(\varepsilon {\sqrt {\log n}})$ 오차가 커집니다. $평균$ O $(\$ n $})$ 입니다 $O(\varepsilon {\sqrt {\log n}})$ $O(\varepsilon {\sqrt {\log n}})$

소프트웨어 구현

쌍별 합계는 NumPy^[8] 및 Julia 기술 계산 ^[9]언어의 기본 합산 알고리즘이며, 두 경우 모두 (큰 베이스 케이스를 사용한 덕분에) 순진한 합산과 동등한 속도를 가지고 있는 것으로 나타났습니다.

기타 소프트웨어 구현에는 C Sharp 언어용 HPCsharp^[10] 라이브러리와 D로 된 표준 라이브러리^[11] 합계가 포함됩니다.

레퍼런스

^ ^a ^b ^c ^d ^e ^f ^g Higham, Nicholas J. (1993), "The accuracy of floating point summation", SIAM Journal on Scientific Computing, 14 (4): 783–799, CiteSeerX 10.1.1.43.3535, doi:10.1137/0914050
^ ^a ^b ^c Manfred Tasche와 Hansmartin Zeuner 응용수학 Boca Raton, FL: CRC Press, 2000).
^ ^a ^b S. G. 존슨과 M.Frigo, "실제로 FFT 구현 , C가 편집한 고속 푸리에 변환에서. 시드니 버러스(2008).
^ Higham, Nicholas (2002). Accuracy and Stability of Numerical Algorithms (2 ed). SIAM. pp. 81–82.
^ Radu Rugina와 Martin Rinard, "Recursion unrolling for divide and cquer programs" (분할 및 정복 프로그램을 위한 재귀 전개), 병렬 컴퓨팅을 위한 언어 및 컴파일러, 제3장, 페이지 34-48.컴퓨터 사이언스 강의 노트 vol. 2017 (베를린: Springer, 2001).
^ 앤서니 M. 카스탈도, R. 클린트 웨일리, 앤서니 T.Chronopoulos, "슈퍼블록 알고리즘 패밀리를 사용하여 닷 곱의 부동소수점 오차를 줄인다." SIAM J. Sci. Comput., vol. 32, 페이지 1156–1174 (2008)
^ L. N. 트레페텐과 D.Bau, 수치 선형 대수학(SIAM: Philadelphia, 1997).
^ ENH: 쌍별 합계를 구현합니다.github.com/numpy/numpy 풀 요청 #3685(2013년 9월).
^ RFC: github.com/JuliaLang/julia pull request #4039(2013년 8월)의 sum, cumsum 및 cumprod에 대해 pairwise summary를 사용합니다.
^ https://github.com/DragonSpit/HPCsharp 하이 퍼포먼스 C# 알고리즘의 HPCharp nuget 패키지
^ "std.algorithm.iteration - D Programming Language". dlang.org. Retrieved 2021-04-23.

[Higham93-1] ^ ^a ^b ^c ^d ^e ^f ^g Higham, Nicholas J. (1993), "The accuracy of floating point summation", SIAM Journal on Scientific Computing, 14 (4): 783–799, CiteSeerX 10.1.1.43.3535, doi:10.1137/0914050

[Tasche-2] Manfred Tasche와 Hansmartin Zeuner 응용수학 Boca Raton, FL: CRC Press, 2000).

[JohnsonFrigo08-3] S. G. 존슨과 M.Frigo, "실제로 FFT 구현 , C가 편집한 고속 푸리에 변환에서. 시드니 버러스(2008).

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

[5] Radu Rugina와 Martin Rinard, "Recursion unrolling for divide and cquer programs" (분할 및 정복 프로그램을 위한 재귀 전개), 병렬 컴퓨팅을 위한 언어 및 컴파일러, 제3장, 페이지 34-48.컴퓨터 사이언스 강의 노트 vol. 2017 (베를린: Springer, 2001).

[Castaldo08-6] 앤서니 M. 카스탈도, R. 클린트 웨일리, 앤서니 T.Chronopoulos, "슈퍼블록 알고리즘 패밀리를 사용하여 닷 곱의 부동소수점 오차를 줄인다." SIAM J. Sci. Comput., vol. 32, 페이지 1156–1174 (2008)

[7] L. N. 트레페텐과 D.Bau, 수치 선형 대수학(SIAM: Philadelphia, 1997).

[8] ENH: 쌍별 합계를 구현합니다.github.com/numpy/numpy 풀 요청 #3685(2013년 9월).

[9] RFC: github.com/JuliaLang/julia pull request #4039(2013년 8월)의 sum, cumsum 및 cumprod에 대해 pairwise summary를 사용합니다.

[10] ttps://github.com/DragonSpit/HPCsharp 하이 퍼포먼스 C# 알고리즘의 HPCharp nuget 패키지

[11] "std.algorithm.iteration - D Programming Language". dlang.org. Retrieved 2021-04-23.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

Search

쌍집합

네임스페이스

더

목차

알고리즘

정확성.

소프트웨어 구현

레퍼런스