Sign in to follow this  
vusak

Any online references for Multigrid methods for n-body force models?

Recommended Posts

vusak    122
Im currently tinkering around with some stuff in python, and im up to implementing some kind of physics system for applying forces in n-body systems. My initial approach was to provide an abstract force_mesh type object which is an arbitrary size 2d array of force_magnitudes. In the implementation for n-body gravity, i figured this would simulate a kind of gravity well at each location in the mesh. So for any given object (with mass) located on the mesh, it would contribute its mass to it's position's force_magnitude. Then i could calculate force vectors between all non-zero force_mesh locations and sum them for the objects within those locations. An increase in accuracy coming from calculating force vectors for all objects within the same position in the force_mesh and applying them as well. The mesh was intended to provide a coarser representation of the forces on individual objects, with the idea being that i can scale the resolution of the force_mesh to fit my accuracy requirements. However im still using an O(N^2) method, ie. if all objects reside in one location, or if one object resides in each location, i get no optimization benefit. So then i do some research and read about multigrid, O(N) under reasonable conditions and used for n-body problems for quite some time now. My initial understanding of the idea is (eg. for calc gravity): 1. Start with list of positions and respective masses in world (ie. grid with maximum dimensions, each world point is a grid location) 2. Combine sections of existing grid into coarser grid sections 3. Sum masses for everything within a grid section and add it to 'corners' of the grid 4. Repeat 2-3 until grid reaches fully coarse 1x1 grid with 4 corners 5. Generate a new 1x1 grid with gravity vectors at each corner based on the 1x1 grids 4 corner magnitudes 6. Divide the new grid into finer sections 7. Interpolate corner gravity vectors to calculate the appropriate gravity vectors for the newly generated grid junctions 8. Use the matching sized grid from steps 2-3 and apply corrective adjustments to the interpolated gravity vectors 9. Repeat 6-8 until you can have no matching sized grid to correct with 10. Interpolate gravity vectors from finest grid for masses in world. However i got most of that from an example for calculating point charge and potentials, and in the transition to gravity i want to make sure i still have the right idea. Also im unsure how i should try and 'correct' properly in step 8. Ive found other explanations of the algorithm that use adaptive meshing, which i understand to be a way to avoid the subdivision step (and subsequent interpolation step) on grid sections that have little or no error, which i guess would be grid sections with zero or one masses within? And finally, and the main reason im posting, ive searched the net and the site and have found plenty of theoretical overviews of multigrid, but no actual source code demonstrating it, or a detailed enough explanation for me to accurately translate to my specific problem. So im especially interested in seeing any code demonstrating the algorithm, mainly so i can ensure i dont accidentally apply some naive approach to a part of an otherwise fast algorithm. If anyone has a good resource to check, id be very interested (www.mgnet.org doesnt seem to exist anymore??). Thanks. (edited the subject title because i realized it sounded like i was suggesting i was providing resources as opposed to requesting them) [Edited by - vusak on August 17, 2008 10:23:04 PM]

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this