My Project  debian-1:4.1.1-p2+ds-4
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 104 of file minpoly.h.

Constructor & Destructor Documentation

◆ NewVectorMatrix()

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

Definition at line 181 of file minpoly.cc.

182 {
183  this->n = n;
184  this->p = p;
185 
186  matrix = new unsigned long *[n];
187  for(int i = 0; i < n; i++)
188  {
189  matrix[i] = new unsigned long[n];
190  }
191 
192  pivots = new unsigned[n];
193 
194  nonPivots = new unsigned[n];
195 
196  for (int i = 0; i < n; i++)
197  {
198  nonPivots[i] = i;
199  }
200 
201  rows = 0;
202 }

◆ ~NewVectorMatrix()

NewVectorMatrix::~NewVectorMatrix ( )

Definition at line 204 of file minpoly.cc.

205 {
206  delete nonPivots;
207  delete pivots;
208 
209  for(int i = 0; i < n; i++)
210  {
211  delete[]matrix[i];
212  }
213  delete matrix;
214 }

Member Function Documentation

◆ findLargestNonpivot()

int NewVectorMatrix::findLargestNonpivot ( )

Definition at line 366 of file minpoly.cc.

367 {
368  // This method isn't very efficient, but it is called at most a few times, so efficiency is not important.
369  if(rows == n)
370  return -1;
371 
372  for(int i = n-1; i >= 0; i--)
373  {
374  bool isPivot = false;
375  for(int j = 0; j < rows; j++)
376  {
377  if(pivots[j] == i)
378  {
379  isPivot = true;
380  break;
381  }
382  }
383 
384  if(!isPivot)
385  {
386  return i;
387  }
388  }
389  abort();
390 }

◆ findSmallestNonpivot()

int NewVectorMatrix::findSmallestNonpivot ( )

Definition at line 339 of file minpoly.cc.

340 {
341  // This method isn't very efficient, but it is called at most a few times,
342  // so efficiency is not important.
343  if(rows == n)
344  return -1;
345 
346  for(int i = 0; i < n; i++)
347  {
348  bool isPivot = false;
349  for(int j = 0; j < rows; j++)
350  {
351  if(pivots[j] == i)
352  {
353  isPivot = true;
354  break;
355  }
356  }
357 
358  if(!isPivot)
359  {
360  return i;
361  }
362  }
363  abort();
364 }

◆ firstNonzeroEntry()

int NewVectorMatrix::firstNonzeroEntry ( unsigned long *  row)

Definition at line 216 of file minpoly.cc.

217 {
218  for(int i = 0; i < n; i++)
219  if(row[i] != 0)
220  return i;
221 
222  return -1;
223 }

◆ insertMatrix()

void NewVectorMatrix::insertMatrix ( LinearDependencyMatrix mat)

Definition at line 331 of file minpoly.cc.

332 {
333  for(int i = 0; i < mat.rows; i++)
334  {
335  insertRow (mat.matrix[i]);
336  }
337 }

◆ insertRow()

void NewVectorMatrix::insertRow ( unsigned long *  row)

Definition at line 236 of file minpoly.cc.

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

◆ normalizeRow()

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

Definition at line 225 of file minpoly.cc.

226 {
227  unsigned long inv = modularInverse (row[i], p);
228  row[i] = 1;
229 
230  for(int j = i + 1; j < n; j++)
231  {
232  row[j] = multMod (row[j], inv, p);
233  }
234 }

Field Documentation

◆ matrix

unsigned long** NewVectorMatrix::matrix
private

Definition at line 108 of file minpoly.h.

◆ n

unsigned long NewVectorMatrix::n
private

Definition at line 107 of file minpoly.h.

◆ nonPivots

unsigned* NewVectorMatrix::nonPivots
private

Definition at line 110 of file minpoly.h.

◆ p

unsigned NewVectorMatrix::p
private

Definition at line 106 of file minpoly.h.

◆ pivots

unsigned* NewVectorMatrix::pivots
private

Definition at line 109 of file minpoly.h.

◆ rows

unsigned NewVectorMatrix::rows
private

Definition at line 111 of file minpoly.h.


The documentation for this class was generated from the following files:
ip_smatrix
Definition: matpol.h:13
j
int j
Definition: facHensel.cc:105
x
Variable x
Definition: cfModGcd.cc:4023
LinearDependencyMatrix::rows
unsigned rows
Definition: minpoly.h:75
NewVectorMatrix::normalizeRow
void normalizeRow(unsigned long *row, unsigned i)
Definition: minpoly.cc:225
NewVectorMatrix::matrix
unsigned long ** matrix
Definition: minpoly.h:108
NewVectorMatrix::firstNonzeroEntry
int firstNonzeroEntry(unsigned long *row)
Definition: minpoly.cc:216
multMod
static unsigned long multMod(unsigned long a, unsigned long b, unsigned long p)
Definition: minpoly.h:201
NewVectorMatrix::insertRow
void insertRow(unsigned long *row)
Definition: minpoly.cc:236
NewVectorMatrix::pivots
unsigned * pivots
Definition: minpoly.h:109
NewVectorMatrix::p
unsigned p
Definition: minpoly.h:106
i
int i
Definition: cfEzgcd.cc:125
LinearDependencyMatrix::matrix
unsigned long ** matrix
Definition: minpoly.h:72
NewVectorMatrix::n
unsigned long n
Definition: minpoly.h:107
NewVectorMatrix::rows
unsigned rows
Definition: minpoly.h:111
NewVectorMatrix::nonPivots
unsigned * nonPivots
Definition: minpoly.h:110
modularInverse
unsigned long modularInverse(long long x, long long p)
Definition: minpoly.cc:744