My Project
Loading...
Searching...
No Matches
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 105 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}
int i
Definition: cfEzgcd.cc:132
unsigned * nonPivots
Definition: minpoly.h:111
unsigned p
Definition: minpoly.h:107
unsigned rows
Definition: minpoly.h:112
unsigned * pivots
Definition: minpoly.h:110
unsigned long n
Definition: minpoly.h:108

◆ ~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}
unsigned long ** matrix
Definition: minpoly.h:109

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}
int j
Definition: facHensel.cc:110

◆ 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}
unsigned long ** matrix
Definition: minpoly.h:73
void insertRow(unsigned long *row)
Definition: minpoly.cc:236

◆ 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}
Variable x
Definition: cfModGcd.cc:4082
void normalizeRow(unsigned long *row, unsigned i)
Definition: minpoly.cc:225
int firstNonzeroEntry(unsigned long *row)
Definition: minpoly.cc:216
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.

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}
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: