Loading...
Searching...
No Matches
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(unsigned long 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;
}
i
int i
Definition cfEzgcd.cc:132
LinearDependencyMatrix::tmprow
unsigned long * tmprow
Definition minpoly.h:74
LinearDependencyMatrix::p
unsigned p
Definition minpoly.h:71
LinearDependencyMatrix::pivots
unsigned * pivots
Definition minpoly.h:75
LinearDependencyMatrix::n
unsigned long n
Definition minpoly.h:72
LinearDependencyMatrix::matrix
unsigned long ** matrix
Definition minpoly.h:73
LinearDependencyMatrix::rows
unsigned rows
Definition minpoly.h:76

## ~LinearDependencyMatrix()

LinearDependencyMatrix::~LinearDependencyMatrix | ( |  | ) |

Definition at line 34 of file minpoly.cc.

{
delete[]tmprow;
delete[]pivots;
for(unsigned long 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(unsigned long 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(unsigned long i = 0; i <= n; i++)
{
dep[i] = tmprow[n + i];
}
return true;
}
else
{
normalizeTmp (newpivot);
for(unsigned long i = 0; i < 2 * n + 1; i++)
{
matrix[rows][i] = tmprow[i];
}
pivots[rows] = newpivot;
rows++;
return false;
}
}
LinearDependencyMatrix::normalizeTmp
void normalizeTmp(unsigned i)
Definition minpoly.cc:88
LinearDependencyMatrix::firstNonzeroEntry
int firstNonzeroEntry(unsigned long *row)
Definition minpoly.cc:51
LinearDependencyMatrix::reduceTmpRow
void reduceTmpRow()
Definition minpoly.cc:60

## firstNonzeroEntry()

int LinearDependencyMatrix::firstNonzeroEntry | ( | unsigned long * | row | ) |

Definition at line 51 of file minpoly.cc.

{
for(unsigned long 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(unsigned long j = i + 1; j < 2 * n + 1; j++)
tmprow[j] = multMod (tmprow[j], inv, p);
}
j
int j
Definition facHensel.cc:110
modularInverse
unsigned long modularInverse(long long x, long long p)
Definition minpoly.cc:744
multMod
static unsigned long multMod(unsigned long a, unsigned long b, unsigned long p)
Definition minpoly.h:202

## reduceTmpRow()

void LinearDependencyMatrix::reduceTmpRow | ( |  | ) |

Definition at line 60 of file minpoly.cc.

{
for(unsigned long 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(unsigned 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;
}
}
}
}
}
}
x
Variable x
Definition cfModGcd.cc:4090

## resetMatrix()

void LinearDependencyMatrix::resetMatrix | ( |  | ) |

Definition at line 46 of file minpoly.cc.

{
rows = 0;
}

## Friends And Related Symbol 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