Optimizing spacing of mesh containing a given set of points

A place to discuss the science of computers and programs, from algorithms to computability.

Formal proofs preferred.

Moderators: phlip, Moderators General, Prelates

Posts: 6
Joined: Tue Dec 28, 2010 4:45 am UTC

Optimizing spacing of mesh containing a given set of points

Postby Feynman » Sat Jan 15, 2011 9:27 pm UTC

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]

Say I have 3 initial points: xmin, 5 and xmax
known(num_ivc)=[xmin,5,xmax] //my arrays start at 1. Assume "known" always starts sorted

I store my mesh/grid points in an array called coord. Say I want 10 points total in my mesh/grid.
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:
or just

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 thank all those who attempt this dastardly problem.
Good luck!

Posts: 687
Joined: Mon May 05, 2008 2:14 am UTC

Re: Optimizing spacing of mesh containing a given set of poi

Postby 0xBADFEED » Sun Jan 16, 2011 6:11 pm UTC

I'm not sure you've fully specified the problem. It sounds like what you really want to do is maximize the spacing between points while minimizing the spacing variance. Is this correct? What I mean is consider the case of,

Code: Select all

N = 10
knowns = [4.5, 5.5]
min = 0, max = 10

In this case, the way you've specified the problem, placing all the remaining points on the interval (4.5, 5.5) could give you 10 perfectly spaced points completely inside the boundary and would be a completely valid solution to the problem (unless you're also counting the spacing to the boundary points). Though, I expect it's not the "answer" you would want.

Is there a problem with just dividing up the remaining values based on the size-ratios of the intervals between known points and the boundary values? It seems like it would give good results in the vast majority of cases. I could see where this might run into a problem when you have a large number of "knowns" that are already near the optimum spacing but it seems that the way you've specified the problem you'll always need to make some fairly arbitrary trade-off between spacing variance and minimum-spacing if you don't further constrain the problem.
Last edited by 0xBADFEED on Sun Jan 16, 2011 7:02 pm UTC, edited 2 times in total.

Posts: 6
Joined: Tue Dec 28, 2010 4:45 am UTC

Re: Optimizing spacing of mesh containing a given set of poi

Postby Feynman » Sun Jan 16, 2011 6:50 pm UTC

Since it is a closed interval, the spacing between all consecutive points counts--even boundary points. This is one of the places I ran into difficulty--one algorithm would only perform well if the points were close to the boundary while another would only work well if the points were far away.

But yes, I would want to minimize variance. However, I caution you approaching this from a minimization perspective only because minimization often involves time consuming iterative algorithms. It just seems as though there should be an intuitive approach--like the one you mentioned--involving taking the ratios of the intervals. The problem I ran into with that was that I could not figure out what to do about the end points of the intervals. It is difficult to articulate, but see if you can write up a pseudocode (with for loops and if statements.) I suspect you will have to do some clever coding to get the right number of points between the intervals. I had considered this approach, but always failed to get it to work consistently (along with all my other approaches.)

Can you write up a pseudocode that does this approach?

Thank you very much for taking a look at the problem.
I really appreciate any help I can get!

Posts: 548
Joined: Tue Jan 12, 2010 1:04 am UTC

Re: Optimizing spacing of mesh containing a given set of poi

Postby squareroot » Sun Jan 16, 2011 8:17 pm UTC

As far as I know, this is somewhat close to what my dad does; I asked him, and he says that the best approach depends a lot on what kind of problem you're trying to solve. Assuming this is a DE, are the knowns your function values, derivatives, or second derivatives? Does the DE start to exhibit very different behaviour near the boundary?

EDIT: I just saw the "most general way possible" clause. Sounds like it's going to be tough. Maybe keep your different partial-solutions stored, and then choose between them at runtime depending on the problem? There's nothing wrong with that, MATLAB has some 6 or 7 DE solvers built-in...
<signature content="" style="tag:html;" overused meta />
Good fucking job Will Yu, you found me - __ -

Posts: 6
Joined: Tue Dec 28, 2010 4:45 am UTC

Re: Optimizing spacing of mesh containing a given set of poi

Postby Feynman » Sun Jan 16, 2011 8:56 pm UTC

Ok, my solver uses green's functions right now. So you have to be able to solve for the green's function. It uses an iterative scheme that gives what seems to be the right answer (based on the graph), just off by scaling factor that seems to increase with every iteration. I am planning to switch my scheme to a similar method that should take care of this problem. I based the principles of the method on Huygen's principle (although I generalized the algorithm to whatever green's function you want), but I later realized I was evaluating the path integral a of a free particle--while constraining certain points (based on boundary conditions.)

I guess I should mention I am using Neumann boundary conditions. I plan on investigating a few approaches I have thought up based on the lagrangian formalism of quantum field theory--I plan on constructing a taylor series of e^(i*S/h + J)--which I suspect will come out to be a corrected version of what I am already doing (i.e. without the divergent scaling factor.)

But without this mesh spacing algorithm, I can't be sure my tests are accurate in all scenarios. If you guys are interested, I would be happy to go into more detail (perhaps on a new thread)!

Posts: 2
Joined: Wed Jan 18, 2012 1:05 pm UTC

Re: Optimizing spacing of mesh containing a given set of poi

Postby nortski » Wed Jan 18, 2012 1:17 pm UTC

Hi Feynman, I think that would be a good idea. I would definately appreciate a new thread on this topic. :)

Posts: 6
Joined: Tue Dec 28, 2010 4:45 am UTC

Re: Optimizing spacing of mesh containing a given set of poi

Postby Feynman » Thu Jan 19, 2012 4:51 am UTC

Wow, I am glad I am subscribed to this thread by email. I have not worked on it in a long time, but I still have the program, and I remember the general approach I took.

nortski, I assume when you said you would like me to start a new thread on "this topic" you meant the green's function path integral. You were not refering to the original mesh optimization algorithm were you?

Just clarify that and I will gladly start a new thread.

PS: I never solved the mesh optimization problem for N-dimensional space, but I did come up with a process for the one dimensional case, and the program seemed to come up with reasonable solutions to a bounded scalar wave equation (free particle case.) You could change the equations of motion by changing the green's function--which was just represented by an arbitrary function definition.

Anyway, I tried to write up an explaination of the method (to the best of my recollection), but it was really hard to follow, so I made an illustration to accompany it. Then I realized the illustration spoke for itself, and I just deleted the confusing narrative.

Here is a bad ascii representation of the general process:
| = boundary
@ = known point
O = normal grid point:
anything else = some poor ascii representation of space between points (pretend the symbol is just a few black pixels)
Start off with an interval that might look something like this:
| @ @ |
Uniformly add points in between boundary/known points:
The spacing on each interval was something like:
with L being a length, and N_quota being the total number of points you want to use. You always plot the first point of the interval because (assuming you are sweeping across the domain from left to right) that will always be a known point (by definition, each interval begins and ends with either a known point or a boundary--both of which must be plotted.)
The quantity
is like an "average" grid spacing. You want the spacing over each interval to be as close to that as possible.
Note how each interval has a different number of grid points in it, and a slightly different (but uniform) spacing. Say you need to use 2 extra points you need to use to meet your quota. Make a list that ranks each interval by how close its spacing is to the spacing L_total/N_quota.
If I recall correctly, interval's "rating" is given by:
The lower the remainder, the closer that interval's spacing is to the "average" spacing L_total/N_quota. The quantity is a little more intuitive when you multiply it by N_quota:
where N_remainder=the number of extra points (=2 in this example.) This represents the number of "extra points" that should be squeezed into that interval.
sum(remainder(L_total/L_interval))=1, so
sum(N_remainder*remainder(L_total/L_interval))=N_remainder (proof that my interpretation of the quantity at least "adds up" so to speak.)

Then, in the case of two extra points, just pick out the the intervals with the largest two remainders and stick on point in each. You will never have to put more than one point in the same interval because the remainder represents the number of extra points that should be put there, and by definition, a remainder is always less than 1.

Any questions (other than how to generalize it to N dimensions--which I cannot answer)?

Return to “Computer Science”

Who is online

Users browsing this forum: No registered users and 6 guests