home *** CD-ROM | disk | FTP | other *** search
/ Math Solutions 1995 October / Math_Solutions_CD-ROM_Walnut_Creek_October_1995.iso / pc / mac / discrete / lib / rowspace.g < prev    next >
Encoding:
Text File  |  1993-05-05  |  26.1 KB  |  867 lines
  1. #############################################################################
  2. ##
  3. #A  rowspace.g                  GAP library                    J\"urgen Mnich
  4. ##
  5. #A  @(#)$Id: rowspace.g,v 3.9 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 all functions for row spaces.
  10. ##
  11. ##  $Log: rowspace.g,v $
  12. #H  Revision 3.9  1993/02/09  14:25:55  martin
  13. #H  made undefined globals local
  14. #H
  15. #H  Revision 3.8  1992/12/16  19:47:27  martin
  16. #H  replaced quoted record names with escaped ones
  17. #H
  18. #H  Revision 3.7  1992/04/07  16:15:32  jmnich
  19. #H  adapted to changes in the finite field module
  20. #H
  21. #H  Revision 3.6  1992/04/03  13:10:09  fceller
  22. #H  changed 'Shifted...' into 'Sifted...'
  23. #H
  24. #H  Revision 3.5  1992/03/17  12:31:20  jmnich
  25. #H  minor style changes, more bug fixes
  26. #H
  27. #H  Revision 3.4  1992/02/29  13:25:11  jmnich
  28. #H  general library review, some bug fixes
  29. #H
  30. #H  Revision 3.3  1992/01/09  13:37:06  jmnich
  31. #H  fixed a minor bug in 'BaseTypeRowSpace'
  32. #H
  33. #H  Revision 3.2  1992/01/07  12:21:07  jmnich
  34. #H  changed a lot
  35. #H
  36. #H  Revision 3.1  1991/09/24  14:24:59  fceller
  37. #H  Initial Release under RCS
  38. #H
  39. ##
  40.  
  41.  
  42. #############################################################################
  43. ##
  44. #F  InfoVectorSpace1(...) . . . . . . . . . . . . . . . . package information
  45. #F  InfoVectorSpace2(...) . . . . . . . . . . . . . package debug information
  46. ##
  47. if not IsBound( InfoVectorSpace1 )  then  InfoVectorSpace1 := Ignore;  fi;
  48. if not IsBound( InfoVectorSpace2 )  then  InfoVectorSpace2 := Ignore;  fi;
  49.  
  50.  
  51. #############################################################################
  52. ##
  53. #F  IntegerTable( <field> ) . . . . . . . . . . . . . calculate integer table
  54. ##
  55. IntegerTable := function( field )
  56.     local   pow, int, i;
  57.  
  58.     if IsBound( field.integers ) then  return field.integers;  fi;
  59.     if not IsFinite( field ) then
  60.         Error( "sorry, field has to be finite\n" );
  61.     fi;
  62.     if field.degree <> 1 then
  63.         Error( "sorry, field has to be a prime field\n" );
  64.     fi;
  65.  
  66.     pow := 1;
  67.     int := Int( field.root );
  68.     field.integers := [1..field.char-1];
  69.     field.integers[1] := pow;
  70.     for i in [2..field.char-1] do
  71.         pow := (pow * int) mod field.char;
  72.         field.integers[i] := pow;
  73.     od;
  74.     return field.integers;
  75. end;
  76.  
  77.  
  78. #############################################################################
  79. ##
  80. #F  RowSpace( <gens>, <field>[, <zero>] ) . . . . . . . .  create a row space
  81. ##
  82. RowSpace := function( arg )
  83.     local   gens, v, zero, i;
  84.  
  85.     if Length( arg ) < 2 or Length( arg ) > 3
  86.         or (not IsList( arg[1] ) and not IsInt( arg[1] ))
  87.         or not IsField( arg[2] ) then
  88.             Error(  "usage: RowSpace( <generators>, <field>[, <zero>] )\n",
  89.                     "   or: RowSpace(  <dimension>, <field>[, <zero>] )" );
  90.     fi;
  91.  
  92.     # process the arguments, extracting the zero element
  93.  
  94.     if IsInt( arg[1] ) then
  95.         if arg[1] < 1 then
  96.             Error( "sorry, dimension must be a positive integer" );
  97.         fi;
  98.         gens := [ [] ];
  99.         for i in [1..arg[1]] do  gens[1][i] := arg[2].zero;          od;
  100.         for i in [2..arg[1]] do  gens[i] := ShallowCopy( gens[1] );  od;
  101.         for i in [1..arg[1]] do  gens[i][i] := arg[2].one;           od;
  102.         ForAll( gens, IsVector );
  103.  
  104.         if Length( arg ) = 3 then   zero := arg[3];
  105.         else                        zero := 0 * gens[1];
  106.         fi;
  107.     else
  108.         if Length( arg ) = 3 then   zero := arg[3];
  109.         elif arg[1] <> [] then      zero := 0 * arg[1][1];
  110.         else
  111.             Error( "sorry, need at least one element" );
  112.         fi;
  113.         gens := [];
  114.         for v in arg[1] do
  115.             if v <> zero then  Add( gens, v );  fi;
  116.         od;
  117.     fi;
  118.  
  119.     # create the row space record
  120.  
  121.     return rec(
  122.         generators    := gens,
  123.         field         := arg[2],
  124.         zero          := zero,
  125.         isDomain      := true,
  126.         isVectorSpace := true,
  127.         isRowSpace    := true,
  128.         isFinite      := IsFinite( arg[2] ) or gens = [],
  129.         operations    := RowSpaceOps
  130.     );
  131. end;
  132.  
  133.  
  134. #############################################################################
  135. ##
  136. #F  IsRowSpace( <obj> ) . . . . . . . . . .  test if an object is a row space
  137. ##
  138. IsRowSpace := function( obj )
  139.     return  IsRec( obj )
  140.         and IsBound( obj.isRowSpace ) and obj.isRowSpace;
  141. end;
  142.  
  143.  
  144. #############################################################################
  145. ##
  146. #V  RowSpaceOps . . . . . . . . . . . . . .  operations record for row spaces
  147. ##
  148. RowSpaceOps := ShallowCopy( VectorSpaceOps );
  149.  
  150.  
  151. #############################################################################
  152. ##
  153. #F  RowSpaceOps.\=( <V>, <W> ) . . . . . .  test if two row spaces are equal
  154. ##
  155. ##  Two  row spaces are  considered  equal  if they are written over the same
  156. ##  field  and  the canonical bases (i.e.  those that are computed via a full
  157. ##  gauss  algorithm) are identical. If the attached bases were not computed,
  158. ##  test  whether  the  base  of  <V>  is  a  subset  of  <W> and compare the
  159. ##  dimensions.
  160. ##
  161. RowSpaceOps.\= := function( V, W )
  162.     local   iseq, vbase, wbase;
  163.  
  164.     if IsRowSpace( V )  and IsRowSpace( W )  then
  165.         if V.field = W.field then
  166.             vbase := Base( V );
  167.             wbase := Base( W );
  168.             if V.isComputedBase and W.isComputedBase then
  169.                 iseq := vbase = wbase;
  170.             else
  171.                 iseq := ForAll( vbase, x -> x in W )
  172.                         and Dimension( V ) = Dimension( W );
  173.             fi;
  174.         else
  175.             iseq := false;
  176.         fi;
  177.     else
  178.         iseq := DomainOps.\=( V, W );
  179.     fi;
  180.     return iseq;
  181. end;
  182.  
  183.  
  184. #############################################################################
  185. ##
  186. #F  RowSpaceOps.\<( <V>, <W> ) . . .  test if row space <V> is less than <W>
  187. ##
  188. ##  The algorithm to test one row space being less than an other one may seem
  189. ##  odd, as it checks wether the reversed canonical base is less than that of
  190. ##  the other row space if the fields are equal. Otherwise the decision is
  191. ##  made upon the ordering on the fields.
  192. ##
  193. RowSpaceOps.\< := function( V, W )
  194.     local   isless, vbase, wbase;
  195.  
  196.     if IsRowSpace( V )  and IsRowSpace( W )  then
  197.         if V.field = W.field then
  198.             vbase := Base( V );
  199.             wbase := Base( W );
  200.             if not V.isComputedBase then
  201.                 vbase := V.operations.Base( V );
  202.             fi;
  203.             if not W.isComputedBase then
  204.                 wbase := W.operations.Base( W );
  205.             fi;
  206.             isless := Reversed( vbase ) < Reversed( wbase );
  207.         else
  208.             isless := V.field < W.field;
  209.         fi;
  210.     else
  211.         isless := DomainOps.\<( V, W );
  212.     fi;
  213.     return isless;
  214. end;
  215.  
  216.  
  217. #############################################################################
  218. ##
  219. #F  RowSpaceOps.\in( <v>, <V> )  . . . . . . . . . . . test if <v> is in <V>
  220. ##
  221. RowSpaceOps.\in := function( v, V )
  222.     return SiftedVector( V, v ) = V.zero;
  223. end;
  224.  
  225.  
  226. #############################################################################
  227. ##
  228. #F  RowSpaceOps.Print( <obj> )  . . . . . . . . . . . . . . print a row space
  229. ##
  230. RowSpaceOps.Print := function( V )
  231.     if IsBound( V.name ) then
  232.         Print( V.name );
  233.     elif V.generators = [] then
  234.         Print( "RowSpace( [  ], ", V.field, ", ", V.zero, " )" );
  235.     elif Information( V ).isStandardBase then
  236.         Print( "RowSpace( ", Dimension( V ), ", ", V.field, " )" );
  237.     else
  238.         Print( "RowSpace( ", V.generators, ", ", V.field, " )" );
  239.     fi;
  240. end;
  241.  
  242.  
  243. #############################################################################
  244. ##
  245. #F  RowSpaceOps.Intersection( <V>, <W> )  . .  intersection of two row spaces
  246. ##
  247. RowSpaceOps.Intersection := function( V, W )
  248.     local   vbase, wbase, mat, v, vdim, mlen, fpos, gens, i, j;
  249.  
  250.     if V.zero <> W.zero or V.field <> W.field then
  251.         Error( "sorry, row spaces are incompatible" );
  252.     fi;
  253.  
  254.     vbase := Base( V );
  255.     if vbase = [] then  return RowSpace( [], V.field, V.zero );  fi;
  256.     wbase := Base( W );
  257.     if wbase = [] then  return RowSpace( [], V.field, V.zero );  fi;
  258.  
  259.     # set up the matrix for the zassenhaus algorithm
  260.  
  261.     mat := [];
  262.     for v in vbase do
  263.         v := ShallowCopy( v );
  264.         Append( v, v );
  265.         IsVector( v );
  266.         Add( mat, v );
  267.     od;
  268.     for v in wbase do
  269.         v := ShallowCopy( v );
  270.         Append( v, W.zero );
  271.         IsVector( v );
  272.         Add( mat, v );
  273.     od;
  274.  
  275.     # triangulize matrix and extract the base for the intersection space
  276.  
  277.     TriangulizeMat( mat );
  278.     vdim := Length( V.zero );
  279.     mlen := Length( mat );
  280.     fpos := 1;
  281.     while fpos <= mlen and Position( mat[fpos], V.field.one ) <= vdim do
  282.         fpos := fpos + 1;
  283.     od;
  284.     gens := [];
  285.     for i in [fpos..mlen] do
  286.         v := ShallowCopy( V.zero );
  287.         for j in [1..vdim] do
  288.             v[j] := mat[i][vdim+j];
  289.         od;
  290.         Add( gens, v );
  291.     od;
  292.     return RowSpace( gens, V.field, V.zero );
  293. end;
  294.  
  295.  
  296. #############################################################################
  297. ##
  298. #F  RowSpaceOps.Base( <V> ) . . . . . . . . . . . . . . . base of a row space
  299. ##
  300. RowSpaceOps.Base := function( V )
  301.     if V.generators = [] then   return [];
  302.     else                        return BaseMat( V.generators );
  303.     fi;
  304. end;
  305.  
  306.  
  307. #############################################################################
  308. ##
  309. #F  BaseTypeRowSpace( <V> ) . . . . . . . . . determine type of attached base
  310. ##
  311. ##  the following basetypes (where one type includes all previous types)
  312. ##  are currently supported:
  313. ##
  314. ##  TriangulizedBase    the matrix of the base is in upper triangular form
  315. ##  NormedBase          each vector of the basis is (additionally) normed
  316. ##  NormalizedBase      all base vectors have 0 at another vectors weight
  317. ##  StandardBaseSubset  the matrix of the base just has identity matrix rows
  318. ##  StandardBase        the matrix of the base is the identity matrix
  319. ##
  320. BaseTypeRowSpace := function( V )
  321.     local   base, dim, vdim, normed, isnormalized, ismonomial, i, j;
  322.  
  323.     isnormalized := function ()
  324.         local   i, j;
  325.         for i in [2..dim] do
  326.             for j in [1..i-1] do
  327.                 if base[j][V.weights[i]] <> V.field.zero then
  328.                     return false;
  329.                 fi;
  330.             od;
  331.         od;
  332.         return true;
  333.     end;
  334.  
  335.     ismonomial := function ()
  336.         local   i, j;
  337.         for i in [1..dim] do
  338.             for j in [V.weights[i]+1..vdim] do
  339.                 if base[i][j] <> V.field.zero then  return false;  fi;
  340.             od;
  341.         od;
  342.         return true;
  343.     end;
  344.  
  345.     if not IsBound( V.base ) then  Base( V );  fi;
  346.  
  347.     base   := V.base;
  348.     dim    := Length( base );
  349.     vdim   := Length( V.zero );
  350.     normed := true;
  351.  
  352.     V.weights              := [];
  353.     V.isStandardBase       := false;
  354.     V.isStandardBaseSubset := false;
  355.     V.isNormalizedBase     := false;
  356.     V.isNormedBase         := false;
  357.     V.isTriangulizedBase   := false;
  358.  
  359.     for i in [1..dim] do
  360.         j := 1;
  361.         while base[i][j] = V.field.zero do  j := j + 1;  od;
  362.         V.weights[i] := j;
  363.         if base[i][j] <> V.field.one then  normed := false;  fi;
  364.     od;
  365.  
  366.  
  367.     # finally determine the exact state of the base, that is, set all
  368.     # the flags to their correct value.
  369.  
  370.     if IsSet( V.weights ) then
  371.         V.isTriangulizedBase := true;
  372.         if normed then
  373.             V.isNormedBase := true;
  374.             if isnormalized() then
  375.                 V.isNormalizedBase := true;
  376.                 if V.weights = [1..vdim] then
  377.                     V.isStandardBase       := true;
  378.                     V.isStandardBaseSubset := true;
  379.                 elif ismonomial() then
  380.                     V.isStandardBaseSubset := true;
  381.                 fi;
  382.             fi;
  383.         fi;
  384.     fi;
  385. end;
  386.  
  387.  
  388. #############################################################################
  389. ##
  390. #F  RowSpaceOps.Information( <V> )  . . . . . information about the row space
  391. ##
  392. RowSpaceOps.Information := function( V )
  393.     local   base, dim, size, info, pows, pow, i;
  394.  
  395.  
  396.     # first step: general information about the row space
  397.  
  398.     info := rec(
  399.         field    := V.field,
  400.         zero     := V.zero,
  401.         isFinite := IsFinite( V )
  402.     );
  403.  
  404.  
  405.     # second step: details about the field
  406.  
  407.     info.isFiniteField := IsFinite( V.field );
  408.     if info.isFiniteField then
  409.         info.isFinitePrimeField := V.field.degree = 1;
  410.         if info.isFinitePrimeField then
  411.             info.integers := IntegerTable( V.field );
  412.         fi;
  413.     else
  414.         info.isFinitePrimeField := false;
  415.     fi;
  416.  
  417.  
  418.     # third step: base and dimension
  419.  
  420.     base := Base( V );
  421.     dim  := Length( base );
  422.  
  423.     info.base      := base;
  424.     info.dimension := dim;
  425.  
  426.  
  427.     # fourth step: enumeration information
  428.     #              only applicable if the field is finite
  429.  
  430.     if info.isFiniteField then
  431.         size := Size( V.field );
  432.         pows := [];
  433.         pow  := 1;
  434.  
  435.         for i in [1..dim] do
  436.             pows[i] := pow;
  437.             pow := pow * size;
  438.         od;
  439.  
  440.         info.powers    := Reversed( pows );
  441.         info.exponents := List( base, x -> size );
  442.     fi;
  443.  
  444.  
  445.     # fifth step: coefficients information
  446.  
  447.     info.zeroCoefficients := List( base, x -> V.field.zero );
  448.     IsVector( info.zeroCoefficients );
  449.  
  450.  
  451.     # sixth step: general base information
  452.  
  453.     BaseTypeRowSpace( info );
  454.  
  455.     return info;
  456. end;
  457.  
  458.  
  459. #############################################################################
  460. ##
  461. #F  RowSpaceOps.Coefficients( <V>, <v> )  . . . .  coefficients of <v> in <V>
  462. ##
  463. RowSpaceOps.Coefficients := function( V, v )
  464.     local   cf, info, z, i;
  465.  
  466.     if not IsBound( V.information ) then
  467.         Information( V );
  468.     fi;
  469.     info := V.information;
  470.     if info.isStandardBase then
  471.         cf := ShallowCopy( v );
  472.     elif info.isNormalizedBase then
  473.         cf := ShallowCopy( info.zeroCoefficients );
  474.         for i in [1..info.dimension] do  cf[i] := v[info.weights[i]];  od;
  475.     elif info.isNormedBase then
  476.         cf := ShallowCopy( info.zeroCoefficients );
  477.         for i in [1..info.dimension] do
  478.             z := v[info.weights[i]];
  479.             if z <> V.field.zero then
  480.                 v := v - z * info.base[i];
  481.                 cf[i] := z;
  482.             fi;
  483.         od;
  484.     elif info.isTriangulizedBase then
  485.         cf := ShallowCopy( info.zeroCoefficients );
  486.         for i in [1..info.dimension] do
  487.             z := v[info.weights[i]];
  488.             if z <> V.field.zero then
  489.                 z := z / info.base[i][info.weights[i]];
  490.                 v := v - z * info.base[i];
  491.                 cf[i] := z;
  492.             fi;
  493.         od;
  494.     else
  495.         Error( "sorry, can't compute coefficients for base" );
  496.     fi;
  497.     return cf;
  498. end;
  499.  
  500.  
  501. #############################################################################
  502. ##
  503. #F  SiftedVector( <V>, <v> )  . . . . . . . . . . .  residuum of <v> over <V>
  504. ##
  505. SiftedVector := function( V, v )
  506.     return V.operations.SiftedVector( V, v );
  507. end;
  508.  
  509.  
  510. #############################################################################
  511. ##
  512. #F  RowSpaceOps.SiftedVector( <V>, <v> )  . . . . .  residuum of <v> over <V>
  513. ##
  514. RowSpaceOps.SiftedVector := function( V, v )
  515.     local   info, z, i;
  516.  
  517.     if not IsBound( V.information ) then
  518.         Information( V );
  519.     fi;
  520.     info := V.information;
  521.     if info.isStandardBase then
  522.         v := 0 * v;
  523.     elif info.isStandardBaseSubset then
  524.         v := ShallowCopy( v );
  525.         for i in [1..info.dimension] do
  526.             v[info.weights[i]] := V.field.zero;
  527.         od;
  528.     elif info.isNormedBase then
  529.         for i in [1..info.dimension] do
  530.             z := v[info.weights[i]];
  531.             if z <> V.field.zero then
  532.                 v := v - z * info.base[i];
  533.             fi;
  534.         od;
  535.     elif info.isTriangulizedBase then
  536.         for i in [1..info.dimension] do
  537.             z := v[info.weights[i]];
  538.             if z <> V.field.zero then
  539.                 v := v - z / info.base[i][info.weights[i]] * info.base[i];
  540.             fi;
  541.         od;
  542.     else
  543.         Error( "sorry, can't compute residuum for base" );
  544.     fi;
  545.     return v;
  546. end;
  547.  
  548.  
  549. #############################################################################
  550. ##
  551. #F  RowSpaceOps.Enumeration( <V> )  . . . enumeration for the elements of <V>
  552. ##
  553. RowSpaceOps.Enumeration := function( V )
  554.     local   enum, e;
  555.  
  556.     if not IsFinite( V ) then
  557.         Error( "sorry, row space is infinite" );
  558.     fi;
  559.  
  560.     e := ShallowCopy( Information( V ) );
  561.  
  562.     e.number := function ( enum, v )
  563.         local   num, z, i;
  564.  
  565.         if enum.base = [] then
  566.             return 1;
  567.         fi;
  568.  
  569.         if enum.isFinitePrimeField then
  570.             if enum.isStandardBase then
  571. #T                num := 1;
  572. #T                for i in [1..enum.dimension] do
  573. #T                    z := LogVecFFE( v, i );
  574. #T                    if z <> false then
  575. #T                        num := num + enum.powers[i] * enum.integers[z+1];
  576. #T                    fi;
  577. #T                od;
  578.                 num := NumberVecFFE( v, enum.powers, enum.integers );
  579.             elif enum.isNormalizedBase then
  580.                 num := 1;
  581.                 for i in [1..enum.dimension] do
  582.                     z := LogVecFFE( v, enum.weights[i] );
  583.                     if z <> false then
  584.                         num := num + enum.powers[i] * enum.integers[z+1];
  585.                     fi;
  586.                 od;
  587.             elif enum.isNormedBase then
  588.                 num := 1;
  589.                 for i in [1..enum.dimension] do
  590.                     z := LogVecFFE( v, enum.weights[i] );
  591.                     if z <> false then
  592.                         num := num + enum.powers[i] * enum.integers[z+1];
  593.                         v := v - z * enum.base[i];
  594.                     fi;
  595.                 od;
  596.             elif enum.isTriangulizedBase then
  597.                 num := 1;
  598.                 for i in [1..enum.dimension] do
  599.                     z := v[enum.weights[i]];
  600.                     if z <> V.field.zero then
  601.                         z := z / enum.base[i][enum.weights[i]];
  602.                         num := num + enum.powers[i] * enum.integers[LogFFE(z)+1];
  603.                         v := v - z * enum.base[i];
  604.                     fi;
  605.                 od;
  606.             else
  607.                 Error( "sorry, can't compute number of element for base" );
  608.             fi;
  609.         else
  610.             if enum.isStandardBase then
  611.                 num := 1;
  612.                 for i in [1..enum.dimension] do
  613.                     z := LogVecFFE( v, i );
  614.                     if z <> false then
  615.                         num := num + enum.powers[i] * (z+1);
  616.                     fi;
  617.                 od;
  618.             elif enum.isNormalizedBase then
  619.                 num := 1;
  620.                 for i in [1..enum.dimension] do
  621.                     z := LogVecFFE( v, enum.weights[i] );
  622.                     if z <> false then
  623.                         num := num + enum.powers[i] * (z+1);
  624.                     fi;
  625.                 od;
  626.             elif enum.isNormedBase then
  627.                 num := 1;
  628.                 for i in [1..enum.dimension] do
  629.                     z := v[enum.weights[i]];
  630.                     if z <> V.field.zero then
  631.                         num := num + enum.powers[i] * (LogFFE( z )+1);
  632.                         v := v - z * enum.base[i];
  633.                     fi;
  634.                 od;
  635.             elif enum.isTriangulizedBase then
  636.                 num := 1;
  637.                 for i in [1..enum.dimension] do
  638.                     z := v[enum.weights[i]];
  639.                     if z <> V.field.zero then
  640.                         z := z / enum.base[i][enum.weights[i]];
  641.                         num := num + enum.powers[i] * (LogFFE( z )+1);
  642.                         v := v - z * enum.base[i];
  643.                     fi;
  644.                 od;
  645.             else
  646.                 Error( "sorry, can't compute number of element for base" );
  647.             fi;
  648.         fi;
  649.         return num;
  650.     end;
  651.  
  652.     e.element := function( enum, num )
  653.         local   cf, v, i;
  654.  
  655.         if enum.base = [] then
  656.             return enum.zero;
  657.         fi;
  658.  
  659.         if enum.isFinitePrimeField then
  660.             if enum.isStandardBase then
  661.                 v := MakeVecFFE( CoefficientsInt( enum.exponents, num-1 ), enum.field.one );
  662.             elif enum.isStandardBaseSubset then
  663.                 cf := MakeVecFFE( CoefficientsInt( enum.exponents, num-1 ), enum.field.one );
  664.                 v  := ShallowCopy( enum.zero );
  665.                 for i in [1..enum.dimension] do
  666.                     v[enum.weights[i]] := cf[i];
  667.                 od;
  668.             else
  669.                 v := CoefficientsInt( enum.exponents, num-1 ) * enum.base;
  670.             fi;
  671.         else
  672.             if enum.isStandardBase then
  673.                 cf := CoefficientsInt( enum.exponents, num-1 );
  674.                 v  := ShallowCopy( enum.zero );
  675.                 for i in [1..enum.dimension] do
  676.                     if cf[i] <> V.field.zero then
  677.                         v[i] := enum.field.root ^ cf[i];
  678.                     fi;
  679.                 od;
  680.             elif enum.isStandardBaseSubset then
  681.                 cf := CoefficientsInt( enum.exponents, num-1 );
  682.                 v  := ShallowCopy( enum.zero );
  683.                 for i in [1..enum.dimension] do
  684.                     if cf[i] <> V.field.zero then
  685.                         v[enum.weights[i]] := enum.field.root ^ cf[i];
  686.                     fi;
  687.                 od;
  688.             else
  689.                 cf := CoefficientsInt( enum.exponents, num-1 );
  690.                 v  := enum.zero;
  691.                 for i in [1..enum.dimension] do
  692.                     if cf[i] <> V.field.zero then
  693.                         v := v + enum.field.root ^ cf[i] * enum.base[i];
  694.                     fi;
  695.                 od;
  696.             fi;
  697.         fi;
  698.         return v;
  699.     end;
  700.  
  701.     return e;
  702. end;
  703.  
  704.  
  705. #############################################################################
  706. ##
  707. #F  RowSpaceOps.\mod( <V>, <W> ) . . . . . . . . . . .  construct a modspace
  708. ##
  709. ##  The infix operator 'mod' for row spaces will create a faked factorspace of
  710. ##  the  given row spaces. This new structure is basically there to calculate
  711. ##  coefficients of vectors in the corresponding factorspace.
  712. ##
  713. RowSpaceOps.\mod := function( V, W )
  714.     local vbase, wbase, base, fac, i;
  715.  
  716.     # a base for the Modspace is the canonical one
  717.  
  718.     vbase := Base( V );
  719.     wbase := Base( W );
  720.  
  721.     if vbase = [] or wbase = [] then  return ShallowCopy( V );  fi;
  722.  
  723.     base  := BaseMat( List( vbase, x -> SiftedVector( W, x ) ) );
  724.  
  725.     fac := rec(
  726.  
  727.         # fields that are the same with row spaces
  728.  
  729.         generators     := base,
  730.         base           := base,
  731.         field          := V.field,
  732.         zero           := V.zero,
  733.  
  734.         # special Modspace fields
  735.  
  736.         parentspace    := V,
  737.         subspace       := W,
  738.         parentInfo     := Information( V ),
  739.         subInfo        := Information( W ),
  740.         mergedSpace    := rec(),
  741.  
  742.         # flags and operations
  743.  
  744.         isDomain       := true,
  745.         isModspace     := true,
  746.         isFinite       := IsFinite( V.field ) or base = [],
  747.         isComputedBase := V.isComputedBase,
  748.         operations     := ModspaceOps
  749.     );
  750.  
  751.     if    fac.parentInfo.isTriangulizedBase
  752.       and fac.subInfo.isTriangulizedBase then
  753.         base := ShallowCopy( vbase );
  754.         for i in [1..fac.subInfo.dimension] do
  755.             base[Position(
  756.                 fac.parentInfo.weights,
  757.                 fac.subInfo.weights[i] )] := wbase[i];
  758.         od;
  759.         fac.mergedSpace := RowSpace( base, V.field, V.zero );
  760.         AddBase( fac.mergedSpace, base );
  761.     else
  762.         Error( "sorry, bases have to be triangulized" );
  763.     fi;
  764.  
  765.     return fac;
  766. end;
  767.  
  768.  
  769. #############################################################################
  770. ##
  771. #V  ModspaceOps . . . . . . . . . . . . . . . operations record for modspaces
  772. ##
  773. ModspaceOps := ShallowCopy( RowSpaceOps );
  774.  
  775.  
  776. #############################################################################
  777. ##
  778. #F  ModspaceOps.Base( <V> ) . . . . . . . . . . . . . . .  base of a modspace
  779. ##
  780. ModspaceOps.Base := function( V )
  781.     return V.generators;
  782. end;
  783.  
  784.  
  785. #############################################################################
  786. ##
  787. #F  ModspaceOps.Coefficients( <V>, <v> )  . . . .  coefficients of <v> in <V>
  788. ##
  789. ModspaceOps.Coefficients := function( V, v )
  790.     local   info, minfo, cf, z, i, j;
  791.  
  792.     if V.subInfo.isStandardBase then
  793.         return [];
  794.     else
  795.         if not IsBound( V.information ) then
  796.             Information( V );
  797.         fi;
  798.         if not IsBound( V.mergedSpace.information ) then
  799.             Information( V.mergedSpace );
  800.         fi;
  801.         info  := V.information;
  802.         minfo := V.mergedSpace.information;
  803.  
  804.         if minfo.isNormalizedBase then
  805.             cf := ShallowCopy( info.zeroCoefficients );
  806.             for i in [1..info.dimension] do
  807.                 cf[i] := v[info.weights[i]];
  808.             od;
  809.         elif minfo.isNormedBase then
  810.             cf := ShallowCopy( info.zeroCoefficients );
  811.             j  := 1;
  812.             for i in [1..minfo.dimension] do
  813.                 z := v[minfo.weights[i]];
  814.                 if z <> V.field.zero then
  815.                     v := v - z * minfo.base[i];
  816.                     if minfo.weights[i] in info.weights then
  817.                         cf[j] := z;
  818.                         j := j + 1;
  819.                     fi;
  820.                 elif minfo.weights[i] in info.weights then
  821.                     j := j + 1;
  822.                 fi;
  823.             od;
  824.         elif minfo.isTriangulizedBase then
  825.             cf := ShallowCopy( info.zeroCoefficients );
  826.             j  := 1;
  827.             for i in [1..minfo.dimension] do
  828.                 z := v[minfo.weights[i]];
  829.                 if z <> V.field.zero then
  830.                     z := z / minfo.base[i][minfo.weights[i]];
  831.                     v := v - z * minfo.base[i];
  832.                     if minfo.weights[i] in info.weights then
  833.                         cf[j] := z;
  834.                         j := j + 1;
  835.                     fi;
  836.                 elif minfo.weights[i] in info.weights then
  837.                     j := j + 1;
  838.                 fi;
  839.             od;
  840.         fi;
  841.     fi;
  842.     return cf;
  843. end;
  844.  
  845.  
  846. #############################################################################
  847. ##
  848. #F  ModspaceOps.Print( <V> )  . . . . . . . . . . . . . . print of a modspace
  849. ##
  850. ModspaceOps.Print := function( V )
  851.     Print( V.parentspace, " mod ", V.subspace );
  852. end;
  853.  
  854.  
  855. #############################################################################
  856. ##
  857. #E  Emacs . . . . . . . . . . . . . . . . . . . . . . . local emacs variables
  858. ##
  859. ##  Local Variables:
  860. ##  mode:               outline
  861. ##  outline-regexp:     "#F\\|#V\\|#E"
  862. ##  fill-column:        73
  863. ##  fill-prefix:        "##  "
  864. ##  eval:               (hide-body)
  865. ##  End:
  866. ##
  867.