Taxa de convergência do FFT Poisson solver

16

Qual é a taxa de convergência teórica para um solucionador de FFT Poison?

Estou resolvendo uma equação de Poisson: com n ( x , y , z ) = 3

2VH(x,y,z)=-4πn(x,y,z)
no domínio[0,2]×[0,2]×[0,2]com condição de contorno periódica. Essa densidade de carga é neutra em termos líquidos. A solução é dada por: VH(x)=n(
n(x,y,z)=3π((x-1 1)2+(y-1 1)2+(z-1 1)2-1 1)
[0 0,2]×[0 0,2]×[0 0,2] ondex=(x,y,z). No espaço recíproco VH(G)=4πn(G)
VH(x)=n(y)|x-y|d3y
x=(x,y,z) ondeGsão os vetores espaciais recíprocos. Estou interessado na energia Hartree: EH=1
VH(G)=4πn(G)G2
G No espaço recíproco, isso se torna (após discretização): EH=2πG0 | n( G ) | 2
EH=1 12n(x)n(y)|x-y|d3xd3y=1 12VH(x)n(x)d3x
OtermoG=0é omitido, o que efetivamente neutraliza a rede de densidade de carga (e, como já é neutra, tudo é consistente).
EH=2πG0 0|n(G)|2G2
G=0 0

EH=12835π=1,16410 ...

Aqui está um programa usando o NumPy que faz o cálculo.

from numpy import empty, pi, meshgrid, linspace, sum
from numpy.fft import fftn, fftfreq
E_exact = 128/(35*pi)
print "Hartree Energy (exact):      %.15f" % E_exact
f = open("conv.txt", "w")
for N in range(3, 384, 10):
    print "N =", N
    L = 2.
    x1d = linspace(0, L, N)
    x, y, z = meshgrid(x1d, x1d, x1d)

    nr = 3 * ((x-1)**2 + (y-1)**2 + (z-1)**2 - 1) / pi
    ng = fftn(nr) / N**3

    G1d = N * fftfreq(N) * 2*pi/L
    kx, ky, kz = meshgrid(G1d, G1d, G1d)
    G2 = kx**2+ky**2+kz**2
    G2[0, 0, 0] = 1  # omit the G=0 term

    tmp = 2*pi*abs(ng)**2 / G2
    tmp[0, 0, 0] = 0  # omit the G=0 term
    E = sum(tmp) * L**3
    print "Hartree Energy (calculated): %.15f" % E
    f.write("%d %.15f\n" % (N, E))
f.close()

E aqui está um gráfico de convergência (apenas plotando o conv.txtscript acima, aqui está um caderno que faz isso se você quiser brincar com isso):

Gráfico de convergência FFT

Como você pode ver, a convergência é linear, o que foi uma surpresa para mim, pensei que a FFT converge muito mais rápido que isso.

Atualização :

A solução tem uma cúspide na fronteira (eu não percebi isso antes). Para que a FFT converja rapidamente, a solução deve ter todos os derivados suaves. Então, eu também tentei o seguinte lado direito:

nr = 3*pi*sin(pi*x)*sin(pi*y)*sin(pi*z)/4

VH=pecado(πx)pecado(πy)pecado(πz)EH=3π8

Alguém conhece alguma referência em 3D para que eu possa ver uma convergência mais rápida do que linear?

Ondřej Čertík
fonte
Ondrej, a transformação de Fourier da sua densidade suave não é uma função delta? Admito que tenho preguiça de executá-lo, mas deve obter a resposta exata na primeira tentativa.
Matt Knepley
Eu acho que é. Mas ele não converge em uma iteração, como pode ser visto nos gráficos do notebook. Eu não tenho idéia do que está acontecendo.
Ondřej Čertík
Ondrej, você tem certeza de que sua implementação está correta? Lembro-me de tentar implementar solucionadores espectrais para um trabalho de casa na pós-graduação e esbarrar totalmente nas constantes. Percebo que você está medindo erro observando a distância absoluta entre a energia calculada e a exata. Como é a sua convergência para a solução real do problema? Isso deve ser fácil de calcular e até plotar sobre uma fatia 2-D do problema.
Aron Ahmadia
Aron --- verifiquei minha implementação em relação a outro código, mas estava verificando se havia uma amostra inicial incorreta; portanto, tive o mesmo bug nos dois códigos. Matt estava certo, agora converge na primeira tentativa. Veja minha resposta abaixo.
Ondřej Čertík

Respostas:

10

Deixe-me primeiro responder a todas as perguntas:

Qual é a taxa de convergência teórica para um solucionador de FFT Poison?

A convergência teórica é exponencial desde que a solução seja suficientemente suave.

Quão rápido essa energia deve convergir?

EH

Alguém conhece alguma referência em 3D para que eu possa ver uma convergência mais rápida do que linear?

Qualquer lado direito que produza uma solução periódica e infinitamente diferenciável (inclusive além da fronteira periódica) deve convergir exponencialmente.


No código acima, ocorre um erro, que faz com que a convergência seja mais lenta que a exponencial. Usando o código de densidade suave ( https://gist.github.com/certik/5549650/ ), o seguinte patch corrige o erro:

@@ -6,7 +6,7 @@ f = open("conv.txt", "w")
 for N in range(3, 180, 10):
     print "N =", N
     L = 2.
-    x1d = linspace(0, L, N)
+    x1d = linspace(0, L, N+1)[:-1]
     x, y, z = meshgrid(x1d, x1d, x1d)

     nr = 3*pi*sin(pi*x)*sin(pi*y)*sin(pi*z)/4

O problema era que a amostragem no espaço real não pode repetir o primeiro e o último ponto (que tem o mesmo valor devido à condição de contorno periódica). Em outras palavras, o problema estava em configurar a amostragem inicial.

Após essa correção, a densidade converge em uma iteração, como Matt disse acima. Então, eu nem plotei os gráficos de convergência.

No entanto, pode-se tentar uma densidade mais difícil, por exemplo:

     nr = 3*pi*exp(sin(pi*x)*sin(pi*y)*sin(pi*z))/4

então a convergência é exponencial, como esperado. Aqui estão os gráficos de convergência para essa densidade: insira a descrição da imagem aqui insira a descrição da imagem aqui

Ondřej Čertík
fonte
Impressionante. Desculpe por não ter ajudado mais!
Aron Ahmadia