Public Member Functions | Private Attributes
NewVectorMatrix Class Reference

#include <minpoly.h>

Public Member Functions

 NewVectorMatrix (unsigned n, unsigned long p)
 
 ~NewVectorMatrix ()
 
int firstNonzeroEntry (unsigned long *row)
 
void normalizeRow (unsigned long *row, unsigned i)
 
void insertRow (unsigned long *row)
 
void insertMatrix (LinearDependencyMatrix &mat)
 
int findSmallestNonpivot ()
 
int findLargestNonpivot ()
 

Private Attributes

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

Detailed Description

Definition at line 107 of file minpoly.h.

Constructor & Destructor Documentation

§ NewVectorMatrix()

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

Definition at line 183 of file minpoly.cc.

184 {
185  this->n = n;
186  this->p = p;
187 
188  matrix = new unsigned long *[n];
189  for(int i = 0; i < n; i++)
190  {
191  matrix[i] = new unsigned long[n];
192  }
193 
194  pivots = new unsigned[n];
195 
196  nonPivots = new unsigned[n];
197 
198  for (int i = 0; i < n; i++)
199  {
200  nonPivots[i] = i;
201  }
202 
203  rows = 0;
204 }
unsigned * pivots
Definition: minpoly.h:112
unsigned long n
Definition: minpoly.h:110
int i
Definition: cfEzgcd.cc:123
unsigned * nonPivots
Definition: minpoly.h:113
unsigned rows
Definition: minpoly.h:114
unsigned p
Definition: minpoly.h:109

§ ~NewVectorMatrix()

NewVectorMatrix::~NewVectorMatrix ( )

Definition at line 206 of file minpoly.cc.

207 {
208  delete nonPivots;
209  delete pivots;
210 
211  for(int i = 0; i < n; i++)
212  {
213  delete[]matrix[i];
214  }
215  delete matrix;
216 }
unsigned * pivots
Definition: minpoly.h:112
unsigned long n
Definition: minpoly.h:110
int i
Definition: cfEzgcd.cc:123
unsigned * nonPivots
Definition: minpoly.h:113
unsigned long ** matrix
Definition: minpoly.h:111

Member Function Documentation

§ findLargestNonpivot()

int NewVectorMatrix::findLargestNonpivot ( )

Definition at line 368 of file minpoly.cc.

369 {
370  // This method isn't very efficient, but it is called at most a few times, so efficiency is not important.
371  if(rows == n)
372  return -1;
373 
374  for(int i = n-1; i >= 0; i--)
375  {
376  bool isPivot = false;
377  for(int j = 0; j < rows; j++)
378  {
379  if(pivots[j] == i)
380  {
381  isPivot = true;
382  break;
383  }
384  }
385 
386  if(!isPivot)
387  {
388  return i;
389  }
390  }
391  abort();
392 }
unsigned * pivots
Definition: minpoly.h:112
int j
Definition: myNF.cc:70
unsigned long n
Definition: minpoly.h:110
int i
Definition: cfEzgcd.cc:123
unsigned rows
Definition: minpoly.h:114

§ findSmallestNonpivot()

int NewVectorMatrix::findSmallestNonpivot ( )

Definition at line 341 of file minpoly.cc.

342 {
343  // This method isn't very efficient, but it is called at most a few times,
344  // so efficiency is not important.
345  if(rows == n)
346  return -1;
347 
348  for(int i = 0; i < n; i++)
349  {
350  bool isPivot = false;
351  for(int j = 0; j < rows; j++)
352  {
353  if(pivots[j] == i)
354  {
355  isPivot = true;
356  break;
357  }
358  }
359 
360  if(!isPivot)
361  {
362  return i;
363  }
364  }
365  abort();
366 }
unsigned * pivots
Definition: minpoly.h:112
int j
Definition: myNF.cc:70
unsigned long n
Definition: minpoly.h:110
int i
Definition: cfEzgcd.cc:123
unsigned rows
Definition: minpoly.h:114

§ firstNonzeroEntry()

int NewVectorMatrix::firstNonzeroEntry ( unsigned long *  row)

Definition at line 218 of file minpoly.cc.

219 {
220  for(int i = 0; i < n; i++)
221  if(row[i] != 0)
222  return i;
223 
224  return -1;
225 }
unsigned long n
Definition: minpoly.h:110
int i
Definition: cfEzgcd.cc:123

§ insertMatrix()

void NewVectorMatrix::insertMatrix ( LinearDependencyMatrix mat)

Definition at line 333 of file minpoly.cc.

334 {
335  for(int i = 0; i < mat.rows; i++)
336  {
337  insertRow (mat.matrix[i]);
338  }
339 }
unsigned long ** matrix
Definition: minpoly.h:75
int i
Definition: cfEzgcd.cc:123
void insertRow(unsigned long *row)
Definition: minpoly.cc:238

§ insertRow()

void NewVectorMatrix::insertRow ( unsigned long *  row)

Definition at line 238 of file minpoly.cc.

239 {
240  for(int i = 0; i < rows; i++)
241  {
242  unsigned piv = pivots[i];
243  unsigned x = row[piv];
244  // if the corresponding entry in the row is zero, there is nothing to do
245  if(x != 0)
246  {
247  // subtract row[i] times the i-th row
248  // only the non-pivot entries have to be considered
249  // (and also the first entry)
250  row[piv] = 0;
251 
252  int smallestNonPivIndex = 0;
253  while (nonPivots[smallestNonPivIndex] < piv)
254  {
255  smallestNonPivIndex++;
256  }
257 
258  for (int j = smallestNonPivIndex; j < n-rows; j++)
259  {
260  unsigned ind = nonPivots[j];
261  if (matrix[i][ind] != 0)
262  {
263  unsigned long tmp = multMod (matrix[i][ind], x, p);
264  tmp = p - tmp;
265  row[ind] += tmp;
266  if (row[ind] >= p)
267  {
268  row[ind] -= p;
269  }
270  }
271  }
272  }
273  }
274 
275  unsigned piv = firstNonzeroEntry (row);
276 
277  if(piv != -1)
278  {
279  // Normalize and insert row into the matrix.
280  // Then reduce upwards.
281  normalizeRow (row, piv);
282  for(int i = 0; i < n; i++)
283  {
284  matrix[rows][i] = row[i];
285  }
286 
287 
288  for (int i = 0; i < rows; i++)
289  {
290  unsigned x = matrix[i][piv];
291  // if the corresponding entry in the matrix is zero,
292  // there is nothing to do
293  if (x != 0)
294  {
295  for (int j = piv; j < n; j++)
296  {
297  if (row[j] != 0)
298  {
299  unsigned long tmp = multMod(row[j], x, p);
300  tmp = p - tmp;
301  matrix[i][j] += tmp;
302  if (matrix[i][j] >= p)
303  {
304  matrix[i][j] -= p;
305  }
306  }
307  }
308  }
309  }
310 
311  pivots[rows] = piv;
312 
313  // update nonPivots
314  for (int i = 0; i < n-rows; i++)
315  {
316  if (nonPivots[i] == piv)
317  {
318  // shift everything one position to the left
319  for (int j = i; j < n-rows-1; j++)
320  {
321  nonPivots[j] = nonPivots[j+1];
322  }
323 
324  break;
325  }
326  }
327 
328  rows++;
329  }
330 }
unsigned * pivots
Definition: minpoly.h:112
static unsigned long multMod(unsigned long a, unsigned long b, unsigned long p)
Definition: minpoly.h:204
int j
Definition: myNF.cc:70
void normalizeRow(unsigned long *row, unsigned i)
Definition: minpoly.cc:227
unsigned long n
Definition: minpoly.h:110
int i
Definition: cfEzgcd.cc:123
unsigned * nonPivots
Definition: minpoly.h:113
Variable x
Definition: cfModGcd.cc:4023
unsigned rows
Definition: minpoly.h:114
unsigned p
Definition: minpoly.h:109
int firstNonzeroEntry(unsigned long *row)
Definition: minpoly.cc:218

§ normalizeRow()

void NewVectorMatrix::normalizeRow ( unsigned long *  row,
unsigned  i 
)

Definition at line 227 of file minpoly.cc.

228 {
229  unsigned long inv = modularInverse (row[i], p);
230  row[i] = 1;
231 
232  for(int j = i + 1; j < n; j++)
233  {
234  row[j] = multMod (row[j], inv, p);
235  }
236 }
static unsigned long multMod(unsigned long a, unsigned long b, unsigned long p)
Definition: minpoly.h:204
int j
Definition: myNF.cc:70
unsigned long n
Definition: minpoly.h:110
int i
Definition: cfEzgcd.cc:123
unsigned long modularInverse(long long x, long long p)
Definition: minpoly.cc:746
unsigned p
Definition: minpoly.h:109

Field Documentation

§ matrix

unsigned long** NewVectorMatrix::matrix
private

Definition at line 111 of file minpoly.h.

§ n

unsigned long NewVectorMatrix::n
private

Definition at line 110 of file minpoly.h.

§ nonPivots

unsigned* NewVectorMatrix::nonPivots
private

Definition at line 113 of file minpoly.h.

§ p

unsigned NewVectorMatrix::p
private

Definition at line 109 of file minpoly.h.

§ pivots

unsigned* NewVectorMatrix::pivots
private

Definition at line 112 of file minpoly.h.

§ rows

unsigned NewVectorMatrix::rows
private

Definition at line 114 of file minpoly.h.


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