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 105 of file minpoly.h.

Constructor & Destructor Documentation

NewVectorMatrix()

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

Definition at line 181 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[n];
  }
 
  pivots = new unsigned[n];
 
  nonPivots = new unsigned[n];
 
  for (int i = 0; i < n; i++)
  {
     nonPivots[i] = i;
  }
 
  rows = 0;
}

~NewVectorMatrix()

NewVectorMatrix::~NewVectorMatrix

(

)

Definition at line 204 of file minpoly.cc.

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

Member Function Documentation

findLargestNonpivot()

int NewVectorMatrix::findLargestNonpivot

(

)

Definition at line 366 of file minpoly.cc.

{
  // This method isn't very efficient, but it is called at most a few times, so efficiency is not important.
  if(rows == n)
    return -1;
 
  for(int i = n-1; i >= 0; i--)
  {
    bool isPivot = false;
    for(int j = 0; j < rows; j++)
    {
      if(pivots[j] == i)
      {
        isPivot = true;
        break;
      }
    }
 
    if(!isPivot)
    {
      return i;
    }
  }
  abort();
}

findSmallestNonpivot()

int NewVectorMatrix::findSmallestNonpivot

(

)

Definition at line 339 of file minpoly.cc.

{
  // This method isn't very efficient, but it is called at most a few times,
  // so efficiency is not important.
  if(rows == n)
    return -1;
 
  for(int i = 0; i < n; i++)
  {
    bool isPivot = false;
    for(int j = 0; j < rows; j++)
    {
      if(pivots[j] == i)
      {
        isPivot = true;
        break;
      }
    }
 
    if(!isPivot)
    {
      return i;
    }
  }
  abort();
}

firstNonzeroEntry()

int NewVectorMatrix::firstNonzeroEntry

(

unsigned long *

row

)

Definition at line 216 of file minpoly.cc.

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

insertMatrix()

void NewVectorMatrix::insertMatrix

(

LinearDependencyMatrix &

mat

)

Definition at line 331 of file minpoly.cc.

{
  for(int i = 0; i < mat.rows; i++)
  {
    insertRow (mat.matrix[i]);
  }
}

insertRow()

void NewVectorMatrix::insertRow

(

unsigned long *

row

)

Definition at line 236 of file minpoly.cc.

{
  for(int i = 0; i < rows; i++)
  {
    unsigned piv = pivots[i];
    unsigned x = row[piv];
    // if the corresponding entry in the row is zero, there is nothing to do
    if(x != 0)
    {
      // subtract row[i] times the i-th row
      // only the non-pivot entries have to be considered
      // (and also the first entry)
      row[piv] = 0;
 
      int smallestNonPivIndex = 0;
      while (nonPivots[smallestNonPivIndex] < piv)
      {
        smallestNonPivIndex++;
      }
 
      for (int j = smallestNonPivIndex; j < n-rows; j++)
      {
        unsigned ind = nonPivots[j];
        if (matrix[i][ind] != 0)
        {
          unsigned long tmp = multMod (matrix[i][ind], x, p);
          tmp = p - tmp;
          row[ind] += tmp;
          if (row[ind] >= p)
          {
            row[ind] -= p;
          }
        }
      }
    }
  }
 
  unsigned piv = firstNonzeroEntry (row);
 
  if(piv != -1)
  {
    // Normalize and insert row into the matrix.
    // Then reduce upwards.
    normalizeRow (row, piv);
    for(int i = 0; i < n; i++)
    {
      matrix[rows][i] = row[i];
    }
 
 
    for (int i = 0; i < rows; i++)
    {
      unsigned x = matrix[i][piv];
      // if the corresponding entry in the matrix is zero,
      // there is nothing to do
      if (x != 0)
      {
        for (int j = piv; j < n; j++)
        {
          if (row[j] != 0)
          {
            unsigned long tmp = multMod(row[j], x, p);
            tmp = p - tmp;
            matrix[i][j] += tmp;
            if (matrix[i][j] >= p)
            {
              matrix[i][j] -= p;
            }
          }
        }
      }
    }
 
    pivots[rows] = piv;
 
    // update nonPivots
    for (int i = 0; i < n-rows; i++)
    {
      if (nonPivots[i] == piv)
      {
        // shift everything one position to the left
        for (int j = i; j < n-rows-1; j++)
        {
          nonPivots[j] = nonPivots[j+1];
        }
 
        break;
      }
    }
 
    rows++;
  }
}

normalizeRow()

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

Definition at line 225 of file minpoly.cc.

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

Field Documentation

matrix

unsigned long** NewVectorMatrix::matrix

private

Definition at line 109 of file minpoly.h.

n

unsigned long NewVectorMatrix::n

private

Definition at line 108 of file minpoly.h.

nonPivots

unsigned* NewVectorMatrix::nonPivots

private

Definition at line 111 of file minpoly.h.

p

unsigned NewVectorMatrix::p

private

Definition at line 107 of file minpoly.h.

pivots

unsigned* NewVectorMatrix::pivots

private

Definition at line 110 of file minpoly.h.

rows

unsigned NewVectorMatrix::rows

private

Definition at line 112 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