http://nl.mathworks.com/matlabcentral/newsreader/view_thread/281496
MATLAB Central Newsreader  Computation of ALL zeros of Bivariate Polynomial system
Feed for thread: Computation of ALL zeros of Bivariate Polynomial system
enus
©19942017 by MathWorks, Inc.
webmaster@mathworks.com
MATLAB Central Newsreader
http://blogs.law.harvard.edu/tech/rss
60
MathWorks
http://nl.mathworks.com/images/membrane_icon.gif

Thu, 06 May 2010 17:19:04 +0000
Computation of ALL zeros of Bivariate Polynomial system
http://nl.mathworks.com/matlabcentral/newsreader/view_thread/281496#742770
Mian Ahmed
I have two bivariate polynomials f(x,y) and g(x,y) and i want to compute all values of x and y for which f(x,y)=g(x,y)=0. The order of the two polynomials is 12. I need to find a code that can solve this problem. Please help

Thu, 06 May 2010 18:00:04 +0000
Re: Computation of ALL zeros of Bivariate Polynomial system
http://nl.mathworks.com/matlabcentral/newsreader/view_thread/281496#742783
Roger Stafford
"Mian Ahmed" <mmianilyas@gmail.com> wrote in message <hrutm8$pj8$1@fred.mathworks.com>...<br>
> I have two bivariate polynomials f(x,y) and g(x,y) and i want to compute all values of x and y for which f(x,y)=g(x,y)=0. The order of the two polynomials is 12. I need to find a code that can solve this problem. Please help <br>
        <br>
You could use 'fsolve' in the Optimization Toolbox. However, you need to proceed with care. This function requires an 'x0' "starting" value. In your case the equations f(x,y)=0 and g(x,y)=0 will each have very complicated locus curves in the xy plane and very probably a great many crossing points between them. You will need a new 'x0' to obtain each one, and working out how to do this will be no easy task. I would try to do an 'ezplot' or something of the kind to get an idea where the crossings are.<br>
<br>
Roger Stafford

Thu, 06 May 2010 19:01:28 +0000
Re: Computation of ALL zeros of Bivariate Polynomial system
http://nl.mathworks.com/matlabcentral/newsreader/view_thread/281496#742805
Walter Roberson
Mian Ahmed wrote:<br>
> I have two bivariate polynomials f(x,y) and g(x,y) and i want to compute <br>
> all values of x and y for which f(x,y)=g(x,y)=0. The order of the two <br>
> polynomials is 12. I need to find a code that can solve this problem. <br>
<br>
There are relatively few degree 12 multinomials for which exact zeros <br>
can be found, especially if the zeros are to be represented in binary <br>
floating point rather than symbolically. For example, even if the degree <br>
12 multinomial happened to simplify to x^22 then because sqrt(2) cannot <br>
be exactly represented in a finite binary string, it is a matter of <br>
chance and roundoff error as to whether a value could be found that, <br>
when substituted in, came out _exactly_ as zero. It would depend in part <br>
on whether the multinomial was partly factored or fully expanded: <br>
evaluating a partly factored multinomial would have different roundoff <br>
then the fullyexpanded one. On the other hand, the more factoring you <br>
can do, the easier it is to find zeros.<br>
<br>
If you have to find the roots by techniques such as looking for zero <br>
crossings (because the multinomial does not factor easily), then with <br>
multinomials as high as degree 12, chances are fairly high that you will <br>
end up finding that a zero crossing must exist and yet not be able to <br>
find it numerically because the rounded evaluation at a trial root lies <br>
on one side of zero, but the rounded evaluation for the adjacent binary <br>
number falls on the other side of zero  with a 12th order polynomial, <br>
a change of deltax in the trial root makes an evaluation difference of <br>
12 * deltax if deltax is less than one part in sqrt(2^53), so about 11 <br>
times in 12, a root that will make the expression an exact 0 will <br>
usually not be findable.<br>
<br>
The problem is certainly complicated by the values needing to be the <br>
roots of both multinomials.<br>
<br>
The way you stated the problem was that the values had to make <br>
f(x,y)=g(x,y)=0 which implies that the evaluation at the located points <br>
must come out as zero  which is a question of floating point numerics.<br>
<br>
You did not ask for the roots in common between the multinomials: that <br>
would instead be an algebraic question involving lots of square roots <br>
and cube roots and so on. The algebraic question is, in general, not <br>
solvable for degree 12  the algebraic question is, in general, only <br>
solvable up to degree 4 (at least for polynomials; I do not know if <br>
there is theory for solutions of multinomials.)<br>
<br>
Now reconsider the numerics case. Suppose a multinomial happens to have <br>
no terms of order 0 (constants) or 1 (x or y alone): then every term <br>
would involve the multiplication of at least two values. If the <br>
multiplication of the terms is done before multiplication by the <br>
constants, then in such a case any pair of x and y each less than about <br>
1/sqrt(10^308) would result in floating point underflow to 0 for all the <br>
terms, in which case the constant multipliers could be of any magnitude <br>
and the entire multinomial would evaluate numerically to 0. There are <br>
quite a few (x,y) pairs representable in binary floating point in which <br>
x and y are both smaller than that magnitude  do you really want the <br>
program to be listing out roughly 10^180 pairs ??<br>
<br>
Thus, if you say that you want the algebraic roots then the problem is <br>
usually unsolvable, and if you say that you want the floating point <br>
values that evaluate to 0, you might get anywhere from none to a list of <br>
every possible pair of floating point numbers (because all of the <br>
coefficients might be 0 and every number times 0 is 0...)<br>
<br>
You are going to have to think about how you want to define the problem.

Thu, 06 May 2010 20:05:22 +0000
Re: Computation of ALL zeros of Bivariate Polynomial system
http://nl.mathworks.com/matlabcentral/newsreader/view_thread/281496#742832
Roger Stafford
Walter Roberson <roberson@hushmail.com> wrote in message <imEEn.1$gv4.0@newsfe09.iad>...<br>
> Mian Ahmed wrote:<br>
> > I have two bivariate polynomials f(x,y) and g(x,y) and i want to compute <br>
> > all values of x and y for which f(x,y)=g(x,y)=0. The order of the two <br>
> > polynomials is 12. I need to find a code that can solve this problem. <br>
> <br>
> There are relatively few degree 12 multinomials for which exact zeros <br>
> can be found, especially if the zeros are to be represented in binary <br>
> floating point rather than symbolically. For example, even if the degree <br>
> 12 multinomial happened to simplify to x^22 then because sqrt(2) cannot <br>
> be exactly represented in a finite binary string, it is a matter of <br>
> chance and roundoff error as to whether a value could be found that, <br>
> when substituted in, came out _exactly_ as zero. It would depend in part <br>
> on whether the multinomial was partly factored or fully expanded: <br>
> evaluating a partly factored multinomial would have different roundoff <br>
> then the fullyexpanded one. On the other hand, the more factoring you <br>
> can do, the easier it is to find zeros.<br>
> <br>
> If you have to find the roots by techniques such as looking for zero <br>
> crossings (because the multinomial does not factor easily), then with <br>
> multinomials as high as degree 12, chances are fairly high that you will <br>
> end up finding that a zero crossing must exist and yet not be able to <br>
> find it numerically because the rounded evaluation at a trial root lies <br>
> on one side of zero, but the rounded evaluation for the adjacent binary <br>
> number falls on the other side of zero  with a 12th order polynomial, <br>
> a change of deltax in the trial root makes an evaluation difference of <br>
> 12 * deltax if deltax is less than one part in sqrt(2^53), so about 11 <br>
> times in 12, a root that will make the expression an exact 0 will <br>
> usually not be findable.<br>
> <br>
> The problem is certainly complicated by the values needing to be the <br>
> roots of both multinomials.<br>
> <br>
> The way you stated the problem was that the values had to make <br>
> f(x,y)=g(x,y)=0 which implies that the evaluation at the located points <br>
> must come out as zero  which is a question of floating point numerics.<br>
> <br>
> You did not ask for the roots in common between the multinomials: that <br>
> would instead be an algebraic question involving lots of square roots <br>
> and cube roots and so on. The algebraic question is, in general, not <br>
> solvable for degree 12  the algebraic question is, in general, only <br>
> solvable up to degree 4 (at least for polynomials; I do not know if <br>
> there is theory for solutions of multinomials.)<br>
> <br>
> Now reconsider the numerics case. Suppose a multinomial happens to have <br>
> no terms of order 0 (constants) or 1 (x or y alone): then every term <br>
> would involve the multiplication of at least two values. If the <br>
> multiplication of the terms is done before multiplication by the <br>
> constants, then in such a case any pair of x and y each less than about <br>
> 1/sqrt(10^308) would result in floating point underflow to 0 for all the <br>
> terms, in which case the constant multipliers could be of any magnitude <br>
> and the entire multinomial would evaluate numerically to 0. There are <br>
> quite a few (x,y) pairs representable in binary floating point in which <br>
> x and y are both smaller than that magnitude  do you really want the <br>
> program to be listing out roughly 10^180 pairs ??<br>
> <br>
> Thus, if you say that you want the algebraic roots then the problem is <br>
> usually unsolvable, and if you say that you want the floating point <br>
> values that evaluate to 0, you might get anywhere from none to a list of <br>
> every possible pair of floating point numbers (because all of the <br>
> coefficients might be 0 and every number times 0 is 0...)<br>
> <br>
> You are going to have to think about how you want to define the problem.<br>
        <br>
Walter, I don't think Mian is actually looking for either an algebraic solution, which is highly likely to be impossible, or a case where numerically f(x,y) and g(x,y) happen to both give a precise floating point zero, which is also highly unlikely ever to occur. I believe all that is wanted here is to find pairs of floating point numbers, admittedly inexact, which when used as arguments to f(x,y) and g(x,y) will produce values that are reasonably close to zero relative to other quantities involved in the computation, the expectation being that such x and y values are correspondingly reasonably close to an ideal solution pair in the purely mathematical sense. To expect otherwise would be quite unreasonable.<br>
<br>
Roger Stafford

Thu, 06 May 2010 20:30:23 +0000
Re: Computation of ALL zeros of Bivariate Polynomial system
http://nl.mathworks.com/matlabcentral/newsreader/view_thread/281496#742847
Bruno Luong
I have been intrigued by this topic now and then but I don't know much about it. I just want to point out a file in FEX that has the merit of giving an *attempt* to solve roots for multivariate polynomial.<br>
<br>
<a href="http://www.mathworks.com/matlabcentral/fileexchange/24478groebner">http://www.mathworks.com/matlabcentral/fileexchange/24478groebner</a><br>
<br>
Bruno

Thu, 06 May 2010 21:05:07 +0000
Re: Computation of ALL zeros of Bivariate Polynomial system
http://nl.mathworks.com/matlabcentral/newsreader/view_thread/281496#742860
Walter Roberson
Roger Stafford wrote:<br>
<br>
> Walter, I don't think Mian is actually looking for either an algebraic <br>
> solution, which is highly likely to be impossible, or a case where <br>
> numerically f(x,y) and g(x,y) happen to both give a precise floating <br>
> point zero, which is also highly unlikely ever to occur. I believe all <br>
> that is wanted here is to find pairs of floating point numbers, <br>
> admittedly inexact, which when used as arguments to f(x,y) and g(x,y) <br>
> will produce values that are reasonably close to zero relative to other <br>
> quantities involved in the computation, the expectation being that such <br>
> x and y values are correspondingly reasonably close to an ideal solution <br>
> pair in the purely mathematical sense. To expect otherwise would be <br>
> quite unreasonable.<br>
<br>
We've had many posters over the years expecting things that are "quite <br>
unreasonable" to the people who happen to know something about the <br>
mathematics of the subject being queried. Look how many people we've had <br>
just in the last week expecting to be able to find "the" equation behind <br>
a finite set of data.<br>
<br>
I pointed out some problems if the question was a theoretical one; I <br>
pointed some false positives and some false negatives to expect if the <br>
question was a numerical one.<br>
<br>
Speaking of the theory: what (roughly) does theory say about the ability <br>
to examine a higher dimension polynomial and find bounds on its roots <br>
such that the roots could be searched for numerically?<br>
<br>
Differentiating a quintic would give a quartic and since quartics can be <br>
solved exactly, the inflection points of the quintic could be found; the <br>
sign of the leading term would give its orientation... so it seems to me <br>
the relative positions of the zeros should be discernible, thus allowing <br>
a numeric search to be sure of finding all the zeros ?<br>
<br>
Is there any relevant theory that extends this to higher dimensions? <br>
Guess I could peak at roots() and see if it does anything clever. <br>
Perhaps something involving the N complex roots of unity would allow one <br>
to constrain the complex space for each root??<br>
<br>
Is there a theoretical limit on the number of roots of a multinomial <br>
based upon the maximum of the total degree over each term? Perhaps a <br>
limit of d^n where d is that maximum total degree and n is the number of <br>
variables??<br>
<br>
At the moment, not knowing these things, I don't know whether the "ideal <br>
solutions" could be reasonably constrained: if they cannot be, then due <br>
to the possibility of false positives, how would one know when to stop <br>
searching?<br>
<br>
It seems to me that if there _is_ a general solution strategy that <br>
allowed one to pigeonhole the zeros up to degree N, then that would be <br>
the same as saying that there is a general solution strategy to find the <br>
global minimum of a bivariate multinomial of maximum total degree up to <br>
N+1. I don't recall ever hearing of such a strategy  and if such a <br>
strategy was known for all finite degrees, then that would suggest that <br>
people could do series expansion of many continuous nonmultinomial <br>
functions and do such a search and thereby find interesting estimates of <br>
the global minima ?<br>
<br>
Just musing aloud...

Fri, 07 May 2010 11:21:05 +0000
Re: Computation of ALL zeros of Bivariate Polynomial system
http://nl.mathworks.com/matlabcentral/newsreader/view_thread/281496#743044
Mian
"Roger Stafford" <ellieandrogerxyzzy@mindspring.com.invalid> wrote in message <hrv034$6k7$1@fred.mathworks.com>...<br>
> "Mian Ahmed" <mmianilyas@gmail.com> wrote in message <hrutm8$pj8$1@fred.mathworks.com>...<br>
> > I have two bivariate polynomials f(x,y) and g(x,y) and i want to compute all values of x and y for which f(x,y)=g(x,y)=0. The order of the two polynomials is 12. I need to find a code that can solve this problem. Please help <br>
>         <br>
> You could use 'fsolve' in the Optimization Toolbox. However, you need to proceed with care. This function requires an 'x0' "starting" value. In your case the equations f(x,y)=0 and g(x,y)=0 will each have very complicated locus curves in the xy plane and very probably a great many crossing points between them. You will need a new 'x0' to obtain each one, and working out how to do this will be no easy task. I would try to do an 'ezplot' or something of the kind to get an idea where the crossings are.<br>
> <br>
> Roger Stafford<br>
<br>
Thanks for your suggestion. The choice of starting points will be an issue for 'fsolve' command. 'ezplot' or other function plotters might be useful in suggesting 'x0'. I think there must be a code or toolbox that can solve all these issues without looking into locus curves, because it is not a new problem.

Fri, 07 May 2010 11:29:04 +0000
Re: Computation of ALL zeros of Bivariate Polynomial system
http://nl.mathworks.com/matlabcentral/newsreader/view_thread/281496#743045
Mian
"Bruno Luong" <b.luong@fogale.findmycountry> wrote in message <hrv8sv$lv7$1@fred.mathworks.com>...<br>
> I have been intrigued by this topic now and then but I don't know much about it. I just want to point out a file in FEX that has the merit of giving an *attempt* to solve roots for multivariate polynomial.<br>
> <br>
> <a href="http://www.mathworks.com/matlabcentral/fileexchange/24478groebner">http://www.mathworks.com/matlabcentral/fileexchange/24478groebner</a><br>
> <br>
> Bruno<br>
<br>
Thanks alot Bruno. It seems to be very useful. I will try these m.files.

Fri, 07 May 2010 13:19:02 +0000
Re: Computation of ALL zeros of Bivariate Polynomial system
http://nl.mathworks.com/matlabcentral/newsreader/view_thread/281496#743067
Steven Lord
<br>
"Mian " <mmianilyas@gmail.com.remove> wrote in message <br>
news:hs0t31$5nj$1@fred.mathworks.com...<br>
> "Roger Stafford" <ellieandrogerxyzzy@mindspring.com.invalid> wrote in <br>
> message <hrv034$6k7$1@fred.mathworks.com>...<br>
>> "Mian Ahmed" <mmianilyas@gmail.com> wrote in message <br>
>> <hrutm8$pj8$1@fred.mathworks.com>...<br>
>> > I have two bivariate polynomials f(x,y) and g(x,y) and i want to <br>
>> > compute all values of x and y for which f(x,y)=g(x,y)=0. The order of <br>
>> > the two polynomials is 12. I need to find a code that can solve this <br>
>> > problem. Please help<br>
>>         <br>
>> You could use 'fsolve' in the Optimization Toolbox. However, you need <br>
>> to proceed with care. This function requires an 'x0' "starting" value. <br>
>> In your case the equations f(x,y)=0 and g(x,y)=0 will each have very <br>
>> complicated locus curves in the xy plane and very probably a great many <br>
>> crossing points between them. You will need a new 'x0' to obtain each <br>
>> one, and working out how to do this will be no easy task. I would try to <br>
>> do an 'ezplot' or something of the kind to get an idea where the <br>
>> crossings are.<br>
>><br>
>> Roger Stafford<br>
><br>
> Thanks for your suggestion. The choice of starting points will be an issue <br>
> for 'fsolve' command. 'ezplot' or other function plotters might be useful <br>
> in suggesting 'x0'. I think there must be a code or toolbox that can <br>
> solve all these issues without looking into locus curves, because it is <br>
> not a new problem.<br>
<br>
Just because a problem is not new doesn't mean it's not difficult. Look at <br>
computer vision, teaching a robot to walk upright, or the Turing test  <br>
humans mastered those skills ages ago.<br>
<br>
 <br>
Steve Lord<br>
slord@mathworks.com<br>
comp.softsys.matlab (CSSM) FAQ: <a href="http://matlabwiki.mathworks.com/MATLAB_FAQ">http://matlabwiki.mathworks.com/MATLAB_FAQ</a>

Fri, 07 May 2010 13:52:19 +0000
Re: Computation of ALL zeros of Bivariate Polynomial system
http://nl.mathworks.com/matlabcentral/newsreader/view_thread/281496#743079
Mian
"Steven Lord" <slord@mathworks.com> wrote in message <hs1401$av3$1@fred.mathworks.com>...<br>
> <br>
> "Mian " <mmianilyas@gmail.com.remove> wrote in message <br>
> news:hs0t31$5nj$1@fred.mathworks.com...<br>
> > "Roger Stafford" <ellieandrogerxyzzy@mindspring.com.invalid> wrote in <br>
> > message <hrv034$6k7$1@fred.mathworks.com>...<br>
> >> "Mian Ahmed" <mmianilyas@gmail.com> wrote in message <br>
> >> <hrutm8$pj8$1@fred.mathworks.com>...<br>
> >> > I have two bivariate polynomials f(x,y) and g(x,y) and i want to <br>
> >> > compute all values of x and y for which f(x,y)=g(x,y)=0. The order of <br>
> >> > the two polynomials is 12. I need to find a code that can solve this <br>
> >> > problem. Please help<br>
> >>         <br>
> >> You could use 'fsolve' in the Optimization Toolbox. However, you need <br>
> >> to proceed with care. This function requires an 'x0' "starting" value. <br>
> >> In your case the equations f(x,y)=0 and g(x,y)=0 will each have very <br>
> >> complicated locus curves in the xy plane and very probably a great many <br>
> >> crossing points between them. You will need a new 'x0' to obtain each <br>
> >> one, and working out how to do this will be no easy task. I would try to <br>
> >> do an 'ezplot' or something of the kind to get an idea where the <br>
> >> crossings are.<br>
> >><br>
> >> Roger Stafford<br>
> ><br>
> > Thanks for your suggestion. The choice of starting points will be an issue <br>
> > for 'fsolve' command. 'ezplot' or other function plotters might be useful <br>
> > in suggesting 'x0'. I think there must be a code or toolbox that can <br>
> > solve all these issues without looking into locus curves, because it is <br>
> > not a new problem.<br>
> <br>
> Just because a problem is not new doesn't mean it's not difficult. Look at <br>
> computer vision, teaching a robot to walk upright, or the Turing test  <br>
> humans mastered those skills ages ago.<br>
> <br>
>  <br>
> Steve Lord<br>
> slord@mathworks.com<br>
> comp.softsys.matlab (CSSM) FAQ: <a href="http://matlabwiki.mathworks.com/MATLAB_FAQ">http://matlabwiki.mathworks.com/MATLAB_FAQ</a> <br>
> <br>
You are right steve but i have seen some papers with algorithms for computation of all zeros of multivariate polynomials such as Auzenger algorithm (published in 1988). The problem is known to be dificult and in some cases impossible to solve.