next up previous
Next: A Bifurcation Problem. Up: Stability of Polynomials Previous: Test file for

The Problem of Specialization.

We have already met the specialization problem in the context of linear algebra and discussed the `proviso' technique for dealing with it. This problem also appears here, although harmlessly, according to the theorem below.

The difficulty is that if contains parameters, the calculation of the GCD of and may be incorrect on specialization; that is, the GCD may `almost always' be 1 but for certain values of the parameter the GCD may be nontrivial.

For example, consider . Then and the GCD of p and is 1, unless c=0 or c=2.

> p := x^4 + 2*x^3 + 3*x^2 + 4*x + c;

                              4      3      2
                        p := x  + 2 x  + 3 x  + 4 x + c

> pstar := x^4 - 2*x^3 + 3*x^2 - 4*x + c;
                                4      3      2
                      pstar := x  - 2 x  + 3 x  - 4 x + c

> gcd(p,pstar);
                                       1

> gcd(subs(c=0,p),subs(c=0,pstar));
                                       x

> gcd(subs(c=2,p),subs(c=2,pstar));
                                      2
                                     x  + 2
Note that the result returned from Maple's gcd is incorrect on specialization and this happens with no warning whatsoever. It turns out that the problem of detecting nontrivial specializations of multivariate GCD's is extremely computationally intensive when the number of parameters and variables are large. However, in the present context it is not so bad. Indeed, the following theorem shows that we already have all the information in the Stieltjes continued fraction to detect all the special cases.

Theorem Theorem: Let p be a polynomial with complex coefficients, containing a complex-valued parameter. The GCD of p and its paraconjugate calculated as a multivariate polynomial GCD will be correct on specialization if each in the Stieltjes continued fraction for . Thus investigation of the poles and zeros of the , considered as functions of the parameter, will uncover all the special cases of the GCD.

Thus the routine Hurwitz automatically gives its own proviso for correctness of the results.

Proof. If then d | p and (the symbol is read as `divides'). Hence and . Likewise, if , then D | p and . Hence D = d.

The Stieltjes continued fraction is computed with the Euclidean algorithm for the computation of the GCD of and . The reported partial quotients can be wrong only if division by zero occurs, which will happen if one of the remainders is zero on specialization. This will give rise to a pole in the partial quotient at the special value of the parameter, followed by a zero in the next partial quotient, and a pole in the one following, and so on.

Remark. If one of the partial quotients has a pole or zero, the computed GCD may or may not be wrong. This proviso is a provision for correctness, and hence is a necessary condition.

The following example should make this theorem more clear.

> p := lambda^3 + 6*lambda^2 + 10*lambda + 4 - a - I*b;

                          3           2
               p := lambda  + 6 lambda  + 10 lambda + 4 - a - I b

> with(share):
> readlib(Hurwitz):
> Hurwitz(p,lambda);
                                      FAIL

> Stieltjes_continued_fraction_and_GCD := `Hurwitz/data`(p,lambda);
        Stieltjes_continued_fraction_and_GCD := [

                                I b         lambda
            [1/6 lambda, 216 --------- + 36 ------,
                                     2      56 + a
                             (56 + a)

                                       2
                             I (56 + a)  b
                ---------------------------------------
                                        2    3        2
                - 12544 + 2688 a + 108 a  + a  + 216 b

                                               3
                                       (56 + a)  lambda
                     - 1/6 ---------------------------------------], 1]
                                                   2    3        2
                           - 12544 + 2688 a + 108 a  + a  + 216 b
Note the GCD is computed as GCD = 1. This is almost always correct. We examine special values of the parameters a and b. First set a = -56.
> subs(a=-56,p);
                         3           2
                   lambda  + 6 lambda  + 10 lambda + 60 - I b

> SCF := `Hurwitz/data`(",lambda);
                                        /               2\
                                        | 60      lambda |
                 SCF := [[1/6 lambda, I |---- + 6 -------|], 1]
                                        \  b         b   /
We see the GCD is still trivial there.
> subs(a=-56,b=0,p);
                            3           2
                      lambda  + 6 lambda  + 10 lambda + 60

> SCF := `Hurwitz/data`(",lambda);
                                             2
                           SCF := [[], lambda  + 10]
Now we see that the GCD is nontrivial. Thus the vanishing or blowing-up of the coefficients is a necessary but not sufficient condition.
> Stieltjes_continued_fraction_and_GCD[1][3];
                                      2
                            I (56 + a)  b
               ---------------------------------------
                                       2    3        2
               - 12544 + 2688 a + 108 a  + a  + 216 b

                                              3
                                      (56 + a)  lambda
                    - 1/6 ---------------------------------------
                                                  2    3        2
                          - 12544 + 2688 a + 108 a  + a  + 216 b

> denom(");
                                           2      3         2
                  - 75264 + 16128 a + 648 a  + 6 a  + 1296 b

> readlib(isolate)(",b^2);
                     2   1568                  2          3
                    b  = ---- - 112/9 a - 1/2 a  - 1/216 a
                          27

> map(factor,");
                          2                           2
                         b  = - 1/216 (a - 4) (56 + a)
So if the above equation holds, we MIGHT have a nontrivial GCD. Remembering the source of this problem, we can find a nice parametric solution of the above equation as follows.
> subs(lambda=I*t,p);

                           3      2
                      - I t  - 6 t  + 10 I t + 4 - a - I b

> evalc(Re("));

                                      2
                                 - 6 t  + 4 - a

> A := solve(",a);

                                          2
                                A := - 6 t  + 4

> """;

                           3      2
                      - I t  - 6 t  + 10 I t + 4 - a - I b

> evalc(Im("));

                                   3
                                - t  + 10 t - b

> B := solve(",b);

                                        3
                                B := - t  + 10 t

> subs(a=A,b=B,p);

                  3           2                  2         3
            lambda  + 6 lambda  + 10 lambda + 6 t  - I (- t  + 10 t)

> New := `Hurwitz/data`(",lambda);

                                                  2
                    New := [[], lambda - RootOf(_Z  + 1) t]
And we see a nontrivial GCD for any value of t.

For a completely different approach to the same problem, see [].



next up previous
Next: A Bifurcation Problem. Up: Stability of Polynomials Previous: Test file for



Robert Corless
Wed Feb 28 18:25:56 EST 1996