Soma pareada - Pairwise summation

Na análise numérica , a soma de pares , também chamada de soma em cascata , é uma técnica para somar uma sequência de números de ponto flutuante de precisão finita que reduz substancialmente o erro de arredondamento acumulado em comparação com o acúmulo ingênuo da soma em sequência. Embora existam outras técnicas, como a soma de Kahan, que normalmente têm erros de arredondamento ainda menores, a soma dos pares é quase tão boa (diferindo apenas por um fator logarítmico), embora tenha um custo computacional muito menor - ela pode ser implementada de modo a ter quase o mesmo custo (e exatamente o mesmo número de operações aritméticas) que a soma ingênua.

Em particular, a soma de pares de uma sequência de n números x _n funciona quebrando recursivamente a sequência em duas metades, somando cada metade e adicionando as duas somas: um algoritmo de divisão e conquista . Seus erros de arredondamento de pior caso crescem assintoticamente como no máximo O (ε log  n ), onde ε é a precisão da máquina (assumindo um número de condição fixo , como discutido abaixo). Em comparação, a técnica ingênua de acumular a soma em sequência (somando cada x _i um de cada vez para i  = 1, ...,  n ) tem erros de arredondamento que crescem na pior das hipóteses como O (ε n ). A soma de Kahan tem um erro de pior caso de aproximadamente O (ε), independente de n , mas requer várias vezes mais operações aritméticas. Se os erros de arredondamento forem aleatórios e, em particular, tiverem sinais aleatórios, eles formam um passeio aleatório e o crescimento do erro é reduzido a uma média de para a soma dos pares. ${\ displaystyle O (\ varepsilon {\ sqrt {\ log n}})}$

Uma estrutura recursiva de soma muito semelhante é encontrada em muitos algoritmos de transformada rápida de Fourier (FFT) e é responsável pelo mesmo acúmulo de arredondamento lento dessas FFTs.

O algoritmo

Em pseudocódigo , o algoritmo de soma de pares para uma matriz x de comprimento n > 0 pode ser escrito:

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

Para alguns N suficientemente pequenos , este algoritmo muda para um somatório baseado em loop ingênuo como um caso base , cujo limite de erro é O (Nε). A soma inteira tem um erro de pior caso que cresce assintoticamente como O (ε log  n ) para n grande , para um determinado número de condição (veja abaixo).

Em um algoritmo desse tipo (como para algoritmos de divisão e conquista em geral), é desejável usar um caso base maior para amortizar o overhead da recursão. Se N  = 1, então existe aproximadamente uma chamada de subrotina recursiva para cada entrada, mas mais geralmente não é uma chamada recursiva para (aproximadamente) todos os N / 2 entradas se a recursividade pára exactamente  N  =  N . Ao tornar N suficientemente grande, a sobrecarga de recursão pode se tornar desprezível (precisamente esta técnica de um grande caso base para soma recursiva é empregada por implementações FFT de alto desempenho).

Independentemente de N , exatamente n −1 adições são realizadas no total, o mesmo que para a soma ingênua, então se a sobrecarga de recursão for negligenciada, então a soma de pares tem essencialmente o mesmo custo computacional que para a soma ingênua.

Uma variação dessa ideia é quebrar a soma em b blocos em cada estágio recursivo, somando cada bloco recursivamente e, em seguida, somando os resultados, o que foi apelidado de algoritmo de "superbloco" por seus proponentes. Os corresponde aos pares algoritmo acima para b  = 2 para cada fase, excepto para a última fase em que é  b  =  N .

Precisão

Suponha que se esteja somando n valores x _i , para i  = 1, ...,  n . A soma exata é:

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

(calculado com precisão infinita).

Com a soma dos pares para um caso base N  = 1, obtém-se , em vez disso , onde o erro é limitado acima por: ${\ displaystyle S_ {n} + E_ {n}}$${\ displaystyle E_ {n}}$

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

onde ε é a precisão da máquina da aritmética sendo empregada (por exemplo, ε ≈ 10 ⁻¹⁶ para ponto flutuante de dupla precisão padrão ). Normalmente, a quantidade de juros é o erro relativo , que é, portanto, limitado acima por: ${\ displaystyle | E_ {n} | / | S_ {n} |}$

${\ displaystyle {\ frac {| E_ {n} |} {| S_ {n} |}} \ leq {\ frac {\ varepsilon \ log _ {2} n} {1- \ varejpsilon \ log _ {2} n}} \ left ({\ frac {\ sum _ {i = 1} ^ {n} | x_ {i} |} {\ left | \ sum _ {i = 1} ^ {n} x_ {i} \ direita |}} \ direita).}$

Na expressão para o limite de erro relativo, a fração (Σ | x _i | / | Σ x _i |) é o número de condição do problema de soma. Essencialmente, o número da condição representa a sensibilidade intrínseca do problema de soma a erros, independentemente de como ele é calculado. O limite de erro relativo de cada método de soma ( estável para trás ) por um algoritmo fixo em precisão fixa (ou seja, não aqueles que usam aritmética de precisão arbitrária , nem algoritmos cujos requisitos de memória e tempo mudam com base nos dados), é proporcional a este número de condição . Um problema de soma mal condicionado é aquele em que essa proporção é grande e, neste caso, mesmo a soma de pares pode ter um grande erro relativo. Por exemplo, se as somas x _i forem números aleatórios não correlacionados com média zero, a soma é um passeio aleatório e o número da condição aumentará proporcionalmente a . Por outro lado, para entradas aleatórias com diferente de zero, significa o número de condição assíntotas para uma constante finita como . Se as entradas forem todas não negativas , o número da condição será 1. ${\ displaystyle {\ sqrt {n}}}$${\ displaystyle n \ to \ infty}$

Observe que o denominador é efetivamente 1 na prática, pois é muito menor que 1 até que n se torne da ordem 2 ^{1 / ε} , que é aproximadamente 10 ^{10 15} em precisão dupla. ${\ displaystyle 1- \ varepsilon \ log _ {2} n}$${\ displaystyle \ varepsilon \ log _ {2} n}$

Em comparação, o limite de erro relativo para soma ingênua (simplesmente adicionando os números em sequência, arredondando em cada etapa) cresce multiplicado pelo número da condição. Na prática, é muito mais provável que os erros de arredondamento tenham um sinal aleatório, com média zero, de modo que formem um passeio aleatório; neste caso, a soma ingênua tem uma raiz quadrada média do erro relativo que cresce como e a soma dos pares tem um erro que cresce na média. ${\ displaystyle O (\ varepsilon n)}$${\ displaystyle O (\ varepsilon {\ sqrt {n}})}$${\ displaystyle O (\ varepsilon {\ sqrt {\ log n}})}$

Implementações de software

A soma pareada é o algoritmo de soma padrão em NumPy e na linguagem de computação técnica Julia , onde em ambos os casos foi encontrada uma velocidade comparável à soma ingênua (graças ao uso de um grande caso base).

Outras implementações de software incluem a biblioteca HPCsharp para o C afiada linguagem e o somatório biblioteca padrão em D .

Referências