Real-time collaboration for Jupyter Notebooks, Linux Terminals, LaTeX, VS Code, R IDE, and more,
all in one place.
Real-time collaboration for Jupyter Notebooks, Linux Terminals, LaTeX, VS Code, R IDE, and more,
all in one place.
| Download
GAP 4.8.9 installation with standard packages -- copy to your CoCalc project to get it
Project: cocalc-sagemath-dev-slelievre
Views: 418346#############################################################################
##
#W scanmtx.gi GAP 4 packages AtlasRep and MeatAxe Thomas Breuer
#W Frank Lübeck
##
#Y Copyright (C) 2001, Lehrstuhl D für Mathematik, RWTH Aachen, Germany
##
## Whenever this file is changed in one of the packages
## `atlasrep' or `meataxe',
## do not forget to update the corresponding file in the other package!
##
## This file contains the implementation part of the interface routines for
## reading and writing C-MeatAxe text and binary format,
## and straight line programs used in the ATLAS of Group Representations.
##
## The functions `CMtxBinaryFFMatOrPerm' and `FFMatOrPermCMtxBinary'
## were contributed by Frank Lübeck.
##
############################################################################
##
#V CMeatAxe
##
InstallValue( CMeatAxe,
rec(
gennames := [],
alpha := "abcdefghijklmnopqrstuvwxyz",
maxnr := 0
) );
#############################################################################
##
## The C-MeatAxe defines the bijection between the elements in the field
## with $q = p^d$ elements and the set $\{ 0, 1, \ldots, q-1 \}$ of integers
## by assigning the field element $\sum_{i=0}^{d-1} c_i z^i$ to the integer
## $\sum_{i=0}^{d-1} c_i p^i$,
## where the $c_i$ are in the set $\{ 0, 1, \ldots, p-1 \}$ and $z$ is the
## primitive root of the field with $q$ elements that corresponds to the
## residue class of the indeterminate, modulo the ideal spanned by the
## Conway polynomial of degree $d$ over the field with $p$ elements.
##
## The bijection is implemented via lookup tables `l1 = FFList( GF(<q>) )'
## and `l2 = FFLogList( GF(<q>) )'.
##
## If the field element <x> corresponds to the integer <i> then
## the relations $<i> = `Position( FFList( GF(<q>) ), <x> )' - 1$ and
## $<x> = `FFList( GF(<q>) )'[ <i>+1 ]$ hold.
##
## If $q = p$ then $<i> = `IntFFE'( <x> )$ holds,
## which is cheaper to compute than via `Position';
## Also $<x> = <i> * `Z(p)^0'$ holds, so the lookup table need not be
## created for large prime fields.
##
## In order to avoid the calls to `Position' also in the case of non-prime
## fields, the lookup list `FFLogList( GF(<q>) )' is used.
## For $<x> = <z>^k$,
## we have `String( <i> ) = FFLogList( GF(<q>) )[ LogFFE( <x>, <z> ) + 1 ]'.
##
#############################################################################
##
#V FFLists
#V FFLogLists
#V NONNEG_INTEGERS_STRINGS
##
InstallFlushableValue( FFLists, [] );
InstallFlushableValue( FFLogLists, [] );
InstallFlushableValue( NONNEG_INTEGERS_STRINGS, [] );
#############################################################################
##
#F FFList( <F> )
##
## (This program was originally written by Meinolf Geck.)
##
InstallGlobalFunction( FFList, function( F )
local sizeF,
p,
dim,
elms,
root,
powers,
i,
pow;
sizeF:= Size( F );
if not IsBound( FFLists[ sizeF ] ) then
p:= Characteristic( F );
dim:= DegreeOverPrimeField( F );
elms:= List( Cartesian( List( [ 1 .. dim ], i -> [ 0 .. p-1 ] ) ),
Reversed );
root:= PrimitiveRoot( F );
pow:= One( root );
powers:= [ pow ];
for i in [ 2 .. dim ] do
pow:= pow * root;
powers[i]:= pow;
od;
elms:= elms * powers;
ConvertToVectorRep( elms, sizeF );
FFLists[ sizeF ]:= elms;
fi;
return FFLists[ sizeF ];
end );
#############################################################################
##
#F FFLogList( <F> )
##
InstallGlobalFunction( FFLogList, function( F )
local sizeF, fflist, z, result, i;
sizeF:= Size( F );
if not IsBound( FFLogLists[ sizeF ] ) then
fflist:= FFList( F );
z:= Z( sizeF );
result:= [ 0 ];
result[ Length( fflist ) ]:= 0;
for i in [ 2 .. Length( fflist ) ] do
result[ LogFFE( fflist[i], z ) + 1 ]:= String( i-1 );
od;
FFLogLists[ sizeF ]:= result;
fi;
return FFLogLists[ sizeF ];
end );
#############################################################################
##
#F IntegerStrings( <q> )
##
InstallGlobalFunction( IntegerStrings, function( q )
local i;
for i in [ Length( NONNEG_INTEGERS_STRINGS ) + 1 .. q ] do
NONNEG_INTEGERS_STRINGS[i]:= String( i-1 );
od;
return NONNEG_INTEGERS_STRINGS;
end );
#############################################################################
##
#F CMeatAxeFileHeaderInfo( <string> )
##
InstallGlobalFunction( "CMeatAxeFileHeaderInfo", function( string )
local lline, header, pos, line, degree;
# Remove a comment part if necessary.
pos:= Position( string, '#' );
if pos <> fail then
string:= string{ [ 1 .. pos ] };
fi;
# Split the header string, and convert the entries to integers.
lline:= List( SplitString( string, "", " \n" ), Int );
if fail in lline then
# If the header is valid then it is of new type;
# remove everything before a leading `"'.
header:= SplitString( string, "", " \n" );
pos:= First( header, x -> not IsEmpty( x ) and x[1] = '\"' );
if pos <> fail then
header:= header{ [ pos .. Length( header ) ] };
fi;
if Length( header ) = 2 and header[1] = "permutation" then
line:= [ 12, 1,, 1 ];
if 7 < Length( header[2] ) and header[2]{ [ 1 .. 7 ] } = "degree=" then
degree:= Int( header[2]{ [ 8 .. Length( header[2] ) ] } );
line[3]:= degree;
fi;
elif Length( header ) = 4 and header[1] = "matrix" then
line:= [ 6 ];
if 6 < Length( header[2] ) and header[2]{ [ 1 .. 6 ] } = "field=" then
line[2]:= Int( header[2]{ [ 7 .. Length( header[2] ) ] } );
if IsInt( line[2] ) and line[2] < 10 then
line[1]:= 1;
fi;
fi;
if 5 < Length( header[3] ) and header[3]{ [ 1 .. 5 ] } = "rows=" then
line[3]:= Int( header[3]{ [ 6 .. Length( header[3] ) ] } );
fi;
if 5 < Length( header[4] ) and header[4]{ [ 1 .. 5 ] } = "cols=" then
line[4]:= Int( header[4]{ [ 6 .. Length( header[4] ) ] } );
fi;
fi;
if fail in line or Number( line ) <> 4 then
Info( InfoCMeatAxe, 1,
"corrupted (new) MeatAxe file header" );
return fail;
fi;
else
# The header is of old type, consisting of four integers.
if Length( lline ) = 3 and lline[1] = 12 then
# We may be dealing with permutations of a degree requiring
# (at least) six digits, for example the header for a permutation
# on $100000$ points can be `12 1100000 1'.
line:= String( lline[2] );
if line[1] = '1' then
lline[4]:= lline[3];
lline[3]:= Int( line{ [ 2 .. Length( line ) ] } );
lline[2]:= 1;
fi;
fi;
if Length( lline ) <> 4 then
Info( InfoCMeatAxe, 1,
"corrupted (old) MeatAxe file header" );
return fail;
fi;
line:= lline;
fi;
return line;
end );
#############################################################################
##
#F ScanMeatAxeFile( <filename>[, <q>] )
#F ScanMeatAxeFile( <string>[, <q>], "string" )
##
InstallGlobalFunction( ScanMeatAxeFile, function( arg )
local PermListWithTest,
filename,
file,
line,
q,
mode,
degree,
result,
string,
headlen,
pos,
pos2,
offset,
j,
imgs,
i,
Fsize,
F,
nrows,
fflist,
newline,
ncols,
one,
len;
PermListWithTest:= function( list )
local perm;
perm:= PermList( list );
if perm = fail then
if ForAny( list, x -> not IsInt( x ) ) then
Info( InfoCMeatAxe, 1,
"non-permutation in file, contains ",
Filtered( list, x -> not IsInt( x ) ) );
fi;
Info( InfoCMeatAxe, 1,
"non-permutation in file,\n#I ",
Difference( [ 1 .. degree ], list ), " missing, ",
List( Filtered( Collected( list ),
x -> x[2] <> 1 ), x -> x[1] ), " duplicate" );
fi;
return perm;
end;
if Length( arg ) = 1
or ( Length( arg ) = 2 and IsPosInt( arg[2] ) ) then
filename:= arg[1];
# Do we want to read the file *fast* (but using more space)?
InfoRead1( "#I reading `", filename, "' started\n" );
if IsBound( CMeatAxe.FastRead ) and CMeatAxe.FastRead = true then
string:= AGR.StringFile( filename );
if Length( arg ) = 1 then
return ScanMeatAxeFile( string, "string" );
else
return ScanMeatAxeFile( string, arg[2], "string" );
fi;
fi;
file:= InputTextFile( filename );
if file = fail then
Error( "cannot create input stream for file <filename>" );
fi;
line:= ReadLine( file );
if line = fail then
Info( InfoCMeatAxe, 1, "no first line exists" );
CloseStream( file );
return fail;
fi;
while not '\n' in line do
Append( line, ReadLine( file ) );
od;
if Length( arg ) = 2 then
q:= arg[2];
fi;
elif ( Length( arg ) = 2 and IsString( arg[1] ) and arg[2] = "string" )
or ( Length( arg ) = 3 and IsString( arg[1] ) and IsPosInt( arg[2] )
and arg[3] = "string" ) then
# Cut out the header line.
string:= arg[1];
headlen:= Position( string, '\n' );
if headlen = fail then
return fail;
fi;
line:= string{ [ 1 .. headlen-1 ] };
string:= ShallowCopy( string );
string{ [ 1 .. headlen ] }:= ListWithIdenticalEntries( headlen, ' ' );
if Length( arg ) = 3 then
q:= arg[2];
fi;
else
Error( "usage: ScanMeatAxeFile( <filename>[, <q>] )" );
fi;
# Interpret the first line as file header.
# From the first line, determine whether a matrix or a permutation
# is to be read.
line:= CMeatAxeFileHeaderInfo( line );
if line = fail then
Info( InfoCMeatAxe, 1, "corrupted file header" );
if not IsBound( string ) then
CloseStream( file );
fi;
return fail;
fi;
mode:= line[1];
if mode in [ 2, 12 ] then
# a permutation, to be converted to a matrix,
# or a list of permutations
if not IsBound( string ) then
string:= AGR.StringFile( filename );
# Omit the header line.
headlen:= Position( string, '\n' );
string{ [ 1 .. headlen ] }:= ListWithIdenticalEntries( headlen, ' ' );
CloseStream( file );
InfoRead1( "#I reading `", filename, "' done\n" );
fi;
# Remove comment parts
# (not really clever, but we actually do not expect comments).
pos:= Position( string, '#' );
while pos <> fail do
pos2:= Position( string, '\n', pos );
if pos2 = fail then
pos2:= Length( string ) + 1;
fi;
string:= Concatenation( string{ [ 1 .. pos-1 ] },
string{ [ pos2 .. Length( string ) ] } );
pos:= Position( string, '#' );
od;
# Split the line into substrings representing numbers.
# (Admittedly, the code looks ugly, but simply calling `SplitString'
# and `Int' is slower, and calling `SplitString' and `EvalString'
# would be even slower than that.)
if 12 < headlen then
string{ [ 1 .. 13 ] }:= "SMFSTRING:=[ ";
else
string:= Concatenation( "SMFSTRING:=[ ", string );
fi;
NormalizeWhitespace( string );
pos:= Position( string, ' ' );
pos:= Position( string, ' ', pos );
while pos <> fail do
string[ pos ]:= ',';
pos:= Position( string, ' ', pos );
od;
Append( string, "];" );
file:= InputTextString( string );
Read( file );
string:= SMFSTRING;
SMFSTRING:= "";
if mode = 12 then
# mode = 12:
# a list of permutations (in free format)
degree:= line[3];
result:= [];
if Length( string ) <> degree * line[4] then
Info( InfoCMeatAxe, 1, "corrupted file, wrong number of entries" );
return fail;
fi;
if line[4] = 1 then
# This is the usual case (avoid duplicating the list).
result[1]:= PermListWithTest( string );
else
offset:= 0;
for j in [ 1 .. line[4] ] do
result[j]:=
PermListWithTest( string{ [ offset+1 .. offset+degree ] } );
offset:= offset + degree;
od;
fi;
if fail in result then
return fail;
fi;
else
# mode = 2:
# a permutation, to be converted to a matrix
# (Note that we cannot leave the task to `PermutationMat'
# because we admit also non-square results.)
nrows:= line[3];
if Length( string ) <> nrows then
Info( InfoCMeatAxe, 1, "corrupted file" );
return fail;
fi;
F:= GF( line[2] );
result:= NullMat( nrows, line[4], F );
one:= One( F );
for i in [ 1 .. nrows ] do
result[i][ string[i] ]:= one;
od;
# Convert the matrix to the compressed representation.
MakeImmutable( result );
if not IsBound( q ) then
q:= line[2];
fi;
ConvertToMatrixRep( result, q );
fi;
elif mode = 1 then
# a matrix, in fixed format
Fsize:= line[2];
F:= GF( Fsize );
fflist:= FFList( F );
fflist:= fflist{ Concatenation( ListWithIdenticalEntries( 47, 1 ),
[ 1 .. Length( fflist ) ] ) };
nrows:= line[3];
ncols:= line[4];
result:= [];
if IsBound( string ) then
# Remove comment parts
# (not really clever, but we actually do not expect comments).
pos:= Position( string, '#' );
while pos <> fail do
pos2:= Position( string, '\n', pos );
if pos2 = fail then
pos2:= Length( string ) + 1;
fi;
string:= Concatenation( string{ [ 1 .. pos-1 ] },
string{ [ pos2 .. Length( string ) ] } );
pos:= Position( string, '#' );
od;
# The string is available in GAP.
RemoveCharacters( string, " \n" );
if Length( string ) <> nrows * ncols then
Info( InfoCMeatAxe, 1, "string length does not fit" );
return fail;
fi;
pos:= 0;
for i in [ 1 .. nrows ] do
result[i]:= fflist{ INTLIST_STRING(
string{ [ pos+1 .. pos+ncols ] }, -1 ) };
pos:= pos + ncols;
od;
else
# The file is read line by line (for space reasons).
line:= "";
len:= 0;
for i in [ 1 .. nrows ] do
# Read enough lines from the file to fill the `i'-th row.
while len < ncols do
newline:= ReadLine( file );
if newline = fail then
Info( InfoCMeatAxe, 1, "corrupted file" );
CloseStream( file );
return fail;
fi;
while not '\n' in newline do
Append( newline, ReadLine( file ) );
od;
# Remove comment parts.
pos:= Position( newline, '#' );
if pos <> fail then
newline:= newline{ [ 1 .. pos-1 ] };
fi;
RemoveCharacters( newline, " \n" );
Append( line, newline );
len:= len + Length( newline );
od;
result[i] := fflist{ INTLIST_STRING( line{ [ 1 .. ncols ] }, -1 ) };
line:= line{ [ ncols + 1 .. len ] };
len:= len - ncols;
od;
# Close the stream.
CloseStream( file );
InfoRead1( "#I reading `", filename, "' done\n" );
fi;
# Convert further.
MakeImmutable( result );
if not IsBound( q ) then
q:= Fsize;
fi;
ConvertToMatrixRep( result, q );
elif mode in [ 3, 4, 5, 6 ] then
# a matrix, in various free formats
# (Prime fields could be treated in a special way,
# without calling `FFList'; but this seems to yield no speedup,
# except in exotic cases where `FFList' itself is the most expensive
# part of the computation.)
Fsize:= line[2];
F:= GF( Fsize );
nrows:= line[3];
ncols:= line[4];
result:= [];
if not IsBound( q ) then
q:= Fsize;
fi;
if mode = 5 then
one:= One( F );
else
fflist:= FFList( F );
fi;
# The case of a string that is available in GAP is dealt with
# in parallel with the case of a file that is read line by line
# (for space reasons).
if IsBound( string ) then
# Remove comment parts if applicable.
# (not really clever, but we actually do not expect comments).
while '#' in string do
pos:= Position( string, '#' );
pos2:= Position( string, '\n', pos );
if pos2 = fail then
pos2:= Length( string ) + 1;
fi;
string:= Concatenation( string{ [ 1 .. pos-1 ] },
string{ [ pos2 .. Length( string ) ] } );
od;
# Split the string into substrings representing numbers.
# (Admittedly, the code looks ugly, but simply calling `SplitString'
# and `Int' is slower, and calling `SplitString' and `EvalString'
# would be even slower than that.)
if 12 < headlen then
string{ [ 1 .. 13 ] }:= "SMFSTRING:=[ ";
else
string:= Concatenation( "SMFSTRING:=[ ", string );
fi;
NormalizeWhitespace( string );
pos:= Position( string, ' ' );
pos:= Position( string, ' ', pos );
while pos <> fail do
string[ pos ]:= ',';
pos:= Position( string, ' ', pos );
od;
Append( string, "];" );
file:= InputTextString( string );
Read( file );
string:= SMFSTRING;
SMFSTRING:= "";
line:= string;
if Length( line ) <> nrows * ncols then
Info( InfoCMeatAxe, 1, "corrupted file" );
return fail;
fi;
pos:= 0;
for i in [ 1 .. nrows ] do
if mode = 5 then
# an integer matrix (in free format), to be reduced mod a prime
result[i]:= ( line{ [ pos+1 .. pos+ncols ] } + 1 ) * one;
else
result[i]:= fflist{ line{ [ pos+1 .. pos+ncols ] } + 1 };
fi;
pos:= pos + ncols;
od;
else
# The file is read line by line (for space reasons).
line:= "";
len:= 0;
for i in [ 1 .. nrows ] do
# Read enough lines from the file to fill the `i'-th row.
while len < ncols do
newline:= ReadLine( file );
if newline = fail then
Info( InfoCMeatAxe, 1, "corrupted file" );
CloseStream( file );
return fail;
fi;
while not '\n' in newline do
Append( newline, ReadLine( file ) );
od;
# Remove comment parts.
pos:= Position( newline, '#' );
if pos <> fail then
newline:= newline{ [ 1 .. pos-1 ] };
fi;
newline:= List( SplitString( newline, "", " \n" ), Int );
Append( line, newline );
len:= len + Length( newline );
od;
if mode = 5 then
# an integer matrix (in free format), to be reduced mod a prime
result[i]:= ( line{ [ 1 .. ncols ] } + 1 ) * one;
else
result[i]:= fflist{ line{ [ 1 .. ncols ] } + 1 };
fi;
line:= line{ [ ncols + 1 .. len ] };
len:= len - ncols;
od;
# Close the stream.
CloseStream( file );
InfoRead1( "#I reading `", filename, "' done\n" );
fi;
# Convert further.
MakeImmutable( result );
ConvertToMatrixRep( result, q );
else
Info( InfoCMeatAxe, 1, "unknown mode" );
return fail;
fi;
return result;
end );
#############################################################################
##
#M MeatAxeString( <mat>, <q> )
##
InstallMethod( MeatAxeString,
[ "IsTable and IsFFECollColl", "IsPosInt" ],
function( mat, q )
local nrows, # number of rows of `mat'
ncols, # number of columns of `mat'
one, # identity element of the field of matrix entries
zero, # zero element of the field of matrix entries
perm, # list of perm. images if `mat' is a perm. matrix
i, # loop over the rows of `mat'
noone, # no `one' found yet in the current row
row, # one row of `mat'
j, # loop over the columns of `mat'
mode, # mode of the MeatAxe string (first header entry)
str, # MeatAxe string, result
tail, #
fflist, #
ffloglist, #
z, #
values,
linelen,
nol,
k;
# Check that `mat' is rectangular.
if not IsMatrix( mat ) then
Error( "<mat> must be a matrix" );
fi;
nrows:= Length( mat );
ncols:= Length( mat[1] );
# Check that `q' and `mat' are compatible.
if not IsPrimePowerInt( q ) or ( q mod Characteristic( mat ) <> 0 ) then
Error( "<q> and the characteristic of <mat> are incompatible" );
fi;
one:= One( mat[1][1] );
zero:= Zero( one );
perm:= fail;
if UserPreference( "AtlasRep", "WriteMeatAxeFilesOfMode2" ) = true then
# If the matrix is a ``generalized permutation matrix''
# then construct a string of MeatAxe mode 2.
perm:= [];
for i in [ 1 .. nrows ] do
noone:= true;
row:= mat[i];
if IsZero( row ) then
perm:= fail;
else
for j in [ 1 .. ncols ] do
if row[j] = one then
if noone and not j in perm then
perm[i]:= j;
noone:= false;
else
perm:= fail;
break;
fi;
elif row[j] <> zero then
perm:= fail;
break;
fi;
od;
fi;
if perm = fail then
break;
fi;
od;
fi;
# Start with the header line.
# We try to keep the files as small as possible by using the (old)
# mode `1' whenever possible.
if perm <> fail then
mode:= "2";
elif q < 10 then
mode:= "1";
else
mode:= "6";
fi;
str:= ShallowCopy( mode ); # mode,
Append( str, " " );
Append( str, String( q ) ); # field size,
Append( str, " " );
Append( str, String( nrows ) ); # number of rows,
Append( str, " " );
Append( str, String( ncols ) ); # number of columns
Append( str, "\n" );
# Add the matrix entries.
if mode = "1" then
# Set the parameters for filling lines in the fixed format
values:= "0123456789";
linelen:= 80;
nol:= Int( ncols / linelen );
tail:= [ nol * linelen + 1 .. ncols ];
fflist:= FFList( GF(q) );
for row in mat do
i:= 1;
for j in [ 0 .. nol-1 ] do
for k in [ 1 .. linelen ] do
Add( str, values[ Position( fflist, row[i] ) ] );
i:= i + 1;
od;
Add( str, '\n' );
od;
if not IsEmpty( tail ) then
for i in tail do
Add( str, values[ Position( fflist, row[i] ) ] );
od;
Add( str, '\n' );
fi;
od;
elif mode = "2" then
for i in perm do
Append( str, String( i ) );
Add( str, '\n' );
od;
else
# free format
if IsPrimeInt( q ) then
# Avoid the call to `FFList', and expensive `Position' calls.
# Also store the strings once;
# this cache avoids garbage collections and thus saves time
# if the matrix is not too small, compared to the field.
values:= IntegerStrings( q );
for row in mat do
for i in row do
Append( str, values[ IntFFE( i ) + 1 ] );
Add( str, '\n' );
od;
od;
else
# Avoid expensive `Position' calls for the result of `FFList'.
ffloglist:= FFLogList( GF(q) );
z:= Z(q);
for row in mat do
for i in row do
if i = zero then
Append( str, "0\n" );
else
Append( str, ffloglist[ LogFFE( i, z ) + 1 ] );
Add( str, '\n' );
fi;
od;
od;
fi;
fi;
# Return the result.
return str;
end );
#############################################################################
##
#M MeatAxeString( <perms>, <degree> )
##
InstallMethod( MeatAxeString,
[ "IsPermCollection and IsList", "IsPosInt" ],
function( perms, degree )
local str, perm, i;
# Start with the header line.
str:= "12 1 ";
Append( str, String( degree ) );
Append( str, " " );
Append( str, String( Length( perms ) ) );
Append( str, "\n" );
# Add the images.
for perm in perms do
for i in [ 1 .. degree ] do
Append( str, String( i ^ perm ) );
Add( str, '\n' );
od;
od;
# Return the result.
return str;
end );
#############################################################################
##
#M MeatAxeString( <perm>, <q>, <dims> )
##
InstallMethod( MeatAxeString,
[ "IsPerm", "IsPosInt", "IsList" ],
function( perm, q, dims )
local str, i;
# Start with the header line.
# (The mode is `2': a permutation, to be converted to a matrix.)
str:= "2 "; # mode,
Append( str, String( q ) ); # field size,
Append( str, " " );
Append( str, String( dims[1] ) ); # number of rows,
Append( str, " " );
Append( str, String( dims[2] ) ); # number of columns
Append( str, "\n" );
# Add the images.
for i in [ 1 .. dims[1] ] do
Append( str, String( i ^ perm ) );
Add( str, '\n' );
od;
# Return the result.
return str;
end );
#############################################################################
##
#F CMtxBinaryFFMatOrPerm( <mat>, <q>, <outfile> )
#F CMtxBinaryFFMatOrPerm( <perm>, <deg>, <outfile>[, <base>] )
##
InstallGlobalFunction( CMtxBinaryFFMatOrPerm, function( arg )
local mat, q, outfile, res, qr, imgs, i, f, a, epb, qpwrs, ffloglist, z,
len, ind, row, x;
if Length( arg ) < 3 or 4 < Length( arg ) then
Error( "usage: ",
"CMtxBinaryFFMatOrPerm( <perm>, <deg>, <outfile>[, <base>] )" );
fi;
mat:= arg[1];
q:= arg[2];
outfile:= arg[3];
if IsPerm( mat ) then
res:= [ 255, 255, 255, 255 ];
qr:= q;
for i in [ 1 .. 4 ] do
Add( res, RemInt( qr, 256 ) );
qr:= QuoInt( qr, 256 );
od;
Append( res, [ 1, 0, 0, 0 ] );
imgs:= OnTuples( [ 1 .. q ], mat );
if Length( arg ) = 4 and arg[4] = 0 then
imgs:= imgs - 1;
fi;
for qr in imgs do
for i in [ 1 .. 4 ] do
Add( res, RemInt( qr, 256 ) );
qr:= QuoInt( qr, 256 );
od;
od;
f:= OutputTextFile( outfile, false );
WriteAll( f, STRING_SINTLIST( res ) );
elif q <= 256 then
# ff elts per byte
a := q;
epb := 0;
while a<=256 do
a := a*q;
epb := epb+1;
od;
# q-powers
qpwrs := List([epb-1,epb-2..0], i-> q^i);
# open outfile
f := OutputTextFile(outfile, false);
# header is 12 = 3x4 bytes, (field size, nrrows, nrcols),
# each number in 256-adic decomposition, least significant first
res := [];
for a in [q,Length(mat),Length(mat[1])] do
qr := [a,0];
for i in [1..4] do
qr := QuotientRemainder(qr[1],256);
Add(res,qr[2]);
od;
od;
WriteAll(f, STRING_SINTLIST(res));
# now the data, pack each epb entries in one byte, weighted with qpwrs
ffloglist:= List(FFLogList( GF(q) ), Int);
z:= Z(q);
for row in mat do
len := QuoInt(Length(row), epb);
if len * epb < Length(row) then
len := len+1;
fi;
res := 0*[1..len];
ind := [1,1];
for x in row do
if not IsZero(x) then
a := ffloglist[LogFFE(x, z) + 1];
res[ind[1]] := res[ind[1]] + a*qpwrs[ind[2]];
fi;
if ind[2] = epb then
ind := [ind[1]+1, 1];
else
ind[2] := ind[2]+1;
fi;
od;
WriteAll(f, STRING_SINTLIST(res));
od;
else
Error( "<q> must be at most 256" );
fi;
CloseStream(f);
end );
#############################################################################
##
#F FFMatOrPermCMtxBinary( <fname> )
##
InstallGlobalFunction( FFMatOrPermCMtxBinary, function( fname )
local f, head, v, q, deg, bytes, list, j, zero, i, res, nrows, ncols, a,
epb, lenrow, fflist, poslist, eltsbyte, row;
# open file and read first 12 bytes as header
# header is 12 = 3x4 bytes,
# (in the matrix case field size, nrrows, nrcols;
# in the permutation case -1, degree, 1),
# each number in 256-adic decomposition, least significant first
f := InputTextFile(fname);
if f = fail then
Info( InfoCMeatAxe, 1,
"cannot open ", fname );
return fail;
fi;
head := ReadAll(f, 12);
if head = fail or Length( head ) < 12 then
Info( InfoCMeatAxe, 1,
"file too short: ", fname );
CloseStream( f );
return fail;
fi;
head := INTLIST_STRING(head, 1);
v := [1, 256, 256^2, 256^3];
q := v * head{[1..4]};
if q = 4294967295 then
# permutation
deg:= v * head{ [ 5 .. 8 ] };
bytes:= INTLIST_STRING( ReadAll( f ), 1 );
CloseStream( f );
list:= [];
j:= 1;
zero:= false;
for i in [ 1 .. deg ] do
list[i]:= v * bytes{ [ j .. j+3 ] };
if list[i] = 0 then
zero:= true;
fi;
j:= j + 4;
od;
if zero then
# format used in C-MeatAxe 2.4 (zero-based): add 1 to all entries
for i in [ 1 .. deg ] do
list[i]:= list[i] + 1;
od;
fi;
res:= PermList( list );
# ugly hack:
# several of the data files on the server are stored in a wrong format.
if res = fail then
v:= [ 256^3, 256^2, 256, 1 ];
j:= 1;
zero:= false;
for i in [ 1 .. deg ] do
list[i]:= v * bytes{ [ j .. j+3 ] };
if list[i] = 0 then
zero:= true;
fi;
j:= j + 4;
od;
if zero then
# format used in C-MeatAxe 2.4 (zero-based): add 1 to all entries
for i in [ 1 .. deg ] do
list[i]:= list[i] + 1;
od;
fi;
res:= PermList( list );
if res = fail then
Info( InfoCMeatAxe, 1,
"not a permutation: ", fname );
fi;
fi;
else
# matrix
nrows := v * head{[5..8]};
ncols := v * head{[9..12]};
# ff elts per byte
a := q;
epb := 0;
while a<=256 do
a := a*q;
epb := epb+1;
od;
# length of row in bytes
lenrow := QuoInt(ncols, epb);
if lenrow*epb < ncols then
lenrow := lenrow+1;
fi;
# map from bytes to element lists
fflist := FFList(GF(q));
poslist := Cartesian(List([1..epb], i-> [0..q-1]));
eltsbyte := List(poslist, a-> fflist{a+1});
# now read line by line
res := [];
for i in [1..nrows] do
bytes := ReadAll(f, lenrow);
bytes := INTLIST_STRING(bytes, 1);
row := Concatenation(eltsbyte{bytes+1});
while Length(row) > ncols do
Unbind(row[Length(row)]);
od;
ConvertToVectorRep(row, q);
Add(res, row);
od;
CloseStream(f);
ConvertToMatrixRep(res);
fi;
return res;
end );
#############################################################################
##
#F ScanStraightLineProgramOrDecision( <strdata>, <mode> )
##
BindGlobal( "ScanStraightLineProgramOrDecision", function( strdata, mode )
local data, echo, line, pos, labels, nrinputs, i, lines, output, a, b, c,
outputs, result, search;
data:= [];
echo:= [];
for line in SplitString( strdata, "", "\n" ) do
# Omit empty lines and comment parts.
if 4 < Length( line ) and line{ [ 1 .. 4 ] } = "echo" then
Add( echo, line );
elif not IsEmpty( line ) then
pos:= Position( line, '#' );
if pos <> fail then
line:= line{ [ 1 .. pos-1 ] };
fi;
line:= SplitString( line, "", " \n" );
if not IsEmpty( line ) then
Add( data, line );
fi;
fi;
od;
# Determine the labels that occur.
labels:= [];
nrinputs:= 0;
if IsEmpty( data ) or data[1][1] <> "inp" then
# There is no `inp' line.
# The default input is given by the labels `1' and `2'.
labels:=[ "1", "2" ];
nrinputs:= 2;
fi;
for line in data do
if line[1] = "inp" then
if Length( line ) = 2 and Int( line[2] ) <> fail then
Append( labels, List( [ 1 .. Int( line[2] ) ], String ) );
nrinputs:= nrinputs + Int( line[2] );
elif Int( line[2] ) = Length( line ) - 2 then
Append( labels, line{ [ 3 .. Length( line ) ] } );
nrinputs:= nrinputs + Length( line ) - 2;
else
Info( InfoCMeatAxe, 1, "corrupted line `", line, "'" );
return fail;
fi;
elif not ( line[1] in [ "cjr", "chor" ] ) then
i:= Length( line );
if not line[i] in labels then
Add( labels, line[i] );
fi;
fi;
od;
# Translate the lines.
lines:= [];
output:= [];
c:= 0;
for line in data do
if line[1] = "oup" or line[1] = "op" then
Add( output, line );
elif line[1] <> "inp" then
if line[1] = "mu" and Length( line ) = 4 then
a:= Position( labels, line[2] );
b:= Position( labels, line[3] );
c:= Position( labels, line[4] );
Add( lines, [ [ a, 1, b, 1 ], c ] );
elif line[1] = "iv" and Length( line ) = 3 then
a:= Position( labels, line[2] );
b:= Position( labels, line[3] );
Add( lines, [ [ a, -1 ], b ] );
elif line[1] = "pwr" and Length( line ) = 4 then
a:= Int( line[2] );
b:= Position( labels, line[3] );
c:= Position( labels, line[4] );
Add( lines, [ [ b, a ], c ] );
elif line[1] = "cjr" and Length( line ) = 3 then
a:= Position( labels, line[2] );
b:= Position( labels, line[3] );
Add( lines, [ [ b, -1, a, 1, b, 1 ], a ] );
elif line[1] = "cp" and Length( line ) = 3 then
a:= Position( labels, line[2] );
b:= Position( labels, line[3] );
Add( lines, [ [ a, 1 ], b ] );
elif line[1] = "cj" and Length( line ) = 4 then
a:= Position( labels, line[2] );
b:= Position( labels, line[3] );
c:= Position( labels, line[4] );
Add( lines, [ [ b, -1, a, 1, b, 1 ], c ] );
elif line[1] = "com" and Length( line ) = 4 then
a:= Position( labels, line[2] );
b:= Position( labels, line[3] );
c:= Position( labels, line[4] );
Add( lines, [ [ a, -1, b, -1, a, 1, b, 1 ], c ] );
# improve: three multiplications and one inversion suffice!
elif line[1] = "chor" and Length( line ) = 3 then
if mode = "program" then
Info( InfoCMeatAxe, 1,
"no \"chor\" lines allowed in straight line programs" );
return fail;
fi;
a:= Position( labels, line[2] );
b:= Int( line[3] );
Add( lines, [ "Order", a, b ] );
else
Info( InfoCMeatAxe, 1, "strange line `", line, "'" );
return fail;
fi;
if a = fail or b = fail or c = fail then
Info( InfoCMeatAxe, 1, "line `", line, "' uses undefined label" );
return fail;
fi;
fi;
od;
# Specify the output.
result:= rec();
if IsEmpty( output ) and mode = "program" then
# The default output is given by the labels `1' and `2'.
# Note that this is allowed only if these labels really occur.
if IsSubset( labels, [ "1", "2" ] ) then
Add( lines, [ [ Position( labels, "1" ), 1 ],
[ Position( labels, "2" ), 1 ] ] );
else
Info( InfoCMeatAxe, 1, "missing `oup' statement" );
return fail;
fi;
elif mode = "program" then
# The `oup' lines list the output labels.
outputs:= [];
for line in output do
if Length( line ) = 2 and Int( line[2] ) <> fail then
Append( outputs, List( [ 1 .. Int( line[2] ) ],
x -> [ Position( labels, String( x ) ), 1 ] ) );
elif Length( line ) = Int( line[2] ) + 2 then
Append( outputs, List( line{ [ 3 .. Length( line ) ] },
x -> [ Position( labels, x ), 1 ] ) );
else
Info( InfoCMeatAxe, 1, "corrupted line `", line, "'" );
return fail;
fi;
od;
if ForAny( outputs, pair -> pair[1] = fail ) then
Info( InfoCMeatAxe, 1, "undefined label used in output line(s)" );
return fail;
fi;
Add( lines, outputs );
# The straight line program is thought for computing
# class representatives,
# and the bijection between the output labels and the class names
# is given by the `echo' lines.
# For the line `oup <l> <b1> <b2> ... <bl>',
# there must be the `echo' line `Classes <n1> <n2> ... <nl>'.
echo:= List( echo, line -> SplitString( line, "", "\" \n" ) );
while not IsEmpty( echo )
and LowercaseString( echo[1][2] ) <> "classes" do
echo:= echo{ [ 2 .. Length( echo ) ] };
od;
if not IsEmpty( echo ) then
# Check that the `echo' lines fit to the `oup' lines.
echo:= List( echo, x -> Filtered( x,
y -> y <> "echo" and LowercaseString( y ) <> "classes" ) );
outputs:= Concatenation( echo );
output:= Sum( List( output, x -> Int( x[2] ) ), 0 );
if Length( outputs ) < output then
Info( InfoCMeatAxe, 1,
"`oup' and `echo' lines not compatible" );
return fail;
fi;
outputs:= outputs{ [ 1 .. output ] };
result.outputs:= outputs;
fi;
fi;
# Construct and return the result.
if mode = "program" then
result.program:= StraightLineProgramNC( lines, nrinputs );
else
result.program:= StraightLineDecisionNC( lines, nrinputs );
fi;
return result;
end );
#############################################################################
##
#F ScanStraightLineDecision( <string> )
##
InstallGlobalFunction( ScanStraightLineDecision,
string -> ScanStraightLineProgramOrDecision( string, "decision" ) );
#############################################################################
##
#F ScanStraightLineProgram( <filename> )
#F ScanStraightLineProgram( <string>, "string" )
##
InstallGlobalFunction( ScanStraightLineProgram, function( arg )
local filename, strdata;
if Length( arg ) = 1 and arg[1] = fail then
# This is used to simplify other programs.
return fail;
elif Length( arg ) = 1 and IsString( arg[1] ) then
# Read the data.
filename:= arg[1];
InfoRead1( "#I reading `", filename, "' started\n" );
strdata:= AGR.StringFile( filename );
InfoRead1( "#I reading `", filename, "' done\n" );
if strdata = fail then
Error( "cannot read file <filename>" );
fi;
elif Length( arg ) = 2 and IsString( arg[1] ) and arg[2] = "string" then
strdata:= arg[1];
else
Error( "usage: ScanStraightLineProgram( <filename>[, \"string\"] )" );
fi;
return ScanStraightLineProgramOrDecision( strdata, "program" );
end );
#############################################################################
##
#F AtlasStringOfProgram( <prog>[, <outputnames>[, <avoidslots>]] )
#F AtlasStringOfProgram( <prog>[, <format>[, <avoidslots>]] )
##
## <avoidslots> refers only to the result list.
##
InstallGlobalFunction( AtlasStringOfProgram, function( arg )
local format, # "ATLAS" or "mtx"
avoidslots, # optional third argument
prog, # straight line program, first argument
outputnames, # list of strings, optional second argument
resused, # maximal label currently used in the program
lines,
str, # string, result
formats, # record
i,
translateword, # local function
line,
lastresult,
namline,
resline,
inline;
# Get and check the arguments.
format:= "ATLAS";
avoidslots:= [];
if Length( arg ) = 1 then
prog:= arg[1];
elif 2 <= Length( arg ) and IsString( arg[2] ) then
prog:= arg[1];
if LowercaseString( arg[2] ) = "mtx" then
format:= "mtx";
fi;
elif 2 <= Length( arg ) and IsList( arg[2] ) then
prog:= arg[1];
outputnames:= arg[2];
fi;
if Length( arg ) = 3 and IsList( arg[3] ) then
avoidslots:= arg[3];
fi;
if IsBound( prog ) and IsStraightLineProgram( prog ) then
resused:= NrInputsOfStraightLineProgram( prog );
lines:= LinesOfStraightLineProgram( prog );
elif IsBound( prog ) and IsStraightLineDecision( prog ) then
resused:= NrInputsOfStraightLineDecision( prog );
lines:= LinesOfStraightLineDecision( prog );
else
Error( "usage: ",
"AtlasStringOfProgram( <prog>[, <outputnames>] )",
"or AtlasStringOfProgram( <prog>[, \"mtx\"] )" );
fi;
str:= "";
if format = "ATLAS" then
# Write the line of inputs.
Append( str, "inp " );
Append( str, String( resused ) );
Add( str, '\n' );
# Define the line formats.
formats:= rec( iv:= l -> Concatenation( "iv ", String( l[1] ),
" ", String( l[2] ), "\n" ),
cp:= l -> Concatenation( "cp ", String( l[1] ),
" ", String( l[2] ), "\n" ),
pw:= l -> Concatenation( "pwr ", String( l[1] ),
" ", String( l[2] ),
" ", String( l[3] ), "\n" ),
mu:= l -> Concatenation( "mu ", String( l[1] ),
" ", String( l[2] ),
" ", String( l[3] ), "\n" ),
cj:= l -> Concatenation( "cj ", String( l[1] ),
" ", String( l[2] ),
" ", String( l[3] ), "\n" ),
ch:= l -> Concatenation( "chor ", String( l[1] ),
" ", String( l[2] ), "\n" ),
);
else
# Write the line that describes the inputs.
Append( str, "# inputs are expected in " );
Append( str, JoinStringsWithSeparator( List( [ 1 .. resused ],
String ), " " ) );
Add( str, '\n' );
# Define the line formats.
formats:= rec( iv:= l -> Concatenation( "ziv ", String( l[1] ),
" ", String( l[2] ), "\n" ),
cp:= l -> Concatenation( "cp ", String( l[1] ),
" ", String( l[2] ), "\n" ),
pw:= l -> Concatenation( "zsm pwr", String( l[1] ),
" ", String( l[2] ),
" ", String( l[3] ), "\n" ),
mu:= l -> Concatenation( "zmu ", String( l[1] ),
" ", String( l[2] ),
" ", String( l[3] ), "\n" ),
cj:= l -> Concatenation( "cj ", String( l[1] ),
" ", String( l[2] ),
" ", String( l[3] ), "\n" ),
ch:= l -> Concatenation( "chor ", String( l[1] ),
" ", String( l[2] ), "\n" ),
);
fi;
# function to translate a word into a series of simple operations
translateword:= function( word, respos )
local used, # maximal label, including intermediate results
new,
i;
if resused < respos then
resused:= respos;
fi;
used:= resused;
if Length( word ) = 2 then
# The word describes a simple powering.
if word[2] = -1 then
Append( str, formats.iv( [ word[1], respos ] ) );
elif word[2] = 1 then
Append( str, formats.cp( [ word[1], respos ] ) );
elif 0 <= word[2] then
Append( str, formats.pw( [ word[2], word[1], respos ] ) );
else
used:= used + 1;
Append( str, formats.iv( [ word[1], used ] ) );
Append( str, formats.pw( [ -word[2], used, respos ] ) );
fi;
elif Length( word ) = 3 and word[1] = "Order" then
Append( str, formats.ch( [ word[2], word[3] ] ) );
elif Length( word ) = 6 and word[2] = -1 and word[4] = 1
and word[6] = 1 and word[1] = word[5] then
# The word describes a conjugation.
Append( str, formats.cj( [ word[3], word[1], respos ] ) );
else
# Get rid of the powerings.
new:= [];
for i in [ 2, 4 .. Length( word ) ] do
if word[i] = 1 then
Add( new, word[ i-1 ] );
elif 0 < word[i] then
used:= used + 1;
Append( str, formats.pw( [ word[i], word[ i-1 ], used ] ) );
Add( new, used );
else
used:= used + 1;
Append( str, formats.iv( [ word[ i-1 ], used ] ) );
if word[i] < -1 then
used:= used + 1;
Append( str, formats.pw( [ -word[i], used-1, used ] ) );
fi;
Add( new, used );
fi;
od;
# Now form the product of the elements in `new'.
if Length( new ) = 1 then
if new[1] <> respos then
Append( str, formats.cp( [ new[1], respos ] ) );
fi;
elif Length( new ) = 2 then
Append( str, formats.mu( [ new[1], new[2], respos ] ) );
else
used:= used + 1;
Append( str, formats.mu( [ new[1], new[2], used ] ) );
for i in [ 3 .. Length( new )-1 ] do
used:= used + 1;
Append( str, formats.mu( [ used-1, new[i], used ] ) );
od;
used:= used + 1;
Append( str, formats.mu( [ used-1, new[ Length( new ) ],
respos ] ) );
fi;
fi;
end;
# Loop over the lines.
for line in lines do
if ForAll( line, IsList ) then
# The list describes the return values.
lastresult:= [];
for i in [ 1 .. Length( line ) ] do
if Length( line[i] ) = 2 and line[i][2] = 1 then
Add( lastresult, String( line[i][1] ) );
else
repeat
resused:= resused + 1;
until not resused in avoidslots;
translateword( line[i], resused );
Add( lastresult, String( resused ) );
fi;
od;
if IsBound( outputnames ) then
if Length( line ) <> Length( outputnames ) then
Error( "<outputnames> has the wrong length" );
fi;
# Write the `echo' statements.
# (Split the output specifications into lines if necessary.)
i:= 1;
namline:= "";
resline:= "";
inline:= 0;
while i <= Length( outputnames ) do
if 60 < Length( namline ) + Length( outputnames[i] )
or 60 < Length( resline ) + Length( lastresult[i] ) then
Append( str,
Concatenation( "echo \"Classes", namline, "\"\n" ) );
Append( str,
Concatenation( "oup ", String( inline ), resline, "\n" ) );
namline:= "";
resline:= "";
inline:= 0;
fi;
Add( namline, ' ' );
Add( resline, ' ' );
Append( namline, outputnames[i] );
Append( resline, lastresult[i] );
inline:= inline + 1;
i:= i + 1;
od;
if inline <> 0 then
Append( str,
Concatenation( "echo \"Classes", namline, "\"\n" ) );
Append( str,
Concatenation( "oup ", String( inline ), resline, "\n" ) );
fi;
elif ForAll( [ 1 .. Length( line ) ], i -> line[i] = [ i, 1 ] ) then
# Write a short output statement.
if format = "ATLAS" then
Append( str, "oup " );
Append( str, String( Length( line ) ) );
Add( str, '\n' );
else
Append( str, "echo \"outputs are in " );
Append( str, JoinStringsWithSeparator(
List( [ 1 .. Length( line ) ], String ), " " ) );
Append( str, "\"\n" );
fi;
elif format = "ATLAS" then
# Write the full output statements.
i:= 1;
resline:= "";
inline:= 0;
while i <= Length( lastresult ) do
if 60 < Length( resline ) + Length( lastresult[i] ) then
Append( str,
Concatenation( "oup ", String( inline ), resline, "\n" ) );
resline:= "";
inline:= 0;
fi;
Add( resline, ' ' );
Append( resline, lastresult[i] );
inline:= inline + 1;
i:= i + 1;
od;
if inline <> 0 then
Append( str,
Concatenation( "oup ", String( inline ), resline, "\n" ) );
fi;
else
Append( str, "echo \"outputs are in " );
Append( str, JoinStringsWithSeparator( lastresult, " " ) );
Append( str, "\"\n" );
fi;
# Return the result.
return str;
else
# Separate word and position where to put the result,
# and translate the line into a sequence of simple steps.
if ForAll( line, IsInt ) then
resused:= resused + 1;
lastresult:= resused;
translateword( line, resused );
elif line[1] = "Order" then
translateword( line, "dummy" );
else
lastresult:= line[2];
translateword( line[1], lastresult );
fi;
fi;
od;
# (If we arrive here then there is exactly one output value.)
# Write the `echo' statements if applicable.
# (This isn't really probable, is it?)
if IsBound( outputnames ) then
if Length( outputnames ) <> 1 then
Error( "<outputnames> has the wrong length" );
fi;
Append( str,
Concatenation( "echo \"Classes ", outputnames[1], "\"\n" ) );
fi;
# Write the output statement in the case of straight line programs.
if IsStraightLineProgram( prog ) then
if format = "ATLAS" then
Append( str, "oup 1 " );
Append( str, String( lastresult ) );
Add( str, '\n' );
else
Append( str, "echo \"outputs are in " );
Append( str, String( lastresult ) );
Append( str, "\"\n" );
fi;
fi;
# Return the result;
return str;
end );
#############################################################################
##
#E