MeatAxe  2.4
Programs for working with modular representations
1 // C MeatAxe - library interfaces
3 //
4 // (C) Copyright 1998-2015 Michael Ringe, Lehrstuhl D fuer Mathematik, RWTH Aachen
5 //
6 // This program is free software; see the file COPYING for details.
12 #include <stdio.h>
13 #include <stdarg.h>
15 #define MTX_VERSION "2.4"
17 #if defined GCC
18 #define MTX_PRINTF_ATTRIBUTE(f,v) __attribute__((format(printf,f,v)))
19 #else
20 #define MTX_PRINTF_ATTRIBUTE(f,v)
21 #endif
23 extern char *MtxVersion;
29 #define FM_READ 0x01
30 #define FM_CREATE 0x02
31 #define FM_APPEND 0x03
32 #define FM_TEXT 0x10
33 #define FM_LIB 0x20
34 #define FM_NOERROR 0x40
39 int SysCreateDirectory(const char *name);
40 int SysGetPid();
41 void SysInit(void);
42 void *SysMalloc(size_t nbytes);
43 FILE *SysFopen(const char *name, int mode);
44 void SysFree(void *x);
45 int SysFseek(FILE *f,long pos);
46 int SysFseekRelative(FILE *file, long distance);
47 void *SysRealloc(void *buf, size_t nbytes);
48 int SysReadLong32(FILE *f, long *buf, int n);
49 #define SysReadLong SysReadLong32
50 int SysReadLongX(FILE *f, long *buf, int n);
51 int SysRemoveDirectory(const char *name);
52 int SysRemoveFile(const char *name);
53 void SysSetTimeLimit(long nsecs);
54 long SysTimeUsed(void);
55 int SysWriteLong32(FILE *f, const long *buf, int n);
56 #define SysWriteLong SysWriteLong32
57 int SysWriteLongX(FILE *f, const long *buf, int n);
59 #define ALLOC(type) ((type *) SysMalloc(sizeof(type)))
60 #define NALLOC(type,n) ((type *) SysMalloc((size_t)(n) * sizeof(type)))
61 #define NREALLOC(x,type,n)\
62  ((type *) SysRealloc(x,(size_t)(n) * sizeof(type)))
63 #define FREE(x) SysFree(x)
69 /* ---------------------------------------------------------------------------------------------- */
76 /* Data types and constants
77  ------------------------ */
79 #if ZZZ==0
81 typedef unsigned char FEL;
82 typedef FEL *PTR;
83 #define FF_ZERO ((FEL)0)
84 #define FF_ONE ((FEL)1)
85 #define ZZZVERSION 6
87 #elif ZZZ==1
89 typedef unsigned short FEL;
90 typedef unsigned short *PTR;
91 #define FF_ZERO ((FEL)0xFFFF)
92 #define FF_ONE ((FEL)0)
93 #define ZZZVERSION 0x101
95 #else
97 #error "ZZZ undefined"
99 #endif
101 /* Kernel variables and functions
102  ------------------------------ */
104 extern int FfOrder;
105 extern int FfChar;
106 extern FEL FfGen;
107 extern int FfNoc;
108 extern size_t FfCurrentRowSize;
111 /* Arithmetic */
112 FEL FfAdd(FEL a, FEL b);
113 FEL FfSub(FEL a, FEL b);
114 FEL FfMul(FEL a, FEL b);
115 FEL FfDiv(FEL a, FEL b);
116 FEL FfNeg(FEL a);
117 FEL FfInv(FEL a);
119 int FfMakeTables(int field);
120 int FfSetField(int field);
121 int FfSetNoc(int noc);
124 void FfAddMulRow(PTR dest, PTR src, FEL f);
125 PTR FfAddRow(PTR dest, PTR src);
126 PTR FfAddRowPartial(PTR dest, PTR src, int first, int len);
127 PTR FfAlloc(int nor);
128 int FfCmpRows(PTR p1, PTR p2);
129 void FfCleanRow(PTR row, PTR matrix, int nor, const int *piv);
130 void FfCleanRow2(PTR row, PTR matrix, int nor, const int *piv, PTR row2);
131 void FfCleanRowAndRepeat(PTR row, PTR mat, int nor, const int *piv,
132  PTR row2, PTR mat2);
133 void FfCopyRow(PTR dest, PTR src);
134 FEL FfEmbed(FEL a, int subfield);
135 FEL FfExtract(PTR row, int col);
136 void FfExtractColumn(PTR mat,int nor,int col,PTR result);
137 int FfFindPivot(PTR row, FEL *mark);
138 void FfFree(PTR x);
139 FEL FfFromInt(int l);
140 PTR FfGetPtr(PTR base, int row);
141 void FfInsert(PTR row, int col, FEL mark);
142 void FfMulRow(PTR row, FEL mark);
143 FILE *FfReadHeader(const char *name, int *fld, int *nor, int *noc);
144 int FfReadRows(FILE *f, PTR buf, int n);
145 FEL FfRestrict(FEL a, int subfield);
146 size_t FfRowSize(int noc);
147 FEL FfScalarProduct(PTR a, PTR b);
148 int FfSeekRow(FILE *f, int pos);
149 int FfStepPtr(PTR *x);
150 void FfSwapRows(PTR dest, PTR src);
151 const char *FfToGap(FEL f);
152 int FfToInt(FEL f);
153 size_t FfTrueRowSize(int noc);
154 FILE *FfWriteHeader(const char *name, int fld, int nor, int noc);
155 int FfWriteRows(FILE *f, PTR buf, int n);
158 /* --------------------------------------------------------------------------
159  Macro versions of kernel functions
160  -------------------------------------------------------------------------- */
163 #if ZZZ==0
165 extern FEL mtx_tmult[256][256];
166 extern FEL mtx_tadd[256][256];
167 extern FEL mtx_taddinv[256], mtx_tmultinv[256];
168 extern FEL mtx_tffirst[256][2];
169 extern FEL mtx_textract[8][256];
170 extern FEL mtx_tnull[8][256];
171 extern FEL mtx_tinsert[8][256];
172 extern long mtx_embedord[4];
173 extern FEL mtx_embed[4][16];
174 extern FEL mtx_restrict[4][256];
176 #define FfAdd(a,b) ((FEL)mtx_tadd[(int)(unsigned char)a][(int)(unsigned char)b])
177 #define FfDiv(a,b) FfMul((a),FfInv(b))
178 #define FfInv(a) (mtx_tmultinv[(int)(unsigned char)a])
179 #define FfMul(a,b) ((FEL)mtx_tmult[(int)(unsigned char)a][(int)(unsigned char)b])
180 #define FfNeg(a) (mtx_taddinv[(int)(unsigned char)a])
181 #define FfSub(a,b) FfAdd((a),FfNeg(b))
183 #elif ZZZ==1
185 #define FfExtract(row,col) ((FEL)((row)[(col)-1]))
186 #define FfInsert(row,col,mark) ((void)((row)[(col)-1] = mark))
189 #endif
193 /* ------------------------------------------------------------------
194  Other low-level functions (zzz2.c)
195  ------------------------------------------------------------------ */
197 void FfMapRow(PTR row, PTR matrix, int nor, PTR result);
198 void FfPermRow(PTR row, const long *perm, PTR result);
199 int FfSumAndIntersection(PTR wrk1, int *nor1, int *nor2, PTR wrk2, int *piv);
202 /* ------------------------------------------------------------------
203  Library initialization and cleanup
204  ------------------------------------------------------------------ */
206 extern int Mtx_IsInitialized;
207 extern int Mtx_IsX86;
208 extern int MtxOpt_UseOldWordGenerator;
210 int MtxInitLibrary();
211 void MtxCleanupLibrary();
227 typedef struct {
228  char *S; /* pointer to NUL terminated string */
229 } String;
231 String StrAlloc(size_t initial_capacity);
232 void StrFree(String *s);
233 void StrAppend(String *s, const char *text);
235 void StrAppendF(String *s, const char *fmt, ...);
237 void StrPrintF(String *s, const char *fmt, ...);
244 /* ------------------------------------------------------------------
245  Application framework
246  ------------------------------------------------------------------ */
248 extern char MtxBinDir[]; /* MeatAxe library directory */
249 extern char MtxLibDir[]; /* MeatAxe program directory */
251 #define APP_MAX_ARGS 50
274 typedef struct
275 {
276  const char *Name;
277  const char *Description;
278  const char *Help;
290 typedef struct
291 {
293  int OrigArgC;
294  const char **OrigArgV;
295  int ArgC;
296  const char **ArgV;
297  int OptEnd;
298  unsigned long IsDone[APP_MAX_ARGS];
299  const char *OptArg;
300  int OptInd;
301  char TempDirName[200];
305 MtxApplication_t *AppAlloc(MtxApplicationInfo_t const *ai, int argc, const char **argv);
306 int AppFree(MtxApplication_t *a);
307 int AppGetOption(MtxApplication_t *app, const char *spec);
308 int AppGetCountedOption(MtxApplication_t *app, const char *spec);
309 const char *AppGetTextOption(MtxApplication_t *app, const char *spec,
310  const char *dflt);
311 int AppGetIntOption(MtxApplication_t *app, const char *spec, int dflt,
312  int min, int max);
313 int AppGetArguments(MtxApplication_t *app, int min_argc, int max_argc);
314 const char *AppCreateTempDir(MtxApplication_t *app);
317  "[<Options>]"
320  " -Q ...................... Quiet, no messages\n" \
321  " -V ...................... Verbose, more messages\n" \
322  " -T <MaxTime> ............ Set CPU time limit [s]\n"
325 /* ------------------------------------------------------------------
326  Messages and error handling
327  ------------------------------------------------------------------ */
328  /* Error message codes (%E arguments) */
329 #define MTX_ERR_NOMEM 1 /* Not enough memory */
330 #define MTX_ERR_GAME_OVER 2 /* Time limit exceeded */
331 #define MTX_ERR_DIV0 8 /* Division by 0 or singular Matrix */
332 #define MTX_ERR_FILEFMT 24 /* Bad format */
333 #define MTX_ERR_BADARG 31 /* Bad argument */
334 #define MTX_ERR_RANGE 33 /* Out of range */
335 #define MTX_ERR_NOTECH 34 /* Matrix not in chelon form */
336 #define MTX_ERR_NOTSQUARE 35 /* Matrix not square */
337 #define MTX_ERR_INCOMPAT 36 /* Arguments are incompatible */
338 #define MTX_ERR_BADUSAGE 41 /* Bad command line */
339 #define MTX_ERR_OPTION 42 /* Bad usage of option */
340 #define MTX_ERR_NARGS 43 /* Bad number of arguments */
341 #define MTX_ERR_NOTMATRIX 51 /* Not a matrix */
342 #define MTX_ERR_NOTPERM 53 /* Not a permutation */
349 typedef struct { const char *Name; const char *BaseName; } MtxFileInfo_t;
354 typedef struct { const MtxFileInfo_t *FileInfo; int LineNo; const char *Text; }
357 typedef void MtxErrorHandler_t(const MtxErrorRecord_t *);
359 #define MTX_DEFINE_FILE_INFO \
360  static MtxFileInfo_t Mtx_ThisFile = { __FILE__, NULL };
362 int MtxError(MtxFileInfo_t *fi, int line, const char *text, ...);
366 #define MTX_ERROR(msg) MtxError(&Mtx_ThisFile,__LINE__,msg)
367 #define MTX_ERROR1(msg,a1) MtxError(&Mtx_ThisFile,__LINE__,msg,a1)
368 #define MTX_ERROR2(msg,a1,a2) MtxError(&Mtx_ThisFile,__LINE__,msg,a1,a2)
369 #define MTX_ERROR3(msg,a1,a2,a3) MtxError(&Mtx_ThisFile,__LINE__,msg,a1,a2,a3)
370 #define MTX_ERROR4(msg,a1,a2,a3,a4) MtxError(&Mtx_ThisFile,__LINE__,\
371  msg,a1,a2,a3,a4)
372 #define MTX_ERROR5(msg,a1,a2,a3,a4,a5) MtxError(&Mtx_ThisFile,__LINE__,\
373  msg,a1,a2,a3,a4,a5)
374 #define MTX_ERROR7(msg,a1,a2,a3,a4,a5,a6,a7) MtxError(&Mtx_ThisFile,__LINE__,\
375  msg,a1,a2,a3,a4,a5,a6,a7)
378 #define MTX_VERIFY(e) ((void)((e) ||\
379  MtxError(&Mtx_ThisFile,__LINE__,"Assertion failed: %s",#e)))
381 #ifdef _DEBUG
382 #define DEBUG 1
383 #endif
385 #ifdef DEBUG
386 #define MTX_ASSERT(e) MTX_VERIFY(e)
387 #else
388 #define MTX_ASSERT(e)
389 #undef PARANOID
390 #endif
394 /* ------------------------------------------------------------------
395  Messages
396  ------------------------------------------------------------------ */
398 int MtxFormatMessage(char *buf, int bufsize, const char *msg, va_list al);
399 int MtxPrintMessage(FILE *f, const char *fmt, ...);
401 extern int MtxMessageLevel;
402 #define MSG0 (MtxMessageLevel >= 0)
403 #define MSG1 (MtxMessageLevel >= 1)
404 #define MSG2 (MtxMessageLevel >= 2)
405 #define MSG3 (MtxMessageLevel >= 3)
406 #define MSG4 (MtxMessageLevel >= 4)
407 #define MESSAGE(level,args)\
408  (MtxMessageLevel>=(level) ? ( printf args , fflush(stdout), 1) : 0 )
411 /* ------------------------------------------------------------------
412  Miscellaneous
413  ------------------------------------------------------------------ */
415 void MtxRandomInit(unsigned seed);
416 long int MtxRandom(void);
417 int MtxRandomInt(int max);
418 long gcd(long a, long b);
419 long lcm(long a, long b);
422 /* ------------------------------------------------------------------
423  Structured text files (stfXXX.c)
424  ------------------------------------------------------------------ */
430 typedef struct
431 {
432  FILE *File;
433  char *LineBuf;
434  char *GetPtr;
436  int OutPos;
437  int LineNo;
438 } StfData;
440 int StfClose(StfData *f);
441 StfData *StfOpen(const char *name, int mode);
443 int StfPut(StfData *f, const char *text);
444 int StfPutInt(StfData *f, int value);
445 int StfPutString(StfData *f, const char *text);
446 int StfPutVector(StfData *f, int size, const int *value);
447 int StfBeginEntry(StfData *f, const char *name);
448 int StfEndEntry(StfData *f);
449 int StfWriteValue(StfData *f, const char *name, const char *value);
450 int StfWriteInt(StfData *f, const char *name, int value);
451 int StfWriteString(StfData *f, const char *name, const char *value);
452 int StfWriteVector(StfData *f, const char *name, int size, const int *value);
454 int StfReadLine(StfData *f);
455 const char *StfGetName(StfData *f);
456 int StfGetInt(StfData *f, int *buf);
457 int StfGetString(StfData *f, char *buf, size_t bufsize);
458 int StfMatch(StfData *f, const char *pattern);
459 int StfGetVector(StfData *f, int *bufsize, int *buf);
462 /* ------------------------------------------------------------------
463  MeatAxe files
464  ------------------------------------------------------------------ */
469 typedef struct
470 {
471  unsigned long Magic;
472  int Field;
473  int Nor;
474  int Noc;
475  FILE *File;
476  char *Name;
477 } MtxFile_t;
479 int MfIsValid(const MtxFile_t *file);
480 MtxFile_t *MfOpen(const char *name);
481 MtxFile_t *MfCreate(const char *name, int field, int nor, int noc);
482 int MfClose(MtxFile_t *file);
483 int MfReadLong(MtxFile_t *f, long *buf, int nrows);
484 int MfReadRows(MtxFile_t *f, PTR buf, int nrows);
485 int MfWriteLong(MtxFile_t *f, const long *buf, int count);
486 int MfWriteRows(MtxFile_t *f, PTR buf, int nrows);
489 /* ---------------------------------------------------------------------------------------------- */
492 typedef struct
493 {
494  unsigned long Magic;
495  int Field;
496  int Nor;
497  int Noc;
499  size_t RowSize;
500  int *PivotTable;
501 } Matrix_t;
503 Matrix_t *MatAdd(Matrix_t *dest, const Matrix_t *src);
504 Matrix_t *MatAddMul(Matrix_t *dest, const Matrix_t *src, FEL coeff);
505 Matrix_t *MatAlloc(int field, int nor, int noc);
506 int MatClean(Matrix_t *mat, const Matrix_t *sub);
507 int MatCompare(const Matrix_t *a, const Matrix_t *b);
508 int MatCopyRegion(Matrix_t *dest, int destrow, int destcol,
509  const Matrix_t *src, int row1, int col1, int nrows, int ncols);
510 Matrix_t *MatCut(const Matrix_t *src, int row1, int col1, int nrows, int ncols);
511 Matrix_t *MatCutRows(const Matrix_t *src, int row1, int nrows);
512 Matrix_t *MatDup(const Matrix_t *src);
513 int MatEchelonize(Matrix_t *mat);
514 int MatFree(Matrix_t *mat);
515 PTR MatGetPtr(const Matrix_t *mat, int row);
516 Matrix_t *MatId(int fl, int nor);
517 Matrix_t *MatInverse(const Matrix_t *src);
518 int MatIsValid(const Matrix_t *m);
519 Matrix_t *MatLoad(const char *fn);
520 Matrix_t *MatMul(Matrix_t *dest, const Matrix_t *src);
521 Matrix_t *MatMulScalar(Matrix_t *dest, FEL coeff);
522 long MatNullity(const Matrix_t *mat);
523 long MatNullity__(Matrix_t *mat);
524 Matrix_t *MatNullSpace(const Matrix_t *mat);
525 Matrix_t *MatNullSpace_(Matrix_t *mat, int flags);
527 int MatOrder(const Matrix_t *mat);
528 int MatPivotize(Matrix_t *mat);
529 Matrix_t *MatPower(const Matrix_t *mat, long n);
530 void MatPrint(const char *name, const Matrix_t *m);
531 Matrix_t *MatRead(FILE *f);
532 int MatSave(const Matrix_t *mat, const char *fn);
533 FEL MatTrace(const Matrix_t *mat);
534 Matrix_t *MatTransposed(const Matrix_t *src);
535 int MatWrite(const Matrix_t *mat, FILE *f);
537 /* For internal use only */
538 void Mat_DeletePivotTable(Matrix_t *mat);
542 /* ------------------------------------------------------------------
543  Greased matrices
544  ------------------------------------------------------------------ */
551 typedef struct {
552  long ***tabs; /* tables for different remainders
553  of byte numbers mod grrows */
554  int *nrvals; /* number of values produced by each table */
555  int nrtabs; /* number of tables used */
558 const GrExtractionTable_t *GrGetExtractionTable(int fl,int grrows);
565 typedef struct
566 {
567  unsigned long Magic;
568  int Field, Nor, Noc;
569  int GrRows; /* Grease level (# of rows, 0=no grease) */
570  int GrBlockSize; /* Vectors per block (= Field^GrRows) */
571  int NumVecs; /* Total number of vectors in <PrecalcData> */
572  PTR PrecalcData; /* Precalculated data */
573  const GrExtractionTable_t
574  *ExtrTab; /* Extraction table */
575  int MPB; /* Number of marks per byte */
578 void GrMapRow(PTR v,GreasedMatrix_t *M, PTR w);
579 GreasedMatrix_t *GrMatAlloc(const Matrix_t *m, int gr_rows);
580 int GrMatFree(GreasedMatrix_t *mat);
581 int GrMatIsValid(const GreasedMatrix_t *mat);
585 /* ------------------------------------------------------------------
586  Permutations
587  ------------------------------------------------------------------ */
590 typedef struct
591 {
592  unsigned long Magic;
593  int Degree;
594  long *Data;
595 } Perm_t;
598 Perm_t *PermAlloc(int deg);
599 int PermCompare(const Perm_t *a, const Perm_t *b);
600 Perm_t *PermDup(const Perm_t *src);
601 int PermFree(Perm_t *p);
602 Perm_t *PermInverse(const Perm_t *src);
603 int PermIsValid(const Perm_t *p);
604 Perm_t *PermLoad(const char *fn);
605 Perm_t *PermMul(Perm_t *dest, const Perm_t *src);
606 int PermOrder(const Perm_t *perm);
607 void PermPrint(const char *name, const Perm_t *perm);
608 Perm_t *PermPower(const Perm_t *p, int n);
609 Perm_t *PermRead(FILE *f);
610 int PermSave(const Perm_t *perm, const char *fn);
611 int PermWrite(const Perm_t *perm, FILE *f);
613 void Perm_ConvertOld(long *data, int len);
615 /* ------------------------------------------------------------------
616  Polynomials
617  ------------------------------------------------------------------ */
619 typedef struct
620 {
621  unsigned long Magic;
622  int Field;
623  int Degree;
626  int BufSize;
627 }
628 Poly_t;
631 Poly_t *PolAdd(Poly_t *dest, const Poly_t *src);
632 Poly_t *PolAlloc(int fl, int n);
633 int PolCompare(const Poly_t *a, const Poly_t *b);
634 Poly_t *PolDerive(Poly_t *pol);
635 Poly_t *PolDivMod(Poly_t *a, const Poly_t *b);
636 Poly_t *PolDup(const Poly_t *p);
637 int PolFree(Poly_t *p);
638 Poly_t *PolGcd(const Poly_t *a, const Poly_t *b);
639 int PolGcdEx(const Poly_t *a, const Poly_t *b, Poly_t **result);
640 int PolIsValid(const Poly_t *p);
641 Poly_t *PolMod(Poly_t *a, const Poly_t *b);
642 void Pol_Normalize(Poly_t *p);
643 Poly_t *PolLoad(const char *fn);
644 Poly_t *PolMul(Poly_t *dest, const Poly_t *src);
645 void PolPrint(char *name, const Poly_t *p);
646 Poly_t *PolRead(FILE *f);
647 int PolSave(const Poly_t *pol, const char *fn);
648 int PolWrite(const Poly_t *p, FILE *f);
652 /* ------------------------------------------------------------------
653  Factored polynomials
654  ------------------------------------------------------------------ */
656 typedef struct
657 {
658  unsigned long Magic;
659  int NFactors;
660  int BufSize;
662  int *Mult;
663 } FPoly_t;
665 FPoly_t *FpAlloc();
666 int FpFree(FPoly_t *x);
667 int FpIsValid(const FPoly_t *p);
668 FPoly_t *FpMul(FPoly_t *dest, const FPoly_t *src);
669 FPoly_t *FpMulP(FPoly_t *dest, const Poly_t *src, int pwr);
670 int FpPrint(const char *name, const FPoly_t *p);
672 /* ---------------------------------------------------------------------------------------------- */
674 typedef struct
675 {
676  unsigned long Magic;
677  int Size;
678  int BufSize;
679  long Data[1];
681 } BitString_t;
683 BitString_t *BsAlloc(int size);
684 int BsAnd(BitString_t *dest, const BitString_t *src);
685 int BsClear(BitString_t *bs, int i);
686 int BsClearAll(BitString_t *bs);
687 int BsCompare(const BitString_t *a, const BitString_t *b);
688 BitString_t *BsCopy(BitString_t *dest, const BitString_t *src);
689 BitString_t *BsDup(const BitString_t *src);
690 int BsFree(BitString_t *bs);
691 int BsIntersectionCount(const BitString_t *a, const BitString_t *b);
692 int BsIsSub(const BitString_t *a, const BitString_t *b);
693 int BsIsValid(const BitString_t *bs);
694 int BsMinus(BitString_t *dest, const BitString_t *src);
695 int BsOr(BitString_t *dest, const BitString_t *src);
696 void BsPrint(const char *name, const BitString_t *bs);
697 BitString_t *BsRead(FILE *f);
698 int BsSet(BitString_t *bs, int i);
699 int BsTest(const BitString_t *bs, int i);
700 int BsWrite(BitString_t *bs, FILE *f);
702 #ifndef DEBUG
704 #define BS_BPL (sizeof(long) * 8)
705 #define BsSet(bs,i) ((bs)->Data[(i) / BS_BPL] |= 1L << ((i) % BS_BPL))
706 #define BsClear(bs,i) ((bs)->Data[(i) / BS_BPL] &= ~(1L << ((i) % BS_BPL)))
707 #define BsTest(bs,i) (((bs)->Data[(i) / BS_BPL] & (1L << ((i) % BS_BPL))) != 0 ? 1 : 0)
709 #endif
712 /* ------------------------------------------------------------------
713  Sets
714  ------------------------------------------------------------------ */
716 typedef struct
717 {
718  unsigned long Magic;
719  int Size;
720  int BufSize;
721  long *Data;
722 } Set_t;
725 Set_t *SetAlloc();
726 int SetContains(const Set_t *set, long elem);
727 Set_t *SetDup(const Set_t *s);
728 int SetFree(Set_t *x);
729 int SetInsert(Set_t *set, long elem);
730 int SetIsValid(const Set_t *s);
731 int SetPrint(char *name, const Set_t *s);
734 /* ------------------------------------------------------------------
735  Integer matrices
736  ------------------------------------------------------------------ */
738 typedef struct
739 {
740  unsigned long Magic;
741  int Nor;
742  int Noc;
743  long *Data;
744 } IntMatrix_t;
746 IntMatrix_t *ImatAlloc(int nor, int noc);
747 int ImatFree(IntMatrix_t *mat);
748 int ImatIsValid(const IntMatrix_t *m);
749 IntMatrix_t *ImatLoad(const char *fn);
750 IntMatrix_t *ImatRead(FILE *f);
751 int ImatSave(const IntMatrix_t *mat, const char *file_name);
752 int ImatWrite(const IntMatrix_t *mat, FILE *f);
755 /* --------------------------------------------------------------------------
756  Polymorphic objects
757  -------------------------------------------------------------------------- */
759 void *XDup(void *a);
760 int XIsCompatible(void *a, void *b);
761 void XFree(void *a);
762 void *XInverse(void *a);
763 void *XLoad(const char *fn);
764 void XMul(void *a, void *b);
765 long XOrder(void *a);
766 void *XPower(void *a, int n);
767 int XSave(void *a, const char *fn);
775 /* --------------------------------------------------------------------------
776  Matrix sets
777  -------------------------------------------------------------------------- */
783 typedef struct
784 {
785  Matrix_t *Matrix;
786  int PivRow;
787  int PivCol;
788  FEL PivMark;
795 typedef struct {
796  unsigned long Magic;
797  int Len;
798  MatrixSetElement_t *List;
799 } MatrixSet_t;
802 int MsClean(const MatrixSet_t *set, Matrix_t *mat);
803 int MsCleanAndAppend(MatrixSet_t *set, Matrix_t *mat);
804 int MsFree(MatrixSet_t *set);
805 int MsIsValid(const MatrixSet_t *set);
809 /* --------------------------------------------------------------------------
810  Matrix representations
811  -------------------------------------------------------------------------- */
813 typedef struct
814 {
815  unsigned long Magic;
816  int NGen;
817  Matrix_t **Gen;
818 } MatRep_t;
820 #define MR_COPY_GENERATORS 0x0001
822 int MrAddGenerator(MatRep_t *rep, Matrix_t *gen, int flags);
823 MatRep_t *MrAlloc(int ngen, Matrix_t **gen, int flags);
824 int MrChangeBasis(MatRep_t *rep, const Matrix_t *trans);
825 int MrIsValid(const MatRep_t *rep);
826 int MrFree(MatRep_t *rep);
827 MatRep_t *MrLoad(const char *basename, int ngen);
828 int MrSave(const MatRep_t *rep, const char *basename);
829 MatRep_t *MrTransposed(const MatRep_t *rep);
833 /* ------------------------------------------------------------------
834  The word generator
835  ------------------------------------------------------------------ */
837 typedef struct
838 {
839  const MatRep_t *Rep;
840  Matrix_t *Basis[8];
841  int N2[8];
842  int *Description;
843 } WgData_t;
846 WgData_t *WgAlloc(const MatRep_t *rep);
847 int *WgDescribeWord(WgData_t *b, long n);
848 int WgFree(WgData_t *b);
849 Matrix_t *WgMakeWord(WgData_t *b, long n);
850 void WgMakeFingerPrint(WgData_t *b, int fp[6]);
851 const char *WgSymbolicName(WgData_t *b, long n);
857 /* ------------------------------------------------------------------
858  Spin-up, Split, Quotients, etc.
859  ------------------------------------------------------------------ */
861 #define SF_FIRST 0x0001 /* Try only the first seed vector */
862 #define SF_EACH 0x0002 /* Try each seed vector */
863 #define SF_MAKE 0x0004 /* Try all 1-dimensional subspaces */
864 #define SF_SUB 0x0010 /* Try until finding a proper subspace */
865 #define SF_CYCLIC 0x0020 /* Try until finding a cyclic vector */
866 #define SF_COMBINE 0x0040 /* Combine the spans */
867 #define SF_SEED_MASK 0x000F
868 #define SF_MODE_MASK 0x00F0
869 #define SF_STD 0x0100 /* Spin up 'canonically' */
871 Matrix_t *QProjection(const Matrix_t *subspace, const Matrix_t *vectors);
872 Matrix_t *QAction(const Matrix_t *sub, const Matrix_t *gen);
873 Matrix_t *SAction(const Matrix_t *sub, const Matrix_t *gen);
875 typedef struct
876 {
877  int MaxSubspaceDimension;
878  int MaxTries;
879  int Result;
880 } SpinUpInfo_t;
882 int SpinUpInfoInit(SpinUpInfo_t *info);
883 Matrix_t *SpinUp(const Matrix_t *seed, const MatRep_t *rep, int flags,
884  IntMatrix_t **script, SpinUpInfo_t *info);
885 Matrix_t *SpinUpWithScript(const Matrix_t *seed, const MatRep_t *rep,
886  const IntMatrix_t *script);
887 int Split(Matrix_t *subspace, const MatRep_t *rep,
888  MatRep_t **sub, MatRep_t **quot);
890 int ConvertSpinUpScript(IntMatrix_t *script);
892 Matrix_t *SpinUpWithPermutations(const Matrix_t *seed, int ngen,
893  const Perm_t **gen, int flags, IntMatrix_t **script, SpinUpInfo_t *info);
896 /* ------------------------------------------------------------------
897  Seed vector generator
898  ------------------------------------------------------------------ */
900 long MakeSeedVector(const Matrix_t *basis, long lastno, PTR vec);
904 /* ------------------------------------------------------------------
905  Miscellaneous algorithms
906  ------------------------------------------------------------------ */
908 Matrix_t *MatInsert_(Matrix_t *mat, const Poly_t *pol);
909 Matrix_t *MatInsert(const Matrix_t *mat, const Poly_t *pol);
910 int IsSubspace(const Matrix_t *sub, const Matrix_t *space, int ngen);
912 Matrix_t *MatTensor(const Matrix_t *m1, const Matrix_t *m2);
913 int MatrixToVector(const Matrix_t *mat, Matrix_t *vecs, int n);
914 Matrix_t *VectorToMatrix(Matrix_t *vecs, int n, int noc);
915 Matrix_t *TensorMap(Matrix_t *vec, const Matrix_t *a, const Matrix_t *b);
917 int StablePower(const Matrix_t *mat, int *pwr, Matrix_t **ker);
918 int StablePower_(Matrix_t *mat, int *pwr, Matrix_t **ker);
922 /* ------------------------------------------------------------------
923  Polynomial factorization (Berlekamp algorithm)
924  ------------------------------------------------------------------ */
926 FPoly_t *Factorization(const Poly_t *pol);
930 /* ------------------------------------------------------------------
931  Characteristic and minimal polynomials (charpol.c, minpol.c)
932  ------------------------------------------------------------------ */
934 extern long CharPolSeed;
935 Poly_t *CharPolFactor(const Matrix_t *mat);
936 FPoly_t *CharPol(const Matrix_t *mat);
938 FPoly_t *MinPol(Matrix_t *mat);
942 /* ------------------------------------------------------------------
943  The lattice package
944  ------------------------------------------------------------------ */
950 #define MAXGEN 20 /* Max. number of generators */
951 #define LAT_MAXCF 200 /* Max. number of composition factors */
952 #define MAXCYCL 30000 /* Max. number of cyclic submodules */
953 #define MAXDOTL 90000 /* Max. number of dotted lines */
954 #define MAXNSUB 20000 /* Max. number of submodules */
955 #define LAT_MAXBASENAME 100
957 typedef struct
958 {
959  long dim, num, mult;
960  long idword; /* Identifying word */
961  Poly_t *idpol;
962  long peakword; /* Peak word */
963  Poly_t *peakpol;
964  long nmount; /* Number of mountains */
965  long ndotl; /* Number of dotted lines */
966  long spl; /* Degree of splitting field */
967 }
968 CfInfo;
970 typedef struct
971 {
972  char BaseName[LAT_MAXBASENAME];
973  int Field;
974  int NGen;
975  int NCf;
976  CfInfo Cf[LAT_MAXCF];
977  int NSocles;
978  int *Socle;
979  int NHeads;
980  int *Head;
981 } Lat_Info;
983 int Lat_ReadInfo(Lat_Info *li, const char *basename);
984 int Lat_WriteInfo(const Lat_Info *li);
985 const char *Lat_CfName(const Lat_Info *li, int cf);
986 int Lat_AddHead(Lat_Info *li, int *mult);
987 int Lat_AddSocle(Lat_Info *li, int *mult);
990 #define LAT_RG_INVERT 0x0001 /* Invert generators */
991 #define LAT_RG_TRANSPOSE 0x0002 /* Transpose generators */
992 #define LAT_RG_STD 0x0004 /* Use standard form */
994 MatRep_t *Lat_ReadCfGens(Lat_Info *info, int cf, int flags);
1001 /* ------------------------------------------------------------------
1002  Tensor condensation package
1003  ------------------------------------------------------------------ */
1013 typedef struct
1014 {
1015  char NameM[LAT_MAXBASENAME];
1016  char NameN[LAT_MAXBASENAME];
1017  int Dim;
1018  int NCf;
1019  int CfIndex[2][LAT_MAXCF];
1020 } TkData_t;
1022 int TK_ReadInfo(TkData_t *tki, const char *name);
1023 int TK_WriteInfo(TkData_t *tki, const char *name);
1028 /* !!!!!!!!!!!!!!! 2.3 STUFF below !!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!! */
1029 /* !!!!!!!!!!!!!!! 2.3 STUFF below !!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!! */
1030 /* !!!!!!!!!!!!!!! 2.3 STUFF below !!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!! */
1034 /* ------------------------------------------------------------------
1035  Return codes
1036  ------------------------------------------------------------------ */
1038 #define EXIT_OK 0 /* Exit code: normal end */
1039 #define EXIT_ERR 1 /* error */
1043 /* ------------------------------------------------------------------
1044  Function operating on representations and vector spaces
1045  ------------------------------------------------------------------ */
1047 int IsIsomorphic(const MatRep_t *rep1, const CfInfo *info1,
1048  const MatRep_t *rep2, Matrix_t **trans, int use_pw);
1049 int MakeEndomorphisms(const MatRep_t *rep, const Matrix_t *nsp,
1050  Matrix_t *endo[]);
1051 Matrix_t *HomogeneousPart(MatRep_t *m, MatRep_t *s, Matrix_t *npw,
1052  const IntMatrix_t *op, int dimends);
1056 /* ------------------------------------------------------------------
1057  Lattice drawing functions
1058  ------------------------------------------------------------------ */
1063 typedef struct
1064 {
1065  double PosX, PosY; /* Position [0..1] */
1066  unsigned long UserData; /* User-defined attributes */
1067  int Layer; /* Layer number */
1068  double Score; /* Used in optimization */
1069  int ScoreCount;
1070 } LdNode_t;
1075 typedef struct
1076 {
1077  int NNodes;
1078  LdNode_t *Nodes;
1079  int *IsSub; /* Incidence relation, <NNodes> * <NNodes> entries */
1080  int *LayerNo; /* Layer numbers */
1081  int NLayers;
1082 } LdLattice_t;
1084 #define LD_ISSUB(l,i,k) ((l)->IsSub[(i) * (l)->NNodes + (k)])
1086 LdLattice_t *LdAlloc(int num_nodes);
1087 int LdFree(LdLattice_t *l);
1088 int LdAddIncidence(LdLattice_t *lat, int sub, int sup);
1089 int LdSetPositions(LdLattice_t *l);
1094 /* OLD STUFF */
1095 int ChangeBasisOLD(const Matrix_t *M, int ngen, const Matrix_t *gen[],
1096  Matrix_t *newgen[]);
1099 #endif /* !defined(_MEATAXE_H_) */
Poly_t ** Factor
List of irreducible factors.
Definition: meataxe.h:661
FPoly_t * Factorization(const Poly_t *pol)
Factor a polynomial.
Definition: berlekmp.c:275
int Nor
Number of rows.
Definition: meataxe.h:496
IntMatrix_t * ImatAlloc(int nor, int noc)
Create a new integer matrix.
Definition: imatcore.c:61
int FfOrder
The current field order.
Definition: zzz2.c:30
const char ** OrigArgV
Original argv from main().
Definition: meataxe.h:294
Matrix_t * SpinUpWithScript(const Matrix_t *seed, const MatRep_t *rep, const IntMatrix_t *script)
Spin-up with script.
Definition: spinup2.c:56
int SysRemoveDirectory(const char *name)
Removes a directory (which must be empty).
Definition: os.c:289
int MatWrite(const Matrix_t *mat, FILE *f)
Write a matrix to a file.
Definition: matwrite.c:27
int PolIsValid(const Poly_t *p)
Check a polynomial.
Definition: polcore.c:48
void StrFree(String *s)
Free a string.
Definition: string.c:132
FPoly_t * FpMul(FPoly_t *dest, const FPoly_t *src)
Multiply factored polynomials.
Definition: fpmul2.c:27
FEL FfNeg(FEL a)
Finite field negative.
int PolFree(Poly_t *p)
Free a polynomial This function frees a polynomial data structure and cleans up all internal data...
Definition: polcore.c:123
void StrAppend(String *s, const char *text)
Appends text to the end of a string.
Definition: string.c:166
int FfToInt(FEL f)
Convert field element to integer.
Definition: kernel-0.c:687
int StfWriteVector(StfData *f, const char *name, int size, const int *value)
Write a vector.
Definition: stfwrite.c:300
Perm_t * PermPower(const Perm_t *p, int n)
Power of a permutation This function calculates the n-th power of a permutation.
Definition: permpwr.c:29
Matrix_t * SpinUpWithPermutations(const Matrix_t *seed, int ngen, const Perm_t **gen, int flags, IntMatrix_t **script, SpinUpInfo_t *info)
Spin Up With Permutations.
Definition: spinup.c:562
int ArgC
Number of arguments.
Definition: meataxe.h:295
BitString_t * BsRead(FILE *f)
Read a bit string from a file.
Definition: bsread.c:24
FEL FfFromInt(int l)
Convert integer to field element.
Definition: kernel-0.c:670
int StfGetString(StfData *f, char *buf, size_t bufsize)
Read a string.
Definition: stfread.c:201
FILE * File
The stream we're using.
Definition: meataxe.h:432
WgData_t * WgAlloc(const MatRep_t *rep)
Initialize the word generator.
Definition: wgen.c:416
MatRep_t * MrLoad(const char *basename, int ngen)
Load a Matrix Representation.
Definition: mrread.c:37
const char * Help
Help text.
Definition: meataxe.h:278
Structured text file.
Definition: meataxe.h:430
char * Name
File name.
Definition: meataxe.h:476
int * Description
Symbolic description of a word.
Definition: meataxe.h:842
int MatSave(const Matrix_t *mat, const char *fn)
Write a matrix to a file.
Definition: matwrite.c:60
int Size
Number of elements.
Definition: meataxe.h:719
void FfPermRow(PTR row, const long *perm, PTR result)
Multiply a Vector by a Permutation.
Definition: zpermrow.c:29
int Noc
Number of columns.
Definition: meataxe.h:474
long CharPolSeed
Seed for Characteristic Polynomial.
Definition: charpol.c:29
int GrMatIsValid(const GreasedMatrix_t *mat)
Check a greased matrix.
Definition: grmatcore.c:45
int FfReadRows(FILE *f, PTR buf, int n)
Read Rows This function reads 1 or more rows from a file.
Definition: ffio.c:28
int BsClear(BitString_t *bs, int i)
Clear one bit in a bit string.
void MtxRandomInit(unsigned seed)
Initializes the random number generator.
Definition: random.c:39
Poly_t * CharPolFactor(const Matrix_t *mat)
Characteristic Polynomial.
Definition: charpol.c:202
int MatClean(Matrix_t *mat, const Matrix_t *sub)
Clean a matrix.
Definition: matclean.c:28
PTR Data
Data, organized as array of rows.
Definition: meataxe.h:498
int OptInd
Used internally.
Definition: meataxe.h:300
int BufSize
Used internally for memory management.
Definition: meataxe.h:626
int MsClean(const MatrixSet_t *set, Matrix_t *mat)
Clean a matrix with a matrix set.
Definition: msclean.c:48
unsigned long Magic
Used internally.
Definition: meataxe.h:658
int StfPutInt(StfData *f, int value)
Write an integer.
Definition: stfwrite.c:54
int PermIsValid(const Perm_t *p)
Check a permutation.
Definition: permcore.c:54
int BufSize
Used internally for memory management.
Definition: meataxe.h:660
void FfExtractColumn(PTR mat, int nor, int col, PTR result)
Extract one column of a matrix.
Definition: kernel-0.c:865
int SysFseek(FILE *f, long pos)
Set file pointer.
Definition: os.c:255
int SpinUpInfoInit(SpinUpInfo_t *info)
Initialize spin-up parameters.
Definition: spinup.c:584
int SetIsValid(const Set_t *s)
Check a set.
Definition: setcore.c:39
MeatAxe data file object.
Definition: meataxe.h:469
int BsFree(BitString_t *bs)
Free a bit string.
Definition: bscore.c:112
char MtxBinDir[]
MeatAxe Binary Directory.
Definition: args.c:118
int FfFindPivot(PTR row, FEL *mark)
Find pivot column.
Definition: kernel-0.c:968
int ImatIsValid(const IntMatrix_t *m)
Check an integer matrix.
Definition: imatcore.c:38
A pointer to a row vector.
Definition: meataxe.h:82
const char * StfGetName(StfData *f)
Get entry name.
Definition: stfread.c:88
int FfChar
Characteristic of the current field.
Definition: zzz2.c:24
int * Mult
Multiplicity of each factor.
Definition: meataxe.h:662
char MtxLibDir[]
MeatAxe Library Directory.
Definition: args.c:130
long * Data
The elements in ascending order.
Definition: meataxe.h:721
unsigned char FEL
A finite field element.
Definition: meataxe.h:81
int MrChangeBasis(MatRep_t *rep, const Matrix_t *trans)
Change basis.
Definition: chbasis.c:27
int * WgDescribeWord(WgData_t *b, long n)
Creates a symbolic description of a word.
Definition: wgen.c:328
int BsWrite(BitString_t *bs, FILE *f)
Write a bit string to a file.
Definition: bswrite.c:25
Matrix_t * SpinUp(const Matrix_t *seed, const MatRep_t *rep, int flags, IntMatrix_t **script, SpinUpInfo_t *info)
Spin up.
Definition: spinup.c:540
Source file information.
Definition: meataxe.h:349
int StablePower_(Matrix_t *mat, int *pwr, Matrix_t **ker)
Stable power of a matrix.
Definition: stabpwr.c:37
long MakeSeedVector(const Matrix_t *basis, long lastno, PTR vec)
Generates the next seed vector.
Definition: genseed.c:58
int PermCompare(const Perm_t *a, const Perm_t *b)
Compare two permutations.
Definition: permcmp.c:34
int * Socle
Definition: meataxe.h:978
int NSocles
Loewy length.
Definition: meataxe.h:977
A polynomial over a finite field.
Definition: meataxe.h:619
int MatFree(Matrix_t *mat)
Delete a matrix.
Definition: matcore.c:191
IntMatrix_t * ImatLoad(const char *fn)
Read an integer matrix from a file.
Definition: imatread.c:59
int StfWriteInt(StfData *f, const char *name, int value)
Write an enteger.
Definition: stfwrite.c:263
A bit string.
Definition: meataxe.h:674
int StfBeginEntry(StfData *f, const char *name)
Start a new entry.
Definition: stfwrite.c:149
int FfSetField(int field)
Sets the field order.
Definition: kernel-0.c:300
Perm_t * PermInverse(const Perm_t *src)
Inverse of a permutation This function calulates the inverse of a permutation.
Definition: perminv.c:26
Node in a graphical lattice representation.
Definition: meataxe.h:1063
Matrix_t * MatCutRows(const Matrix_t *src, int row1, int nrows)
Copy a range of rows of a matrix.
Definition: matcut.c:119
int StfPut(StfData *f, const char *text)
Write a raw value.
Definition: stfwrite.c:28
A dynamic string.
Definition: meataxe.h:227
BitString_t * BsAlloc(int size)
Create a bit string.
Definition: bscore.c:78
FEL FfRestrict(FEL a, int subfield)
Restrict to a subfield.
Definition: kernel-0.c:413
int MrSave(const MatRep_t *rep, const char *basename)
Save a Matrix Representation.
Definition: mrwrite.c:31
int NHeads
Number of radical layers.
Definition: meataxe.h:979
Matrix_t * MatMulScalar(Matrix_t *dest, FEL coeff)
Multiply a Matrix by a Constant.
Definition: mmulscal.c:23
Perm_t * PermLoad(const char *fn)
Read a permutation.
Definition: permread.c:94
Matrix_t * MatLoad(const char *fn)
Read a matrix from a file.
Definition: matread.c:57
int MfWriteLong(MtxFile_t *f, const long *buf, int count)
Write long integers to a file.
Definition: mfwritelong.c:31
int BufSize
Used internally for memory management.
Definition: meataxe.h:720
Matrix_t * MatTransposed(const Matrix_t *src)
Transpose a matrix.
Definition: mattr.c:24
String StrAlloc(size_t initial_capacity)
Create a string.
Definition: string.c:119
int SysFseekRelative(FILE *file, long distance)
Set file pointer relative to current position.
Definition: os.c:333
Set_t * SetAlloc()
Create a new set.
Definition: setcore.c:64
size_t FfRowSize(int noc)
Calculate row size.
Definition: kernel-0.c:354
Matrix_t * MatAddMul(Matrix_t *dest, const Matrix_t *src, FEL coeff)
Add a multiple of a matrix.
Definition: maddmul.c:30
Tensor condensation state.
Definition: meataxe.h:1013
int FfWriteRows(FILE *f, PTR buf, int n)
Write rows This function writes 1 or more rows to a file.
Definition: ffio.c:63
PTR FfAddRow(PTR dest, PTR src)
Add two rows.
Definition: kernel-0.c:470
Application information structure.
Definition: meataxe.h:274
int AppFree(MtxApplication_t *a)
End an application.
Definition: args.c:381
int Noc
Number of columns.
Definition: meataxe.h:497
int MfClose(MtxFile_t *file)
Close a File.
Definition: mfcore.c:152
FEL FfExtract(PTR row, int col)
Extract a mark from a row This function returns the entry at position col of row. ...
Definition: kernel-0.c:941
int ImatFree(IntMatrix_t *mat)
Delete an integer matrix.
Definition: imatcore.c:97
int * PivotTable
Pivot table (if matrix is in echelon form).
Definition: meataxe.h:500
size_t FfCurrentRowSize
The number of bytes occupied by a single row in memory.
Definition: kernel-0.c:162
const char * Lat_CfName(const Lat_Info *li, int cf)
Make Constituent Name.
Definition: cfinfo.c:417
int MsFree(MatrixSet_t *set)
Free a matrix set.
Definition: mscore.c:151
void * SysMalloc(size_t nbytes)
Allocate memory.
Definition: os.c:347
void FfCleanRow(PTR row, PTR matrix, int nor, const int *piv)
Clean Row.
Definition: zcleanrow.c:31
Matrix_t * MatDup(const Matrix_t *src)
Duplicate a matrix This function creates a copy of an existing matrix.
Definition: matdup.c:27
int BsAnd(BitString_t *dest, const BitString_t *src)
Intersection of two bit strings.
Definition: bsand.c:25
FPoly_t * CharPol(const Matrix_t *mat)
Characteristic Polynomial.
Definition: charpol.c:256
Matrix_t * MatTensor(const Matrix_t *m1, const Matrix_t *m2)
Tensor Product.
Definition: mtensor.c:30
int PermFree(Perm_t *p)
Free a permutation.
Definition: permcore.c:126
void FfFree(PTR x)
Free memory.
Definition: zzz2.c:83
long gcd(long a, long b)
Calculates the greatest common divisor of two integers.
Definition: gcd.c:23
FPoly_t * FpMulP(FPoly_t *dest, const Poly_t *src, int pwr)
Multiply with an irreducible polynomial.
Definition: fpmul.c:29
int AppGetOption(MtxApplication_t *app, const char *spec)
Check for command line option.
Definition: args.c:431
long SysTimeUsed(void)
CPU time.
Definition: os.c:93
Matrix_t * QProjection(const Matrix_t *subspace, const Matrix_t *vectors)
Projection on quotient.
Definition: quotient.c:44
int ImatWrite(const IntMatrix_t *mat, FILE *f)
Write an integer matrix to a file.
Definition: imatwrite.c:27
FEL FfScalarProduct(PTR a, PTR b)
Scalar Product of Two Vectors.
Definition: kernel-0.c:826
StfData * StfOpen(const char *name, int mode)
Open a structured text file.
Definition: stfcore.c:119
Poly_t * PolMul(Poly_t *dest, const Poly_t *src)
Multiply polynomials.
Definition: polmul.c:27
const GrExtractionTable_t * GrGetExtractionTable(int fl, int grrows)
Calculate extraction table for grease.
Definition: grtable.c:151
Matrix_t * MatAlloc(int field, int nor, int noc)
Create a new matrix.
Definition: matcore.c:100
int BsCompare(const BitString_t *a, const BitString_t *b)
Compare two bit strings.
Definition: bsop.c:43
int WgFree(WgData_t *b)
Terminate the word generator.
Definition: wgen.c:454
PTR FfAlloc(int nor)
Allocate memory and initialize This function allocates a block of memory for a vector (if nrows is 1)...
Definition: zzz2.c:54
MtxApplicationInfo_t const * AppInfo
Program name and description.
Definition: meataxe.h:292
MtxErrorHandler_t * MtxSetErrorHandler(MtxErrorHandler_t *h)
Define an application error handler.
Definition: error.c:90
int StfWriteString(StfData *f, const char *name, const char *value)
Write a string.
Definition: stfwrite.c:227
const char * WgSymbolicName(WgData_t *b, long n)
Symbolic name of a word.
Definition: wgen.c:250
int FfSeekRow(FILE *f, int pos)
Move to a Row.
Definition: ffio.c:103
Field generator.
Definition: zzz2.c:35
int NCf
Number of relevant constituents.
Definition: meataxe.h:1018
int MrAddGenerator(MatRep_t *rep, Matrix_t *gen, int flags)
Add a Matrix to a Representation.
Definition: mraddgen.c:33
long int MtxRandom(void)
Get the next (pseudo-)random number This function returns a nonnegative (pseudo) random number...
Definition: random.c:59
int PolGcdEx(const Poly_t *a, const Poly_t *b, Poly_t **result)
Greatest common divisor of two polynomials.
Definition: polgcd.c:121
int PolWrite(const Poly_t *p, FILE *f)
Write a polynomial to a file.
Definition: polwrite.c:45
void SysSetTimeLimit(long nsecs)
Set CPU time limit.
Definition: os.c:165
void SysInit(void)
OS-specific initialization.
Definition: os.c:78
FILE * FfReadHeader(const char *name, int *field, int *nor, int *noc)
Open File and Read Header.
Definition: ffio.c:133
const char * AppCreateTempDir(MtxApplication_t *app)
Create a temporary directory.
Definition: args.c:663
void * SysRealloc(void *buf, size_t nbytes)
Resizes a memory block.
Definition: os.c:371
int MakeEndomorphisms(const MatRep_t *rep, const Matrix_t *nsp, Matrix_t *endo[])
Calculate the endomorphism ring.
Definition: mkendo.c:61
Matrix_t * SAction(const Matrix_t *sub, const Matrix_t *gen)
Action on a subspace.
Definition: saction.c:39
Matrix_t * MatNullSpace__(Matrix_t *mat)
Null-space of a matrix This function calculates the null-space of a matrix and deletes the original m...
Definition: matnull.c:189
unsigned long Magic
Used internally.
Definition: meataxe.h:676
int MatIsValid(const Matrix_t *m)
Check if the matrix is valid.
Definition: matcore.c:73
Matrix_t * MatInverse(const Matrix_t *src)
Inverse of a matrix This function calculates the inverse of a matrix.
Definition: matinv.c:82
GreasedMatrix_t * GrMatAlloc(const Matrix_t *m, int gr_rows)
Create a greased matrix.
Definition: grmatcore.c:101
const char ** ArgV
Definition: meataxe.h:296
Matrix_t * MatInsert_(Matrix_t *mat, const Poly_t *pol)
Insert a matrix into a polynomial Given a square matrix A and a polynomial p over the same field...
Definition: matins.c:28
FPoly_t * MinPol(Matrix_t *mat)
Minimal polynomial.
Definition: minpol.c:260
Poly_t * PolDerive(Poly_t *pol)
Derive a polynomial.
Definition: polderive.c:34
char * LineBuf
Buffers one 'line'.
Definition: meataxe.h:433
Matrix_t * QAction(const Matrix_t *sub, const Matrix_t *gen)
Action on Quotient.
Definition: quotient.c:110
int StfMatch(StfData *f, const char *pattern)
Skip text.
Definition: stfread.c:283
void FfInsert(PTR row, int col, FEL mark)
Insert a mark into a row This function inserts the field element mark at position col into row...
Definition: kernel-0.c:907
int GrMatFree(GreasedMatrix_t *mat)
Free a greased matrix.
Definition: grmatcore.c:71
Poly_t * MinPolFactor(Matrix_t *mat)
Minimal Polynomial.
Definition: minpol.c:207
int StfGetInt(StfData *f, int *buf)
Read an integer.
Definition: stfread.c:149
BitString_t * BsCopy(BitString_t *dest, const BitString_t *src)
Copy a bit string.
Definition: bsop.c:64
const char * OptArg
Used internally.
Definition: meataxe.h:299
FEL * Data
Definition: meataxe.h:624
Word Generator Data.
Definition: meataxe.h:837
FILE * SysFopen(const char *name, int mode)
Open a file.
Definition: os.c:206
int * Head
Definition: meataxe.h:980
BitString_t * BsDup(const BitString_t *src)
Duplicate a bit string.
Definition: bsdup.c:24
void GrMapRow(PTR v, GreasedMatrix_t *M, PTR w)
Multiply a vector by a greased matrix.
Definition: grmaprow.c:115
int SysRemoveFile(const char *name)
Remove a file This function deletes a file.
Definition: os.c:272
Extraction table for greasing.
Definition: meataxe.h:551
A matrix over a finite field.
Definition: meataxe.h:492
Perm_t * PermAlloc(int deg)
Allocate a permutation This function creates a permutation of the specified degree.
Definition: permcore.c:88
Matrix_t * MatNullSpace(const Matrix_t *mat)
Null-space of a matrix This function calculates the null-space of a matrix.
Definition: matnull.c:161
int StfPutVector(StfData *f, int size, const int *value)
Write a vector.
Definition: stfwrite.c:99
int StfPutString(StfData *f, const char *text)
Write a string.
Definition: stfwrite.c:65
MtxFile_t * MfCreate(const char *name, int field, int nor, int noc)
Open a File for Writing.
Definition: mfcore.c:121
FILE * FfWriteHeader(const char *name, int field, int nor, int noc)
Open file and write header.
Definition: ffio.c:183
void PolPrint(char *name, const Poly_t *p)
Print a polynomial This function prints a polynomial on the standard output in a human-readable form...
Definition: polprint.c:31
void FfMulRow(PTR row, FEL mark)
Multiply a row by a coefficient.
Definition: kernel-0.c:612
A matrix representation.
Definition: meataxe.h:813
int StfReadLine(StfData *f)
Read next line.
Definition: stfread.c:31
Poly_t * PolGcd(const Poly_t *a, const Poly_t *b)
Greatest common divisor of two polynomials.
Definition: polgcd.c:49
int Lat_ReadInfo(Lat_Info *li, const char *basename)
Read a Lattice Information File.
Definition: cfinfo.c:144
int MtxRandomInt(int max)
Random number.
Definition: random.c:85
int OrigArgC
Original argc from main().
Definition: meataxe.h:293
size_t FfTrueRowSize(int noc)
Number of used bytes in a row.
Definition: kernel-0.c:370
Application data.
Definition: meataxe.h:290
void FfCopyRow(PTR dest, PTR src)
Copy a row.
Definition: zzz2.c:99
int SysReadLong32(FILE *f, long *buf, int n)
Read long integers.
Definition: intio.c:39
int MfWriteRows(MtxFile_t *f, PTR buf, int nrows)
Write row vectors to a file.
Definition: mfwrite.c:31
Matrix_t * WgMakeWord(WgData_t *b, long n)
Calculates a word.
Definition: wgen.c:358
int TK_ReadInfo(TkData_t *tki, const char *name)
Read a .tki file.
Definition: tkinfo.c:120
const MatRep_t * Rep
The representation.
Definition: meataxe.h:839
A Permutation.
Definition: meataxe.h:590
PTR FfGetPtr(PTR base, int row)
Get row pointer.
Definition: zzz2.c:148
int BsMinus(BitString_t *dest, const BitString_t *src)
Difference of two bit strings.
Definition: bsminus.c:27
unsigned long Magic
Used internally.
Definition: meataxe.h:592
void WgMakeFingerPrint(WgData_t *b, int fp[6])
Calculate finger print.
Definition: wgen.c:488
unsigned long Magic
Used internally.
Definition: meataxe.h:471
int StablePower(const Matrix_t *mat, int *pwr, Matrix_t **ker)
Stable power of a matrix.
Definition: stabpwr.c:93
void Mat_DeletePivotTable(Matrix_t *mat)
Delete the pivot table of a matrix.
Definition: matcore.c:175
int Dim
Dimension of condensed module.
Definition: meataxe.h:1017
Matrix_t * MatCut(const Matrix_t *src, int row1, int col1, int nrows, int ncols)
Cut a rectangle out of a matrix.
Definition: matcut.c:38
MtxApplication_t * AppAlloc(MtxApplicationInfo_t const *ai, int argc, const char **argv)
Initialize the application.
Definition: args.c:307
void BsPrint(const char *name, const BitString_t *bs)
Print a bit string on stdout.
Definition: bsprint.c:28
int MatPivotize(Matrix_t *mat)
Reduce to echelon form.
Definition: matpivot.c:64
int PermOrder(const Perm_t *perm)
Order of a permutation.
Definition: permorder.c:25
int Degree
Degree of the polynomial.
Definition: meataxe.h:623
Matrix_t * MatId(int fl, int nor)
Identity matrix This function creates an identity matrix with nor nows over GF(fl).
Definition: matid.c:27
const char * AppGetTextOption(MtxApplication_t *app, const char *spec, const char *dflt)
Check for command line option.
Definition: args.c:478
Graphical lattice representation.
Definition: meataxe.h:1075
FEL FfMul(FEL a, FEL b)
Finite field multiplication.
int PermSave(const Perm_t *perm, const char *fn)
Write a Permutation to a File.
Definition: permwrite.c:60
int Field
Field order or type id.
Definition: meataxe.h:472
int MatCompare(const Matrix_t *a, const Matrix_t *b)
Compare two matrices If the matrices are equal, the return value is 0.
Definition: matcmp.c:40
int NFactors
Number of different irreducible factors.
Definition: meataxe.h:659
long * Data
Marks (row by row).
Definition: meataxe.h:743
int Field
Field order.
Definition: meataxe.h:622
long MatNullity(const Matrix_t *mat)
Nullity of a matrix.
Definition: matech.c:138
MatrixSet_t * MsAlloc()
Allocate a matrix set.
Definition: mscore.c:127
An element of a matrix set.
Definition: meataxe.h:783
Matrix_t * TensorMap(Matrix_t *vec, const Matrix_t *a, const Matrix_t *b)
Map under tensor product.
Definition: temap.c:30
int MtxPrintMessage(FILE *f, const char *fmt,...)
Print a message.
Definition: message.c:189
FILE * File
File to read frmo/write to.
Definition: meataxe.h:475
Poly_t * PolAlloc(int fl, int n)
Allocate a polynomial This function creates the polynomial p(x)=x^n over the current field...
Definition: polcore.c:83
int FfStepPtr(PTR *x)
Advance to next row.
Definition: zzz2.c:177
int MtxError(MtxFileInfo_t *fi, int line, const char *text,...)
Signal an error.
Definition: error.c:111
Constituent data structure.
Definition: meataxe.h:957
const char * FfToGap(FEL f)
Convert to GAP format.
Definition: zgap.c:22
A Set of Integers.
Definition: meataxe.h:716
Matrix_t * VectorToMatrix(Matrix_t *vecs, int n, int noc)
Convert vector to matrix.
Definition: vec2mat.c:33
int FpFree(FPoly_t *x)
Free a factored polynomial.
Definition: fpcore.c:109
void FfAddMulRow(PTR dest, PTR src, FEL f)
Add a multiple of a row.
Definition: kernel-0.c:640
int MtxFormatMessage(char *buf, int bufsize, const char *msg, va_list al)
Format a message.
Definition: message.c:137
int BsIsValid(const BitString_t *bs)
Check if a bit string is valid.
Definition: bscore.c:50
FEL FfInv(FEL a)
Finite field inversion.
int AppGetCountedOption(MtxApplication_t *app, const char *spec)
Count repeatable command line option.
Definition: args.c:453
int MatOrder(const Matrix_t *mat)
Order of a matrix.
Definition: matorder.c:30
Perm_t * PermRead(FILE *f)
Read a Permutation from a File.
Definition: permread.c:51
int StfEndEntry(StfData *f)
End entry.
Definition: stfwrite.c:170
FEL FfDiv(FEL a, FEL b)
Finite field division.
int FpIsValid(const FPoly_t *p)
Check a factored polynomial.
Definition: fpcore.c:33
int MfReadRows(MtxFile_t *f, PTR buf, int nrows)
Read row vectors from a file.
Definition: mfread.c:30
FEL FfEmbed(FEL a, int subfield)
Embed a subfield.
Definition: kernel-0.c:386
int MrFree(MatRep_t *rep)
Delete a matrix representation.
Definition: mrcore.c:182
int AppGetIntOption(MtxApplication_t *app, const char *spec, int dflt, int min, int max)
Check for integer-valued option.
Definition: args.c:522
int StfClose(StfData *f)
Close a structured text file.
Definition: stfcore.c:66
void SysFree(void *x)
Free memory block.
Definition: os.c:392
FPoly_t * FpAlloc()
Allocate a factored polynomial.
Definition: fpcore.c:75
int FfSetNoc(int noc)
Set the row length.
Definition: kernel-0.c:326
Matrix_t * MatPower(const Matrix_t *mat, long n)
Power of a matrix.
Definition: matpwr.c:75
Matrix_t * MatNullSpace_(Matrix_t *mat, int flags)
Null-space of a matrix This function calculates the null-space of a matrix.
Definition: matnull.c:120
int Lat_AddHead(Lat_Info *li, int *mult)
Add a Layer to the Radical Series.
Definition: cfinfo.c:463
int BsClearAll(BitString_t *bs)
Clear a bit string This function clears all bits in a bit string.
Definition: bsop.c:27
PTR FfAddRowPartial(PTR dest, PTR src, int first, int len)
Add a part two rows.
Definition: kernel-0.c:553
PTR MatGetPtr(const Matrix_t *mat, int row)
Pointer to a row of a matrix.
Definition: matcore.c:148
int Size
Number of bits.
Definition: meataxe.h:677
int MatrixToVector(const Matrix_t *mat, Matrix_t *vecs, int n)
Convert matrix to vector.
Definition: mat2vec.c:33
FEL FfSub(FEL a, FEL b)
Finite field subtraction.
unsigned long Magic
Used internally.
Definition: meataxe.h:621
int LineNo
Current line number (reading and writing)
Definition: meataxe.h:437
Poly_t * PolDivMod(Poly_t *a, const Poly_t *b)
Polynomial division.
Definition: poldiv.c:38
int MfReadLong(MtxFile_t *f, long *buf, int nrows)
Read long integers from a file.
Definition: mfreadlong.c:31
int SysGetPid()
Get process id.
Definition: os.c:410
int AppGetArguments(MtxApplication_t *app, int min_argc, int max_argc)
Get command line arguments.
Definition: args.c:601
void FfCleanRow2(PTR row, PTR matrix, int nor, const int *piv, PTR row2)
Clean Row and Record Operations.
Definition: zcleanrow.c:59
Perm_t * PermDup(const Perm_t *src)
Duplicate a permutation.
Definition: permdup.c:26
int Nor
Number of rows.
Definition: meataxe.h:473
size_t RowSize
Size (in bytes) of one row.
Definition: meataxe.h:499
void FfCleanRowAndRepeat(PTR row, PTR mat, int nor, const int *piv, PTR row2, PTR mat2)
Clean Row and Repeat Operations.
Definition: zcleanrow.c:94
const char * Name
Program name.
Definition: meataxe.h:276
int Nor
Number of rows.
Definition: meataxe.h:741
void PermPrint(const char *name, const Perm_t *perm)
Print a permutation This function prints a permutation on the standard output using cycle notation...
Definition: permprint.c:37
MatRep_t * MrTransposed(const MatRep_t *rep)
Transpose a Representation.
Definition: mrtranspose.c:27
int TK_WriteInfo(TkData_t *tki, const char *name)
Write a .tki file.
Definition: tkinfo.c:155
MatRep_t * MrAlloc(int ngen, Matrix_t **gen, int flags)
Create a matrix representation.
Definition: mrcore.c:123
int FpPrint(const char *name, const FPoly_t *p)
Print a factored polynomial.
Definition: fpprint.c:26
int SysCreateDirectory(const char *name)
Create a directory.
Definition: os.c:308
int Split(Matrix_t *subspace, const MatRep_t *rep, MatRep_t **sub, MatRep_t **quot)
Split a Representation.
Definition: split.c:87
int MtxMessageLevel
Message level.
Definition: message.c:27
int OptEnd
Used internally.
Definition: meataxe.h:297
Perm_t * PermMul(Perm_t *dest, const Perm_t *src)
Multiply permutations.
Definition: permmul.c:28
A Factored Polynomial.
Definition: meataxe.h:656
int SysWriteLong32(FILE *f, const long *buf, int n)
Write long integers.
Definition: intio.c:95
Matrix_t * MatRead(FILE *f)
Read a matrix from a file.
Definition: matread.c:25
int Degree
Degree of the permutation.
Definition: meataxe.h:593
long * Data
Images of 0,1,2,...
Definition: meataxe.h:594
Matrix_t * MatMul(Matrix_t *dest, const Matrix_t *src)
Multiply matrices This function multiplies dest from the right by src.
Definition: matmul.c:32
Matrix_t * MatInsert(const Matrix_t *mat, const Poly_t *pol)
Insert a matrix into a polynomial Given a square matrix A and a polynomial p over the same field...
Definition: matins.c:106
int Lat_AddSocle(Lat_Info *li, int *mult)
Add a Layer to the Socle Series.
Definition: cfinfo.c:447
Matrix_t * MatAdd(Matrix_t *dest, const Matrix_t *src)
Sum of two matrices.
Definition: matadd.c:25
int SetFree(Set_t *x)
Destroy a set.
Definition: setcore.c:93
Poly_t * PolDup(const Poly_t *p)
Duplicate a polynomial.
Definition: poldup.c:27
Set_t * SetDup(const Set_t *s)
Duplicate a set.
Definition: setcore.c:110
int MatCopyRegion(Matrix_t *dest, int destrow, int destcol, const Matrix_t *src, int row1, int col1, int nrows, int ncols)
Copy a rectangular region of a matrix This function copies a rectangular region of src tp dest...
Definition: matcopy.c:39
long MatNullity__(Matrix_t *mat)
Nullity of a matrix.
Definition: matech.c:151
void Pol_Normalize(Poly_t *p)
Normalize a polynomial.
Definition: polcore.c:139
char * GetPtr
Current input position.
Definition: meataxe.h:434
int SetContains(const Set_t *set, long elem)
Check if a number is in a set.
Definition: settest.c:25
int SetInsert(Set_t *set, long elem)
Insert an element into a set.
Definition: setinsert.c:27
int MfIsValid(const MtxFile_t *file)
Check a File Object.
Definition: mfcore.c:34
int BsSet(BitString_t *bs, int i)
Set one bit in a bit string.
Poly_t * PolMod(Poly_t *a, const Poly_t *b)
Polynomial division.
Definition: poldiv.c:92
int StfWriteValue(StfData *f, const char *name, const char *value)
Write a string.
Definition: stfwrite.c:195
unsigned long Magic
Used internally.
Definition: meataxe.h:494
int MatEchelonize(Matrix_t *mat)
Reduce to echelon form This function performs a Gaussian elimination on the matrix |mat|...
Definition: matech.c:81
int Field
Field order.
Definition: meataxe.h:973
int BsIsSub(const BitString_t *a, const BitString_t *b)
Bit string incidence relation.
Definition: bsissub.c:25
void StrPrintF(String *s, const char *fmt,...)
snprintf() replacement.
Definition: string.c:242
void StrAppendF(String *s, const char *fmt,...)
snprintf() replacement.
Definition: string.c:204
FEL MatTrace(const Matrix_t *mat)
Trace of a Matrix.
Definition: mattrace.c:21
int OutPos
Number of chars in current line (writing only)
Definition: meataxe.h:436
int PermWrite(const Perm_t *perm, FILE *f)
Write a Permutation to a File.
Definition: permwrite.c:28
int Lat_WriteInfo(const Lat_Info *li)
Write a Lattice Information File.
Definition: cfinfo.c:303
int BsTest(const BitString_t *bs, int i)
Test a bit in a bit string.
int NGen
Number of generators.
Definition: meataxe.h:974
FEL FfAdd(FEL a, FEL b)
Finite field addition.
int MsCleanAndAppend(MatrixSet_t *set, Matrix_t *mat)
Extend a matrix set.
Definition: msclean.c:95
MtxFile_t * MfOpen(const char *name)
Open a File for Reading.
Definition: mfcore.c:80
int BsOr(BitString_t *dest, const BitString_t *src)
Union of two bit strings.
Definition: bsor.c:26
Poly_t * PolRead(FILE *f)
Read a polynomial from a file.
Definition: polread.c:48
int PolSave(const Poly_t *pol, const char *fn)
Write a polynomial to a File.
Definition: polwrite.c:84
A greased matrix.
Definition: meataxe.h:565
int MsIsValid(const MatrixSet_t *set)
Check a matrix set.
Definition: mscore.c:58
void MatPrint(const char *name, const Matrix_t *m)
Print a matrix on stdout.
Definition: matprint.c:28
int FfNoc
Current row size.
Definition: zzz2.c:41
int BsIntersectionCount(const BitString_t *a, const BitString_t *b)
Intersection count.
Definition: bsmatch.c:46
int MrIsValid(const MatRep_t *rep)
Check a matrix representation.
Definition: mrcore.c:87
const char * Description
One-line description of the program.
Definition: meataxe.h:277
int BufSize
Used internally for memory management.
Definition: meataxe.h:678
int LineBufSize
Current buffer size.
Definition: meataxe.h:435
int ImatSave(const IntMatrix_t *mat, const char *file_name)
Write an integer matrix to a file.
Definition: imatwrite.c:57
int Noc
Number of colums.
Definition: meataxe.h:742
void FfSwapRows(PTR dest, PTR src)
Exchange two rows This function exchanges the contents of two rows.
Definition: zzz2.c:115
int FfCmpRows(PTR p1, PTR p2)
Compare two rows.
Definition: zcmprow.c:33
Poly_t * PolLoad(const char *fn)
Read a Polynomial from a File.
Definition: polread.c:94
An integer matrix.
Definition: meataxe.h:738
IntMatrix_t * ImatRead(FILE *f)
Read an integer matrix from a file.
Definition: imatread.c:27
int FfSumAndIntersection(PTR wrk1, int *nor1, int *nor2, PTR wrk2, int *piv)
Sum and Intersection of Two Vector Spaces.
Definition: sumint.c:44
A set of matrices.
Definition: meataxe.h:795
int StfGetVector(StfData *f, int *bufsize, int *buf)
Read a vector.
Definition: stfread.c:352
int Field
Field order.
Definition: meataxe.h:495
Run-time error information.
Definition: meataxe.h:354
Spin-up Parameters.
Definition: meataxe.h:875
long lcm(long a, long b)
Calculates the least common multiple of two integers.
Definition: gcd.c:48
MatRep_t * Lat_ReadCfGens(Lat_Info *info, int cf, int flags)
Load a Constituent.
Definition: rdcfgen.c:32
Module Structure Information.
Definition: meataxe.h:970
int NCf
Number of irred.
Definition: meataxe.h:975
unsigned long Magic
Used internally.
Definition: meataxe.h:718

MeatAxe 2.4 documentation, generated on Wed Jan 7 2015 08:38:36