Discover MakerZone

MATLAB and Simulink resources for Arduino, LEGO, and Raspberry Pi

Learn more

Discover what MATLAB® can do for your career.

Opportunities for recent engineering grads.

Apply Today

Thread Subject:
adaptive contour maps for z=f(x,y) where function evaluation is very expensive

Subject: adaptive contour maps for z=f(x,y) where function evaluation is very expensive

From: Rahul

Date: 1 Jul, 2008 19:50:10

Message: 1 of 16

If I have an unknown z=f(x,y) and I want to "map" it, say by contours
over xmin<x<xmax and ymin<y<ymax. Thus given x,y I can compute z. But
each such computation is fairly expensive. [Perhaps one can pretencd
there is a "cost" of each evaluation and impose a maximum on the number
of evaluations.]

What's the "best" strategy? I know I'm ambigious but I wanted a better
idea of what people think is the objective function here to define
"best". Maybe nothing rigourous but at least something that makes sense
heuristically.

For example a brute force approach would be to use a reactangular
sampling grid over x and y. But then we sample densely even in regions
where z does not vary much at all.

Are there any algorithms for "adaptive" contour mapping? If so, any
implimentations in Matlab or Octave? Perpaps some leads to the algorithms
or code-snippets in case I must code it myself.

Don't want to re-invent the wheel if there are any existing tools out
there already!

--
Rahul

Subject: adaptive contour maps for z=f(x,y) where function evaluation

From: Han de Bruijn

Date: 2 Jul, 2008 07:39:23

Message: 2 of 16

Rahul wrote:

> If I have an unknown z=f(x,y) and I want to "map" it, say by contours
> over xmin<x<xmax and ymin<y<ymax. Thus given x,y I can compute z. But
> each such computation is fairly expensive. [Perhaps one can pretencd
> there is a "cost" of each evaluation and impose a maximum on the number
> of evaluations.]

So you have a "known" function, but you want to visualize it. Question:
has your function (partial first) derivatives that can be computed with
not too much effort, preferrably exactly ?

> What's the "best" strategy? I know I'm ambigious but I wanted a better
> idea of what people think is the objective function here to define
> "best". Maybe nothing rigourous but at least something that makes sense
> heuristically.

> For example a brute force approach would be to use a reactangular
> sampling grid over x and y. But then we sample densely even in regions
> where z does not vary much at all.

Regions where (df/dx)^2 + (df/dy)^2 is large IMO should be more refined.
That's why the derivatives could be useful but don't know how to employ
this information effectively.

> Are there any algorithms for "adaptive" contour mapping? If so, any
> implimentations in Matlab or Octave? Perpaps some leads to the algorithms
> or code-snippets in case I must code it myself.
>
> Don't want to re-invent the wheel if there are any existing tools out
> there already!

I've done some humble programming myself, though not exactly your case.

http://hdebruijn.soo.dto.tudelft.nl/www/programs/delphi.htm#omtrek

Han de Bruijn

Subject: adaptive contour maps for z=f(x,y) where function evaluation

From: Han de Bruijn

Date: 2 Jul, 2008 09:05:35

Message: 3 of 16

Rahul wrote:

> If I have an unknown z=f(x,y) and I want to "map" it, say by contours
> over xmin<x<xmax and ymin<y<ymax. Thus given x,y I can compute z. But
> each such computation is fairly expensive. [Perhaps one can pretencd
> there is a "cost" of each evaluation and impose a maximum on the number
> of evaluations.]

So you have a function that is not unknown in principle, but you want
to have a visualization of it, because a picture says more .. Right ?

> What's the "best" strategy? I know I'm ambigious but I wanted a better
> idea of what people think is the objective function here to define
> "best". Maybe nothing rigourous but at least something that makes sense
> heuristically.
>
> For example a brute force approach would be to use a reactangular
> sampling grid over x and y. But then we sample densely even in regions
> where z does not vary much at all.

Does your function have (first order partial) _derivatives_ that can be
computed with not too much effort ? Because then the following quantity
(df/dx)^2 + (df/dy)^2 could be a measure for how much to refine a grid
at certain places. At least that's what I would think of ..

> Are there any algorithms for "adaptive" contour mapping? If so, any
> implimentations in Matlab or Octave? Perpaps some leads to the algorithms
> or code-snippets in case I must code it myself.
>
> Don't want to re-invent the wheel if there are any existing tools out
> there already!

I've done some humble programming, though not exactly what you're asking
for. But it's free software. Bits and pieces at 'The Art of Contouring':

http://hdebruijn.soo.dto.tudelft.nl/www/programs/delphi.htm#omtrek

An idea would be to subdivide the area of interest into triangles and
use more triangles where gradients are steeper. Trial and error does
help sometimes, when automatism is lacking.

Han de Bruijn

Subject: adaptive contour maps for z=f(x,y) where function evaluation

From: Han de Bruijn

Date: 2 Jul, 2008 09:25:53

Message: 4 of 16

Han de Bruijn wrote:

[ .. whatever .. ] Sorry for posting almost the same article two times.
Didn't see it appear in 'sci.math.num-analysis' and now understand why.

Han de Bruijn

Subject: adaptive contour maps for z=f(x,y) where function evaluation is very expensive

From: spellucci@fb04373.mathematik.tu-darmstadt.de (Peter Spellucci)

Date: 2 Jul, 2008 10:21:44

Message: 5 of 16


In article <Xns9ACE96F01E7FB6650A1FC0D7811DDBC81@85.214.90.236>,
 Rahul <nospam@nospam.invalid> writes:
 >If I have an unknown z=f(x,y) and I want to "map" it, say by contours
 >over xmin<x<xmax and ymin<y<ymax. Thus given x,y I can compute z. But
 >each such computation is fairly expensive. [Perhaps one can pretencd
 >there is a "cost" of each evaluation and impose a maximum on the number
 >of evaluations.]
 >
 >What's the "best" strategy? I know I'm ambigious but I wanted a better
 >idea of what people think is the objective function here to define
 >"best". Maybe nothing rigourous but at least something that makes sense
 >heuristically.
 >
 >For example a brute force approach would be to use a reactangular
 >sampling grid over x and y. But then we sample densely even in regions
 >where z does not vary much at all.
 >
 >Are there any algorithms for "adaptive" contour mapping? If so, any
 >implimentations in Matlab or Octave? Perpaps some leads to the algorithms
 >or code-snippets in case I must code it myself.
 >
 >Don't want to re-invent the wheel if there are any existing tools out
 >there already!
 >
 >--
 >Rahul

 where are lots of freely available codes for contouring,
 but all I know of need a rectangular grid with z-values before.
 what could be an idea: if you know a _line_ (x or y fixed) where
 your f will behave "representative", then you can evaluate f along that line,
 then construct curves going through the values on that line by contructing
 then tangent vectors at a grid point by finite differencing (which again
 needs evaluation on a local grid). but it is clear that you might miss lot
 of information on f that way.
 (rule: info "out" is always less than info "in" )
 hth
 peter
 

Subject: adaptive contour maps for z=f(x,y) where function evaluation is very expensive

From: Rahul

Date: 2 Jul, 2008 18:32:25

Message: 6 of 16

Han de Bruijn <Han.deBruijn@DTO.TUDelft.NL> wrote in
news:65333$486b30ab$82a1e228$18655@news1.tudelft.nl:
>
> So you have a "known" function, but you want to visualize it.
>

Exactly. At least I have a known function in a "black box". Feed the box a
x, y and it returns a z (and perhaps the derivatives, see below in this
post)

> Question: has your function (partial first) derivatives that can be
> computed with not too much effort, preferrably exactly ?

I think I might have those derivatives. I'm not always sure though. We have
two implementations of the z=f(x,y). Without going into the gory details,
one implementation returns only the z. The other returns z and the partial
derivatives (a numerical approximation to those at least; I don't think
they are analytically computed). But I wrote some code to minimize z=f(x,y)
recently and there had occasion to use the derivatives that the "black
box" threw at me. Worked fine then.

In summary, it would be great if I could find a "countourer" that does not
want the derivatives but for now even if I find one that needs those I can
live with it.

>
> Regions where (df/dx)^2 + (df/dy)^2 is large IMO should be more
> refined. That's why the derivatives could be useful but don't know how
> to employ this information effectively.

Absolutely. That's what I think. But not sure how to formalize my
intuition. Then again we could refine this another level by having the

> I've done some humble programming myself, though not exactly your
> case.
>
> http://hdebruijn.soo.dto.tudelft.nl/www/programs/delphi.htm#omtrek

Well, that's not so "humble" Hans! I'm impressed with the codes you have
there. Thanks for the leads and I'm looking for whatever suggestions you
and others might have on this.

 I did not find much literature out there, maybe I just looked at the wrong
places..... Somehow, it doesn't make sense that nobody has worked on this
before. There seem to be so many practical real-life applications that come
to mind. Say, I was a geologist mapping water-tables or oil-reservoirs by
drilling boreholes. A brothel drilling job is a relatively expensive task.
Surely, they must have a strategy to figure where best to drill the next
hole. That seems like a problem very similar to ours!

--
Rahul

Subject: adaptive contour maps for z=f(x,y) where function evaluation is very expensive

From: Rahul

Date: 2 Jul, 2008 18:43:27

Message: 7 of 16

spellucci@fb04373.mathematik.tu-darmstadt.de (Peter Spellucci) wrote in
news:g4fkro$ajg$1@fb04373.mathematik.tu-darmstadt.de:

> where are lots of freely available codes for contouring,
> but all I know of need a rectangular grid with z-values before.

Exactly. I wonder though whether the rectangular grid is arbitrary and
effecient. I mean in most cases effeciency is not very important in these
days of cheap silicon. Its only when one encounters f(x,y) that are
expensive to evaluate does the question become relevant. Otherwise one can
always compensate the ineffeciency of a uniformly spaced rectangular grid
by increasing the grid points.


--
Rahul

Subject: adaptive contour maps for z=f(x,y) where function evaluation is

From: david bateman

Date: 14 Jul, 2008 23:15:37

Message: 8 of 16

On Jul 1, 9:50 pm, Rahul <nos...@nospam.invalid> wrote:
> If I have an unknown z=f(x,y) and I want to "map" it, say by contours
> over xmin<x<xmax and ymin<y<ymax. Thus given x,y I can compute z. But
> each such computation is fairly expensive. [Perhaps one can pretencd
> there is a "cost" of each evaluation and impose a maximum on the number
> of evaluations.]
>
> What's the "best" strategy? I know I'm ambigious but I wanted a better
> idea of what people think is the objective function here to define
> "best". Maybe nothing rigourous but at least something that makes sense
> heuristically.
>
> For example a brute force approach would be to use a reactangular
> sampling grid over x and y. But then we sample densely even in regions
> where z does not vary much at all.
>
> Are there any algorithms for "adaptive" contour mapping? If so, any
> implimentations in Matlab or Octave? Perpaps some leads to the algorithms
> or code-snippets in case I must code it myself.
>
> Don't want to re-invent the wheel if there are any existing tools out
> there already!
>
> --
> Rahul

Rahul,

This newsgroup is not used that much and your question might be better
directed to help@octave.org. However if the the issue is that you'd
like to avoid some calculations due to their cost and therefore not
have a rectilinear grid for the contouring, why not use the "griddata"
function that is available in both Octave and Matlab to take irregular
data and interpolate to a uniform grid (with some Delaunay
triangulation under the hood). So can then apply the standard
contouring methods to the interpolated data.

The only question is then where to best calculate your data points to
get reasonable results from the interpolation. If you have the partial
derivatives of your function then where its rapidly varying is where
you should add more data points. So start with a coarse rectilinear
mesh and refine the mesh in the regions where the partial derivatives
are rapidly varying.

Cheers
David

Subject: adaptive contour maps for z=f(x,y) where function evaluation is

From: Bruno Luong

Date: 15 Jul, 2008 06:30:20

Message: 9 of 16

david bateman <dbateman@free.fr> wrote in message
<b22ba406-ba10-4405-a2bc-4f5025769964@r66g2000hsg.googlegroups.com>...

>
> The only question is then where to best calculate your
data points to
> get reasonable results from the interpolation. If you have
the partial
> derivatives of your function then where its rapidly
varying is where
> you should add more data points. So start with a coarse
rectilinear
> mesh and refine the mesh in the regions where the partial
derivatives
> are rapidly varying.

I don't think it is that simple.

Locally the contour line can be expressed as c : x -> y(x)
and the derivative of c is

c'(x) = -df/dy / df/dx

As you see the contour line derivative get larger when the
partial derivative of f (to x) get smaller. In other word,
in the human term, contour line is better define for
function with steep slope or large gradient.

What is relevant would not be the change rate of the
gradient, but rather the change rate of the its direction,
which provides the curvature of the contour line.

Bruno

Subject: adaptive contour maps for z=f(x,y) where function evaluation is

From: david bateman

Date: 15 Jul, 2008 12:09:25

Message: 10 of 16

On Jul 15, 8:30 am, "Bruno Luong" <b.lu...@fogale.fr> wrote:
> david bateman <dbate...@free.fr> wrote in message
>
> <b22ba406-ba10-4405-a2bc-4f5025769...@r66g2000hsg.googlegroups.com>...
>
>
>

Hey the follow-up was to cssm, didn't notice that till now.. so my
comment on csso not being the primary support means for Octave of
course doesn't apply to cssm and Matlab.

>
> > The only question is then where to best calculate your
> data points to
> > get reasonable results from the interpolation. If you have
> the partial
> > derivatives of your function then where its rapidly
> varying is where
> > you should add more data points. So start with a coarse
> rectilinear
> > mesh and refine the mesh in the regions where the partial
> derivatives
> > are rapidly varying.
>
> I don't think it is that simple.
>
> Locally the contour line can be expressed as c : x -> y(x)
> and the derivative of c is
>
> c'(x) = -df/dy / df/dx
>
> As you see the contour line derivative get larger when the
> partial derivative of f (to x) get smaller. In other word,
> in the human term, contour line is better define for
> function with steep slope or large gradient.
>
> What is relevant would not be the change rate of the
> gradient, but rather the change rate of the its direction,
> which provides the curvature of the contour line.

Basically it was one in the morning when I send my response and had no
intention of going into too many details. Basically, I was putting
forward the use of the griddata function and the underlying Delaunay
triangulation in a refinement scheme and interpolation to a
rectilinear grid before contouring, and didn't care too much about how
the points in the refinement were selected.

I suspect your formula above is incorrect however, as there should be
symmetrical behavior for both the x and y axis, and your formula means
that c'(x) gets larger as df/dy gets larger or df/dx gets smaller.. I
suspect you're thinking of a coordinate system has x parallel to the
contour and y normal to it, but even that doesn't make sense as df/dx
would then be zero by definition. So from the formula I'm not really
sure what you're getting at [was it one in the morning when you sent
your response as well :-) ].

D.

Subject: adaptive contour maps for z=f(x,y) where function evaluation is

From: Bruno Luong

Date: 15 Jul, 2008 12:38:01

Message: 11 of 16

david bateman <dbateman@free.fr> wrote in message
<8209f84f-[was it one in the morning when you sent
> your response as well :-) ].
>

Yes I must swap the two partial derivatives (and yes I
realized 5 minutes after I sent the response after a hot
coffee), but the point I wanted to make still prevails, even
if it's swapped.

Yes probably you are right, this newsgroup is probably
filled with mistakes, but after all even with few mistakes,
constructive discussions might help to progress. It is
certainly not useless to the point that readers that seek
for help should go away.

As for griddata idea, one does not really need because Han's
routine can handle contour line from the triangular mesh, if
you read his web link above.

This does not solve the CPU issue since the function is
expensive to evaluate and replacing the rectangular mesh by
a triangular mesh with equivalent density will not help to
reduce the run time.

Bruno

Subject: adaptive contour maps for z=f(x,y) where function evaluation is

From: david bateman

Date: 16 Jul, 2008 10:14:28

Message: 12 of 16

On Jul 15, 2:38 pm, "Bruno Luong" <b.lu...@fogale.fr> wrote:
> Yes I must swap the two partial derivatives (and yes I
> realized 5 minutes after I sent the response after a hot
> coffee), but the point I wanted to make still prevails, even
> if it's swapped.

Swapping the partial derivatives doesn't address the issue of the
symmetry in the Cartesian coordinate system of the contouring problem,
so my criticism of your solution still stands. Define your coordinates
or your solution makes no sense.

> Yes probably you are right, this newsgroup is probably
> filled with mistakes, but after all even with few mistakes,
> constructive discussions might help to progress. It is
> certainly not useless to the point that readers that seek
> for help should go away.

Bruno, I'm not sure which of your buttons I pushed, but at no time did
I ever say someone asking for help should go away. CSSM is not a
newsgroup I visit often, but if your examine my track record at

http://www.nabble.com/Octave-f1895.html

you'll see that if I don't have something constructive to say I don't
bother opening my mouth. I prefer to ignore things rather than make
useless responses.

As stated I made a hand waving argument in my original post and said
something with the partial derivatives can be used for a mesh
refinement without going into details, something the you attacked me
for, not the reverse.

> As for griddata idea, one does not really need because Han's
> routine can handle contour line from the triangular mesh, if
> you read his web link above.

As stated I answered the post at CSSO and not CSSM and had no access
to Han's post. Essentially it seems that Han uses gradient
calculations on the individual patches of the Delaunay triangulation
in the contouring rather than a rectilinear mesh and yes that does
make griddata redundant, which is a good thing as it avoids the need
for an interpolation step.

However, Han's code is written in Pascal which if the goal is
"implementations in Matlab or Octave" as the original author asked
then that makes their use, except as the basis for a new
implementation in C/C++/F77, moot. So the idea to use griddata to get
something similar without having to rewrite Han's code stands as a
valid alternative.

> This does not solve the CPU issue since the function is
> expensive to evaluate and replacing the rectangular mesh by
> a triangular mesh with equivalent density will not help to
> reduce the run time.

No, but arbitrarily picking and choosing where the points that are
calculated will. IE if you arbitrarily pick and choose the calculation
points you end up with an irregular grid, and the common way of
meshing that is a triangulation. So yes a triangular mesh is an
important part of ANY reduction in CPU time in this problem.

I'm sick of this chest thumping, I'll go away.

D.

Subject: adaptive contour maps for z=f(x,y) where function evaluation is

From: Bruno Luong

Date: 16 Jul, 2008 10:49:02

Message: 13 of 16

david bateman <dbateman@free.fr> wrote in message
<a49bfe8e-3f76-4391-bc8f-3cf628501bf4@2g2000hsn.googlegroups.com>...

>
> Swapping the partial derivatives doesn't address the issue
of the
> symmetry in the Cartesian coordinate system of the
contouring problem,
> so my criticism of your solution still stands. Define your
coordinates
> or your solution makes no sense.

David,

No it makes sense, the formula does not depends on the
coordinates. Here is how it goes:

Assuming x -> c(x) is local (small) piece of contour line

That means:

f(x,c(x)) = Cte. (1) for x in some interval

Take the derivative of (1) with respect to x, one find

df/dx + df/dy*c'(x) = 0
Which gives us c'(x) = -df/dx / df/dy.

That the correct formula without the need to redefine the
coordinates.

This calculation is the basic idea of the proof of
"implicite theorem". I'm not the one who invent it, I'm just
citing what I have learn in my calculus course long ago.

> I ever say someone asking for help should go away. CSSM is
not a
> newsgroup I visit often, but if your examine my track
record at
>
> http://www.nabble.com/Octave-f1895.html
>
> you'll see that if I don't have something constructive to
say I don't
> bother opening my mouth. I prefer to ignore things rather
than make
> useless responses.
>
> As stated I made a hand waving argument in my original
post and said
> something with the partial derivatives can be used for a mesh
> refinement without going into details, something the you
attacked me
> for, not the reverse.

Look David, I must admit that I might react a little bit too
aggressively with your original argument about refining
mesh, so I apologize.

However, try to put you in the place of contributors [John,
Walter, Peter, Steve, Roger, Greg, us, Mat, ...] in this
newsgroup who spent a lot of time to help others and read
the comment such as "This newsgroup is not used that much ...".

>
> I'm sick of this chest thumping, I'll go away.
>

That's up to you David.

Regards,

Bruno

Subject: adaptive contour maps for z=f(x,y) where function evaluation is

From: david bateman

Date: 16 Jul, 2008 11:27:19

Message: 14 of 16

On Jul 16, 12:49 pm, "Bruno Luong" <b.lu...@fogale.fr> wrote:
> david bateman <dbate...@free.fr> wrote in message
>
> <a49bfe8e-3f76-4391-bc8f-3cf628501...@2g2000hsn.googlegroups.com>...
>
>
>
>
>
> > Swapping the partial derivatives doesn't address the issue
> of the
> > symmetry in the Cartesian coordinate system of the
> contouring problem,
> > so my criticism of your solution still stands. Define your
> coordinates
> > or your solution makes no sense.
>
> David,
>
> No it makes sense, the formula does not depends on the
> coordinates. Here is how it goes:
>
> Assuming x -> c(x) is local (small) piece of contour line

So c(x) is a parameterized curve and and your "x" refers to that
parameter and not the cartesian coords.

> However, try to put you in the place of contributors [John,
> Walter, Peter, Steve, Roger, Greg, us, Mat, ...] in this
> newsgroup who spent a lot of time to help others and read
> the comment such as "This newsgroup is not used that much ...".

Please look at

http://groups.google.com/group/comp.soft-sys.octave/browse_thread/thread/0fcd65cade8ec105

which is where I replied, Not in the matlab newsgroup. Then check

http://groups.google.com/group/comp.soft-sys.octave/browse_thread/thread/bbf44b60a7b79184

and also my comments about CSSO and CSSM.. I did not post to CSSM, but
CSSO but the original author set the Followup to CSSM. My comment
"This newsgroup is not used much" referred to CSSO, which is a
newsgroups that was created against the wishes of the Octave
developers (mainly it seems to mimic CSSM).

I'm an Octave contributor not in no way consider myself a Matlab
contributor. Though if you check

http://www.cise.ufl.edu/research/sparse/CXSparse/

from Tim Davis and the fact that Matlab now also links to CXSparse
you'll find that inadvertently I'm also a Matlab contributor. If you
want to know to what point I'm an Octave contributor check the title
page of the latest Octave manual for version 3.0.0 and 3.0.1

D.

Subject: adaptive contour maps for z=f(x,y) where function evaluation is

From: Bruno Luong

Date: 16 Jul, 2008 11:57:02

Message: 15 of 16

david bateman <dbateman@free.fr> wrote in message
<8b134cad-52cc-41c9-ab50-15c4101e6c74@c58g2000hsc.googlegroups.com>...
> On Jul 16, 12:49 pm, "Bruno Luong" <b.lu...@fogale.fr> wrote:
> > david bateman <dbate...@free.fr> wrote in message
> >
> >
<a49bfe8e-3f76-4391-bc8f-3cf628501...@2g2000hsn.googlegroups.com>...
> >
> >
> >
> >
> >
> > > Swapping the partial derivatives doesn't address the issue
> > of the
> > > symmetry in the Cartesian coordinate system of the
> > contouring problem,
> > > so my criticism of your solution still stands. Define your
> > coordinates
> > > or your solution makes no sense.
> >
> > David,
> >
> > No it makes sense, the formula does not depends on the
> > coordinates. Here is how it goes:
> >
> > Assuming x -> c(x) is local (small) piece of contour line
>
> So c(x) is a parameterized curve and and your "x" refers
to that
> parameter and not the cartesian coords.

Yes, it can be the first cartesian coordinates of the
function f.

> My comment
> "This newsgroup is not used much" referred to CSSO, which is a
> newsgroups that was created against the wishes of the Octave
> developers (mainly it seems to mimic CSSM).

OK, I completely miss-understood then because of the
confusion of cross-posting. I much prefer that. Apologize to
you again.

Bruno

Subject: adaptive contour maps for z=f(x,y) where function evaluation is

From: Mathieu Claeys

Date: 16 Jul, 2008 12:45:06

Message: 16 of 16

Hello,
I vaguely remember that during some wind tunnel
measurements at university, we measured pressure points at
the end of the tunnel on a non-uniform grid, that was
called something like a Chebyshev grid, and wich had
supposedly good statistical properties. So it might be a
little better than a uniform grid. Well, I don't remember
the details, so I can't tell you for what kinds of
functions this holds true, or if it just applies to tunnel
measurements to limit side effects, or whatever. You might
want check this with google if the derivative methods
don't work.
Mathieu

Tags for this Thread

No tags are associated with this thread.

What are tags?

A tag is like a keyword or category label associated with each thread. Tags make it easier for you to find threads of interest.

Anyone can tag a thread. Tags are public and visible to everyone.

Contact us