Implementação eficiente de campo gravitacional

8

Fiz uma pergunta semelhante em physics.stackexchange , ignorando este site.

Estou basicamente procurando uma maneira eficiente de implementar campos gravitacionais.

Eu tenho um espaço 2D enorme, com milhares de objetos. Preciso simular como esses objetos são afetados pela gravidade um do outro.

Eu pensei que seria possível classificar os objetos em coleções e verificar todos os objetos fora dessa coleção contra essa coleção, e não todos os objetos individuais dentro dela. Logo cheguei à conclusão de que isso simplesmente não era possível. O campo gravitacional de vários objetos não pode ser representado como um campo uniforme, calculado com apenas uma massa e distância.

Todo objeto dentro da simulação pode ser considerado uma esfera. Eu estou bem com aproximações, desde que pareça razoavelmente realista.

optimization simulation approximation Jeroen
fonte

Respostas:

5

Você pode tentar usar uma biblioteca que implemente o Fast Multipole Method (FMM), que deve reduzir drasticamente a quantidade de memória necessária e diminuir a complexidade dos produtos vetoriais de matriz de para . É difícil de implementar, mas deve haver algumas bibliotecas por aí.O(N2)O(N)

Outro algoritmo para a simulação de corpos N é o Barnes-Hut, que é mais fácil de implementar e provavelmente também possui implementações de bibliotecas disponíveis. É considerado menos eficiente (no sentido assintótico) que o FMM.

Se o seu domínio for periódico, talvez você possa fazer algo como o somatório de Ewald da malha de partículas? (Eu sei menos sobre essa abordagem.)

Geoff Oxberry
fonte
Já li sobre isso e parece agrupar elementos. Como todos os meus elementos estarão bastante próximos um do outro e as massas tratadas são bastante pequenas, isso ainda será preciso?
Jeroen
1
Eu não tenho nenhuma experiência em usá-lo; Eu participei apenas de algumas palestras sobre o método. O FMM deve ser robusto, e a ideia geral é que a ordem do somatório seja truncada depois de atingir precisão suficiente (limites de erro podem ser derivados para o somatório, portanto, eles são usados ​​para o teste de precisão). Além disso, a precisão não deve ser dependente da distribuição de origem. O FMM deveria ser mais eficiente do que a malha de partículas Ewald quando as fontes estão próximas.
precisa
4
Embora toda massa individual tenha um campo monopolar associado a ela, uma soma de massas não possui um campo monopolar puro. O ponto do FMM é que essa soma de campos pode ser representada eficientemente por um campo multipolar (ordem relativamente baixa), já que os modos mais altos do campo decaem rapidamente com a distância.
Wolfgang Bangerth 24/03
Se eu usasse o campo apenas para calcular a aceleração, essa limitação abriria um novo escopo de possíveis maneiras de fazê-lo?
Jeroen