数理解析研究所講究録986 巻 1997 年 147-152

147

Implementing
Algorithm andIts Application$\mathrm{s}\mathrm{t}\mathrm{u}\mathrm{r}\mathrm{m}\mathrm{s}9$(Qifan Lu)
愛媛大学工野田松太郎 (Matu-Tarow Noda)
愛媛大学工呂其凡

Abstract. Sturm’s theorem is useful to count and to isolate real roots for polynomials. In this paper we show, by introducing a method of integral power of two, how
to implement this algorithm more efficiently. We also give some results of isolation. The experiment shows that the newand computation time by Maple andmethod is more efficient for polynomials with more real roots. Finally, two application of the algorithm are given. One is to solve ill-condition polynomial system, theother is to plot implicit curves.
$\mathrm{R}\mathrm{i}\mathrm{s}\mathrm{a}/\mathrm{A}\mathrm{s}\mathrm{i}\mathrm{r}$1. Introduction
1.1. Isolation of Roots
Let A be a polynomial over Q. The isolation of real roots is to compute a sequence ofdisjoint intervals with rational endpoints, each containing exactly one real zero of A andtogether containing all real zeros of A.

1.2. Sturm Sequence
For a univariate polynomial $P(x)$ with integer coefficients, the Sturm sequence is asequence $p_{0}(x),p_{1}(x),$ $\ldots,pr(x)$ .
$p_{0}(X)=P(X)$$p_{1}(x)=P/(x)$$p_{i}(x)=$-remain der $(p_{i2}-(x),pi-1(x))$

The coefficients of Sturm sequence can be simplified by the method of sub-resultants.

1.3. Sturm’s Theorem
For rational numbers a, such that $a<b$ and a, are not roots of $P(x)$ , we define$v(P, a)$ and $v(P, b)$ as the number of sign changes in the Sturm sequence respectively:$\mathrm{b}$$\mathrm{b}$$(p_{0}(a),p_{1}(a),$ $\ldots,p_{r}(a))$$(p_{0}(b),p_{1}(b),$ $\ldots,p_{r}(b))$

148
Sturm’s theorem shows that the number of real roots of $P(x)$ in intervals $(a, b)$ is equal to$v(P, a)-v(P, b)$ .

Sturm’s theorem gives a basis of root isolation. Based on this theorem, an algorithm ofreal root isolation for univariate polynomials is given.

2. To Implement Real Roots Isolation Algorithm Efficiently
2.1. Question Proposed
In practical programming, there appears some problems:$\bullet$$\bullet$

For polynomials with high degree and with much real roots, the representation ofisolated intervals becomes very complicated.
The isolation costs much more in time.

Example$1:\mathrm{I}\mathrm{s}\mathrm{o}\mathrm{l}\mathrm{a}\mathrm{t}\mathrm{i}\mathrm{n}\mathrm{g}$the real roots of polynomial $P1(x)$ and $P2(x)$ respectively.

$P1(x)= \prod_{=i1}^{20}(x+i)$$P2(x)= \prod_{i=1}^{20}(X+i)+2^{(-23)}X^{19}$

Using the Sturm’s algorithm, we get the isolated results respectively as follows. Each result
are included by a set of intervals. Each interval includes one and only one real root in it.

$\{(\frac{-735}{64},$$\frac{-1365}{128}),$ $( \frac{-1365}{128},$ $\frac{-315}{32}),$$( \frac{-2205}{128},$$\frac{-525}{32}),$$( \frac{-105}{32},$$\frac{-315}{128}),$$( \frac{-105}{4},$ $\frac{-315}{16}),$$( \frac{-315}{128},$$\frac{-105}{64}),$$( \frac{-105}{16},$ $\frac{-735}{128}),$$( \frac{-1575}{128},$$( \frac{-945}{128},$$( \frac{-315}{32},$ $\frac{-525}{64}),$$\frac{-105}{16}),$$( \frac{-105}{64},0),$$( \frac{-525}{32},$$( \frac{-1155}{64},$$\frac{-1995}{128}),$$\frac{-945}{64})$$\frac{-315}{64})$,$\frac{-105}{32}),$$( \frac{-525}{64},$$\frac{-945}{128})$,$\frac{-1155}{64}),$$( \frac{-945}{64},$$\frac{-105}{8})\}$$( \frac{-315}{64},$$( \frac{-315}{16},$$( \frac{-1995}{128},$,$( \frac{-735}{128},$$( \frac{-105}{8},$ $\frac{-1575}{128}),$$\frac{-735}{64}),$$\frac{-2205}{128})$$\{(\frac{-12331253767}{2147483648},$ $\frac{-5284823043}{1073741824}),$ $( \frac{-1761607681}{268435456},$ $\frac{-12331253767}{2147483648})$$( \frac{-15854469129}{2147483648},$ $\frac{-1761607681}{268435456}),$$( \frac{-5284823043}{536870912},$ $\frac{-8808038405}{1073741824}),$$( \frac{-5284823043}{2147483648},$$( \frac{-8808038405}{1073741824},$ $\frac{-15854469129}{2147483648})$$( \frac{-1761607681}{1073741824},0)$,$\frac{-1761607681}{1073741824}),$ $( \frac{-1761607681}{536870912},$ $\frac{-5284823043}{2147483648})$

,,,,

149

$( \frac{-1761607681}{67108864},$ $\frac{-1761607681}{134217728}),$$( \frac{-5284823043}{1073741824},$$\frac{-1761607681}{536870912})\}$So we show a new method to implement Sturm’s algorithm.
, a square-free integral polynomial of positive degree.
Bound. $Larrow(-b, b)$ where $b=2^{n} \geq\max|\alpha_{i}|$ for all zerosof A.
as a Sturm sequence of A by sub-resultantSturm
method.
Test.for every interval $(a, b]$ in do bisect it into $(a, m]$ and $(m, b]$ ,if is a real root of ,$\mathrm{I}\mathrm{n}\mathrm{p}\mathrm{u}\mathrm{t}:\mathrm{A}$$\alpha_{i}$$\mathrm{s}\mathrm{e}\mathrm{q}\mathrm{u}\mathrm{e}\mathrm{n}\mathrm{c}\mathrm{e}:\mathrm{c}_{0}\mathrm{m}\mathrm{p}\mathrm{u}\mathrm{t}\mathrm{e}(A, A’, A_{3}, \cdot\vee\cdot, A)r$$\mathrm{L}$$\mathrm{A}$$\mathrm{m}$$\bullet$

output $[m, m]$ . For each subinterval $(a, m),$the number of real zeros
using Sturm’s theorem. (For the case of $(a, m)$ , the $r=R-1,$ is the number of realzero in $(a, m].)$-if $r=0$ , drop the interval.
-if $r=1$ , output the interval.
-if $r>1$ , keep the interval in L.
$(m, b]_{\mathrm{C}},\mathrm{o}\mathrm{m}_{\mathrm{P}}\mathrm{u}\mathrm{t}\mathrm{e}$$\mathrm{r}$$\mathrm{R}$else
for each subinterval $(a, m],(m, b]$ compute the number-if $r=0$ , drop the interval.
-if $r=1$ , output the interval.
-if $r>1$ keep the interval in L.

$\bullet$$\mathrm{r}$of real zeros.

list of isolating intervals with rational endpoints for all real zeros of A.
Compared with the way mentioned in [1], here we make the following modification:$\mathrm{O}\mathrm{u}\mathrm{t}\mathrm{p}\mathrm{u}\mathrm{t}:\mathrm{A}$$\bullet$$\bullet$$\bullet$The univariate polynomial is made square-free at first.
When calculating the boundary of maximal root, we select it as an integral power of2.
is square-free polynomial, output isUsing the shape-changed Sturm’s theorem(half-open, half close intervals), we omit to calculate the minimal distance between
roots any more.
$\mathrm{I}\mathrm{n}\mathrm{p}\mathrm{u}\mathrm{t}$3. Experimental Results$P1(x)=i= \prod^{0}(X+i)21$$P2(x)= \prod_{i=1}^{20}(x+i)+2^{(-23)}X^{19}$$P3(x)= \prod_{i=1}^{25}(X-i)$

150$P4(x)=3x^{6}-5_{X^{4}}+3x^{3}-7x^{2}+2$$P5(x)= \prod_{i=1}^{0}(110X+i)$

We implement our algorithm in the Maple andThe roots of $P1(x)$ is :$\mathrm{R}\mathrm{i}\mathrm{s}\mathrm{a}/\mathrm{A}\mathrm{s}\mathrm{i}\mathrm{r}$, and get the following results.

$\{[-20, -20],$ $[-18, -18],$ $(-18, -16),$ $[-4, -4],$ $(-20, -18),$ $[-6, -6]$ ,$(-8, -6),$ $(-6, -4),$ $[-2, -2],$ $(-4, -2),$ $(-2,0),$ $[-12, -12]$ ,$[-10, -10],$ $[-16, -16],$ $(-10, -8),$ $[-14, -14],$$\langle-12,$$-10),$ $[-8, -8]$ ,$(-14, -12),$ $(-16, -14)\}$

The roots of $P2(x)$ is :$\{(-7,$ $\frac{-13}{2}),$ $( \frac{-13}{2},$ $-6),$ $(-3,$ $\frac{-5}{2}).’(\frac{-5}{2},$ $-2),$ $(-9,$ $\frac{-17}{2}),$ $(-5,$$( \frac{-17}{2},$$-8),$ $(-2,0),$$( \frac{-9}{2},$$\frac{-9}{2})$,$-4),$ $(-32, -16)\}$Time consumed in isolating polynomials above in Maple V.

Time consumed in isolating polynomials above in$\mathrm{R}\mathrm{i}\mathrm{s}\mathrm{a}/\mathrm{A}\mathrm{s}\mathrm{i}\mathrm{r}$.

4. Some Remarks$\bullet$$\bullet$$\bullet$Using new method to isolate roots, we can simplify the results of isolation and avoid
the computation of minimal distance between roots. At the same time, the time canbe saved.
Our method is much efficient when isolating polynomials with more real roots.
In some special cases, for example, root is integer, the root can be obtained exactly infinite steps.

151
5. Appl.i.cations
5.1. Solving Polynomials

Sturm’s Algorithm can be used to solve ill-conditioned multivariate polynomial systems.
Using the numerical methods, usually we couldn’t get all of the roots of system correctly.
Some roots are lost or not correct. But we can always get all of its real roots correctly
using Sturm’s algorithm because there are no any approximate computation in it.
$F_{n}=0$ , we can derive a univariate
For multivariate polynomial system $F_{1}=0,$ $F_{2}=0,$polynomial $G(x)$ by calculating the Gr\"obner basis of the ideal. Then the rootsof $G(x)=0$ can be solved as accurate as we hope using Sturm’s algorithm. Then roots of$G(x)=0$ can substituted back into the other elements of the Gr\"obner basis and the realroots can be determined.
Example2$\cdots,$$(F_{1}, \cdots , F_{n})$$F1=(x^{2}+y^{2}-1)(xy-0.25)+0.0001_{Xy}$$\{$$F2=(x^{2}+y^{2}-1)(x-y)-\mathrm{o}.00001(X+1)$

We derive a univariate polynomial $G(y)$ from the ideal (FI,F2):$G(y)$$=$$22100\mathrm{o}\mathrm{o}\mathrm{o}\mathrm{o}000y-8200000000\mathrm{o}\mathrm{o}y^{7}-391237900000y6+30002210\mathrm{o}\mathrm{o}0y^{5}$$+1990505025\mathrm{o}\mathrm{o}y^{4}-11251424879y-287658500030y2+1249993750y$

The following is the real roots $(x, y)$ we got.it is a approximate representation of set$(x, y)$ .
(0.9990732,0.0432840), (-0.0262280,0.9996512),$(- 1.000000, 0.0),(-0.0227383, - 0.9997464)$ ,$(0.6645091, 0.7471453),(-0.7141434, - 0.6998564)$ ,(0.5000350, 0.5000650), $(-0.5000550, - 0.5000450)$

5.2. Plotting Implicit Curves
The Sturm’s algorithm can also be used to plot implicit curves. The basic idea
the area to plot is covered by a circle.

$\mathrm{i}\mathrm{s}:\mathrm{S}\mathrm{u}\mathrm{p}\mathrm{p}\mathrm{o}\mathrm{S}\mathrm{e}$$f(x, y)=0$$\{$$(x-a)^{(2n)}+(y-b)(2n)=r^{(2n)}$

If the curve $f(x, y)$ have common roots with this circle, it means the curves pass throughthis area. Then the area can be divided into four small areas. In each small areas, we candecide if the curves pass through it or not. If the curve does not pass through, the small
areas can be discard. This procedure can be done many times until the small area is as
small as we hope. See Fig.1. And we can see an example in Fig.2.

152

1

1
1

1

1

1
1
1
1$- \mathrm{a}_{---}---$\llcorner -1---$—-\iota\iota_{-}------$

1
1
1
1

1
$1_{-,\ulcorner 1}$

1
1
1$1$

1
1Figl. .

Fig2. $x^{5}-2x^{2}y+y^{5}$

Future Development:$\bullet$$\bullet$

How to use this algorithm in robotics problems. Because many problems in robotics
is related to whether there are some real roots or in a system.
How to use this algorithm to CAD. Basically, the CAD is isolate real roots in multivariate case.

参考文献[1] Davenport, J.H., Siret,Y., Tournier,E.: Computer Algebra. (Systems and algebraic Computation). ed. Academic Press 1988, pp. 105-111.
$\mathrm{l}\mathrm{t}\mathrm{h}$[2] Collins,G.E., Loos,R.: Real Zeros of Polynomials. Computer Algebra Symbolic and Algebraic
Computationed. Springer-Verlag, Wien,New York, 1983, pp. 83-94.
$2\mathrm{t}\mathrm{h}$[3] Loos,R. Generalized Polynomial Remainder Sequences. Computer Algebra Symbolic andAlgebraic Computationed. Springer-Verlag, Wien, New York, 1983, pp. 115-137.
$2\mathrm{t}\mathrm{h}$[4] Akritas,
pp. 341-349.

$\mathrm{A}.\mathrm{G}.:\mathrm{E}\mathrm{l}\mathrm{e}\mathrm{m}\mathrm{e}\mathrm{n}\mathrm{t}\mathrm{S}$of Computer Algebra with Applications. John Wiley&Sons. 1989,[5] Knuth,: The Art of Computer Programming, Chapter 4, Vo1.2,Algorithms). Reading, Mass.: Addison-Wesley 1981.
$\mathrm{D}.\mathrm{E}.$[6] Maple V manuals. Springer-Verlag. 1992.

$2\mathrm{t}\mathrm{h}$ed. (Semi-numerical