My Project
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 68 of file minpoly.h.

Constructor & Destructor Documentation

◆ LinearDependencyMatrix()

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

Definition at line 19 of file minpoly.cc.

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

◆ ~LinearDependencyMatrix()

LinearDependencyMatrix::~LinearDependencyMatrix ( )

Definition at line 34 of file minpoly.cc.

35 {
36  delete[]tmprow;
37  delete[]pivots;
38 
39  for(int i = 0; i < n; i++)
40  {
41  delete[](matrix[i]);
42  }
43  delete[]matrix;
44 }
unsigned long ** matrix
Definition: minpoly.h:73

Member Function Documentation

◆ findLinearDependency()

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

Definition at line 96 of file minpoly.cc.

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

◆ firstNonzeroEntry()

int LinearDependencyMatrix::firstNonzeroEntry ( unsigned long *  row)

Definition at line 51 of file minpoly.cc.

52 {
53  for(int i = 0; i < n; i++)
54  if(row[i] != 0)
55  return i;
56 
57  return -1;
58 }

◆ normalizeTmp()

void LinearDependencyMatrix::normalizeTmp ( unsigned  i)

Definition at line 88 of file minpoly.cc.

89 {
90  unsigned long inv = modularInverse (tmprow[i], p);
91  tmprow[i] = 1;
92  for(int j = i + 1; j < 2 * n + 1; j++)
93  tmprow[j] = multMod (tmprow[j], inv, p);
94 }
int j
Definition: facHensel.cc:110
unsigned long modularInverse(long long x, long long p)
Definition: minpoly.cc:744
static unsigned long multMod(unsigned long a, unsigned long b, unsigned long p)
Definition: minpoly.h:202

◆ reduceTmpRow()

void LinearDependencyMatrix::reduceTmpRow ( )

Definition at line 60 of file minpoly.cc.

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

◆ resetMatrix()

void LinearDependencyMatrix::resetMatrix ( )

Definition at line 46 of file minpoly.cc.

47 {
48  rows = 0;
49 }

Friends And Related Function Documentation

◆ NewVectorMatrix

friend class NewVectorMatrix
friend

Definition at line 69 of file minpoly.h.

Field Documentation

◆ matrix

unsigned long** LinearDependencyMatrix::matrix
private

Definition at line 73 of file minpoly.h.

◆ n

unsigned long LinearDependencyMatrix::n
private

Definition at line 72 of file minpoly.h.

◆ p

unsigned LinearDependencyMatrix::p
private

Definition at line 71 of file minpoly.h.

◆ pivots

unsigned* LinearDependencyMatrix::pivots
private

Definition at line 75 of file minpoly.h.

◆ rows

unsigned LinearDependencyMatrix::rows
private

Definition at line 76 of file minpoly.h.

◆ tmprow

unsigned long* LinearDependencyMatrix::tmprow
private

Definition at line 74 of file minpoly.h.


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