Public Member Functions | Private Attributes | Friends
LinearDependencyMatrix Class Reference

#include <minpoly.h>

Public Member Functions

 LinearDependencyMatrix (unsigned n, unsigned long p)
 
 ~LinearDependencyMatrix ()
 
void resetMatrix ()
 
int firstNonzeroEntry (unsigned long *row)
 
void reduceTmpRow ()
 
void normalizeTmp (unsigned i)
 
bool findLinearDependency (unsigned long *newRow, unsigned long *dep)
 

Private Attributes

unsigned p
 
unsigned long n
 
unsigned long ** matrix
 
unsigned long * tmprow
 
unsigned * pivots
 
unsigned rows
 

Friends

class NewVectorMatrix
 

Detailed Description

Definition at line 70 of file minpoly.h.

Constructor & Destructor Documentation

§ LinearDependencyMatrix()

LinearDependencyMatrix::LinearDependencyMatrix ( unsigned  n,
unsigned long  p 
)

Definition at line 21 of file minpoly.cc.

22 {
23  this->n = n;
24  this->p = p;
25 
26  matrix = new unsigned long *[n];
27  for(int i = 0; i < n; i++)
28  {
29  matrix[i] = new unsigned long[2 * n + 1];
30  }
31  pivots = new unsigned[n];
32  tmprow = new unsigned long[2 * n + 1];
33  rows = 0;
34 }
unsigned long * tmprow
Definition: minpoly.h:76
unsigned * pivots
Definition: minpoly.h:77
int i
Definition: cfEzgcd.cc:123
unsigned long n
Definition: minpoly.h:74

§ ~LinearDependencyMatrix()

LinearDependencyMatrix::~LinearDependencyMatrix ( )

Definition at line 36 of file minpoly.cc.

37 {
38  delete[]tmprow;
39  delete[]pivots;
40 
41  for(int i = 0; i < n; i++)
42  {
43  delete[](matrix[i]);
44  }
45  delete[]matrix;
46 }
unsigned long * tmprow
Definition: minpoly.h:76
unsigned long ** matrix
Definition: minpoly.h:75
unsigned * pivots
Definition: minpoly.h:77
int i
Definition: cfEzgcd.cc:123
unsigned long n
Definition: minpoly.h:74

Member Function Documentation

§ findLinearDependency()

bool LinearDependencyMatrix::findLinearDependency ( unsigned long *  newRow,
unsigned long *  dep 
)

Definition at line 98 of file minpoly.cc.

100 {
101  // Copy newRow to tmprow (we need to add RHS)
102  for(int i = 0; i < n; i++)
103  {
104  tmprow[i] = newRow[i];
105  tmprow[n + i] = 0;
106  }
107  tmprow[2 * n] = 0;
108  tmprow[n + rows] = 1;
109 
110  reduceTmpRow ();
111 
112  // Is tmprow reduced to zero? Then we have found a linear dependence.
113  // Otherwise, we just add tmprow to the matrix.
114  unsigned newpivot = firstNonzeroEntry (tmprow);
115  if(newpivot == -1)
116  {
117  for(int i = 0; i <= n; i++)
118  {
119  dep[i] = tmprow[n + i];
120  }
121 
122  return true;
123  }
124  else
125  {
126  normalizeTmp (newpivot);
127 
128  for(int i = 0; i < 2 * n + 1; i++)
129  {
130  matrix[rows][i] = tmprow[i];
131  }
132 
133  pivots[rows] = newpivot;
134  rows++;
135 
136  return false;
137  }
138 }
unsigned long * tmprow
Definition: minpoly.h:76
void normalizeTmp(unsigned i)
Definition: minpoly.cc:90
unsigned * pivots
Definition: minpoly.h:77
int i
Definition: cfEzgcd.cc:123
unsigned long n
Definition: minpoly.h:74
int firstNonzeroEntry(unsigned long *row)
Definition: minpoly.cc:53

§ firstNonzeroEntry()

int LinearDependencyMatrix::firstNonzeroEntry ( unsigned long *  row)

Definition at line 53 of file minpoly.cc.

54 {
55  for(int i = 0; i < n; i++)
56  if(row[i] != 0)
57  return i;
58 
59  return -1;
60 }
int i
Definition: cfEzgcd.cc:123
unsigned long n
Definition: minpoly.h:74

§ normalizeTmp()

void LinearDependencyMatrix::normalizeTmp ( unsigned  i)

Definition at line 90 of file minpoly.cc.

91 {
92  unsigned long inv = modularInverse (tmprow[i], p);
93  tmprow[i] = 1;
94  for(int j = i + 1; j < 2 * n + 1; j++)
95  tmprow[j] = multMod (tmprow[j], inv, p);
96 }
unsigned long * tmprow
Definition: minpoly.h:76
static unsigned long multMod(unsigned long a, unsigned long b, unsigned long p)
Definition: minpoly.h:204
int j
Definition: myNF.cc:70
int i
Definition: cfEzgcd.cc:123
unsigned long n
Definition: minpoly.h:74
unsigned long modularInverse(long long x, long long p)
Definition: minpoly.cc:746

§ reduceTmpRow()

void LinearDependencyMatrix::reduceTmpRow ( )

Definition at line 62 of file minpoly.cc.

63 {
64  for(int i = 0; i < rows; i++)
65  {
66  unsigned piv = pivots[i];
67  unsigned x = tmprow[piv];
68  // if the corresponding entry in the row is zero, there is nothing to do
69  if(x != 0)
70  {
71  // subtract tmprow[i] times the i-th row
72  for(int j = piv; j < n + rows + 1; j++)
73  {
74  if (matrix[i][j] != 0)
75  {
76  unsigned long tmp = multMod (matrix[i][j], x, p);
77  tmp = p - tmp;
78  tmprow[j] += tmp;
79  if (tmprow[j] >= p)
80  {
81  tmprow[j] -= p;
82  }
83  }
84  }
85  }
86  }
87 }
unsigned long * tmprow
Definition: minpoly.h:76
static unsigned long multMod(unsigned long a, unsigned long b, unsigned long p)
Definition: minpoly.h:204
int j
Definition: myNF.cc:70
unsigned * pivots
Definition: minpoly.h:77
int i
Definition: cfEzgcd.cc:123
unsigned long n
Definition: minpoly.h:74
Variable x
Definition: cfModGcd.cc:4023

§ resetMatrix()

void LinearDependencyMatrix::resetMatrix ( )

Definition at line 48 of file minpoly.cc.

49 {
50  rows = 0;
51 }

Friends And Related Function Documentation

§ NewVectorMatrix

friend class NewVectorMatrix
friend

Definition at line 71 of file minpoly.h.

Field Documentation

§ matrix

unsigned long** LinearDependencyMatrix::matrix
private

Definition at line 75 of file minpoly.h.

§ n

unsigned long LinearDependencyMatrix::n
private

Definition at line 74 of file minpoly.h.

§ p

unsigned LinearDependencyMatrix::p
private

Definition at line 73 of file minpoly.h.

§ pivots

unsigned* LinearDependencyMatrix::pivots
private

Definition at line 77 of file minpoly.h.

§ rows

unsigned LinearDependencyMatrix::rows
private

Definition at line 78 of file minpoly.h.

§ tmprow

unsigned long* LinearDependencyMatrix::tmprow
private

Definition at line 76 of file minpoly.h.


The documentation for this class was generated from the following files: