Siła wypadkowa cząsteczki - optymalizacja

Pytanie jest krótkie:
W jaki sposób obliczyć siły wypadkowe działające na cząsteczki (w przestrzeni)? Chodzi mi o złożoność mniejszą niż n^2/2 czyli każdy z każdym. Czy w ogóle istnieje taki algorytm lub chociaż optymalizujący liczenie tych sił ciągle (co kilka/kilkanaście ms).

może jeszcze śpię, ale po co każdy z każdym?
Bierzesz pierwszą, i dodajesz kolejno następne. Wypadkowa to suma wektorów chyba, prawda?

Ja zrozumiałem że chodzi o siły grawitacyjne (każda cząsteczka działa na każdą)? Nie słyszałem o algorytmie optymalizującym samo liczenie, ale sam pisałem (z książki) algorytm usprawniający - polegał na dzieleniu przestrzeni na kwadraty/sześciany i liczeniu siły dla cząsteczki tylko na podstawie cząsteczek w jej sześcianie i przylegających.

O takie coś ci chodzi czy nie trafiłem?

j_s_r_n - tak ale potrzeba ją wyliczyć dla każdej z cząteczek

MSM dokładnie o to. Tylko w takim razie gdyby w jednym z tych sześcianów pojawiła się jakaś większza masa, a reszta cząsteczek znajdowała się by w innym to cząsteczki te zamiast lecieć na nią działały by w swoim sześcianie. Czy robić może jakieś osobne reguły dla takich większych mas

Metoda zaproponowana przez MSM tylko z małą modyfikacją. Dzielisz przestrzeń na sektory. Wyliczasz położenie środka masy w danym sektorze. i następnie dla każdego sektora liczysz biorąc pod uwagę oddziaływanie cząsteczek w sektorze plus oddziaływanie innych sektorów wyliczane na podstawie położenia ich środka masy i masy całkowitej sektora.
Środek masy można wyliczać "przy okazji", bo i tak licząc oddziaływania w sektorze musisz przebić się przez sumowanie po każdym. Zatem dodatkowy narzut czasowy nie jest duży.

może jakieś osobne reguły dla takich większych mas

Tu możesz użyć masy zredukowanej. Tylko, że w jej liczeniu jest od cholery dzielenia i jak zależy ci na szybkości, a masz dużo cząsteczek to może być problem.

czyli zostaje tylko problem podzielenia obszaru na rozsądną liczbę sektorów - nie za dużo nie za mało :) dzięki :)

hmm a teraz tak sobie myślę. gdyby policzyć najpierw:
spolozenie = masa1polozenie1+masa2polozenie2...
smasa = masa1+masa2+...

nastepnie iterujac po kazdym elemencie liczyc:
mmasa = smasa-masai
mpolozenie = (smasa-masaipolozeniei)/mmasa
Fi = Gmasai*mmasa/dlugosc_wektora(mpolozenie-polozeniei)^2

czy to by zadzialalo? bo jesli tak to zlozonosc wynosila by zaledwie O(n)

1. Masa układu jest stała. Liczysz tylko raz.
2. Wyznaczasz środek masy układu:

R0= Suma(RiMi)/M
gdzie:
R0 - wektor wodzący środka masy
Ri - wektor dla cząstki i
Mi - masa cząstki i
M - masa układu

Środek masy jest dobrym odniesieniem dla układu w którym cała masa znajduje się w jednym punkcie. Ruch środka masy jest taki sam jak ruch całego układu.

Jeżeli M>>Mi (czyli cząstek jest dużo) to siła oddziaływania pomiędzy Mi i resztą układu jest w przybliżeniu równa sile oddziaływania pomiędzy Mi a środkiem masy.

3. Liczysz siłę:
   F = G*(M-mi)/R^2
   gdzie:

R - odległość pomiędzy środkiem masy, a cząsteczką
G- stała grawitacyjna
M - masa układu
Mi - masa cząsteczki.

Ja powiem tak:
Wszystko zależy od tego co liczysz!
Jeśli chcesz liczyć ruch ciał oddziałujących grawitacyjnie to nie jest to aż tak proste. Oddziaływanie grawitacyjne jest długo zasięgowe i podział na sektory i obliczania dla środków masy muszą spełniać kilka podstawowych warunków.

1. sektory powinny być w miarę kuliste (sześciany są ok) - w zasadzie chodzi o to nie miały formy pręta deski itp.
2. dystans między sektorami, w których stosujesz przybliżenie powinien być dużo większy od wymiarów sektora (to ma znaczący wpływ na wyniki).
   Ten ostatni punkt jest bardzo ważny i w praktyce oznacza, że nie możesz stosować przybliżenia środków masy dla sąsiednich sektorów, co znacznie komplikuje kod.

Jeśli liczysz ruch ciał oddziałujących siłami van de Waalsa (potencjał typu 1/R⁶) lub inne krótkozasięgowe oddziaływania międzycząsteczkowe, to sprawa robi się prostsza.
Ustalasz granicę oddziaływania (zwykle około 30-100 Angstremów) i ignorujesz cząsteczki/atomy których odległość jest większa od tej granicy, a to już daje naturalny podział na sektory, który pozwala przyspieszyć wybór ciał, których oddziaływanie ma być policzone.

PS. @up: przy podziale na sektory masa całkowita nie jest stała, bo cząsteczki wychodzą z i wchodzą do sektora, a w tym przybliżeniu chodzi o uśrednienie oddziaływań ciał z dwóch różnych sektorów, wiec masy sektorów i ich średnie płożenia się zmieniają wraz z ruchem ciał.

@MarekR22, słusznie, ale... kto powiedział, że masa nie jest stała. Środek masy to właśnie taka fajna zabawka, która pozwala na ignorowanie zmiany "zawartości" sektora. Zresztą zła nazwa... bardziej pasuje mi tu grupa cząsteczek. Dzielimy zbiór na N podzbiorów zawierających różne cząsteczki. Dalej już z górki. Nawet jeżeli jakaś cząsteczka zwieje nam na drugi koniec przestrzeni to i tak nie trzeba będzie nic poprawiać. Po prostu jej wkład w jej środek masy będzie proporcjonalnie mniejszy.
Problem sprowadza się do jakiegoś rozsądnego ograniczenia ilości wykonywanych obliczeń. W takim przypadku wybieramy N cząsteczek, z których liczymy dokładne oddziaływanie, a resztę przez uśrednianie. Przy dużej ilości identycznych cząsteczek wyjdzie nam w przybliżeniu samo co przy liczeniu dokładnym. Jeżeli cząsteczek będzie naprawdę dużo to błąd będzie mały na tyle, że będzie można go ignorować i tylko co pewien czas (ilość iteracji) będziemy generować nowe sektory.

http://en.wikipedia.org/wiki/N-body_simulation