CoCalc Logo Icon
StoreFeaturesDocsShareSupportNewsAboutSign UpSign In

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

Views: 418346
Tweet
Share
Share
1
/****************************************************************************

2
**

3
*A  echelonise_matrix.c         ANUPQ source                   Eamonn O'Brien

4
**

5
*Y  Copyright 1995-2001,  Lehrstuhl D fuer Mathematik,  RWTH Aachen,  Germany

6
*Y  Copyright 1995-2001,  School of Mathematical Sciences, ANU,     Australia

7
**

8
*/

9


10
#include "pq_defs.h"

11
#include "pga_vars.h"

12


13
/* left echelonise mod p the matrix a, which has the supplied dimensions;

14
   set up its definition set both as a subset and as a bit string  */

15


16
int echelonise_matrix(int **a,

17
                      int nmr_rows,

18
                      int nmr_columns,

19
                      int p,

20
                      int *subset,

21
                      struct pga_vars *pga)

22
{

23
   Logical zero;

24
   register int bound = nmr_columns - 1;

25
   register int row, column, i, j, index, val;

26
   register int entry;

27
   register int bit_string = 0;

28


29
   for (row = 0; row < nmr_rows; ++row) {

30


31
      /* start with the diagonal entry */

32
      column = row;

33


34
      /* find first non-zero entry, if any, in this column;

35
         if none, advance to next column */

36
      do {

37
         index = row;

38
         while (index < nmr_rows && (zero = (a[index][column] == 0)))

39
            ++index;

40
         if (zero) {

41
            if (column < bound)

42
               ++column;

43
            else

44
               return bit_string;

45
         }

46
      } while (zero);

47


48
      /* store the definition set information for this matrix */

49
      bit_string |= 1 << column;

50
      subset[row] = column;

51


52
      /* if necessary, interchange current row with row index */

53
      if (index > row) {

54
         for (j = column; j < nmr_columns; ++j) {

55
            val = a[index][j];

56
            a[index][j] = a[row][j];

57
            a[row][j] = val;

58
         }

59
      }

60


61
      /* multiply row by the inverse in GF(p) of a[row][column] */

62
      if ((entry = a[row][column]) != 1) {

63
         val = pga->inverse_modp[entry];

64
         a[row][column] = 1;

65
         for (j = column + 1; j < nmr_columns; ++j)

66
            a[row][j] = (a[row][j] * val) % p;

67
      }

68


69
      /* now zero out all other entries in this column */

70
      for (i = 0; i < nmr_rows; ++i) {

71
         if (a[i][column] == 0 || i == row)

72
            continue;

73
         val = p - a[i][column];

74
         a[i][column] = 0;

75
         for (j = column + 1; j < nmr_columns; ++j)

76
            a[i][j] = (a[i][j] + val * a[row][j]) % p;

77
      }

78
   }

79


80
   return bit_string;

81
}

82


83