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.

{
  this->n = n;
  this->p = p;
 
  matrix = new unsigned long *[n];
  for(int i = 0; i < n; i++)
  {
    matrix[i] = new unsigned long[2 * n + 1];
  }
  pivots = new unsigned[n];
  tmprow = new unsigned long[2 * n + 1];
  rows = 0;
}

~LinearDependencyMatrix()

LinearDependencyMatrix::~LinearDependencyMatrix

(

)

Definition at line 34 of file minpoly.cc.

{
  delete[]tmprow;
  delete[]pivots;
 
  for(int i = 0; i < n; i++)
  {
    delete[](matrix[i]);
  }
  delete[]matrix;
}

Member Function Documentation

findLinearDependency()

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

Definition at line 96 of file minpoly.cc.

{
  // Copy newRow to tmprow (we need to add RHS)
  for(int i = 0; i < n; i++)
  {
    tmprow[i] = newRow[i];
    tmprow[n + i] = 0;
  }
  tmprow[2 * n] = 0;
  tmprow[n + rows] = 1;
 
  reduceTmpRow ();
 
  // Is tmprow reduced to zero? Then we have found a linear dependence.
  // Otherwise, we just add tmprow to the matrix.
  unsigned newpivot = firstNonzeroEntry (tmprow);
  if(newpivot == -1)
  {
    for(int i = 0; i <= n; i++)
    {
      dep[i] = tmprow[n + i];
    }
 
    return true;
  }
  else
  {
    normalizeTmp (newpivot);
 
    for(int i = 0; i < 2 * n + 1; i++)
    {
      matrix[rows][i] = tmprow[i];
    }
 
    pivots[rows] = newpivot;
    rows++;
 
    return false;
  }
}

firstNonzeroEntry()

int LinearDependencyMatrix::firstNonzeroEntry

(

unsigned long *

row

)

Definition at line 51 of file minpoly.cc.

{
  for(int i = 0; i < n; i++)
    if(row[i] != 0)
      return i;
 
  return -1;
}

normalizeTmp()

void LinearDependencyMatrix::normalizeTmp

(

unsigned

i

)

Definition at line 88 of file minpoly.cc.

{
  unsigned long inv = modularInverse (tmprow[i], p);
  tmprow[i] = 1;
  for(int j = i + 1; j < 2 * n + 1; j++)
    tmprow[j] = multMod (tmprow[j], inv, p);
}

reduceTmpRow()

void LinearDependencyMatrix::reduceTmpRow

(

)

Definition at line 60 of file minpoly.cc.

{
  for(int i = 0; i < rows; i++)
  {
    unsigned piv = pivots[i];
    unsigned x = tmprow[piv];
    // if the corresponding entry in the row is zero, there is nothing to do
    if(x != 0)
    {
      // subtract tmprow[i] times the i-th row
      for(int j = piv; j < n + rows + 1; j++)
      {
        if (matrix[i][j] != 0)
        {
          unsigned long tmp = multMod (matrix[i][j], x, p);
          tmp = p - tmp;
          tmprow[j] += tmp;
          if (tmprow[j] >= p)
          {
            tmprow[j] -= p;
          }
        }
      }
    }
  }
}

resetMatrix()

void LinearDependencyMatrix::resetMatrix

(

)

Definition at line 46 of file minpoly.cc.

{
  rows = 0;
}

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:

• kernel/linear_algebra/minpoly.h
• kernel/linear_algebra/minpoly.cc