Sat May 30 16:09:31 PDT 1992
REDUCE 3.4.1, 15-Jul-92 ...
1: 1:
2: 2:
3: 3:
Time: 0 ms
4: 4: % Test for the univariate and multivariate polynomial decomposition.
% Herbert Melenk, ZIB Berlin, 1990.
procedure testdecompose u;
begin scalar r,p,val,nextvar;
write "decomposition of ",u;
r := decompose u;
if length r = 1 then rederr "decomposition failed";
write " leads to ",r;
% test if the result is algebraically correct.
r := reverse r;
nextvar := lhs first r; val := rhs first r;
r := rest r;
while not(r={}) do
<< p := first r; r := rest r;
if 'equal = part(p,0) then
<<val := sub(nextvar=val,rhs p); nextvar := lhs p>>
else
val := sub(nextvar=val,p);
>>;
if val = u then write " O.K. "
else
<<write "**** reconstructed polynomial: ";
write val;
rederr "reconstruction leads to different polynomial";
>>;
end;
TESTDECOMPOSE
% univariate decompositions
testdecompose(x**4+x**2+1);
4 2
decomposition of X + X + 1
2 2
leads to {U + U + 1,U=X }
O.K.
testdecompose(x**6+9x**5+52x**4+177x**3+435x**2+630x+593);
6 5 4 3 2
decomposition of X + 9*X + 52*X + 177*X + 435*X + 630*X + 593
3 2 2
leads to {U + 25*U + 210*U + 593,U=X + 3*X}
O.K.
testdecompose(x**6+6x**4+x**3+9x**2+3x-5);
6 4 3 2
decomposition of X + 6*X + X + 9*X + 3*X - 5
2 3
leads to {U + U - 5,U=X + 3*X}
O.K.
testdecompose(x**8-88*x**7+2924*x**6-43912*x**5+263431*x**4-218900*x**3+
65690*x**2-7700*x+234);
8 7 6 5 4
decomposition of X - 88*X + 2924*X - 43912*X + 263431*X
3 2
- 218900*X + 65690*X - 7700*X + 234
2
leads to {U + 35*U + 234,
2
U=V + 10*V,
2
V=X - 22*X}
O.K.
% multivariate cases
testdecompose(u**2+v**2+2u*v+1);
2 2
decomposition of U + 2*U*V + V + 1
2
leads to {W + 1,W=U + V}
O.K.
testdecompose(x**4+2x**3*y + 3x**2*y**2 + 2x*y**3 + y**4 + 2x**2*y
+2x*y**2 + 2y**3 + 5 x**2 + 5*x*y + 6*y**2 + 5y + 9);
4 3 2 2 2 2 3
decomposition of X + 2*X *Y + 3*X *Y + 2*X *Y + 5*X + 2*X*Y
2 4 3 2
+ 2*X*Y + 5*X*Y + Y + 2*Y + 6*Y + 5*Y + 9
2 2 2
leads to {U + 5*U + 9,U=X + X*Y + Y + Y}
O.K.
testdecompose sub(u=(2 x**2 + 17 x+y + y**3),u**2+2 u + 1);
4 3 2 3 2 2 3
decomposition of 4*X + 68*X + 4*X *Y + 4*X *Y + 293*X + 34*X*Y
6 4 3 2
+ 34*X*Y + 34*X + Y + 2*Y + 2*Y + Y + 2*Y + 1
2 2 3
leads to {U + 2*U + 1,U=2*X + 17*X + Y + Y}
O.K.
testdecompose sub(u=(2 x**2 *y + 17 x+y + y**3),u**2+2 u + 1);
4 2 3 2 4 2 2 2
decomposition of 4*X *Y + 68*X *Y + 4*X *Y + 4*X *Y + 4*X *Y
2 3 6 4
+ 289*X + 34*X*Y + 34*X*Y + 34*X + Y + 2*Y
3 2
+ 2*Y + Y + 2*Y + 1
2 2 3
leads to {U + 2*U + 1,U=2*X *Y + 17*X + Y + Y}
O.K.
% some cases which require a special (internal) mapping
testdecompose ( (x + y)**2);
2 2
decomposition of X + 2*X*Y + Y
2
leads to {U ,U=X + Y}
O.K.
testdecompose ((x + y**2)**2);
2 2 4
decomposition of X + 2*X*Y + Y
2 2
leads to {U ,U=X + Y }
O.K.
testdecompose ( (x**2 + y)**2);
4 2 2
decomposition of X + 2*X *Y + Y
2 2
leads to {U ,U=X + Y}
O.K.
testdecompose ( (u + v)**2 +10 );
2 2
decomposition of U + 2*U*V + V + 10
2
leads to {W + 10,W=U + V}
O.K.
% the decomposition is not unique and might generate quite
% different images:
testdecompose ( (u + v + 10)**2 -100 );
2 2
decomposition of U + 2*U*V + 20*U + V + 20*V
leads to {W*(W + 20),W=U + V}
O.K.
% some special (difficult) cases
testdecompose (X**4 + 88*X**3*Y + 2904*X**2*Y**2 - 10*X**2
+ 42592*X*Y**3 - 440*X*Y + 234256*Y**4 - 4840*Y**2);
4 3 2 2 2 3
decomposition of X + 88*X *Y + 2904*X *Y - 10*X + 42592*X*Y
4 2
- 440*X*Y + 234256*Y - 4840*Y
2
leads to {U*(U - 10),U=V ,V=X + 22*Y}
O.K.
% a polynomial with complex coefficients
on complex;
testdecompose(X**4 + (88*I)*X**3*Y - 2904*X**2*Y**2 - 10*X**2 -
(42592*I)*X*Y**3 - (440*I)*X*Y + 234256*Y**4 + 4840*Y**2);
4 3 2 2 2 3
decomposition of X + 88*I*X *Y - 2904*X *Y - 10*X - 42592*I*X*Y
4 2
- 440*I*X*Y + 234256*Y + 4840*Y
2
leads to {U*(U + 10),U= - V ,V=X + 22*I*Y}
O.K.
off complex;
% Examples given by J. Gutierrez and J.M. Olazabal.
f1:=x**6-2x**5+x**4-3x**3+3x**2+5$
testdecompose(f1);
6 5 4 3 2
decomposition of X - 2*X + X - 3*X + 3*X + 5
2 3 2
leads to {U - 3*U + 5,U=X - X }
O.K.
f2:=x**32-1$
testdecompose(f2);
32
decomposition of X - 1
2 2 2 2 2
leads to {U - 1,U=V ,V=W ,W=A ,A=X }
O.K.
f3:=x**4-(2/3)*x**3-(26/9)*x**2+x+3$
testdecompose(f3);
4 3 2
9*X - 6*X - 26*X + 9*X + 27
decomposition of --------------------------------
9
2
U - 9*U + 27 2
leads to {---------------,U=3*X - X}
9
O.K.
f4:=sub(x=x**4-x**3-2x+1,x**3-x**2-1)$
testdecompose(f4);
12 11 10 9 8 7 6
decomposition of X - 3*X + 3*X - 7*X + 14*X - 10*X + 14*X
5 4 3 2
- 20*X + 9*X - 9*X + 8*X - 2*X - 1
3 2 4 3
leads to {U + 2*U + U - 1,U=X - X - 2*X}
O.K.
f5:=sub(x=f4,x**5-5)$
testdecompose(f5);
60 59 58 57 56
decomposition of X - 15*X + 105*X - 485*X + 1795*X
55 54 53 52
- 5873*X + 17255*X - 45845*X + 112950*X
51 50 49
- 261300*X + 567203*X - 1164475*X
48 47 46
+ 2280835*X - 4259830*X + 7604415*X
45 44 43
- 13053437*X + 21545220*X - 34200855*X
42 41 40
+ 52436150*X - 77668230*X + 111050794*X
39 38 37
- 153746645*X + 206190770*X - 267484170*X
36 35 34
+ 336413145*X - 410387890*X + 484672110*X
33 32 31
- 555048350*X + 616671710*X - 663135380*X
30 29 28
+ 690884384*X - 697721320*X + 681039235*X
27 26 25
- 642661265*X + 586604975*X - 516016275*X
24 23 22
+ 437051535*X - 356628245*X + 278991765*X
21 20 19
- 208571965*X + 149093999*X - 101204325*X
18 17 16
+ 64656350*X - 38848040*X + 21710870*X
15 14 13
- 10971599*X + 4928210*X - 1904450*X
12 11 10 9
+ 519730*X - 15845*X - 71947*X + 52015*X
8 7 6 5 4
- 26740*X + 5510*X + 3380*X - 1972*X - 75*X
3
+ 195*X - 10*X - 6
5 4 3 2
leads to {U - 5*U + 10*U - 10*U + 5*U - 6,
3 2
U=V + 2*V + V,
4 3
V=X - X - 2*X}
O.K.
clear f1,f2,f3,f4,f5;
end;
5: 5:
Time: 10591 ms plus GC time: 391 ms
6: 6:
Quitting
Sat May 30 16:09:47 PDT 1992