Otimização da simulação de corpo N, procurando nome ou trabalho existente

durante o desenvolvimento da minha simulação de corpo N com visualização no WebGL, desenvolvi uma otimização e fico imaginando se ele tem um nome. Acho improvável que isso nunca tenha sido feito antes.

Funciona assim: Durante o primeiro passo, faça uma iteração de todos os pares. Durante essa iteração, para cada partícula:

1. Armazene todas as interações próximas em uma lista - representando todas as partículas próximas a essa. Essas interações serão avaliadas a partir de então a cada etapa do processo. Essa lista normalmente contém algumas entradas.
2. Itere em todas as outras partículas e calcule uma força líquida que você armazena com a partícula. Essa força resultante é assim lembrada entre os intervalos de tempo e aplicada continuamente à partícula.

Então, à medida que a simulação continua após seu primeiro passo no tempo, de maneira rotativa, cada passo atualiza um pequeno número de listas de partículas de interações próximas e forças distantes . Para que, durante um certo número de etapas, digamos 1000, todas as interações íntimas das partículas e forças líquidas distantes tenham sido atualizadas. Os que você não atualizar apenas verificará suas interações estreitas e aplicará a força distante líquida. Neste exemplo, a complexidade computacional de cada etapa do tempo é algo como vez de .$N^2 / 1000$$N^2$

Um truque para também tornar isso razoavelmente preciso é identificar melhor "interações íntimas". Às vezes, a proximidade não é o melhor indicador - você também pode considerar a massa e a velocidade relativa e assim por diante. "Interações mais significativas" pode ser uma palavra melhor. Ou "interações mais prováveis ​​de mudar em breve".

Essa otimização permite muito mais partículas interagindo do que o método dos pares, mas não sei como descrevê-lo em termos de O (), pois ele não cria uma solução completa a cada intervalo de tempo, mas reutiliza (ligeiramente incorreto) o antigo informações e espalha o esforço computacional ao longo do tempo.

( Isenção de responsabilidade: minha simulação webgl também possui partículas "vfx" que são afetadas apenas pela gravidade e não retribuem o efeito, por isso não é tão incrivelmente rápido quanto parece )

Então, essa técnica de otimização tem um nome?

O método que você descreve é ​​um pouco semelhante ao algoritmo de Barnes-Hut . A principal diferença é que você tem um único nível de interações próximas, enquanto a Barnes-Hut tem .$\log N$

$O(N \log N)$

EDITAR:

$(N/3.8)^{\frac{1}{4}}$