Optimizing spacing of mesh containing a given set of points
- by Feynman
I tried to summarize the this as best as possible in the title. I am writing an initial value problem solver in the most general way possible. I start with an arbitrary number of initial values at arbitrary locations (inside a boundary.) The first part of my program creates a mesh/grid (I am not sure which is the correct nuance), with N points total, that contains all the initial values. My goal is to optimize the mesh such that the spacing is as uniform as possible. My solver seems to work half decently (it needs some more obscure debugging that is not relevant here.)
I am starting with one dimension. I intend to generalize the algorithm to an arbitrary number of dimensions once I get it working consistently. I am writing my code in fortran, but feel free to reply with pseudocode or the language of your choice.
Allow me to elaborate with an example:
Say I am working on a closed interval [1,10]
xmin=1
xmax=10
Say I have 3 initial points: xmin, 5 and xmax
num_ivc=3
known(num_ivc)=[xmin,5,xmax] //my arrays start at 1. Assume "known" starts sorted
I store my mesh/grid points in an array called coord. Say I want 10 points total in my mesh/grid.
N=10
coord(10)
Remember, all this is arbitrary--except the variable names of course.
The algorithm should set coord to {1,2,3,4,5,6,7,8,9,10}
Now for a less trivial example:
num_ivc=3
known(num_ivc)=[xmin,5.5,xmax
or just
num_ivc=1
known(num_ivc)=[5.5]
Now, would you have 5 evenly spaced points on the interval [1, 5.5] and 5 evenly spaced points on the interval (5.5, 10]? But there is more space between 1 and 5.5 than between 5.5 and 10. So would you have 6 points on [1, 5.5] followed by 4 on (5.5 to 10]. The key is to minimize the difference in spacing.
I have been working on this for 2 days straight and I can assure you it is a lot trickier than it sounds. I have written code that
only works if N is large
only works if N is small
only works if it the known points are close together
only works if it the known points are far apart
only works if at least one of the known points is near a boundary
only works if none of the known points are near a boundary
So as you can see, I have coded the gamut of almost-solutions. I cannot figure out a way to get it to perform equally well in all possible scenarios (that is, create the optimum spacing.)
