BivariatePolynomial - Maple Help

RootFinding

 BivariatePolynomial
 find the solutions of two or more bivariate polynomials

 Calling Sequence BivariatePolynomial(fg, varlist, options)

Parameters

 fg - set or list of two or more polynomials in two variables varlist - list or set of two names; a list defines the order in the solutions pairs returned, a set requests output in the form {x=..,y=..} options - (optional) equations of the form option=value where option is one of exact, verify, or verifyTol.

Description

 • The BivariatePolynomial(fg, varlist, options) command solves the bivariate polynomials fg, in the case when there is only a finite number of solutions.  If there are an infinite number of solutions, this routine may fail.
 • The routine performs a random orthogonal change of coordinates, takes a random linear combination of the two or more input polynomials to produce exactly two polynomials $f\left(x,y\right)$ and $g\left(x,y\right)$.  It then constructs the Bezout matrix $B\left(y\right)$ of $f\left(x,y\right)$ and $g\left(x,y\right)$ with respect to $x$, and then the Companion matrix pencil of the matrix polynomial $B\left(y\right)$.  It then solves the generalized eigenproblem for eigenvalues and eigenvectors of the pencil; the eigenvalues give the values of $y$, and the corresponding values of $x$ are deduced from the eigenvectors.
 If the option verify=true is given (the default), or if there are more than two input polynomials, each putative root is tested on the original polynomials to see if the residual is acceptably small. A residual is judged to be small enough if it is smaller than ilog[10](n+1)*verifyTol times the maxnorm of the polynomial, where n is the number of roots.  By default, verifyTol=Float(1,1-Digits). This default tolerance may be overridden by setting the option verifyTol=... in the call.
 • The routine assumes that $f\left(x,y\right)=g\left(x,y\right)=0$ has only isolated simple roots. Multiple roots are, numerically, perturbed into clusters of simple roots by rounding errors in the process. In practice, if the multiplicity of the root is not too high (say not more than three) then the results may be acceptable. If, however, there are an infinite number of roots (i.e. the dimensionality of the variety is higher than zero), then this routine will fail.  Through rounding errors, a higher-dimensional system MAY be perturbed to a zero-dimensional system, and in this case pseudozeros are calculated and some information may be deduced about the true solutions by repeated solving; the differing random combinations will produce different pseudozeros that can be put together to get a partial picture of the higher- dimensional zero set.
 • Exact solutions are sometimes possible, and may be attempted by specifying the option exact=true. In this case, the random combinations are done over the integers to avoid introducing rounding errors. In the case where the input coefficients are exact and the polynomials are not of too high a degree, this may give exact (though not necessarily useful) answers.
 • Solutions obtained by BivariatePolynomial may be refined by use of fsolve.  See the examples.

Options

 • The options argument can contain the following equation.
 exact = true or false
 If exact=true, the command performs the computation exactly (depending on Eigenvectors succeeding with an exact computation).
 verify = true or false
 If verify=true (the default), the command tests that the values of each input polynomial at each computed root is smaller than 10 ulps, where an ulp is a Unit in the Last Place, measured relative to the user's setting of Digits and a vector norm of the polynomial coefficients. If verify=false, this residual test is not performed and infinite and spurious roots are returned along with any genuine roots.
 verifyTol = positive floating-point number for residual tolerance
 If verifyTol is overridden, the residual test is passed if the residual is less than or equal to ilog[10](n+1)*verifyTol times a vector norm of the polynomial coefficients.
 Note: The resultType = data_type option has been superseded by the exact option.

Examples

 > $\mathrm{with}\left(\mathrm{RootFinding}\right)$
 $\left[{\mathrm{Analytic}}{,}{\mathrm{AnalyticZerosFound}}{,}{\mathrm{BivariatePolynomial}}{,}{\mathrm{EnclosingBox}}{,}{\mathrm{EvaluateAtRoot}}{,}{\mathrm{HasRealRoots}}{,}{\mathrm{Homotopy}}{,}{\mathrm{Isolate}}{,}{\mathrm{NextZero}}{,}{\mathrm{Parametric}}{,}{\mathrm{RefineRoot}}{,}{\mathrm{WitnessPoints}}\right]$ (1)

 > $\mathrm{BivariatePolynomial}\left(\left[25uv-12,{u}^{2}+{v}^{2}-1\right],\left[u,v\right],\mathrm{exact}=\mathrm{true}\right)$
 $\left[{-}\frac{{3}}{{5}}{,}{-}\frac{{4}}{{5}}\right]{,}\left[\frac{{3}}{{5}}{,}\frac{{4}}{{5}}\right]{,}\left[\frac{{4}}{{5}}{,}\frac{{3}}{{5}}\right]{,}\left[{-}\frac{{4}}{{5}}{,}{-}\frac{{3}}{{5}}\right]$ (2)
 > $f≔\mathrm{randpoly}\left(\left[x,y\right],\mathrm{degree}=2,\mathrm{dense}\right)$
 ${f}{≔}{-}{7}{}{{x}}^{{2}}{+}{22}{}{x}{}{y}{-}{94}{}{{y}}^{{2}}{-}{55}{}{x}{+}{87}{}{y}{-}{56}$ (3)
 > $g≔\mathrm{randpoly}\left(\left[x,y\right],\mathrm{degree}=2,\mathrm{dense}\right)$
 ${g}{≔}{-}{62}{}{x}{}{y}{-}{73}{}{{y}}^{{2}}{+}{97}{}{x}{-}{4}{}{y}{-}{83}$ (4)

Set output, and a large residual tolerance

 > $\left\{\mathrm{BivariatePolynomial}\left(\left\{f,g\right\},\left\{y,x\right\},\mathrm{verifyTol}=0.000010\right)\right\}$
 $\left\{\left\{{x}{=}{-3.95035168944360}{-}{5.66623769360476}{}{I}{,}{y}{=}{1.58314710503979}{-}{0.669082838293886}{}{I}\right\}{,}\left\{{x}{=}{-3.95035168944360}{+}{5.66623769360475}{}{I}{,}{y}{=}{1.58314710503979}{+}{0.669082838293884}{}{I}\right\}{,}\left\{{x}{=}{0.217656104641032}{-}{0.580098578671116}{}{I}{,}{y}{=}{0.283760691054643}{-}{0.781752717215506}{}{I}\right\}{,}\left\{{x}{=}{0.217656104641038}{+}{0.580098578671126}{}{I}{,}{y}{=}{0.283760691054644}{+}{0.781752717215506}{}{I}\right\}\right\}$ (5)

A higher-degree example

 > $f≔\mathrm{randpoly}\left(\left[x,y\right],\mathrm{degree}=3,\mathrm{dense}\right)$
 ${f}{≔}{-}{10}{}{{x}}^{{3}}{+}{62}{}{{x}}^{{2}}{}{y}{+}{80}{}{x}{}{{y}}^{{2}}{-}{17}{}{{y}}^{{3}}{-}{82}{}{{x}}^{{2}}{-}{44}{}{x}{}{y}{-}{75}{}{{y}}^{{2}}{+}{71}{}{x}{-}{10}{}{y}{-}{7}$ (6)
 > $g≔\mathrm{randpoly}\left(\left[x,y\right],\mathrm{degree}=3,\mathrm{dense}\right)$
 ${g}{≔}{-}{40}{}{{x}}^{{3}}{+}{42}{}{{x}}^{{2}}{}{y}{+}{23}{}{x}{}{{y}}^{{2}}{+}{6}{}{{y}}^{{3}}{-}{50}{}{{x}}^{{2}}{+}{75}{}{x}{}{y}{+}{74}{}{{y}}^{{2}}{-}{92}{}{x}{+}{72}{}{y}{+}{37}$ (7)
 > $\mathrm{sols}≔\mathrm{BivariatePolynomial}\left(\left\{f,g\right\},\left[x,y\right],\mathrm{verify}=\mathrm{false}\right):$
 > $\mathrm{finiteSols}≔\mathrm{select}\left(\mathrm{type},\mathrm{map}\left(\mathrm{convert},\left\{\mathrm{sols}\right\},\mathrm{set}\right),\mathrm{set}\left(\mathrm{complex}\left(\mathrm{numeric}\right)\right)\right)$
 ${\mathrm{finiteSols}}{≔}\left\{\left\{{-8.72546491823764}{+}{1.35925353545860}{×}{{10}}^{{-17}}{}{I}{,}{-0.804422190778388}{+}{3.34994664560768}{×}{{10}}^{{-18}}{}{I}\right\}{,}\left\{{-1.61657845360198}{+}{1.76908763026871}{×}{{10}}^{{-13}}{}{I}{,}{0.422070508744693}{+}{1.19857563106188}{×}{{10}}^{{-13}}{}{I}\right\}{,}\left\{{-0.786588411682248}{-}{1.14300482684492}{}{I}{,}{0.604101549296862}{-}{0.622769842152083}{}{I}\right\}{,}\left\{{-0.786588411681959}{+}{1.14300482684388}{}{I}{,}{0.604101549296839}{+}{0.622769842152225}{}{I}\right\}{,}\left\{{-0.453554755499160}{-}{1.18516902864060}{}{I}{,}{-0.278993622119871}{+}{1.39562033543789}{}{I}\right\}{,}\left\{{-0.453554755498933}{+}{1.18516902864131}{}{I}{,}{-0.278993622120491}{-}{1.39562033543820}{}{I}\right\}{,}\left\{{-0.373755472345027}{+}{7.92945549673299}{×}{{10}}^{{-15}}{}{I}{,}{0.156992272818564}{-}{6.72289805687904}{×}{{10}}^{{-14}}{}{I}\right\}{,}\left\{{0.237394982252642}{+}{1.13779271541314}{×}{{10}}^{{-14}}{}{I}{,}{0.546628853006322}{-}{9.64664526931731}{×}{{10}}^{{-14}}{}{I}\right\}{,}\left\{{1.19776154305770}{-}{4.99381711787469}{×}{{10}}^{{-14}}{}{I}{,}{1.96030291260013}{+}{5.12600673966412}{×}{{10}}^{{-13}}{}{I}\right\}\right\}$ (8)

Refining the solutions by passing them as initial approximations to fsolve.

 > $\mathrm{finiteSols}≔\mathrm{BivariatePolynomial}\left(\left\{f,g\right\},\left[x,y\right]\right)$
 ${\mathrm{finiteSols}}{≔}\left[{-0.804422190776780}{+}{1.46422793108841}{×}{{10}}^{{-13}}{}{I}{,}{-8.72546491824324}{-}{1.63996064108809}{×}{{10}}^{{-12}}{}{I}\right]{,}\left[{-0.453554755502399}{-}{1.18516902863964}{}{I}{,}{-0.278993622115287}{+}{1.39562033544011}{}{I}\right]{,}\left[{-0.453554755497189}{+}{1.18516902864016}{}{I}{,}{-0.278993622120292}{-}{1.39562033543835}{}{I}\right]{,}\left[{0.422070508744006}{+}{8.37039084916395}{×}{{10}}^{{-14}}{}{I}{,}{-1.61657845360167}{+}{1.43001714671995}{×}{{10}}^{{-14}}{}{I}\right]{,}\left[{-0.786588411674588}{+}{1.14300482683918}{}{I}{,}{0.604101549297744}{+}{0.622769842150686}{}{I}\right]{,}\left[{-0.786588411675714}{-}{1.14300482684893}{}{I}{,}{0.604101549297546}{-}{0.622769842152381}{}{I}\right]{,}\left[{1.96030291261380}{+}{1.18650982072347}{×}{{10}}^{{-11}}{}{I}{,}{1.19776154306172}{+}{2.06586651483422}{×}{{10}}^{{-12}}{}{I}\right]{,}\left[{0.546628853006201}{+}{9.53326896881672}{×}{{10}}^{{-13}}{}{I}{,}{0.237394982252107}{+}{1.65986499189513}{×}{{10}}^{{-13}}{}{I}\right]{,}\left[{0.156992272818433}{-}{1.91316953588403}{×}{{10}}^{{-13}}{}{I}{,}{-0.373755472345041}{-}{3.33107473056885}{×}{{10}}^{{-14}}{}{I}\right]$ (9)
 > $\mathrm{Digits}≔30$
 ${\mathrm{Digits}}{≔}{30}$ (10)
 > $\mathrm{better}≔\mathrm{fsolve}\left(\left\{f,g\right\},\left\{x={{\mathrm{finiteSols}}_{5}}_{1},y={{\mathrm{finiteSols}}_{5}}_{2}\right\}\right)$
 ${\mathrm{better}}{≔}\left\{{x}{=}{-0.804422190778384243337546951432}{,}{y}{=}{-8.72546491823766479368773875110}\right\}$ (11)
 > $\mathrm{subs}\left(\mathrm{better},\left\{f,g\right\}\right)$
 $\left\{{0.}{,}{3.}{×}{{10}}^{{-26}}\right\}$ (12)

A one-dimensional variety, which causes BivariatePolynomial to fail: Note that many roots are found of the form x=1, y=anything (but not an infinite number), and the isolated roots are lost.

 > $\mathrm{Digits}≔\mathrm{trunc}\left(\mathrm{evalhf}\left(\mathrm{Digits}\right)\right)$
 ${\mathrm{Digits}}{≔}{15}$ (13)
 > $f≔\left({x}^{2}+{y}^{2}-1\right)\left(x-1\right)$
 ${f}{≔}\left({{x}}^{{2}}{+}{{y}}^{{2}}{-}{1}\right){}\left({x}{-}{1}\right)$ (14)
 > $g≔\left(25xy-12\right)\left(x-1\right)$
 ${g}{≔}\left({25}{}{x}{}{y}{-}{12}\right){}\left({x}{-}{1}\right)$ (15)
 > $\mathrm{BivariatePolynomial}\left(\left\{f,g\right\},\left[x,y\right],\mathrm{verifyTol}=0.000010\right)$
 $\left[{1.00000000000001}{+}{0.}{}{I}{,}{-44.2792829220309}{-}{0.}{}{I}\right]{,}\left[{0.999999999999998}{+}{0.}{}{I}{,}{8.85157501302492}{-}{0.}{}{I}\right]{,}\left[{0.999999999999998}{-}{2.28983498828939}{×}{{10}}^{{-16}}{}{I}{,}{-0.352677478474666}{+}{1.00257635649826}{}{I}\right]{,}\left[{0.999999999999998}{+}{1.80411241501588}{×}{{10}}^{{-16}}{}{I}{,}{-0.356764630842446}{-}{0.997039491465078}{}{I}\right]{,}\left[{1.00000000000002}{-}{2.88262252609583}{×}{{10}}^{{-16}}{}{I}{,}{0.481584461593518}{-}{0.00389300631624244}{}{I}\right]$ (16)

Another example, worse in that the multiplicity is higher.

 > $f≔{\left(x-3\right)}^{2}\left(xy-6\right)$
 ${f}{≔}{\left({x}{-}{3}\right)}^{{2}}{}\left({x}{}{y}{-}{6}\right)$ (17)
 > $g≔{\left(x-3\right)}^{2}\left(y+1\right)$
 ${g}{≔}{\left({x}{-}{3}\right)}^{{2}}{}\left({y}{+}{1}\right)$ (18)
 > $\mathrm{BivariatePolynomial}\left(\left\{f,g\right\},\left\{x,y\right\},\mathrm{verifyTol}=0.010\right)$
 $\left\{{x}{=}{1.61444903148044}{-}{0.}{}{I}{,}{y}{=}{0.763898897286967}{+}{0.}{}{I}\right\}$ (19)

Correct solutions are not always returned. Doing it again may produce different output (because of the randomness)

 > $\mathrm{BivariatePolynomial}\left(\left\{f,g\right\},\left\{x,y\right\},\mathrm{verifyTol}=0.010\right)$
 $\left\{{x}{=}{2.73814436435934}{-}{0.725571745406410}{}{I}{,}{y}{=}{1.45312067994126}{+}{0.828323525015386}{}{I}\right\}{,}\left\{{x}{=}{3.29782787720106}{-}{0.409284725291712}{}{I}{,}{y}{=}{1.34803030226128}{-}{0.615234355186775}{}{I}\right\}$ (20)
 > $\mathrm{BivariatePolynomial}\left(\left\{f,g\right\},\left\{x,y\right\},\mathrm{verifyTol}=0.010\right)$
 $\left\{{x}{=}{3.56899994105181}{-}{1.61302716647830}{}{I}{,}{y}{=}{-0.430598760149443}{-}{0.0959828272717515}{}{I}\right\}$ (21)
 > $\mathrm{BivariatePolynomial}\left(\left\{f,g\right\},\left\{x,y\right\},\mathrm{verifyTol}=0.010\right)$
 $\left\{{x}{=}{2.20198934663833}{-}{0.00971969562366036}{}{I}{,}{y}{=}{-8.50553116114323}{+}{0.00889436395203620}{}{I}\right\}{,}\left\{{x}{=}{2.71283424639345}{+}{0.0000968297360482233}{}{I}{,}{y}{=}{-5.76272532238580}{-}{0.0000886076010987100}{}{I}\right\}{,}\left\{{x}{=}{4.18582785348240}{+}{0.518458807889304}{}{I}{,}{y}{=}{-0.914609115095914}{+}{1.74179987404571}{}{I}\right\}{,}\left\{{x}{=}{4.18587935513598}{-}{0.519028264653766}{}{I}{,}{y}{=}{-0.914656243572590}{-}{1.74127877174821}{}{I}\right\}$ (22)
 > $\mathrm{BivariatePolynomial}\left(\left\{f,g\right\},\left\{x,y\right\},\mathrm{verifyTol}=0.010\right)$
 $\left\{{x}{=}{1.73929994257694}{+}{0.212413901689147}{}{I}{,}{y}{=}{-0.554498533677898}{+}{1.03622687896322}{}{I}\right\}{,}\left\{{x}{=}{0.0575672432947175}{+}{0.243286301423028}{}{I}{,}{y}{=}{-1.43966697429396}{-}{0.0176580709281279}{}{I}\right\}{,}\left\{{x}{=}{0.670062363179550}{-}{0.783148116579887}{}{I}{,}{y}{=}{-0.642081391140170}{-}{1.17185083506937}{}{I}\right\}$ (23)
 > $\mathrm{Digits}≔30$
 ${\mathrm{Digits}}{≔}{30}$ (24)
 > $\mathrm{BivariatePolynomial}\left(\left\{f,g\right\},\left\{x,y\right\},\mathrm{verifyTol}=0.010\right)$

References

 Barnett, Stephen. Polynomials and Linear Control Systems. Deffer, 1983.
 Manocha, Dinesh. "Numerical methods for solving polynomial equations, in Applications of Computational Geometry." AMS proceedings of applied mathematics, Vol. 53. 1998.