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:
Computation of ALL zeros of Bivariate Polynomial system

Subject: Computation of ALL zeros of Bivariate Polynomial system

From: Mian Ahmed

Date: 6 May, 2010 17:19:04

Message: 1 of 10

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

Subject: Computation of ALL zeros of Bivariate Polynomial system

From: Roger Stafford

Date: 6 May, 2010 18:00:04

Message: 2 of 10

"Mian Ahmed" <mmianilyas@gmail.com> wrote in message <hrutm8$pj8$1@fred.mathworks.com>...
> 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
- - - - - - - - -
  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 x-y 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.

Roger Stafford

Subject: Computation of ALL zeros of Bivariate Polynomial system

From: Walter Roberson

Date: 6 May, 2010 19:01:28

Message: 3 of 10

Mian Ahmed wrote:
> 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.

There are relatively few degree 12 multinomials for which exact zeros
can be found, especially if the zeros are to be represented in binary
floating point rather than symbolically. For example, even if the degree
12 multinomial happened to simplify to x^2-2 then because sqrt(2) cannot
be exactly represented in a finite binary string, it is a matter of
chance and round-off error as to whether a value could be found that,
when substituted in, came out _exactly_ as zero. It would depend in part
on whether the multinomial was partly factored or fully expanded:
evaluating a partly factored multinomial would have different round-off
then the fully-expanded one. On the other hand, the more factoring you
can do, the easier it is to find zeros.

If you have to find the roots by techniques such as looking for zero
crossings (because the multinomial does not factor easily), then with
multinomials as high as degree 12, chances are fairly high that you will
end up finding that a zero crossing must exist and yet not be able to
find it numerically because the rounded evaluation at a trial root lies
on one side of zero, but the rounded evaluation for the adjacent binary
number falls on the other side of zero -- with a 12th order polynomial,
a change of deltax in the trial root makes an evaluation difference of
12 * deltax if deltax is less than one part in sqrt(2^53), so about 11
times in 12, a root that will make the expression an exact 0 will
usually not be findable.

The problem is certainly complicated by the values needing to be the
roots of both multinomials.

The way you stated the problem was that the values had to make
f(x,y)=g(x,y)=0 which implies that the evaluation at the located points
must come out as zero -- which is a question of floating point numerics.

You did not ask for the roots in common between the multinomials: that
would instead be an algebraic question involving lots of square roots
and cube roots and so on. The algebraic question is, in general, not
solvable for degree 12 -- the algebraic question is, in general, only
solvable up to degree 4 (at least for polynomials; I do not know if
there is theory for solutions of multinomials.)

Now reconsider the numerics case. Suppose a multinomial happens to have
no terms of order 0 (constants) or 1 (x or y alone): then every term
would involve the multiplication of at least two values. If the
multiplication of the terms is done before multiplication by the
constants, then in such a case any pair of x and y each less than about
1/sqrt(10^308) would result in floating point underflow to 0 for all the
terms, in which case the constant multipliers could be of any magnitude
and the entire multinomial would evaluate numerically to 0. There are
quite a few (x,y) pairs representable in binary floating point in which
x and y are both smaller than that magnitude -- do you really want the
program to be listing out roughly 10^180 pairs ??

Thus, if you say that you want the algebraic roots then the problem is
usually unsolvable, and if you say that you want the floating point
values that evaluate to 0, you might get anywhere from none to a list of
every possible pair of floating point numbers (because all of the
coefficients might be 0 and every number times 0 is 0...)

You are going to have to think about how you want to define the problem.

Subject: Computation of ALL zeros of Bivariate Polynomial system

From: Roger Stafford

Date: 6 May, 2010 20:05:22

Message: 4 of 10

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

Roger Stafford

Subject: Computation of ALL zeros of Bivariate Polynomial system

From: Bruno Luong

Date: 6 May, 2010 20:30:23

Message: 5 of 10

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.
 
http://www.mathworks.com/matlabcentral/fileexchange/24478-groebner

Bruno

Subject: Computation of ALL zeros of Bivariate Polynomial system

From: Walter Roberson

Date: 6 May, 2010 21:05:07

Message: 6 of 10

Roger Stafford wrote:

> 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.

We've had many posters over the years expecting things that are "quite
unreasonable" to the people who happen to know something about the
mathematics of the subject being queried. Look how many people we've had
just in the last week expecting to be able to find "the" equation behind
a finite set of data.

I pointed out some problems if the question was a theoretical one; I
pointed some false positives and some false negatives to expect if the
question was a numerical one.

Speaking of the theory: what (roughly) does theory say about the ability
to examine a higher dimension polynomial and find bounds on its roots
such that the roots could be searched for numerically?

Differentiating a quintic would give a quartic and since quartics can be
solved exactly, the inflection points of the quintic could be found; the
sign of the leading term would give its orientation... so it seems to me
the relative positions of the zeros should be discernible, thus allowing
a numeric search to be sure of finding all the zeros ?

Is there any relevant theory that extends this to higher dimensions?
Guess I could peak at roots() and see if it does anything clever.
Perhaps something involving the N complex roots of unity would allow one
to constrain the complex space for each root??

Is there a theoretical limit on the number of roots of a multinomial
based upon the maximum of the total degree over each term? Perhaps a
limit of d^n where d is that maximum total degree and n is the number of
variables??

At the moment, not knowing these things, I don't know whether the "ideal
solutions" could be reasonably constrained: if they cannot be, then due
to the possibility of false positives, how would one know when to stop
searching?

It seems to me that if there _is_ a general solution strategy that
allowed one to pigeon-hole the zeros up to degree N, then that would be
the same as saying that there is a general solution strategy to find the
global minimum of a bivariate multinomial of maximum total degree up to
N+1. I don't recall ever hearing of such a strategy -- and if such a
strategy was known for all finite degrees, then that would suggest that
people could do series expansion of many continuous non-multinomial
functions and do such a search and thereby find interesting estimates of
the global minima ?

Just musing aloud...

Subject: Computation of ALL zeros of Bivariate Polynomial system

From: Mian

Date: 7 May, 2010 11:21:05

Message: 7 of 10

"Roger Stafford" <ellieandrogerxyzzy@mindspring.com.invalid> wrote in message <hrv034$6k7$1@fred.mathworks.com>...
> "Mian Ahmed" <mmianilyas@gmail.com> wrote in message <hrutm8$pj8$1@fred.mathworks.com>...
> > 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
> - - - - - - - - -
> 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 x-y 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.
>
> Roger Stafford

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.

Subject: Computation of ALL zeros of Bivariate Polynomial system

From: Mian

Date: 7 May, 2010 11:29:04

Message: 8 of 10

"Bruno Luong" <b.luong@fogale.findmycountry> wrote in message <hrv8sv$lv7$1@fred.mathworks.com>...
> 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.
>
> http://www.mathworks.com/matlabcentral/fileexchange/24478-groebner
>
> Bruno

Thanks alot Bruno. It seems to be very useful. I will try these m.files.

Subject: Computation of ALL zeros of Bivariate Polynomial system

From: Steven Lord

Date: 7 May, 2010 13:19:02

Message: 9 of 10


"Mian " <mmianilyas@gmail.com.remove> wrote in message
news:hs0t31$5nj$1@fred.mathworks.com...
> "Roger Stafford" <ellieandrogerxyzzy@mindspring.com.invalid> wrote in
> message <hrv034$6k7$1@fred.mathworks.com>...
>> "Mian Ahmed" <mmianilyas@gmail.com> wrote in message
>> <hrutm8$pj8$1@fred.mathworks.com>...
>> > 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
>> - - - - - - - - -
>> 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 x-y 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.
>>
>> Roger Stafford
>
> 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.

Just because a problem is not new doesn't mean it's not difficult. Look at
computer vision, teaching a robot to walk upright, or the Turing test --
humans mastered those skills ages ago.

--
Steve Lord
slord@mathworks.com
comp.soft-sys.matlab (CSSM) FAQ: http://matlabwiki.mathworks.com/MATLAB_FAQ

Subject: Computation of ALL zeros of Bivariate Polynomial system

From: Mian

Date: 7 May, 2010 13:52:19

Message: 10 of 10

"Steven Lord" <slord@mathworks.com> wrote in message <hs1401$av3$1@fred.mathworks.com>...
>
> "Mian " <mmianilyas@gmail.com.remove> wrote in message
> news:hs0t31$5nj$1@fred.mathworks.com...
> > "Roger Stafford" <ellieandrogerxyzzy@mindspring.com.invalid> wrote in
> > message <hrv034$6k7$1@fred.mathworks.com>...
> >> "Mian Ahmed" <mmianilyas@gmail.com> wrote in message
> >> <hrutm8$pj8$1@fred.mathworks.com>...
> >> > 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
> >> - - - - - - - - -
> >> 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 x-y 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.
> >>
> >> Roger Stafford
> >
> > 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.
>
> Just because a problem is not new doesn't mean it's not difficult. Look at
> computer vision, teaching a robot to walk upright, or the Turing test --
> humans mastered those skills ages ago.
>
> --
> Steve Lord
> slord@mathworks.com
> comp.soft-sys.matlab (CSSM) FAQ: http://matlabwiki.mathworks.com/MATLAB_FAQ
>
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.

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