Codemist Standard Lisp 3.54 for DEC Alpha: May 23 1994
Dump file created: Mon May 23 10:39:11 1994
REDUCE 3.5, 15-Oct-93 ...
Memory allocation: 6023424 bytes
+++ About to read file ndotest.red
% 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;
(TIME: decompos 28516 29333)
End of Lisp run after 28.53+1.46 seconds