[Ghoser777]

Well, I'm working on a pretty simple app that will need to be able to take equations of the form f(x,y)=g(x,y) i.e. xy^2 + 3xy = 4x^2y -y. I have a bounded region square of size 100 around the origin (10 in all directions) to consider. If the equations where just y=f(x), then I could just find 300 or so points along the x-axis and plug them into the equation and see the results. In the more complex form, it looks like I'd need to try 90000 points, and then have to come up with some threshold for how close one side of the equation has to be to the other for an order pair to be considered on the graph. So, my question is, is my current algorithm as fast as I'm going to get, or is their a fast/easier way to do this?

Thanks,
F-bacher

[tie]

Are you trying to solve f(x,y)=0, where f is a polynomial? If 0 is not a critical value, then the locus of solutions will be a compact 1-dimensional manifold (possibly with boundary on the boundary of your region).

Here's one basic method, which might be easier and more accurate than just a dense sampling. Find two points, one where f is positive and another where f is negative (you might do this by choosing two points at random, by choosing a relatively small number of sample points, by starting with one point and following the gradient to find the other, or whatever). Use Newton's method to solve for a root on the line segment between these points. Move orthogonally to the gradient to trace out the rest of that component of the solution locus. Repeat to find the other components. I'm not an expert, so there may be better ways, but this should get you started.

You can find the critical points where the graph of f is tangent to the plane and so roots are isolated points, by applying this method to the (numerical) derivatives in the x and y directions.

[Ghoser777]

f isn't necessarially a polynomial. It could have trig functions, logarithmic function, factorials, etc. I think your method would work great IF I knew how to programmatically differentiate arbitraty functions. I guess I could find the tangents by approximating them from the left and the right... geesh, I have so much more respect for my HP49G now. I understand your algorithm, but that sounds like a lot of work (although probably more accurate than sampling). How I'd do all this in code is kind of a mystery to me. I have an algorithm I already made that takes functions and plugs numbers into them (soudns easy, huh? RIIIGGGHHHT.) So sampling with that function is trivial... but I like your way too... so many choices!



F-bacher

[kamprath]

Originally posted by Ghoser777:
<STRONG>Well, I'm working on a pretty simple app that will need to be able to take equations of the form f(x,y)=g(x,y) i.e. xy^2 + 3xy = 4x^2y -y. I have a bounded region square of size 100 around the origin (10 in all directions) to consider. If the equations where just y=f(x), then I could just find 300 or so points along the x-axis and plug them into the equation and see the results. In the more complex form, it looks like I'd need to try 90000 points, and then have to come up with some threshold for how close one side of the equation has to be to the other for an order pair to be considered on the graph. So, my question is, is my current algorithm as fast as I'm going to get, or is their a fast/easier way to do this?

Thanks,
F-bacher</STRONG>

If the input is of form f( x, y ) = g( x, y ), then just:

1. Create the new equations 0 = f( x, y ) - g( x, y )
2. Repeat with xi from x_L (left hand side of graph box) to x_R (right hand side) with a step size you desire
a. Use a root finding algorithm to solve for the single unknown y in the equation 0 = f( xi, y ) - g( xi, y )
b. Plot graph point ( xi, y )

There you go! Of course, you have to create a parser to interpret the human input descrining f( x, y ) and g( x, y ), but I am assuming how to do that is not your question.

Michael.


Michael Kamprath

[DaGuy]

There are indeed many choices for root solvers. Some faster than others, a lot will depend on what types of functions you will be working with. I don't know of any "perfect" method that works efficiently on all possible cases. Functions can be very very funky...

You can scan your grid from one end to the other and you will likely find what your looking for (it's conceptually sound) but it's definitely brute force ... In other words REALLY REALLY SLOW. You are better off investing some time learning gradient techniques. These will rely on derivative approximations. These are not too hard once you get use to working with them.

For on screen display purpose, one thing to consider is interpolating your function(s) on a coarser subgrid. This would avoid having to evaluate some pretty hefty functions at all points of your grid -especially when you are far away from your zero(s). There is of course some error but for visual representation, it usually is quite insignificant.

Anyway, there's a very large number of freely available numerical routines on the web. Sorting though them could take some time but it may be worth it in the long run.

Cheers!


[ 03-03-2002: Message edited by: DaGuy ]

[Ghoser777]

Originally posted by kamprath:
<STRONG>


If the input is of form f( x, y ) = g( x, y ), then just:

1. Create the new equations 0 = f( x, y ) - g( x, y )
2. Repeat with xi from x_L (left hand side of graph box) to x_R (right hand side) with a step size you desire
a. Use a root finding algorithm to solve for the single unknown y in the equation 0 = f( xi, y ) - g( xi, y )
b. Plot graph point ( xi, y )

There you go! Of course, you have to create a parser to interpret the human input descrining f( x, y ) and g( x, y ), but I am assuming how to do that is not your question.

Michael.


Michael Kamprath</STRONG>

Alright, I'm making some good progress, except for this: how do I deal with graphs with multiple parts? Like a hyperbola? With this method I only find one of the lines. This is what I get, I suppose, for dealing with things other than functions

F-bacher

[DaGuy]

That's just one of the reasons why functions can really funky

You have to detect the singularity and then "hop" over it. You can set
limits on how much and how fast things should grow. Leverage the fact that you get explosive growth in the neighborhood of asymptotes.

Enjoy!

[Detrius]

Going on top of what other people have said, you could choose several random seed points in the domain and use Newton's method to find the associated zeros. Calculating (estimating) derivatives is quite easy when you are dealing with computers. Remember the following:

Assume F(x,y) is your given function.

dF(x+dx,y)/dx = derivative in x direction.
dF(x,y+dy)/dy = derivative in y direction.
vector associated with these two values gives you gradient, which is the direction giving you the steepest slope.

Newton's method: Calculate the derivative at a given point. Use this derivative to generate a locally linear estimate for your original function. Find where THIS function is equal to zero. Then, use that x (or in this case &lt;x,y&gt; ) value to see if your original function is equal to zero (or within a predefined threshold). If not, use this point to find the next estimate of a zero.

My idea: once you have a zero, you could try the eight neighboring pixels to see if they also could be categorized as a zero of your function. You can define a recursive function to do this. Call the function on each of the neighboring pixels. The function returns if it either does not find a zero at that pixel or if that pixel has already been defined as a zero (you will have to keep an array of zeros whose pointer is passed to each recursion). You can end your recursion when you no longer find any new zeros and when you have already tried a predefined number of seed values for Newton's method.

Reason this should work:

Any continuous function F:R2-&gt;R should either have only a single zero near a given pixel on the screen or it will have an infinite number of zeros, all connected together.

Examples:

f(x,y)=x+y has all of its zeros located along the line y=-x.
f(x,y)=x^2+y^2-1 has all of its zeros located on the unit circle.

warnings: you may need to define your threshold for a zero based on the slope of your function (since you are dealing purely with pixels on a computer screen). You don't need to go in for a hugely precise value. In addition, you may need a more precise estimate of your derivative than using pixel widths. For example, depending on your method, y=1/x may appear to have a zero at x=0. You can use a more precise derivative to attempt to find false zeros.


If you don't understand anything I said above, take Calculus III before attempting this program.

[Ghoser777]

Hehe... I'm a senior in math, don't worry; I understand

I essentially came to the same conclusion on a way to come to a solution a couple minutes before I read your post. I am going to divide me region into 300 slices, and evaluate the function for x at each of those points. Then trying three possible y solutions, I'll use the Newton method to find any roots from the function f(y)=0.

Dealing with multiple roots will be tricky, but not impossible. I'm going to keep track of the last found roots (for a given xi), and then connect any new found roots of xi+1 to the closest previous root. Hopefully this will allow me to do circles and hyperbolas without taking up too much time.

The only problem I see with your method is that it assumes that I'm dealing only with functions that have on curve, while hyperbolas have two curves, and if set up the right way, after finding one root, you'll only be able to map out one curve and not the other.

I'll try my method and report back later... but maybe a lot later; mid terms are about to kick me in the balls.

Thanks,
F-bacher

[kamprath]

Originally posted by Ghoser777:
<STRONG>

Alright, I'm making some good progress, except for this: how do I deal with graphs with multiple parts? Like a hyperbola? With this method I only find one of the lines. This is what I get, I suppose, for dealing with things other than functions

F-bacher</STRONG>

"Multiple Parts" are just equations ( 0 = f( xi, y) - g(xi, y) with more than one root on y. Find all the roots and you'll graph the multiple parts.

Michael

[DaGuy]

So far you can handle single-valued functions that contain no singularities. You have two additional main issues to consider -I'm assuming your seek to handle the more interesting cases.

1. HANDLING SINGULARITIES:

y = 1/x

2. HANDLING MULTIVALUED FUNCTIONS:

x^2+y^2 = C

For the first case see my prior post. For the second case, you may just consider changing changing coordinates (to polar coordinates for that example). For more general cases... well maybe you should take care of your mid-term. Something like

x^n+y^n = C, where n = any positive integer.

Will likely produce some sweat

[Ghoser777]

If I convert it to the form f(x,y) - g(x,y) = 0, I think I don't have to worry about those cases. Essentially, if I'm iterating through a bunch of x's, and for some xi I don't find a root because the function is undefined at the point or there just isn't a real root (such as y-1/0=0 or y^2+1=0), then I just skip the xi and move on.In the case of multiple roots, I explained in my last post how I was going to deal with that.

F-bacher

[Juggle5]

Here are some interesting curves you might want to try:

To see how well your program handles multiple curves:

(plot range x = [-10,10]; y = [-10,10])
cos(x) = sin(y) + 1 --&gt; "circles" on a lattice
cos(x^2 + y^2) --&gt; infinite number of coincentric circles, getting closer and closer together as the radius increases. This one may be tricky.

Curve intersections:

(plot range x = [-10,10]; y = [-10,10])
(x^2 + y^2)^3 = 400*x^2*y^2 --&gt; "Rose of Grandi" (intersection at the origin)
cos(x)*sin(y) = 0 --&gt; grid
cos(x) = sin(y) --&gt; diagonal grid

Fun stuff: (Plot ranges in here are smaller than [-10,10],[-10,10]; I'll let
you find what looks cool.) The parameters "a" and "b" can be varied to modify the size or shape of the curves. |x| means the absolute value of x. I think the names of these curves are just as cool as the curves themselves.

(x^2 - 1)^2 = y^2*(3+2*y) --&gt; pretzel curve
x*y^2 = 4*a^2*(2*a - x) --&gt; Witch of Agnesi
(x^2 + y^2)^2 = a^2*(x^2 - y^2) --&gt; Lemniscate of Bernoulli
x^3 + y^3 = 3*a*x*y --&gt; Folium of Descartes
(x^2 + y^2 - a*x)^2 = b^2*(x^2 + y^2) --&gt; Cardioid
|x|^(2/3) + |y|^(2/3) = 1 --&gt; Astroid
(x^2 + y^2 + a^2)^2 - 4*a^2*x^2 - b^4 = 0 --&gt; Ovals of Cassini
x^2*y + b^2*y - a^2*x = 0 --&gt; Newton's Serpentine
x^2*y^2 = (y+a)^2*(b^2 - y^2) --&gt; Conchoid of Nicomedes
y^2 = x^2*((a - x)/(a + x)) --&gt; Strophoid
|x| + |y| + |x-1| + |y-1| = 2 + sqrt(2) --&gt; octagon

I wrote a simple equation graphing program in C back in 1993 to graph these. Amazingly, it still runs... You can have my source code/executable if you want. No guarantees on the quality of the code: I wasn't too experienced a programmer then. Email me at jcross@wcox.com.

Cheers,

--Juggle5

[DaGuy]

If I convert it to the form f(x,y) - g(x,y) = 0, I think I don't have to worry about those cases.

What if,

<font color = red> f(x,y) = 1/xy and g(x,y)= x^2+y^2 </font>

subtracting both functions doesn't get rid of the singularity. I guess what you mean is, that you will consider nonsingular real valued functions.

You seem to be taking in all the suggestions pretty well. That's a good learning approach. So how are those midterms going

[Ghoser777]

Originally posted by DaGuy:
<STRONG>

What if,

<font color = red> f(x,y) = 1/xy and g(x,y)= x^2+y^2 </font>

subtracting both functions doesn't get rid of the singularity. I guess what you mean is, that you will consider nonsingular real valued functions.

No, if I plug in an x, and after iterating a little while, I don't reach a y-root, I essentially assume there isn't one and move on. Not very efficient, but that case is a rariety. (The purpose of this graph will be mainly for polynomials and such, but sometimes a circl and hyperbola will crop up).

You seem to be taking in all the suggestions pretty well. That's a good learning approach. So how are those midterms going </STRONG>

Math's all about throwing out ideas and having them completely thrashed around to the point where you think your arguments are worse than false. So I get use to it

Mid terms were fine... now I have to worry about all these busy work projects which are half pointless, half stupid. They take up way too much time I could be spending working on this. If I didn't have my 8 page take home midterm for EDPSYCH, I might actually get this *started* this weekend.

But I'm not bitter

F-bacher