low-complexity time algorithm for n-body simulation

[happyjack27]

For comparison, the fastest n-body algorithm know publicly has O(NlogN) computational complexity, and, as far as I know, no solution to when the problem becomes data- bandwidth limited rather than compute-limited. It is calle the Barnes-hut algorithm. http://en.m.wikipedia.org/wiki/Barnes–Hut_simulation

I would like my algorithm to be publicly known, too - not for the fame (though I wouldn't mind the recognition), but so that people can use it for very large simulations, at orders of magnitude lower dollar cost.

Anyone who can help, or knows who I might contact, I would much appreciate it.

[hanelyp]

As an edge case, how would your algorithm do if there was a concentrated patch of ions or current in the simulation? If I'm reading the code right the concentration could be assumed to center on a larger patch when seen by a distant particle.

[happyjack27]

Yep. It would do exactly what you describe. Worst case performance is probably when the particles are distributed according to a "flat" probability distribution. Best case is probably at equilibrium. Within a cluster compute density will still be pretty dense. But between clusters - you got it exactly: the algorithm "clusters" at large distances; it treats many things far away that are close to each other as one thing, from the perspective of that particular observer.

That in referring to electrostatic cases. High concentrations of current doesn't optimize nearly as well with the algorithm. Essentially you'd have to grow the resolution proportionally to the speed if the particle. But that doesn't even compare to existing n-body algorithms, because existing n-body algorithms don't consider current / Inertia; they are zero-order solvers; they only consider position, not velocity.

[happyjack27]

Another way to look at it - which i suppose I should express because it is really a way I looked at it when designing the algorithm - when you look up at the stars. The light from the stars hits the sphere of the earth. The light from the stars hits the sphere of you eyeball. The further away the star, the less area it takes up in your field of vision. According to 1/r^2. But this is not merely a law of sight, it is a law of physics. You see this way because that's how light works.

[ladajo]

I think what is intersting about your approach is its clumping. It is almost like an amplification effect once things cross a threshold of distance. More stuff, more closer, more effect. Like gravity.

[happyjack27]

thanks.

i fixed a bug and added in the local subtraction thing i was talking about, so you can calculate the force on a particle that's already in the system, without creating a concurrency bottleneck. new code is at: http://kbtrader.info/nbody.txt (and the new function is called readWithLocalSubtract) (i'd post it here but i don't want to spam this with a bunch of copies of almost identical code)

[KitemanSA]

Why not just correct the originally posted code with an edited lead in?

[happyjack27]

done.

[mattman]

Happy Jack,

Maybe this can help with this problem:

===

Going through some of the example data from the May 2013 paper. They have a beam of electrons emitted 7 cm from a ring of positive charge. The electron feels a 150 volt drop in front of it. It speeds up, and passes through ring center at ~7E6 meters per second. No problems so far. One can use the Lorenz force, excel and newton’s equations of motion to estimate the velocity.



The electron then enters the polywell. It is not turned on. So, the rings are all just metal donuts which are a positive 150 volts. There are no magnetic fields. The electron is feeling a positive pull in all directions around it. Now, some of these electrons will pass straight into the center. What is an estimate the electron velocity at that point? This is the drift velocity of the beam - and that is the key number. Here is a picture of the problem.



The paper indicates that they measured a positive 125 volts in the center. What is the best way to map the voltage field, as the electron enters the device?

A simple model should work. The problem gets difficult if the electrons are off axis and if vector fields are added. On axis, the electric field is symmetric in the Y and Z directions. Only the X direction matters. The electric field should decay as 1/x^2 and the field must be ~125 volts in the center. We don't know what it is at the center of the ring (?). So finding that first is important. Below is the plot of the Voltage as the electron moves.



I am not sure what the best approach is.

[happyjack27]

i appreciate the effort mattman, and those are nice graphs and a good explanation, but my algorithm is for the general case of any n-body problem where the forces act as 1/r^2 like (such as electromagnetic forces and gravitational force). thus, no details of any PARTICULAR instance or configuration of an n-body 1/r^2 problem - polywell included - are relevant. only things relevant are the mathematical rules that govern ALL systems of bodies of 1/r^2 forces. in short, the algorithm, like all n-body algorithms (and most algorithms in general) is a GENERAL solution.

[mattman]

HappyJack

Sorry. That was rude of me. I apologize.

Mapping Fields is important and any assistance is appreciated.

I wish we had a conference or funding or an real organization where we could coordinate our efforts better.

I could take your code and use it to help solve my problem, and in the process improve on your efforts.

[happyjack27]

it wasn't rude at all, imo. just doesn't help me to improve the algorithm, unfortunately.
from what you describe, it looks like you're just interested in static fields. that's a computationally easy problem. (though its can probably get pretty mathematically complex!) i'm sure there is software and code out there for it. i wouldn't be familiar with it, though. from my recollection, some have in posted in this forum. one that particularly comes to mind is: http://www.mare.ee/indrek/ephi/

[happyjack27]

This is off topic, but I just came up with an idea to augment the standard chess AI algorithm which may have profound implications for game theory and thus other things.

Basically you replace the minimax part with maximum entropy. That is, you evaluate the branch whose long-run outcome is most uncertain. In the simple case where an outcome is either certain or uncertain, this turns out to be equivalent to the conventional minimax. But in the far more xommon case, it's automatic "quescience" that is, in an important way, mathematically optimal.

It's an anti-computer AI strategy to be played _by_ a computer, against itself. It's an anti-anti-anti-computer strategy.

It's variationally optimal in the sense that a computer that considers the same number of moves would be at a disadvantage if it considered the available moves/ leaves in a different order. (And thus failed to consider a different set of moves.)

[happyjack27]

i found a paper for an algorithm similiar to mine. perhaps this explains the idea better:

http://www.stat.uchicago.edu/~lekheng/c ... okhlin.pdf