home *** CD-ROM | disk | FTP | other *** search
/ Math Solutions 1995 October / Math_Solutions_CD-ROM_Walnut_Creek_October_1995.iso / pc / mac / discrete / lib / polyfld.g < prev    next >
Encoding:
Text File  |  1993-05-05  |  6.2 KB  |  218 lines
  1. #############################################################################
  2. ##
  3. #A  polyfld.g                   GAP library                      Frank Celler
  4. ##
  5. #A  @(#)$Id: polyfld.g,v 3.5 1993/02/09 14:25:55 martin Rel $
  6. ##
  7. #Y  Copyright 1990-1992,  Lehrstuhl D fuer Mathematik,  RWTH Aachen,  Germany
  8. ##
  9. ##  This file contains functions for polynomials over fields.
  10. ##
  11. #H  $Log: polyfld.g,v $
  12. #H  Revision 3.5  1993/02/09  14:25:55  martin
  13. #H  made undefined globals local
  14. #H
  15. #H  Revision 3.4  1993/02/04  13:47:12  fceller
  16. #H  added '/' and 'EuclideanQuotient'
  17. #H
  18. #H  Revision 3.3  1992/11/16  12:23:18  fceller
  19. #H  added Laurent polynomials
  20. #H
  21. #H  Revision 3.2  1992/06/01  07:32:24  fceller
  22. #H  Initial GAP 3.2 release
  23. #H
  24. ##
  25.  
  26.  
  27. #############################################################################
  28. ##
  29. #F  InfoPoly1(...)  . . . . . . . . . . . infomation function for polynomials
  30. #F  InfoPoly2(...)  . . . . . . . . . . . . .  debug function for polynomials
  31. ##
  32. if not IsBound(InfoPoly1)    then InfoPoly1   := Ignore;  fi;
  33. if not IsBound(InfoPoly2)    then InfoPoly2   := Ignore;  fi;
  34.  
  35.  
  36. #############################################################################
  37. ##
  38.  
  39. #V  FieldPolynomialRingOps  . . . . . . . . . . . .  full polynomial ring ops
  40. ##
  41. FieldPolynomialRingOps := Copy( PolynomialRingOps );
  42. FieldPolynomialRingOps.name := "FieldPolynomialRingOps";
  43.  
  44.  
  45. #############################################################################
  46. ##
  47. #F  FieldPolynomialRingOps.StandardAssociate( <R>, <f> )  . . . .  normed pol
  48. ##
  49. FieldPolynomialRingOps.StandardAssociate := function( R, f )
  50.     return f * f.coefficients[ Length( f.coefficients ) ]^-1;
  51. end;
  52.  
  53.  
  54. #############################################################################
  55. ##
  56. #F  FieldPolynomialRingOps.Mod( <R>, <f>, <g> ) . . . . . . . . . . use 'mod'
  57. ##
  58. FieldPolynomialRingOps.Mod := function( R, f, g )
  59.     return f mod g;
  60. end;
  61.  
  62.  
  63. #############################################################################
  64. ##
  65. #F  FieldPolynomialRingOps.EuclideanQuotient( <R>, <f>, <g> ) . . . . <l>/<r>
  66. ##
  67. FieldPolynomialRingOps.EuclideanQuotient := function ( R, f, g )
  68.     local   m,  n,  i,  k,  c,  q,  R,  val;
  69.  
  70.     # <f> and <g> must have the same field
  71.     if f.baseRing <> g.baseRing  then
  72.         Error( "<f> and <g> must have the same base ring" );
  73.     fi;
  74.     R := f.baseRing;
  75.  
  76.     # if <f> is zero return it
  77.     if 0 = Length(f.coefficients)  then
  78.     return f;
  79.     fi;
  80.  
  81.     # check the value of the valuation of <f> and <g>
  82.     if f.valuation < g.valuation  then
  83.         return false;
  84.     fi;
  85.     val := f.valuation - g.valuation;
  86.  
  87.     # Try to divide <f> by <g>
  88.     q := [];
  89.     n := Length( g.coefficients );
  90.     m := Length( f.coefficients ) - n;
  91.     f := ShallowCopy( f.coefficients );
  92.     if IsField(R)  then
  93.         for i  in [0 .. m ]  do
  94.             c := f[m-i+n] / g.coefficients[n];
  95.             for k  in [ 1 .. n ]  do
  96.                 f[m-i+k] := f[m-i+k] - c * g.coefficients[k];
  97.             od;
  98.             q[m-i+1] := c;
  99.         od;
  100.     else
  101.         for i  in [0 .. m ]  do
  102.             c := Quotient( R, f[m-i+n], g.coefficients[n] );
  103.             if c = false  then return false;  fi;
  104.             for k  in [ 1 .. n ]  do
  105.                 f[m-i+k] := f[m-i+k] - c * g.coefficients[k];
  106.             od;
  107.             q[m-i+1] := c;
  108.         od;
  109.     fi;
  110.  
  111.     # return the polynomial
  112.     return Polynomial( R, q, val );
  113.  
  114. end;
  115.  
  116.  
  117. #############################################################################
  118. ##
  119.  
  120. #V  FieldLaurentPolynomialRingOps . . . . . . . . .  full polynomial ring ops
  121. ##
  122. FieldLaurentPolynomialRingOps := Copy( LaurentPolynomialRingOps );
  123. FieldLaurentPolynomialRingOps.name := "FieldLaurentPolynomialRingOps";
  124.  
  125.  
  126. #############################################################################
  127. ##
  128. #F  FieldLaurentPolynomialRingOps.StandardAssociate( <R>, <f> ) .  normed pol
  129. ##
  130. FieldLaurentPolynomialRingOps.StandardAssociate := function( R, f )
  131.     local   l;
  132.  
  133.     l := f.coefficients[Length(f.coefficients)];
  134.     return Polynomial( R.baseRing, f.coefficients*l^-1 );
  135. end;
  136.  
  137.  
  138. #############################################################################
  139. ##
  140. #F  FieldLaurentPolynomialRingOps.Mod( <R>, <f>, <g> )  . . . . . . use 'mod'
  141. ##
  142. FieldLaurentPolynomialRingOps.Mod := function( R, f, g )
  143.     local   F,  G,  r;
  144.  
  145.     # construct <F>, <G> such that <F>*x^i = <f> and <G>*x^j = <g>
  146.     F := Polynomial( f.baseRing, f.coefficients, 0 );
  147.     G := Polynomial( g.baseRing, g.coefficients, 0 );
  148.  
  149.     # compute <r> such that <F> = h * <G> + <r>
  150.     r := Mod( PolynomialRing(R.baseRing), F, G );
  151.  
  152.     # now (<F>*x^i) = h*x^(i-j) * (<G>*x^j) + <r>*x^i
  153.     return Polynomial( R.baseRing, r.coefficients, r.valuation+f.valuation );
  154.  
  155. end;
  156.  
  157.  
  158. #############################################################################
  159. ##
  160. #F  FieldLaurentPolynomialRingOps.EuclideanQuotient( <R>, <l>, <r> )  <l>/<r>
  161. ##
  162. FieldLaurentPolynomialRingOps.EuclideanQuotient := function ( R, f, g )
  163.     local   m,  n,  i,  k,  c,  q,  R,  val;
  164.  
  165.     # get the base ring
  166.     R := R.baseRing;
  167.  
  168.     # if <f> is zero return it
  169.     if 0 = Length(f.coefficients)  then
  170.     return f;
  171.     fi;
  172.  
  173.     # get the value of the valuation of <f> / <g>
  174.     val := f.valuation - g.valuation;
  175.  
  176.     # Try to divide <f> by <g>
  177.     q := [];
  178.     n := Length( g.coefficients );
  179.     m := Length( f.coefficients ) - n;
  180.     f := ShallowCopy( f.coefficients );
  181.     if IsField(R)  then
  182.         for i  in [0 .. m ]  do
  183.             c := f[m-i+n] / g.coefficients[n];
  184.             for k  in [ 1 .. n ]  do
  185.                 f[m-i+k] := f[m-i+k] - c * g.coefficients[k];
  186.             od;
  187.             q[m-i+1] := c;
  188.         od;
  189.     else
  190.         for i  in [0 .. m ]  do
  191.             c := Quotient( R, f[m-i+n], g.coefficients[n] );
  192.             if c = false  then return false;  fi;
  193.             for k  in [ 1 .. n ]  do
  194.                 f[m-i+k] := f[m-i+k] - c * g.coefficients[k];
  195.             od;
  196.             q[m-i+1] := c;
  197.         od;
  198.     fi;
  199.  
  200.     # return the result
  201.     return Polynomial( R, q, val );
  202.  
  203. end;
  204.  
  205.  
  206. #############################################################################
  207. ##
  208.  
  209. #E  Emacs . . . . . . . . . . . . . . . . . . . . . . . local emacs variables
  210. ##
  211. ##  Local Variables:
  212. ##  mode:               outline
  213. ##  outline-regexp:     "#F\\|#V\\|#E"
  214. ##  eval:               (local-set-key "\t" 'indent-for-tab-command)
  215. ##  eval:               (hide-body)
  216. ##  End:
  217. ##
  218.