Physicists help!!

[MarxSchmarx]

I have an n-body problem:

Suppose you have two particles, A and B. Particles A only attract other particles of type A through gravitational attraction and likewise for B, but between a particle of type A and a particle of type B, there is also an unspecified force f of attraction that is expressed as:

f = exp(-k(mass of a - mass of b))

where k is a constant, and a is a particle of type A and b is a particle of type B. THis force operates in addition to gravitational attraction. Suppose for simplicity that the mass and charges of all particles are assigned completely at random throughout the space.

Given an initial configuration of n particles with info on their mass and charge, simulate the trajectory of the particles for T discrete time steps in less than T x o(n^2) time; in each time step you calculate the effect of all particles i on particle j, all particles i on particle k, etc..., and only after that update the positions of the particles.

Now the classic barnes-hut routine iirc only works if you calculate mass and centers of gravity across all particles before looking at their pairwise effects. But this seems doable because aggregate mass remains additive when looking at pairwise interactions but in the force calculation above is not.

Don't make me PM you based on the revleft experts database. Anybody have any idea (bmh I am thinking of you in particular).

[Ocean Seal]

It seems like you have all of the physics figured out ie:finding the force of particle i on j/k etc.. You can calculate the trajectory with simple double time integrals. I assume that the finding it in n^2 time is going to be the where the meat of the problem lies.

[MarxSchmarx]

It seems like you have all of the physics figured out ie:finding the force of particle i on j/k etc.. You can calculate the trajectory with simple double time integrals. I assume that the finding it in n^2 time is going to be the where the meat of the problem lies.

Yup; numerically evaluating that double integral takes at least o(n^2) per time step if done naively. Also the integration works as n -> \infinity, and for n quite finite traditionally used numerical approximation schemes for integrals break down.

[black magick hustla]

This is more of a numerical problem than a physics problem. I don't really solve "n-body" simulations, so I am afraid I can't help, sorry.

[black magick hustla]

Actually, now that I think about it, I doubt you want to integrate the eqns of motion just like that because yes, the computation time rises at least n^2 per time step. You probably want to use some sort of mean field approximation where you approximate the force particles at a certain distance as one big average field. The problem is weirdly stated though, cuz' it doesn't really tell you how much error you are allowed for.

[black magick hustla]

http://en.wikipedia.org/wiki/Mean_field_theory

[MarxSchmarx]

How do mean field approximations deal with the effects of spatial distance between particles? My reading of those approaches are that they assume the initial configuration of particles in space is irrelevant, when in fact we are looking at evolution over a time scale where the effect of initial configuration has not been completely erased.

[black magick hustla]

How do mean field approximations deal with the effects of spatial distance between particles? My reading of those approaches are that they assume the initial configuration of particles in space is irrelevant, when in fact we are looking at evolution over a time scale where the effect of initial configuration has not been completely erased.

Not really, I mean at n->infinity the sumtotal effect of all the fields should approach a mean field theory, because the fluctuations become really small (this is the whole basis of statistical mechanics). At time approaches infinity the system probably arrives at some sort of equilibrium too. If you read the wiki of classic barnes-hut it seems it is a mean field theory, as solving the equations of motion numerically is computationally inefficient. The point of MFT is that there are degrees to it. For example, a very rough MFT would follow the movement of one particle in a mean field background, but you can ahve MFT theories were you can take the effects of the nearest particles into account and then the rest treat it as a mean field.


Beyond that I can't really help, but I think cosmological models of how gravity affects structure formations have a degree of MFT in them.

[MarxSchmarx]

^^Just saw your response above whilst composing this:


Actually, now that I think about it, I doubt you want to integrate the eqns of motion just like that because yes, the computation time rises at least n^2 per time step. You probably want to use some sort of mean field approximation where you approximate the force particles at a certain distance as one big average field. .

As I understand it, that is the basic insight behind the Barnes-Hut routine:

http://en.wikipedia.org/wiki/Barnes%E2%80%93Hut_simulation

which basically partitions the spatial grid so that only the average mass of distant objects is calculated while the mass of nearby objects are calculated individually. But I have only seen that routine applied to gravity and particles that differ only in mass. If you add in the effect of electro-magnetism and don't approximate gravity to zero, that's where I'm not sure what the natural extension of a routine like that is.



The problem is weirdly stated though, cuz' it doesn't really tell you how much error you are allowed for

Hmm I guess the idea is that we have a discrete time model

x(t+dt) = x(t) where x is the configuration of particles at a given time, so in a sense error in the calculation is controlled by the magnitude of dt, and one can arbitrarily set dt, forcing the computation time to increase linearly with factor T = 1/dt

[MarxSchmarx]

One thing I need to add is that if we are assuming n->Infinity as happens in statistical mechanics, then something like Ocean seal's solution with appropriate numerical integration approximations that are well worked out in the numerical analysis literature suffice. The issue is when dealing with finite, but still large, numbers of particles (where, I guess, the error would be severe if numerical approximations appropriate for infinite particles are emloyed).


The point of MFT is that there are degrees to it. For example, a very rough MFT would follow the movement of one particle in a mean field background, but you can ahve MFT theories were you can take the effects of the nearest particles into account and then the rest treat it as a mean field.

But doesn't that mean we have to treat the remaining mean-field differently for each particle?

For example particle A, if it's nearest neighbors are all A except for 1 B particle that's fine, but suppose "the rest", however defined, consist of 40% A and 60% B so say 40% gravity and 60% em. Then for example for that 1 B particle near A, "the rest" would constitute 60% gravity and 40% em, etc... It seems that as the number of particle types considered increases relative to the total number of particles, you quickly deviate from the o(n log n) routine and very rapidly approach the o(n^2) implementation