decompos.log 9.4 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390391392393394395396397398399400401402403404405406407408
  1. Sat Jun 29 13:38:31 PDT 1991
  2. REDUCE 3.4, 15-Jul-91 ...
  3. 1: 1:
  4. 2: 2:
  5. 3: 3: % Test for the univariate and multivariate polynomial decomposition.
  6. % Herbert Melenk, ZIB Berlin, 1990.
  7. procedure testdecompose u;
  8. begin scalar r,p,val,nextvar;
  9. write "decomposition of ",u;
  10. r := decompose u;
  11. if length r = 1 then rederr "decomposition failed";
  12. write " leads to ",r;
  13. % test if the result is algebraically correct.
  14. r := reverse r;
  15. nextvar := lhs first r; val := rhs first r;
  16. r := rest r;
  17. while not(r={}) do
  18. << p := first r; r := rest r;
  19. if 'equal = part(p,0) then
  20. <<val := sub(nextvar=val,rhs p); nextvar := lhs p>>
  21. else
  22. val := sub(nextvar=val,p);
  23. >>;
  24. if val = u then write " O.K. "
  25. else
  26. <<write "**** reconstructed polynomial: ";
  27. write val;
  28. rederr "reconstruction leads to different polynomial";
  29. >>;
  30. end;
  31. TESTDECOMPOSE
  32. % univariate decompositions
  33. testdecompose(x**4+x**2+1);
  34. 4 2
  35. decomposition of X + X + 1
  36. 2 2
  37. leads to {U + U + 1,U=X }
  38. O.K.
  39. testdecompose(x**6+9x**5+52x**4+177x**3+435x**2+630x+593);
  40. 6 5 4 3 2
  41. decomposition of X + 9*X + 52*X + 177*X + 435*X + 630*X + 593
  42. 3 2 2
  43. leads to {U + 25*U + 210*U + 593,U=X + 3*X}
  44. O.K.
  45. testdecompose(x**6+6x**4+x**3+9x**2+3x-5);
  46. 6 4 3 2
  47. decomposition of X + 6*X + X + 9*X + 3*X - 5
  48. 2 3
  49. leads to {U + U - 5,U=X + 3*X}
  50. O.K.
  51. testdecompose(x**8-88*x**7+2924*x**6-43912*x**5+263431*x**4-218900*x**3+
  52. 65690*x**2-7700*x+234);
  53. 8 7 6 5 4
  54. decomposition of X - 88*X + 2924*X - 43912*X + 263431*X
  55. 3 2
  56. - 218900*X + 65690*X - 7700*X + 234
  57. 2
  58. leads to {U + 35*U + 234,
  59. 2
  60. U=V + 10*V,
  61. 2
  62. V=X - 22*X}
  63. O.K.
  64. % multivariate cases
  65. testdecompose(u**2+v**2+2u*v+1);
  66. 2 2
  67. decomposition of U + 2*U*V + V + 1
  68. 2
  69. leads to {W + 1,W=U + V}
  70. O.K.
  71. testdecompose(x**4+2x**3*y + 3x**2*y**2 + 2x*y**3 + y**4 + 2x**2*y
  72. +2x*y**2 + 2y**3 + 5 x**2 + 5*x*y + 6*y**2 + 5y + 9);
  73. 4 3 2 2 2 2 3
  74. decomposition of X + 2*X *Y + 3*X *Y + 2*X *Y + 5*X + 2*X*Y
  75. 2 4 3 2
  76. + 2*X*Y + 5*X*Y + Y + 2*Y + 6*Y + 5*Y + 9
  77. 2 2 2
  78. leads to {U + 5*U + 9,U=X + X*Y + Y + Y}
  79. O.K.
  80. testdecompose sub(u=(2 x**2 + 17 x+y + y**3),u**2+2 u + 1);
  81. 4 3 2 3 2 2 3
  82. decomposition of 4*X + 68*X + 4*X *Y + 4*X *Y + 293*X + 34*X*Y
  83. 6 4 3 2
  84. + 34*X*Y + 34*X + Y + 2*Y + 2*Y + Y + 2*Y + 1
  85. 2 2 3
  86. leads to {U + 2*U + 1,U=2*X + 17*X + Y + Y}
  87. O.K.
  88. testdecompose sub(u=(2 x**2 *y + 17 x+y + y**3),u**2+2 u + 1);
  89. 4 2 3 2 4 2 2 2
  90. decomposition of 4*X *Y + 68*X *Y + 4*X *Y + 4*X *Y + 4*X *Y
  91. 2 3 6 4
  92. + 289*X + 34*X*Y + 34*X*Y + 34*X + Y + 2*Y
  93. 3 2
  94. + 2*Y + Y + 2*Y + 1
  95. 2 2 3
  96. leads to {U + 2*U + 1,U=2*X *Y + 17*X + Y + Y}
  97. O.K.
  98. % some cases which require a special (internal) mapping
  99. testdecompose ( (x + y)**2);
  100. 2 2
  101. decomposition of X + 2*X*Y + Y
  102. 2
  103. leads to {U ,U=X + Y}
  104. O.K.
  105. testdecompose ((x + y**2)**2);
  106. 2 2 4
  107. decomposition of X + 2*X*Y + Y
  108. 2 2
  109. leads to {U ,U=X + Y }
  110. O.K.
  111. testdecompose ( (x**2 + y)**2);
  112. 4 2 2
  113. decomposition of X + 2*X *Y + Y
  114. 2 2
  115. leads to {U ,U=X + Y}
  116. O.K.
  117. testdecompose ( (u + v)**2 +10 );
  118. 2 2
  119. decomposition of U + 2*U*V + V + 10
  120. 2
  121. leads to {W + 10,W=U + V}
  122. O.K.
  123. % the decomposition is not unique and might generate quite
  124. % different images:
  125. testdecompose ( (u + v + 10)**2 -100 );
  126. 2 2
  127. decomposition of U + 2*U*V + 20*U + V + 20*V
  128. leads to {W*(W + 20),W=U + V}
  129. O.K.
  130. % some special (difficult) cases
  131. testdecompose (X**4 + 88*X**3*Y + 2904*X**2*Y**2 - 10*X**2
  132. + 42592*X*Y**3 - 440*X*Y + 234256*Y**4 - 4840*Y**2);
  133. 4 3 2 2 2 3
  134. decomposition of X + 88*X *Y + 2904*X *Y - 10*X + 42592*X*Y
  135. 4 2
  136. - 440*X*Y + 234256*Y - 4840*Y
  137. 2
  138. leads to {U*(U - 10),U=V ,V=X + 22*Y}
  139. O.K.
  140. % a polynomial with complex coefficients
  141. on complex;
  142. testdecompose(X**4 + (88*I)*X**3*Y - 2904*X**2*Y**2 - 10*X**2 -
  143. (42592*I)*X*Y**3 - (440*I)*X*Y + 234256*Y**4 + 4840*Y**2);
  144. 4 3 2 2 2
  145. decomposition of X + (88*I)*X *Y - 2904*X *Y - 10*X
  146. 3 4
  147. - (42592*I)*X*Y - (440*I)*X*Y + 234256*Y
  148. 2
  149. + 4840*Y
  150. 2
  151. leads to {U*(U - 10),U=V ,V=X + (22*I)*Y}
  152. O.K.
  153. off complex;
  154. % Examples given by J. Gutierrez and J.M. Olazabal.
  155. f1:=x**6-2x**5+x**4-3x**3+3x**2+5$
  156. testdecompose(f1);
  157. 6 5 4 3 2
  158. decomposition of X - 2*X + X - 3*X + 3*X + 5
  159. 2 3 2
  160. leads to {U - 3*U + 5,U=X - X }
  161. O.K.
  162. f2:=x**32-1$
  163. testdecompose(f2);
  164. 32
  165. decomposition of X - 1
  166. 2 2 2 2 2
  167. leads to {U - 1,U=V ,V=W ,W=A ,A=X }
  168. O.K.
  169. f3:=x**4-(2/3)*x**3-(26/9)*x**2+x+3$
  170. testdecompose(f3);
  171. 4 3 2
  172. 9*X - 6*X - 26*X + 9*X + 27
  173. decomposition of --------------------------------
  174. 9
  175. 2
  176. U - 9*U + 27 2
  177. leads to {---------------,U=3*X - X}
  178. 9
  179. O.K.
  180. f4:=sub(x=x**4-x**3-2x+1,x**3-x**2-1)$
  181. testdecompose(f4);
  182. 12 11 10 9 8 7 6
  183. decomposition of X - 3*X + 3*X - 7*X + 14*X - 10*X + 14*X
  184. 5 4 3 2
  185. - 20*X + 9*X - 9*X + 8*X - 2*X - 1
  186. 3 2 4 3
  187. leads to {U + 2*U + U - 1,U=X - X - 2*X}
  188. O.K.
  189. f5:=sub(x=f4,x**5-5)$
  190. testdecompose(f5);
  191. 60 59 58 57 56
  192. decomposition of X - 15*X + 105*X - 485*X + 1795*X
  193. 55 54 53 52
  194. - 5873*X + 17255*X - 45845*X + 112950*X
  195. 51 50 49
  196. - 261300*X + 567203*X - 1164475*X
  197. 48 47 46
  198. + 2280835*X - 4259830*X + 7604415*X
  199. 45 44 43
  200. - 13053437*X + 21545220*X - 34200855*X
  201. 42 41 40
  202. + 52436150*X - 77668230*X + 111050794*X
  203. 39 38 37
  204. - 153746645*X + 206190770*X - 267484170*X
  205. 36 35 34
  206. + 336413145*X - 410387890*X + 484672110*X
  207. 33 32 31
  208. - 555048350*X + 616671710*X - 663135380*X
  209. 30 29 28
  210. + 690884384*X - 697721320*X + 681039235*X
  211. 27 26 25
  212. - 642661265*X + 586604975*X - 516016275*X
  213. 24 23 22
  214. + 437051535*X - 356628245*X + 278991765*X
  215. 21 20 19
  216. - 208571965*X + 149093999*X - 101204325*X
  217. 18 17 16
  218. + 64656350*X - 38848040*X + 21710870*X
  219. 15 14 13
  220. - 10971599*X + 4928210*X - 1904450*X
  221. 12 11 10 9
  222. + 519730*X - 15845*X - 71947*X + 52015*X
  223. 8 7 6 5 4
  224. - 26740*X + 5510*X + 3380*X - 1972*X - 75*X
  225. 3
  226. + 195*X - 10*X - 6
  227. 5 4 3 2
  228. leads to {U - 5*U + 10*U - 10*U + 5*U - 6,
  229. 3 2
  230. U=V + 2*V + V,
  231. 4 3
  232. V=X - X - 2*X}
  233. O.K.
  234. clear f1,f2,f3,f4,f5;
  235. end;
  236. 4: 4:
  237. Quitting
  238. Sat Jun 29 13:38:58 PDT 1991