reduce-historical/r34/xlog/decompose.log

Sat Jun 29 13:38:31 PDT 1991
REDUCE 3.4, 15-Jul-91 ...

1: 1: 
2: 2: 
3: 3: % 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
decomposition of X  + (88*I)*X *Y - 2904*X *Y  - 10*X

                                 3                         4
                  - (42592*I)*X*Y  - (440*I)*X*Y + 234256*Y

                          2
                  + 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;

4: 4: 
Quitting
Sat Jun 29 13:38:58 PDT 1991