Loading...
Searching...
No Matches
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(unsigned long i = 0; i < n; i++)
{
matrix[i] = new unsigned long[n];
}
pivots = new unsigned[n];
nonPivots = new unsigned[n];
for (unsigned long i = 0; i < n; i++)
{
nonPivots[i] = i;
}
rows = 0;
}
i
int i
Definition cfEzgcd.cc:132
NewVectorMatrix::nonPivots
unsigned * nonPivots
Definition minpoly.h:111
NewVectorMatrix::p
unsigned p
Definition minpoly.h:107
NewVectorMatrix::rows
unsigned rows
Definition minpoly.h:112
NewVectorMatrix::matrix
unsigned long ** matrix
Definition minpoly.h:109
NewVectorMatrix::pivots
unsigned * pivots
Definition minpoly.h:110
NewVectorMatrix::n
unsigned long n
Definition minpoly.h:108

## ~NewVectorMatrix()

NewVectorMatrix::~NewVectorMatrix | ( |  | ) |

Definition at line 204 of file minpoly.cc.

{
delete nonPivots;
delete pivots;
for(unsigned long 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(unsigned long i = n-1; i >= 0; i--)
{
bool isPivot = false;
for(unsigned j = 0; j < rows; j++)
{
if(pivots[j] == i)
{
isPivot = true;
break;
}
}
if(!isPivot)
{
return i;
}
}
abort();
}
j
int j
Definition facHensel.cc:110

## 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(unsigned long i = 0; i < n; i++)
{
bool isPivot = false;
for(unsigned 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(unsigned long 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(unsigned i = 0; i < mat.rows; i++)
{
insertRow (mat.matrix[i]);
}
}
LinearDependencyMatrix::matrix
unsigned long ** matrix
Definition minpoly.h:73
LinearDependencyMatrix::rows
unsigned rows
Definition minpoly.h:76
NewVectorMatrix::insertRow
void insertRow(unsigned long *row)
Definition minpoly.cc:236

## insertRow()

void NewVectorMatrix::insertRow | ( | unsigned long * | row | ) |

Definition at line 236 of file minpoly.cc.

{
for(unsigned long 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 (unsigned long 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(unsigned long i = 0; i < n; i++)
{
matrix[rows][i] = row[i];
}
for (unsigned long 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 (unsigned long 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 (unsigned long i = 0; i < n-rows; i++)
{
if (nonPivots[i] == piv)
{
// shift everything one position to the left
for (unsigned long j = i; j < n-rows-1; j++)
{
nonPivots[j] = nonPivots[j+1];
}
break;
}
}
rows++;
}
}
x
Variable x
Definition cfModGcd.cc:4090
NewVectorMatrix::normalizeRow
void normalizeRow(unsigned long *row, unsigned i)
Definition minpoly.cc:225
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:202

## 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(unsigned long j = i + 1; j < n; j++)
{
row[j] = multMod (row[j], inv, p);
}
}
modularInverse
unsigned long modularInverse(long long x, long long p)
Definition minpoly.cc:744

## 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