Re: [math-fun] Exact N-body simulations?
After Gosper & Schroeppel found some papers of Prof. Donald Greenspan (1928-2010) via Rob Corless, it quickly became clear that Greenspan's entire career was spent developing a theory very similar to the one I was advocating. The best paper of his that I was able to find on the web (quickly) regarding the N-body problem is this one: Greenspan, Donald. "Discrete Mathematical Physics and Particle Modeling". Advances in Electronics and Electron Physics, Vol. 63, pp. 189-268. On pp. 190-202, he goes through the development of a set of _difference equations_ for the 3-body problem in 2-D that conserve mass, energy, linear momentum and angular momentum. He discusses that for each time step of the iteration he needs to solve 12 equations in 12 unknowns. "Such systems are solved easily by the Newton-Lieberstein method (Liberstein, 1960; Greenspan, 1974d)..." "Then the Newton-Lieberstein iteration formulas for this system are ... in which omega is an overrelaxation factor in the range 0<omega<2 and each partial derivative is evaluated at the same point as is the function in the numerator of the term in which the partial derivative occurs. Computer implmentation is always practical because no matrix inversion routines are required". (?????) I haven't yet gone through the development to see how complex these equations are (e.g., whether they require polynomial root-finding), but Greenspan goes a very long way in the direction that I wanted to go. Perhaps the distance to Hilbert's Tenth Problem isn't very great at all: if we can take an arbitrary instance of Hilbert's Tenth Problem and construct an N-body problem of the Greenspan sort to solve it, then we are home. Greenspan apparently did a lot of the work for this paper with Robert LaBudde. LaBudde, Robert A., and Greenspan, Donald. "AN ENERGY CONSERVING MODIFICATION OF NUMERICAL METHODS FOR THE INTEGRATION OF EQUATIONS OF MOTION". Internat. J. Math. & Math. Sci. Vol. 10 No. 1 (1987) 173-179. Much of Greenspan's work during 1968-1978 is available at the U. Wisconsin CS Dept's technical reports web site: http://www.cs.wisc.edu/techreports/
This isn't exactly what you want, but James Gilliam's thesis looks at an analogy of Noether's theorem in discrete physics: http://math.ucr.edu/home/baez/theses.html#gilliam On Wed, Jun 15, 2011 at 7:34 AM, Henry Baker <hbaker1@pipeline.com> wrote:
After Gosper & Schroeppel found some papers of Prof. Donald Greenspan (1928-2010) via Rob Corless, it quickly became clear that Greenspan's entire career was spent developing a theory very similar to the one I was advocating.
The best paper of his that I was able to find on the web (quickly) regarding the N-body problem is this one:
Greenspan, Donald. "Discrete Mathematical Physics and Particle Modeling". Advances in Electronics and Electron Physics, Vol. 63, pp. 189-268.
On pp. 190-202, he goes through the development of a set of _difference equations_ for the 3-body problem in 2-D that conserve mass, energy, linear momentum and angular momentum.
He discusses that for each time step of the iteration he needs to solve 12 equations in 12 unknowns.
"Such systems are solved easily by the Newton-Lieberstein method (Liberstein, 1960; Greenspan, 1974d)..."
"Then the Newton-Lieberstein iteration formulas for this system are ... in which omega is an overrelaxation factor in the range 0<omega<2 and each partial derivative is evaluated at the same point as is the function in the numerator of the term in which the partial derivative occurs. Computer implmentation is always practical because no matrix inversion routines are required". (?????)
I haven't yet gone through the development to see how complex these equations are (e.g., whether they require polynomial root-finding), but Greenspan goes a very long way in the direction that I wanted to go. Perhaps the distance to Hilbert's Tenth Problem isn't very great at all: if we can take an arbitrary instance of Hilbert's Tenth Problem and construct an N-body problem of the Greenspan sort to solve it, then we are home.
Greenspan apparently did a lot of the work for this paper with Robert LaBudde.
LaBudde, Robert A., and Greenspan, Donald. "AN ENERGY CONSERVING MODIFICATION OF NUMERICAL METHODS FOR THE INTEGRATION OF EQUATIONS OF MOTION". Internat. J. Math. & Math. Sci. Vol. 10 No. 1 (1987) 173-179.
Much of Greenspan's work during 1968-1978 is available at the U. Wisconsin CS Dept's technical reports web site:
http://www.cs.wisc.edu/techreports/
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
-- Mike Stay - metaweta@gmail.com http://www.cs.auckland.ac.nz/~mike http://reperiendi.wordpress.com
I have been trying to follow this discussion, and I'm still sort of stuck at the beginning. I'm not sure I understand what Henry is asking for, and I'm not even yet certain that the problem is coherent. Clearly, Henry is look for the definition of a formal dynamical system; furthermore, this system is *not* classical Newtonian gravitational mechanics, since we know the latter will rarely resume rational state once it's set in motion. In other words, the new system might not have anything to say about the actual evolution of a suite of gravitating particles. The energy, momentum, and angular momentum that Henry wants conserved are, I presume, calculated in the usual way: energy is total gravitational potential plus kinetic energy of the usual mvv/2 sort. Correct me if I'm misunderstanding. Furthermore, I think we are constraining positions to be integral. The next state is going to have to be selected by the update rule from among all the states with the same E, p, and L. I'm not convinced that there are enough legal next states for the update rule to be at all interesting. Are we convinced that there are *any* other states that are accessible? On Wed, Jun 15, 2011 at 11:10 AM, Mike Stay <metaweta@gmail.com> wrote:
This isn't exactly what you want, but James Gilliam's thesis looks at an analogy of Noether's theorem in discrete physics: http://math.ucr.edu/home/baez/theses.html#gilliam
On Wed, Jun 15, 2011 at 7:34 AM, Henry Baker <hbaker1@pipeline.com> wrote:
After Gosper & Schroeppel found some papers of Prof. Donald Greenspan (1928-2010) via Rob Corless, it quickly became clear that Greenspan's entire career was spent developing a theory very similar to the one I was advocating.
The best paper of his that I was able to find on the web (quickly) regarding the N-body problem is this one:
Greenspan, Donald. "Discrete Mathematical Physics and Particle Modeling". Advances in Electronics and Electron Physics, Vol. 63, pp. 189-268.
On pp. 190-202, he goes through the development of a set of _difference equations_ for the 3-body problem in 2-D that conserve mass, energy, linear momentum and angular momentum.
He discusses that for each time step of the iteration he needs to solve 12 equations in 12 unknowns.
"Such systems are solved easily by the Newton-Lieberstein method (Liberstein, 1960; Greenspan, 1974d)..."
"Then the Newton-Lieberstein iteration formulas for this system are ... in which omega is an overrelaxation factor in the range 0<omega<2 and each partial derivative is evaluated at the same point as is the function in the numerator of the term in which the partial derivative occurs. Computer implmentation is always practical because no matrix inversion routines are required". (?????)
I haven't yet gone through the development to see how complex these equations are (e.g., whether they require polynomial root-finding), but Greenspan goes a very long way in the direction that I wanted to go. Perhaps the distance to Hilbert's Tenth Problem isn't very great at all: if we can take an arbitrary instance of Hilbert's Tenth Problem and construct an N-body problem of the Greenspan sort to solve it, then we are home.
Greenspan apparently did a lot of the work for this paper with Robert LaBudde.
LaBudde, Robert A., and Greenspan, Donald. "AN ENERGY CONSERVING MODIFICATION OF NUMERICAL METHODS FOR THE INTEGRATION OF EQUATIONS OF MOTION". Internat. J. Math. & Math. Sci. Vol. 10 No. 1 (1987) 173-179.
Much of Greenspan's work during 1968-1978 is available at the U. Wisconsin CS Dept's technical reports web site:
http://www.cs.wisc.edu/techreports/
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
-- Mike Stay - metaweta@gmail.com http://www.cs.auckland.ac.nz/~mike http://reperiendi.wordpress.com
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
Allan is correct, the problem is not well-formulated. There are multiple, potentially conflicting goals. 1. We want a system in 1D, 2D, and/or 3D which preserves the usual conservation & symmetry laws _exactly_ (at least in theory). For computer simulations, rationals are preferred over reals whenever possible, as there is at least the glimmer of hope for exact solutions (perhaps using Chinese Remainder Theorem or other techniques). 2. We're willing to sacrifice continuity for granularity in time & space, so long as the limiting behavior still holds -- e.g., if my space grid points and masses involve integers with 15 decimal digits and relatively slow velocities, then we would hope that the simulation after trillions of iterations is quite close to that of a continuous simulation. 3. We're more interested in long-term & statistical behavior than in short term accuracy/fidelity. We're not trying to land a person on the Moon in 3 days, but to try to get some idea of the Moon's orbit after a billion revolutions. We're also interested in changes in long-term behavior from minor modifications in initial conditions -- e.g., if we change the orbit of Venus by 1 part in 1 million, how does this affect the Earth's orbit in 10 million years? 4. Even if the simulation is significantly different from Newtonian gravity, such a simulation might still be mathematically interesting if one could prove interesting theorems -- e.g., undecidability of long-term stability by reducing the problem to Hilbert's Tenth Problem. 5. If the simulation is sufficient simple, but yields sufficiently interesting behavior, it would be analogous to Conway's "Life" or the 3n+1 problem. At 03:40 PM 6/16/2011, Allan Wechsler wrote:
I have been trying to follow this discussion, and I'm still sort of stuck at the beginning. I'm not sure I understand what Henry is asking for, and I'm not even yet certain that the problem is coherent. Clearly, Henry is look for the definition of a formal dynamical system; furthermore, this system is *not* classical Newtonian gravitational mechanics, since we know the latter will rarely resume rational state once it's set in motion. In other words, the new system might not have anything to say about the actual evolution of a suite of gravitating particles.
The energy, momentum, and angular momentum that Henry wants conserved are, I presume, calculated in the usual way: energy is total gravitational potential plus kinetic energy of the usual mvv/2 sort. Correct me if I'm misunderstanding.
Furthermore, I think we are constraining positions to be integral. The next state is going to have to be selected by the update rule from among all the states with the same E, p, and L. I'm not convinced that there are enough legal next states for the update rule to be at all interesting. Are we convinced that there are *any* other states that are accessible?
participants (3)
-
Allan Wechsler -
Henry Baker -
Mike Stay