My Project  debian-1:4.1.2-p1+ds-2
Data Structures | Enumerations | Functions
nforder.h File Reference

Go to the source code of this file.

Data Structures

class  nforder
 

Enumerations

enum  order_flags_log { one_is_one, is_maximal_known, is_maximal }
 

Functions

void basis_elt (bigintmat *m, int i)
 
nforderonestep (nforder *o, number p, coeffs c)
 
nforderpmaximal (nforder *o, number p)
 
nforderround2 (nforder *o)
 
bigintmatradicalmodpbase (nforder *o, number p, coeffs c)
 
number multring (bigintmat *nbase, nforder *o, number p)
 
void nforder_delete (nforder *o)
 

Enumeration Type Documentation

◆ order_flags_log

Enumerator
one_is_one 
is_maximal_known 
is_maximal 

Definition at line 17 of file nforder.h.

17  {
18  one_is_one, //if 1 is the first basis element
21 };

Function Documentation

◆ basis_elt()

void basis_elt ( bigintmat m,
int  i 
)

Definition at line 422 of file nforder.cpp.

422  {
423  if (((m->rows() == 1) && (i <= m->cols())) || ((m->cols() == 1) && (i <= m->rows()))) {
424  // Falls m Zeilen- oder Spaltenvektor ist, setze alle Einträge auf 0 und Eintrag i auf 1 (Koeff-Vektor des i-ten Basiselements)
425  number t1 = n_Init(0,m->basecoeffs());
426  for (int j=0; ((j<m->rows()) || (j<m->cols())); j++) {
427  m->set(j, t1);
428 
429  }
430  n_Delete(&t1,m->basecoeffs());
431  number t2 = n_Init(1,m->basecoeffs());
432  m->set(i-1, t2);
433  n_Delete(&t2,m->basecoeffs());
434  }
435  else
436  Werror("Error in basis_elt. Not a vector.");
437 }

◆ multring()

number multring ( bigintmat nbase,
nforder o,
number  p 
)

Definition at line 553 of file nforder.cpp.

553  {
554  coeffs R = o->basecoeffs();
555  number divi;
556  int n = o->getDim();
557 
558  bigintmat *inv = new bigintmat(n, n, R);
559  divi = nbase->pseudoinv(inv);
560 
561  // Zusammenbau der "langen" Matrix
562  bigintmat *lon = new bigintmat(n, 0, R);
563  bigintmat *oldlon;
564  bigintmat *mm = new bigintmat(n, n, R);
565  bigintmat *temp = new bigintmat(n, 1, R);
566  bigintmat *nochnetemp = new bigintmat(n, n, R);
567 
568  for (int i=1; i<=n; i++) {
569  nbase->getcol(i, temp);
570  o->multmap(temp, mm);
571  bimMult(inv, mm, nochnetemp);
572  mm->copy(nochnetemp);
573  mm->inpTranspose();
574  oldlon = lon;
575  lon = new bigintmat(n, (i)*n, o->basecoeffs());
576  lon->concatcol(oldlon, mm);
577  delete oldlon;
578  }
579 
580  lon->skaldiv(divi);
581 
582  bigintmat * red;
583  if (1) {
584  bigintmat * cmp = lon->modhnf(p, o->basecoeffs());
585  red = cmp;
586  } else {
587  lon->hnf();
588  red = new bigintmat(n, n, o->basecoeffs());
589  lon->getColRange((n-1)*n+1, n, red);
590  }
591  delete lon;
592  red->inpTranspose();
593 
594  number divisor = red->pseudoinv(nbase);
595  nbase->hnf();
596 
597  delete inv;
598  delete mm;
599  delete temp;
600  delete red;
601  delete nochnetemp;
602  n_Delete(&divi, o->basecoeffs());
603  return divisor;
604 }

◆ nforder_delete()

void nforder_delete ( nforder o)

Definition at line 132 of file nforder.cpp.

132  {
133  if (o->ref_count_decref()>0) {
134  return;
135  }
136  delete o;
137 }

◆ onestep()

nforder* onestep ( nforder o,
number  p,
coeffs  c 
)

Definition at line 608 of file nforder.cpp.

608  {
609  // Berechne F_p-Basis von I_p/pI_p
610  bigintmat *basis;
611  basis = radicalmodpbase(o, p, c);
612 
613 
614  // Bestimme Basis vom Ring der Multiplikatoren (speicher diese in basis), und Nenner davon (in divisor)
615  number divisor = multring(basis, o, p);
616  // Erzeuge neue Ordnung, der o zu Grunde liegt, mit Basis basis und Nenner divisor
617  if (basis->isOne() && n_IsOne(divisor, c)) {
618  delete basis;
619  n_Delete(&divisor, c);
620  return o;
621  }
622 
623  nforder *no = new nforder(o, basis, divisor, c);
624 
625  delete basis;
626  n_Delete(&divisor, c);
627  return no;
628 }

◆ pmaximal()

nforder* pmaximal ( nforder o,
number  p 
)

Definition at line 632 of file nforder.cpp.

632  {
633  coeffs c = o->basecoeffs();
634  nforder *no = o;
635  nforder *otemp;
636  // TODO: check if p^2 still divides disc (maybe in onestep)
637  // simplify the tower
638  do {
639  otemp = no;
640  no = onestep(otemp, p, c);
641  if (no==otemp)
642  break;
643  nforder_delete (otemp);
644  otemp = no->simplify();
645  nforder_delete (no);
646  no = otemp;
647  } while (1);
648  return no;
649 }

◆ radicalmodpbase()

bigintmat* radicalmodpbase ( nforder o,
number  p,
coeffs  c 
)

Definition at line 446 of file nforder.cpp.

446  {
447 
448  number dimen = n_Init(o->getDim(), o->basecoeffs());
449  int n = o->getDim();
450 
451  bigintmat *m, *bas;
452  // Berechnet F_p-Basis von I_p/pI_p (Radical mod p)
453  // Dazu:
454  if (n_Greater(p, dimen, c)) {
455  // Falls Primzahl größer gleich Dimension der Ordnung, so berechne Kern der Spurmatrix modulo p.
456  // also works it p is no prime.
457  m = o->traceMatrix();
458  bas = new bigintmat(n, 1, o->basecoeffs());
459  } else {
460  // Sonst: Berechne Kern der Abbildung x -> x^(p^j) mod p, wobei j>0 mit p^j >= dimension
461  int j = 1;
462  // ex als number, oder reicht long long int?
463  // Finde j von oben und berechne p^j
464  number ex = n_Init(1, o->basecoeffs());
465  number temp;
466  while (n_Greater(dimen, ex, o->basecoeffs())) {
467  temp = n_Mult(ex, p, o->basecoeffs());
468  n_Delete(&ex, o->basecoeffs());
469  ex = temp;
470  j++;
471  }
472 
473  // Berechne Abbildungsmatrix der oben genannten Abbildung und speichere diese in m (genauere Erklärung dazu: Siehe multmap())
474  m = new bigintmat(n, n, o->basecoeffs());
475  bas = new bigintmat(n, 1, o->basecoeffs());
476  bigintmat *prod = new bigintmat(n, 1, o->basecoeffs());
477 
478  number klauf;
479  number eins = n_Init(1, o->basecoeffs());
480 
481  for (int i=1; i<=n; i++) {
482  basis_elt(bas, i);
483  prod->copy(bas);
484  klauf = n_Init(1, o->basecoeffs());
485  for (; n_Greater(ex, klauf, o->basecoeffs());) {
486  o->elMult(prod, bas);
487  prod->mod(p);
488  temp = n_Add(klauf, eins, o->basecoeffs());
489  n_Delete(&klauf, o->basecoeffs());
490  klauf = temp;
491  }
492  n_Delete(&klauf, o->basecoeffs());
493  m->setcol(i, prod);
494  }
495 
496  delete prod;
497  n_Delete(&ex, o->basecoeffs());
498  n_Delete(&eins, o->basecoeffs());
499 
500  }
501 
502  bigintmat *kbase = new bigintmat(n, n, o->basecoeffs());
503 
504  // Speichere Basiselemente von Kern der Matrix m (Spurmatrix oder Abbildungsmatrix, je nach if-else-Fall) (von Z/pZ -> Z/pZ) in kbase (ersten kdim Spalten bilden Basis)
505  int kdim = kernbase(m, kbase, p, c);
506  // Schreibe für jedes i=1,, .., dimension p*(i-tes Basiselement) als Spalten in Matrix gen, dahinter die oben errechnete Basis vom Kern
507  // Wir erhalten (als Spalten) ein Erzeugendensystem vom Kern von Z->Z/pZ: x->x^(p^j)
508  bigintmat *gen = new bigintmat(n, n+kdim, o->basecoeffs());
509 
510  for (int i=1; i<=n; i++) {
511  basis_elt(bas, i);
512  bas->skalmult(p, c);
513  gen->setcol(i, bas);
514  }
515  for (int i=1; i<=kdim; i++) {
516  kbase->getcol(i, bas);
517  gen->setcol(i+n, bas);
518  }
519 
520  // HNF auf EZS anwenden liefert (als letzten dimension Spalten) eine Basis des Kerns
521  gen->hnf();
522  bigintmat *tmp = new bigintmat(n, 1, o->basecoeffs());
523  bigintmat *nbase = new bigintmat(n, n, o->basecoeffs());
524  // Schreibe diese als Spalten in nbase und gib nbase zurück
525  for (int i=1; i<=n; i++) {
526  gen->getcol(gen->cols()-n+i, tmp);
527  nbase->setcol(i, tmp);
528  }
529 
530  n_Delete(&dimen, o->basecoeffs());
531  delete m;
532  delete bas;
533  delete kbase;
534  delete gen;
535  delete tmp;
536  return nbase;
537 
538 }

◆ round2()

nforder* round2 ( nforder o)
is_maximal
Definition: nforder.h:20
j
int j
Definition: facHensel.cc:105
nforder_delete
void nforder_delete(nforder *o)
Definition: nforder.cpp:132
bigintmat::concatcol
void concatcol(bigintmat *a, bigintmat *b)
Definition: bigintmat.cc:1099
bigintmat
Definition: bigintmat.h:49
prod
fq_nmod_poly_t prod
Definition: facHensel.cc:95
n_Delete
static FORCE_INLINE void n_Delete(number *p, const coeffs r)
delete 'p'
Definition: coeffs.h:454
nforder::traceMatrix
bigintmat * traceMatrix()
Definition: nforder.cpp:196
n_Greater
static FORCE_INLINE BOOLEAN n_Greater(number a, number b, const coeffs r)
ordered fields: TRUE iff 'a' is larger than 'b'; in Z/pZ: TRUE iff la > lb, where la and lb are the l...
Definition: coeffs.h:510
n_IsOne
static FORCE_INLINE BOOLEAN n_IsOne(number n, const coeffs r)
TRUE iff 'n' represents the one element.
Definition: coeffs.h:467
basis_elt
void basis_elt(bigintmat *m, int i)
Definition: nforder.cpp:422
nforder::basecoeffs
coeffs basecoeffs() const
Definition: nforder.h:76
nforder::multmap
void multmap(bigintmat *a, bigintmat *m)
Definition: nforder.cpp:404
bimMult
bigintmat * bimMult(bigintmat *a, bigintmat *b)
Definition: bigintmat.cc:255
bigintmat::hnf
void hnf()
transforms INPLACE to HNF
Definition: bigintmat.cc:1661
bigintmat::skaldiv
void skaldiv(number b)
Macht Ganzzahldivision aller Matrixeinträge mit b.
Definition: bigintmat.cc:1862
n_Add
static FORCE_INLINE number n_Add(number a, number b, const coeffs r)
return the sum of 'a' and 'b', i.e., a+b
Definition: coeffs.h:655
kernbase
int kernbase(bigintmat *a, bigintmat *c, number p, coeffs q)
a basis for the nullspace of a mod p: only used internally in Round2. Don't use it.
Definition: bigintmat.cc:2601
nforder
Definition: nforder.h:23
i
int i
Definition: cfEzgcd.cc:125
bigintmat::copy
bool copy(bigintmat *b)
Kopiert Einträge von b auf Bigintmat.
Definition: bigintmat.cc:1260
bigintmat::getColRange
void getColRange(int j, int no, bigintmat *a)
copies the no-columns staring by j (so j...j+no-1) into the pre-allocated a
Definition: bigintmat.cc:779
bigintmat::modhnf
bigintmat * modhnf(number p, coeffs c)
computes HNF(this | p*I)
Definition: bigintmat.cc:1833
bigintmat::isOne
int isOne()
is matrix is identity
Definition: bigintmat.cc:1301
one_is_one
Definition: nforder.h:18
coeffs
n_Mult
static FORCE_INLINE number n_Mult(number a, number b, const coeffs r)
return the product of 'a' and 'b', i.e., a*b
Definition: coeffs.h:635
n_Init
static FORCE_INLINE number n_Init(long i, const coeffs r)
a number representing i in the given coeff field/ring r
Definition: coeffs.h:537
bigintmat::getcol
void getcol(int j, bigintmat *a)
copies the j-th column into the matrix a - which needs to be pre-allocated with the correct size.
Definition: bigintmat.cc:748
nforder::getDim
int getDim()
Definition: nforder.cpp:235
bigintmat::cols
int cols() const
Definition: bigintmat.h:143
bigintmat::pseudoinv
number pseudoinv(bigintmat *a)
Speichert in Matrix a die Pseudoinverse, liefert den Nenner zurück.
Definition: bigintmat.cc:1416
bigintmat::setcol
void setcol(int j, bigintmat *m)
Setzt j-te Spalte gleich übergebenem Vektor (Matrix) m.
Definition: bigintmat.cc:827
is_maximal_known
Definition: nforder.h:19
nforder::ref_count_decref
int ref_count_decref()
Definition: nforder.h:51
nforder::elMult
void elMult(bigintmat *a, bigintmat *b)
Definition: nforder.cpp:321
nforder::simplify
nforder * simplify()
Definition: nforder.cpp:275
Werror
void Werror(const char *fmt,...)
Definition: reporter.cc:188
radicalmodpbase
bigintmat * radicalmodpbase(nforder *o, number p, coeffs c)
Definition: nforder.cpp:446
m
int m
Definition: cfEzgcd.cc:121
onestep
nforder * onestep(nforder *o, number p, coeffs c)
Definition: nforder.cpp:608
R
#define R
Definition: sirandom.c:27
p
int p
Definition: cfModGcd.cc:4019
multring
number multring(bigintmat *nbase, nforder *o, number p)
Definition: nforder.cpp:553
bigintmat::inpTranspose
void inpTranspose()
transpose in place
Definition: bigintmat.cc:50
bigintmat::skalmult
bool skalmult(number b, coeffs c)
Multipliziert zur Matrix den Skalar b hinzu.
Definition: bigintmat.cc:939