Changeset c514f7 in git


Ignore:
Timestamp:
May 8, 2014, 5:31:01 PM (10 years ago)
Author:
Martin Lee <martinlee84@…>
Branches:
(u'spielwiese', 'fe61d9c35bf7c61f2b6cbf1b56e25e2f08d536cc')
Children:
2ed604a09e127188d784bc2189e15095cbbdc700
Parents:
6bf0b477b548d51312b5f5d9ba1d25fadc4086b6
git-author:
Martin Lee <martinlee84@web.de>2014-05-08 17:31:01+02:00
git-committer:
Martin Lee <martinlee84@web.de>2014-05-12 14:35:03+02:00
Message:
chg: moved helper functions from cfCharSets and facAlgFunc to respective Util files
chg: better nomenclature, code format, include structure
Location:
factory
Files:
4 added
5 edited

Legend:

Unmodified
Added
Removed

  • factory/Makefile.am

    r6bf0b4 rc514f7  
    2121                cf_char.cc \
    2222                cfCharSets.cc \
     23                cfCharSetsUtil.cc \
    2324                cf_chinese.cc \
    2425                cf_cyclo.cc \
    … …  
    5455                facAlgExt.cc \
    5556                facAlgFunc.cc \
     57                facAlgFuncUtil.cc \
    5658                facBivar.cc \
    5759                fac_ezgcd.cc \
    … …  
    99101                cf_algorithm.h \
    100102                cfCharSets.h \
     103                cfCharSetsUtil.h \
    101104                cf_cyclo.h \
    102105                cf_defs.h \
    … …  
    126129                facAlgExt.h \
    127130                facAlgFunc.h \
     131                facAlgFuncUtil.h \
    128132                facBivar.h \
    129133                facFactorize.h \

  • factory/cfCharSets.cc

    r6bf0b4 rc514f7  
    1919/*****************************************************************************/
    2020
     21#include "config.h"
     22
    2123#include "timing.h"
    2224
     25#include "canonicalform.h"
    2326#include "cfCharSets.h"
    24 #include "canonicalform.h"
     27#include "cfCharSetsUtil.h"
    2528#include "cf_algorithm.h"
    2629#include "facAlgFunc.h"
    2730
    2831TIMING_DEFINE_PRINT(neworder_time)
    29 
    30 #define __ARRAY_INIT__ -1
    31 
    32 // the maximal degree of polys in PS wrt. variable x
    33 static int
    34 degpsmax (const CFList & PS, const Variable & x,
    35           Intarray & A, Intarray & C)
    36 {
    37   int varlevel= level(x);
    38   if (A[varlevel] != __ARRAY_INIT__)
    39     return A[varlevel];
    40   int max= 0, temp, count= 0;
    41  
    42   for (CFListIterator i= PS; i.hasItem(); i++)
    43   {
    44     temp= degree (i.getItem(), x);
    45     if (temp > max)
    46     {
    47       max= temp;
    48       count = 0;
    49     }
    50     if (temp == max)
    51       count += max;  // we count the number of polys
    52   }
    53   A[varlevel]= max;
    54   C[varlevel]= count;
    55   return max;
    56 }
    57 
    58 // the minimal non-zero degree of polys in PS wrt. x
    59 // returns 0 if variable x doesn't occure in any of the polys
    60 static int
    61 degpsmin (const CFList & PS, const Variable & x, Intarray & A, Intarray & B,
    62           Intarray & C, Intarray & D)
    63 {
    64   int varlevel= level(x);
    65   if (B[varlevel] != __ARRAY_INIT__ )
    66     return B[varlevel];
    67   int min= degpsmax (PS, x, A, C), temp, count= 0;
    68 
    69   if (min == 0)
    70   {
    71     B[varlevel]= min;
    72     D[varlevel]= min;
    73     return min;
    74   }
    75   else
    76   {
    77     for (CFListIterator i= PS; i.hasItem(); i++)
    78     {
    79       temp= degree (i.getItem(), x);
    80       if (temp < min && temp != 0)
    81       {
    82         min= temp;
    83         count= 0;
    84       }
    85       if (temp == min)
    86         count += min; // we count the number of polys
    87     }
    88   }
    89   B[varlevel]= min;
    90   D[varlevel]= count;
    91   return min;
    92 }
    93 
    94 // the minimal total degree of lcoeffs of polys in PS wrt. x
    95 // for those polys having degree degpsmin in x.
    96 // F will be assigned the minimal number of terms of those lcoeffs
    97 static int
    98 Tdeg (const CFList & PS, const Variable & x, Intarray & A, Intarray & B,
    99       Intarray & C, Intarray & D, Intarray & E, Intarray & F)
    100 {
    101   int k= degpsmin (PS, x, A, B, C, D), varlevel= level(x), min= 0;
    102 
    103   if (E[varlevel] != __ARRAY_INIT__)
    104     return E [varlevel];
    105   if (k == 0)
    106   {
    107     E[varlevel]= 0;
    108     F[varlevel]= 0;
    109   }
    110   else
    111   {
    112     int nopslc= 0;
    113     CFList LCdegList;
    114     CanonicalForm elem;
    115     CFListIterator i;
    116 
    117     for (i= PS; i.hasItem(); i++)
    118     {
    119       elem= i.getItem();
    120       if (degree (elem, x) == k)
    121         LCdegList.append (LC (elem, x));
    122     }
    123    
    124     if (LCdegList.length() > 0)
    125     {
    126       CFList TermList;
    127       int newmin, newnopslc;
    128 
    129       min= totaldegree (LCdegList.getFirst());
    130       TermList= get_Terms (LCdegList.getFirst());
    131       nopslc= TermList.length();
    132       for (i= LCdegList; i.hasItem(); i++)
    133       {
    134         elem= i.getItem();
    135         newmin= totaldegree(elem);
    136         TermList= get_Terms(elem);
    137         newnopslc= TermList.length();
    138         if (newmin < min)
    139           min= newmin;
    140         if (newnopslc < nopslc)
    141           nopslc= newnopslc;
    142       }
    143      
    144     }
    145     E[varlevel]= min;
    146     F[varlevel]= nopslc;
    147   }
    148   return min;
    149 }
    150 
    151 // The number of the poly in which Variable x first occures
    152 static int
    153 nr_of_poly( const CFList & PS, const Variable & x, Intarray & G)
    154 {
    155   int min= 0, varlevel= level(x);
    156   if (G[varlevel] != __ARRAY_INIT__)
    157     return G[varlevel];
    158   for (CFListIterator i= PS; i.hasItem(); i++)
    159   {
    160     min += 1;
    161     if (degree (i.getItem(), x) > 0)
    162       break;
    163   }
    164   G[varlevel]= min;
    165   return min;
    166 }
    167 
    168 static int
    169 degord (const Variable & x, const Variable & y, const CFList & PS,
    170         Intarray & A, Intarray & B, Intarray & C, Intarray & D,
    171         Intarray & E, Intarray & F, Intarray & G)
    172 {
    173   int xlevel= level(x), ylevel= level(y);
    174 
    175   if      (degpsmax(PS,y,A,C) < degpsmax(PS,x,A,C))         return 1;
    176   else if (degpsmax(PS,x,A,C) < degpsmax(PS,y,A,C) )        return 0;
    177   else if (C[ylevel] < C[xlevel])                           return 1;
    178   else if (C[xlevel] < C[ylevel])                           return 0;
    179   else if (degpsmin(PS,x,A,B,C,D) < degpsmin(PS,y,A,B,C,D)) return 1;
    180   else if (degpsmin(PS,y,A,B,C,D) < degpsmin(PS,x,A,B,C,D)) return 0;
    181   else if (D[ylevel] < D[xlevel])                           return 1;
    182   else if (D[xlevel] < D[ylevel])                           return 0;
    183   else if (Tdeg(PS,y,A,B,C,D,E,F) < Tdeg(PS,x,A,B,C,D,E,F)) return 1;
    184   else if (Tdeg(PS,x,A,B,C,D,E,F) < Tdeg(PS,y,A,B,C,D,E,F)) return 0;
    185   else if (F[ylevel] < F[xlevel])                           return 1;
    186   else if (F[xlevel] < F[ylevel])                           return 0;
    187   else if (nr_of_poly(PS,x,G) <= nr_of_poly(PS,y,G))        return 1;
    188   else return 0;
    189 }
    190 
    191 // determine the highest variable of all involved Variables in PS
    192 // NOTE:
    193 //    this doesn't give always the correct answer:
    194 //    If a variable is assigned the highest level in the definition of the
    195 //    original ring, but doesn't occure in any of the
    196 //    polynomials, get_max_var returns the variable with a level lower than
    197 //    the highest level.
    198 //    Is there a workaround?
    199 // But for the redefinition of the ring this doesn't matter due to the
    200 // implementation of neworder().
    201 
    202 static Variable
    203 get_max_var(const CFList & PS)
    204 {
    205   Variable x= PS.getFirst().mvar(), y;
    206   for (CFListIterator i= PS; i.hasItem(); i++)
    207   {
    208     y= i.getItem().mvar();
    209     if (y > x)
    210       x= y;
    211   }
    212   return x;
    213 }
    214 
    215 
    216 // determine if variable x is in one and only one of the polynomials in PS
    217 // first criterion for neworder
    218 static CFList
    219 only_in_one (const CFList & PS, const Variable & x)
    220 {
    221   CFList output;
    222 
    223   for (CFListIterator i= PS; i.hasItem(); i++ )
    224   {
    225     if (degree (i.getItem(), x) >= 1)
    226       output.insert (i.getItem());
    227     if (output.length() >= 2)
    228       break;
    229   }
    230   return output;
    231 }
    232 
    233 // initialize all Arrays (of same range) with __ARRAY_INIT__
    234 static void
    235 initArray (const int highest_level, Intarray & A, Intarray & B, Intarray & C,
    236            Intarray & D, Intarray & E, Intarray & F, Intarray & G)
    237 {
    238   for (int i=1 ; i <= highest_level; i ++)
    239   {
    240     A[i]= __ARRAY_INIT__;
    241     B[i]= __ARRAY_INIT__;
    242     C[i]= __ARRAY_INIT__;
    243     D[i]= __ARRAY_INIT__;
    244     E[i]= __ARRAY_INIT__;
    245     F[i]= __ARRAY_INIT__;
    246     G[i]= __ARRAY_INIT__;
    247   }
    248 }
    249 
    250 // now for the second criterion; a little more complex
    251 //
    252 // idea: set up seven arrays of lenth highest_level
    253 //       (of which some entries may be empty, because of only_in_one!)
    254 //   A saves maxdegree of Variable x in A(level(x))
    255 //   B saves mindegree of Variable x in B(level(x))
    256 //   C saves the number of polys in PS which have degree A(level(x)) in
    257 //     D(level(x))
    258 //   D saves the number of polys in PS which have degree B(level(x)) in
    259 //     D(level(x))
    260 //   E saves the minimal total degree of lcoeffs of polys wrt x in E(level(x))
    261 //   F saves the minimal number of terms of lcoeffs of E(level(x)) in F(~)
    262 //   G saves nr of poly Variable x has first deg <> 0
    263 
    264 #define __INIT_GAP__ 3
    265 static Varlist
    266 reorderb (const Varlist & difference, const CFList & PS,
    267           const int highest_level)
    268 {
    269   Intarray A(1, highest_level), B(1, highest_level), C(1, highest_level),
    270            D(1, highest_level), E(1, highest_level), F(1, highest_level),
    271            G(1, highest_level);
    272   initArray (highest_level, A, B, C, D, E, F, G);
    273   int i= 0, j, n= difference.length(), gap= 1 + __INIT_GAP__;
    274   Variable temp;
    275   Array<Variable> v(0, n);
    276   VarlistIterator J;
    277 
    278   for (J= difference; J.hasItem(); J++ )
    279   {
    280     v[i]= J.getItem();
    281     i++;
    282   }
    283  
    284   while (gap <= n)
    285     gap = __INIT_GAP__ * gap + 1;
    286   gap /= __INIT_GAP__;
    287  
    288   while (gap > 0)
    289   {
    290     for (i= gap; i <= n - 1; i++)
    291     {
    292       temp= v[i];
    293       for (j= i - gap; j >=0 ; j -= gap)
    294       {
    295         if (degord (v[j], temp, PS, A, B, C, D, E, F, G))
    296           break;
    297         v[j + gap]= v[j];
    298       }
    299       v[j + gap]= temp;
    300     }
    301     gap /= __INIT_GAP__;
    302   }
    303   Varlist output;
    304   for (i= 0; i <= n - 1; i++)
    305     output.append (v[i]);
    306   return output;
    307 }
    30832
    30933// set up a new orderd list of Variables.
    31034// we try to reorder the variables heuristically optimal.
    31135Varlist
    312 neworder( const CFList & PolyList )
     36neworder (const CFList & PolyList)
    31337{
    31438  CFList PS= PolyList, PS1=PolyList;
    31539  Varlist oldorder, reorder, difference;
    31640
    317   TIMING_START(neworder_time);
    318 
    319   int highest_level= level(get_max_var(PS));
     41  TIMING_START (neworder_time);
     42
     43  int highest_level= level (get_max_var (PS));
    32044
    32145  // set up oldorder and first criterion: only_in_one
    32246  for (int i= highest_level; i>=1; i--)
    32347  {
    324     oldorder.insert (Variable(i));
    325     CFList is_one= only_in_one (PS1, Variable(i));
     48    oldorder.insert (Variable (i));
     49    CFList is_one= only_in_one (PS1, Variable (i));
    32650    if (is_one.length() == 1)
    32751    {
    328       reorder.insert (Variable(i));
     52      reorder.insert (Variable (i));
    32953      PS1= Difference (PS1, is_one);
    33054    }
    … …  
    34973// the same as above, only returning a list of CanonicalForms
    35074CFList
    351 newordercf(const CFList & PolyList )
     75newordercf (const CFList & PolyList)
    35276{
    35377  Varlist reorder= neworder (PolyList);
    … …  
    36286// the same as above, only returning a list of ints
    36387IntList
    364 neworderint(const CFList & PolyList )
     88neworderint (const CFList & PolyList)
    36589{
    36690  Varlist reorder= neworder (PolyList);
    … …  
    37195
    37296  return output;
    373 }
    374 
    375 // swapvar a whole list of CanonicalForms
    376 static CFList
    377 swapvar( const CFList & PS, const Variable & x, const Variable & y)
    378 {
    379   CFList ps;
    380 
    381   for (CFListIterator i = PS; i.hasItem(); i++)
    382     ps.append (swapvar (i.getItem(), x, y));
    383   return ps;
    384 }
    385 
    386 static CFFList
    387 swapvar( const CFFList & PS, const Variable & x, const Variable & y)
    388 {
    389   CFFList ps;
    390 
    391   for (CFFListIterator i= PS; i.hasItem(); i++)
    392     ps.append (CFFactor(swapvar (i.getItem().factor(), x, y), i.getItem().exp()));
    393   return ps;
    39497}
    39598
    … …  
    415118
    416119CFFList
    417 reorder( const Varlist & betterorder, const CFFList & PS)
     120reorder (const Varlist & betterorder, const CFFList & PS)
    418121{
    419122  int i= 1, n= betterorder.length();
    … …  
    443146  return Q1;
    444147}
    445 
    446 static bool
    447 lowerRank (const CanonicalForm & F, const CanonicalForm & G, int & ind)
    448 {
    449   int degF, degG, levelF, levelG;
    450 
    451   levelF= F.level();
    452   levelG= G.level();
    453   if (F.inCoeffDomain())
    454   {
    455     if (G.inCoeffDomain())
    456       ind= 1;
    457     return true;
    458   }
    459   else if (G.inCoeffDomain())
    460     return false;
    461   else if (levelF < levelG)
    462     return true;
    463   else if (levelF == levelG)
    464   {
    465     degF= degree(F);
    466     degG= degree(G);
    467     if (degF < degG)
    468       return true;
    469     else if (degF == degG)
    470       return lowerRank (LC (F), LC (G), ind);
    471     else
    472       return false;
    473   }
    474   return false;
    475 }
    476 
    477 static
    478 CanonicalForm
    479 lowestRank (const CFList & L)
    480 {
    481   CFListIterator i= L;
    482   CanonicalForm f;
    483   int ind= 0;
    484   if (!i.hasItem())
    485     return f;
    486 
    487   f= i.getItem();
    488   i++;
    489 
    490   while (i.hasItem())
    491   {
    492     if (lowerRank (i.getItem(), f, ind))
    493     {
    494       if (ind)
    495       {
    496         if (size (i.getItem()) < size (f))
    497           f= i.getItem();
    498         ind= 0;
    499       }
    500       else
    501         f= i.getItem();
    502     }
    503     i++;
    504   }
    505   return f;
    506 }
    507 
    508 CFList initials (const CFList& L)
    509 {
    510   CFList result;
    511   for (CFListIterator iter= L; iter.hasItem(); iter++)
    512   {
    513     if (!LC(iter.getItem()).inCoeffDomain())
    514       result.append (LC (iter.getItem()));
    515   }
    516   return result;
    517 }
    518 
    519 // sort in descending order of length of elements
    520 void
    521 sortListCFList (ListCFList& list)
    522 {
    523   int l= 1;
    524   int k= 1;
    525   CFList buf;
    526   ListCFListIterator m;
    527   for (ListCFListIterator i= list; l <= list.length(); i++, l++)
    528   {
    529     for (ListCFListIterator j= list; k <= list.length() - l; k++)
    530     {
    531       m= j;
    532       m++;
    533       if (j.getItem().length() < m.getItem().length())
    534       {
    535         buf= m.getItem();
    536         m.getItem()= j.getItem();
    537         j.getItem()= buf;
    538         j++;
    539         j.getItem()= m.getItem();
    540       }
    541       else
    542         j++;
    543     }
    544     k= 1;
    545   }
    546 }
    547 
    548 
    549 // sort in descending order of level of elements
    550 void
    551 sortCFListByLevel (CFList& list)
    552 {
    553   int l= 1;
    554   int k= 1;
    555   CanonicalForm buf;
    556   CFListIterator m;
    557   for (CFListIterator i= list; l <= list.length(); i++, l++)
    558   {
    559     for (CFListIterator j= list; k <= list.length() - l; k++)
    560     {
    561       m= j;
    562       m++;
    563       if ((size (j.getItem()) < size (m.getItem())) ||
    564           ((size (j.getItem()) == size (m.getItem()))
    565             && (j.getItem().level() < m.getItem().level())))
    566       {
    567         buf= m.getItem();
    568         m.getItem()= j.getItem();
    569         j.getItem()= buf;
    570         j++;
    571         j.getItem()= m.getItem();
    572       }
    573       else
    574         j++;
    575     }
    576     k= 1;
    577   }
    578 }
    579 
    580 static bool
    581 member (const CanonicalForm& f, const CFList& F)
    582 {
    583   for (CFListIterator i= F; i.hasItem(); i++)
    584   {
    585     if (i.getItem().mapinto() == f.mapinto())
    586       return 1;
    587   }
    588   return 0;
    589 }
    590 
    591 // are list A and B the same?
    592 static bool
    593 same (const CFList& A, const CFList& B)
    594 {
    595   if (A.length() != B.length())
    596     return 0;
    597 
    598   CFListIterator i;
    599 
    600   for (i= A; i.hasItem(); i++)
    601   {
    602     if (!member (i.getItem(), B))
    603       return 0;
    604   }
    605   for (i= B; i.hasItem(); i++)
    606   {
    607     if (!member (i.getItem(), A))
    608       return 0;
    609   }
    610   return 1;
    611 }
    612 
    613 
    614 // is List cs contained in List of lists pi?
    615 static bool
    616 member (const CFList& cs, const ListCFList& pi)
    617 {
    618   if (pi.isEmpty())
    619     return 0;
    620 
    621   ListCFListIterator i;
    622 
    623   for (i= pi; i.hasItem(); i++)
    624   {
    625     if (i.getItem().length() != cs.length())
    626       continue;
    627     if (same (cs, i.getItem()))
    628       return 1;
    629   }
    630   return 0;
    631 }
    632 
    633 // is PS a subset of Cset ?
    634 static bool
    635 subset (const CFList &PS, const CFList& Cset)
    636 {
    637   for (CFListIterator i= PS; i.hasItem(); i++)
    638   {
    639     if (!member (i.getItem(), Cset))
    640       return 0;
    641   }
    642   return 1;
    643 }
    644 
    645 // Union of two List of Lists
    646 static ListCFList
    647 MyUnion (const ListCFList& a, const ListCFList& b)
    648 {
    649   if (a.isEmpty())
    650     return b;
    651   if (b.isEmpty())
    652     return a;
    653 
    654   ListCFList output;
    655   ListCFListIterator i;
    656   CFList elem;
    657 
    658   for (i= a; i.hasItem(); i++)
    659   {
    660     elem= i.getItem();
    661     if ((!elem.isEmpty()) && (!member (elem, output)))
    662       output.append(elem);
    663   }
    664 
    665   for (i= b; i.hasItem(); i++)
    666   {
    667     elem= i.getItem();
    668     if ((!elem.isEmpty()) && (!member (elem, output)))
    669       output.append(elem);
    670   }
    671   return output;
    672 }
    673 
    674 // Union of a and b stored in b
    675 void
    676 MyUnion2 (const ListCFList& a, ListCFList& b)
    677 {
    678   if (a.isEmpty())
    679     return;
    680   if (b.isEmpty())
    681   {
    682     b= a;
    683     return;
    684   }
    685 
    686   ListCFListIterator i;
    687   CFList elem;
    688 
    689   for (i= a; i.hasItem(); i++)
    690   {
    691     elem= i.getItem();
    692     if ((!elem.isEmpty()) && (!member (elem, b)))
    693       b.insert(elem);
    694   }
    695 }
    696 
    697 //if list b is member of the list of lists remove b and return the rest
    698 static ListCFList
    699 MyDifference (const ListCFList& a, const CFList& b)
    700 {
    701   ListCFList output;
    702   ListCFListIterator i;
    703   CFList elem;
    704 
    705   for (i= a; i.hasItem(); i++)
    706   {
    707     elem= i.getItem();
    708     if ((!elem.isEmpty()) && (!same (elem, b)))
    709       output.append (elem);
    710   }
    711   return output;
    712 }
    713 
    714 // remove all elements of b from list of lists a and return the rest
    715 static ListCFList
    716 Minus( const ListCFList& a, const ListCFList& b)
    717 {
    718   ListCFList output= a;
    719 
    720   for (ListCFListIterator i=b; i.hasItem(); i++)
    721     output = MyDifference (output, i.getItem());
    722 
    723   return output;
    724 }
    725 
    726 static ListCFList
    727 adjoin (const CFList& is, const CFList& qs, const ListCFList& qh)
    728 {
    729   ListCFList iss, qhi;
    730   ListCFListIterator j;
    731   CFList iscopy, itt;
    732   CFListIterator i;
    733   int ind, length;
    734 
    735   for (i= is; i.hasItem(); i++)
    736   {
    737     if (i.getItem().level() > 0)
    738       iscopy= Union (CFList (i.getItem()), iscopy);
    739   }
    740   if (iscopy.isEmpty())
    741     return iss;
    742 
    743   qhi= MyDifference (qh, qs);
    744   length= qhi.length();
    745 
    746   for (i= iscopy; i.hasItem(); i++)
    747   {
    748     itt= Union (qs, CFList (i.getItem()));
    749     ind= 0;
    750     if (length > 0)
    751     {
    752       for (j= qhi; j.hasItem(); j++)
    753       {
    754         if (subset (j.getItem(), itt))
    755           ind= 1;
    756       }
    757     }
    758     if (ind == 0)
    759       iss.append (itt);
    760   }
    761   return iss;
    762 }
    763 
    764 static ListCFList
    765 adjoinb (const CFList & is, const CFList & qs, const ListCFList & qh ,const CFList & cs)
    766 {
    767   ListCFList iss, qhi;
    768   ListCFListIterator j;
    769   CFList iscopy, itt;
    770   CFListIterator i;
    771   int ind, length;
    772 
    773   for (i= is ; i.hasItem(); i++)
    774   {
    775     if (i.getItem().level() > 0)
    776       iscopy= Union (CFList (i.getItem()), iscopy);
    777   }
    778   if (iscopy.isEmpty())
    779     return iss;
    780   qhi= MyDifference (qh, qs);
    781   length= qhi.length();
    782   for (i= iscopy; i.hasItem(); i++)
    783   {
    784     itt= Union (Union (qs, CFList (i.getItem())), cs);
    785     ind= 0;
    786     if (length > 0)
    787     {
    788       for (j= qhi; j.hasItem(); j++)
    789       {
    790         if (subset (j.getItem(), itt))
    791           ind= 1;
    792       }
    793     }
    794     if (ind == 0)
    795       iss.append(itt);
    796   }
    797   return iss;
    798 }
    799 
    800 static void
    801 select (const ListCFList& ppi, int length, ListCFList& ppi1, ListCFList& ppi2)
    802 {
    803   CFList elem;
    804   for (ListCFListIterator i=ppi; i.hasItem(); i++)
    805   {
    806     elem = i.getItem();
    807     if (!elem.isEmpty())
    808     {
    809       if (length <= elem.length())
    810         ppi2.append(elem);
    811       else
    812         ppi1.append(elem);
    813     }
    814   }
    815 }
    816 
    817 CanonicalForm normalize (const CanonicalForm& F)
    818 {
    819   if (F.isZero())
    820     return F;
    821   if (getCharacteristic() == 0)
    822   {
    823     CanonicalForm G;
    824     bool isRat= isOn (SW_RATIONAL);
    825     if (!isRat)
    826       On (SW_RATIONAL);
    827     G= F;
    828     G *= bCommonDen (G);
    829     if (!isRat)
    830       Off (SW_RATIONAL);
    831     if (isRat)
    832       Off (SW_RATIONAL);
    833     G= F/icontent (F);
    834     if (isRat)
    835       On (SW_RATIONAL);
    836     return G;
    837   }
    838 
    839   return F/lc (F);
    840 }
    841 
    842 static
    843 CanonicalForm
    844 Prem (const CanonicalForm& F, const CanonicalForm& G)
    845 {
    846   CanonicalForm f, g, l, test, lu, lv, t, retvalue;
    847   int degF, degG, levelF, levelG;
    848   bool reord;
    849   Variable v, vg= G.mvar();
    850 
    851   if ( (levelF= F.level()) < (levelG= G.level()))
    852     return F;
    853   else
    854   {
    855     if ( levelF == levelG )
    856     {
    857       f= F;
    858       g= G;
    859       reord= false;
    860       v= F.mvar();
    861     }
    862     else
    863     {
    864       v= Variable (levelF + 1);
    865       f= swapvar (F, vg, v);
    866       g= swapvar (G, vg, v);
    867       reord= true;
    868     }
    869     degG= degree (g, v );
    870     degF= degree (f, v );
    871     if (degG <= degF)
    872     {
    873       l= LC (g);
    874       g= g - l*power (v, degG);
    875     }
    876     else
    877       l= 1;
    878     while ((degG <= degF) && (!f.isZero()))
    879     {
    880       test= gcd (l, LC(f));
    881       lu= l / test;
    882       lv= LC(f) / test;
    883       t= g*lv*power (v, degF - degG);
    884 
    885       if (degF == 0)
    886         f= 0;
    887       else
    888         f= f - LC (f)*power (v, degF);
    889 
    890       f= f*lu - t;
    891       degF= degree (f, v);
    892     }
    893 
    894     if (reord)
    895       retvalue= swapvar (f, vg, v);
    896     else
    897       retvalue= f;
    898 
    899     return retvalue;
    900   }
    901 }
    902 
    903 static
    904 CanonicalForm
    905 Premb (const CanonicalForm &f, const CFList &L)
    906 {
    907   CanonicalForm rem= f;
    908   CFList l= L;
    909   l.removeFirst();
    910   CFListIterator i= l;
    911 
    912   for (i.lastItem(); i.hasItem(); i--)
    913     rem= normalize (Prem (rem, i.getItem()));
    914 
    915   CanonicalForm tmp= L.getFirst()/content (L.getFirst());
    916 
    917   bool isRat= isOn (SW_RATIONAL);
    918   if (getCharacteristic() == 0 && !isRat)
    919     On (SW_RATIONAL);
    920   if (fdivides (tmp, rem))
    921   {
    922     if (getCharacteristic() == 0 && !isRat)
    923       Off (SW_RATIONAL);
    924     return 0;
    925   }
    926 
    927   if (getCharacteristic() == 0 && !isRat)
    928     Off (SW_RATIONAL);
    929 
    930   rem= normalize (Prem (rem, L.getFirst()));
    931 
    932   return rem;
    933 }
    934 
    935 static
    936 CanonicalForm
    937 Prem (const CanonicalForm &f, const CFList &L)
    938 {
    939   CanonicalForm rem= f;
    940   CFListIterator i= L;
    941 
    942   for (i.lastItem(); i.hasItem(); i--)
    943     rem= normalize (Prem (rem, i.getItem()));
    944 
    945   return rem;
    946 }
    947 
    948 CFList uniGcd (const CFList& L)
    949 {
    950   CFList tmp;
    951   CanonicalForm g;
    952   CFListIterator i;
    953   for (i= L; i.hasItem(); i++)
    954   {
    955     if (i.getItem().isUnivariate() && i.getItem().level() == 1)
    956       tmp.append (i.getItem());
    957   }
    958   if (tmp.length() <= 2)
    959     return L;
    960   i= tmp;
    961   g= i.getItem();
    962   i++;
    963   g= gcd (g,i.getItem());
    964   i++;
    965   for (; i.hasItem(); i++)
    966     g= gcd (g, i.getItem());
    967   return Union (Difference (L, tmp), CFList (g));
    968 }
    969 
    970 
    971 CFList
    972 factorsOfInitials(const CFList & L)
    973 {
    974   CFList result;
    975   CFFList factors;
    976   CanonicalForm tmp;
    977 
    978   for (CFListIterator i= L; i.hasItem(); i++)
    979   {
    980     factors= factorize (LC (i.getItem()));
    981     for (CFFListIterator j= factors; j.hasItem(); j++)
    982     {
    983       tmp= j.getItem().factor();
    984       if (!tmp.inCoeffDomain())
    985         result= Union (result, CFList (normalize (tmp)));
    986     }
    987   }
    988 
    989   return result;
    990 }
    991 
    992 void
    993 removeContent (CanonicalForm& F, CanonicalForm& cF)
    994 {
    995   if (size (F) == 1)
    996   {
    997     CanonicalForm tmp= F;
    998     F= F.mvar();
    999     cF= tmp/F;
    1000     if (!cF.inCoeffDomain())
    1001       cF= normalize (cF);
    1002     else
    1003       cF= 0;
    1004 
    1005     return;
    1006   }
    1007 
    1008   cF= content (F);
    1009 
    1010   if (cF.inCoeffDomain())
    1011     cF= 0;
    1012   else
    1013   {
    1014     cF= normalize (cF);
    1015     F /= cF;
    1016     F= normalize (F);
    1017   }
    1018 }
    1019 
    1020 CFList
    1021 factorPSet (const CFList& PS)
    1022 {
    1023   CFList result;
    1024   CFFList factors;
    1025   CFFListIterator j;
    1026 
    1027   for (CFListIterator i= PS; i. hasItem(); i++)
    1028   {
    1029     factors= factorize (i.getItem());
    1030     if (factors.getFirst().factor().inCoeffDomain())
    1031       factors.removeFirst();
    1032     for (j= factors; j.hasItem(); j++ )
    1033       result= Union (result, CFList (normalize (j.getItem().factor())));
    1034   }
    1035   return result;
    1036 }
    1037 
    1038 void
    1039 removeFactors (CanonicalForm& r, StoreFactors& StoredFactors,
    1040                CFList& removedFactors)
    1041 {
    1042   CanonicalForm quot;
    1043   CFList testlist;
    1044   int n= level(r);
    1045   bool divides;
    1046   CFListIterator j;
    1047 
    1048   for (int i=1; i<= n; i++)
    1049     testlist.append (CanonicalForm (Variable (i)));
    1050 
    1051   for (j= StoredFactors.FS1; j.hasItem(); j++)
    1052   {
    1053     while (fdivides (j.getItem(), r, quot))
    1054     {
    1055       if (!quot.inCoeffDomain())
    1056         r= quot;
    1057       else
    1058         break;
    1059     }
    1060   }
    1061 
    1062   // remove already removed factors
    1063   for (j= StoredFactors.FS2; j.hasItem(); j++)
    1064   {
    1065     divides= false;
    1066     while (fdivides (j.getItem(), r, quot))
    1067     {
    1068       if (!quot.inCoeffDomain())
    1069       {
    1070         divides= true;
    1071         r= quot;
    1072       }
    1073       else
    1074         break;
    1075     }
    1076     if (divides)
    1077       removedFactors= Union (removedFactors, CFList (j.getItem()));
    1078   }
    1079   r= normalize (r);
    1080 
    1081   // remove variables
    1082   for (j= testlist; j.hasItem() && !r.isOne(); j++)
    1083   {
    1084     while (fdivides (j.getItem(), r, quot))
    1085     {
    1086       if (!quot.inCoeffDomain())
    1087         r= quot;
    1088       else
    1089         break;
    1090       removedFactors= Union (removedFactors, CFList (j.getItem()));
    1091     }
    1092   }
    1093 }
    1094 
    1095 CFList
    1096 removeContent (const CFList & PS, StoreFactors & StoredFactors)
    1097 {
    1098   CFListIterator i= PS;
    1099   if ((!i.hasItem()) || (PS.getFirst().level() == 0 ))
    1100     return PS;
    1101 
    1102   CFList output;
    1103   CanonicalForm cc,elem;
    1104 
    1105   for (; i.hasItem(); i++)
    1106   {
    1107     elem= i.getItem();
    1108     cc= content (elem, elem.mvar());
    1109     if (cc.level() > 0 )
    1110     {
    1111       output.append (elem / cc);
    1112       StoredFactors.FS1 = Union (CFList (cc), StoredFactors.FS1);
    1113     }
    1114     else
    1115       output.append(elem);
    1116   }
    1117   return output;
    1118 }
    1119 
    1120 static bool
    1121 contractsub (const CFList& cs1, const CFList& cs2)
    1122 {
    1123   CFListIterator i;
    1124 
    1125   CanonicalForm r;
    1126   for (i= cs1; i.hasItem(); i++)
    1127   {
    1128     if (Prem (i.getItem(), cs2) != 0)
    1129       return false;
    1130   }
    1131 
    1132   CFList is= factorsOfInitials (cs1);
    1133 
    1134   for (i= is; i.hasItem(); i++)
    1135   {
    1136     if (Prem (i.getItem(), cs2) == 0)
    1137       return false;
    1138   }
    1139   return true;
    1140 }
    1141 
    1142 static ListCFList
    1143 contract (const ListCFList& cs)
    1144 {
    1145   ListCFList mem, ts;
    1146   CFList iitem, jitem;
    1147 
    1148   if (cs.length() < 2)
    1149     return cs;
    1150 
    1151   int l= cs.length();
    1152   int ii= 1;
    1153   ListCFListIterator j;
    1154   for (ListCFListIterator i= cs; i.hasItem() && ii < l; i++, ii++)
    1155   {
    1156     iitem= i.getItem();
    1157     if (!member (iitem, mem))
    1158     {
    1159       j= i;
    1160       j++;
    1161       for (; j.hasItem(); j++)
    1162       {
    1163         jitem= j.getItem();
    1164         if (!member (jitem, mem))
    1165         {
    1166           if (contractsub (iitem, jitem))
    1167           {
    1168             ts.append (jitem);
    1169             mem.append (jitem);
    1170           }
    1171           else
    1172           {
    1173             if (contractsub (jitem, iitem))
    1174               ts.append (iitem); // no mem.append (item) because we assume cs does not contain duplicate entries
    1175           }
    1176         }
    1177       }
    1178     }
    1179   }
    1180   return Minus (cs,ts);
    1181 }
    1182 
    1183148
    1184149CFList
    … …  
    1575540        if (degree (i.getItem()) > 1)
    1576541        {  // search for a non linear elem
    1577           qs= newfactoras (i.getItem(), as, success);
     542          qs= facAlgFunc2 (i.getItem(), as);
    1578543          if (qs.getFirst().factor().inCoeffDomain())
    1579544            qs.removeFirst();

  • factory/cfCharSets.h

    r6bf0b4 rc514f7  
    2222#define CF_CHARSETS
    2323
    24 #ifdef HAVE_CONFIG_H
    25 #include "config.h"
    26 #endif /* HAVE_CONFIG_H */
    27 
    28 #include "canonicalform.h"
    29 
    30 CanonicalForm normalize (const CanonicalForm& F);
     24#include "cfCharSetsUtil.h"
    3125
    3226/*BEGINPUBLIC*/
    33 class StoreFactors
    34 {
    35   public:
    36     CFList FS1;
    37     CFList FS2;
    38     inline StoreFactors& operator= (const StoreFactors& value)
    39     {
    40       if ( this != &value )
    41       {
    42         FS1 = value.FS1;
    43         FS2 = value.FS2;
    44       }
    45       return *this;
    46     }
    47 };
    4827
    4928/// basic set in the sense of Wang a.k.a. minimal ascending set in the sense of

  • factory/facAlgFunc.cc

    r6bf0b4 rc514f7  
    2727
    2828#include "algext.h"
    29 #include "cf_random.h"
    3029#include "cf_generator.h"
    31 #include "cf_irred.h"
    3230#include "cf_iter.h"
    3331#include "cf_util.h"
    … …  
    3735#include "cfCharSets.h"
    3836#include "facAlgFunc.h"
     37#include "facAlgFuncUtil.h"
    3938
    4039void out_cf(const char *s1,const CanonicalForm &f,const char *s2);
    41 
    42 static
    43 CanonicalForm
    44 Prem (const CanonicalForm& F, const CanonicalForm& G)
    45 {
    46   CanonicalForm f, g, l, test, lu, lv, t, retvalue;
    47   int degF, degG, levelF, levelG;
    48   bool reord;
    49   Variable v, vg= G.mvar();
    50 
    51   if ( (levelF= F.level()) < (levelG= G.level()))
    52     return F;
    53   else
    54   {
    55     if ( levelF == levelG )
    56     {
    57       f= F;
    58       g= G;
    59       reord= false;
    60       v= F.mvar();
    61     }
    62     else
    63     {
    64       v= Variable (levelF + 1);
    65       f= swapvar (F, vg, v);
    66       g= swapvar (G, vg, v);
    67       reord= true;
    68     }
    69     degG= degree (g, v );
    70     degF= degree (f, v );
    71     if (degG <= degF)
    72     {
    73       l= LC (g);
    74       g= g - l*power (v, degG);
    75     }
    76     else
    77       l= 1;
    78     while ((degG <= degF) && (!f.isZero()))
    79     {
    80       test= gcd (l, LC(f));
    81       lu= l / test;
    82       lv= LC(f) / test;
    83 
    84       t= power (v, degF - degG)*g*lv;
    85 
    86       if (degF == 0)
    87         f= 0;
    88       else
    89         f= f - LC (f)*power (v, degF);
    90 
    91       f= lu*f - t;
    92       degF= degree (f, v);
    93     }
    94 
    95     if (reord)
    96       retvalue= swapvar (f, vg, v);
    97     else
    98       retvalue= f;
    99 
    100     return retvalue;
    101   }
    102 }
    103 
    104 static
    105 CanonicalForm
    106 Prem( const CanonicalForm &f, const CFList &L)
    107 {
    108   CanonicalForm rem= f;
    109   CFListIterator i= L;
    110 
    111   for (i.lastItem(); i.hasItem(); i--)
    112     rem= normalize (Prem (rem, i.getItem()));
    113 
    114   return rem;
    115 }
    116 
    117 static
    118 CanonicalForm
    119 Prem (const CanonicalForm &f, const CFList &L, const CFList &as)
    120 {
    121   CanonicalForm rem = f;
    122   CFListIterator i = L;
    123   for ( i.lastItem(); i.hasItem(); i-- )
    124     rem = Prem( rem, i.getItem() );
    125   return normalize (rem); //TODO better normalize in case as.length() == 1 && as.getFirst().level() == 1 ???
    126 }
    127 
    128 CFFList
    129 myappend( const CFFList & Inputlist, const CFFactor & TheFactor)
    130 {
    131   CFFList Outputlist ;
    132   CFFactor copy;
    133   CFFListIterator i;
    134   int exp=0;
    135 
    136   for ( i=Inputlist ; i.hasItem() ; i++ )
    137   {
    138     copy = i.getItem();
    139     if ( copy.factor() == TheFactor.factor() )
    140       exp += copy.exp();
    141     else
    142       Outputlist.append(copy);
    143   }
    144   Outputlist.append( CFFactor(TheFactor.factor(), exp + TheFactor.exp()));
    145   return Outputlist;
    146 }
    147 
    148 CFFList
    149 myUnion(const CFFList & Inputlist1,const CFFList & Inputlist2)
    150 {
    151   CFFList Outputlist;
    152   CFFListIterator i;
    153 
    154   for ( i=Inputlist1 ; i.hasItem() ; i++ )
    155     Outputlist = myappend(Outputlist, i.getItem() );
    156   for ( i=Inputlist2 ; i.hasItem() ; i++ )
    157     Outputlist = myappend(Outputlist, i.getItem() );
    158 
    159   return Outputlist;
    160 }
    161 
    162 ///////////////////////////////////////////////////////////////
    163 // generate a minpoly of degree degree_of_Extension in the   //
    164 // field getCharacteristik()^Extension.                      //
    165 ///////////////////////////////////////////////////////////////
    166 CanonicalForm
    167 generate_mipo( int degree_of_Extension , const Variable & Extension )
    168 {
    169   FFRandom gen;
    170   /*if (degree (Extension) < 0)
    171     factoryError("libfac: evaluate: Extension not inFF() or inGF() !");*/
    172   return find_irreducible( degree_of_Extension, gen, Variable(1) );
    173 }
    174 
    175 static Varlist
    176 Var_is_in_AS(const Varlist & uord, const CFList & Astar);
    177 
    178 ////////////////////////////////////////////////////////////////////////
    179 // This implements the algorithm of Trager for factorization of
    180 // (multivariate) polynomials over algebraic extensions and so called
    181 // function field extensions.
    182 ////////////////////////////////////////////////////////////////////////
    183 
    184 // // missing class: IntGenerator:
    185 bool IntGenerator::hasItems() const
    186 {
    187     return 1;
    188 }
    189 
    190 CanonicalForm IntGenerator::item() const
    191 //int IntGenerator::item() const
    192 {
    193   //return current; //CanonicalForm( current );
    194   return mapinto(CanonicalForm( current ));
    195 }
    196 
    197 void IntGenerator::next()
    198 {
    199     current++;
    200 }
    201 
    202 int hasAlgVar(const CanonicalForm &f, const Variable &v)
    203 {
    204   if (f.inBaseDomain()) return 0;
    205   if (f.inCoeffDomain())
    206   {
    207     if (f.mvar()==v) return 1;
    208     return hasAlgVar(f.LC(),v);
    209   }
    210   if (f.inPolyDomain())
    211   {
    212     if (hasAlgVar(f.LC(),v)) return 1;
    213     for( CFIterator i=f; i.hasTerms(); i++)
    214     {
    215       if (hasAlgVar(i.coeff(),v)) return 1;
    216     }
    217   }
    218   return 0;
    219 }
    220 
    221 int hasVar(const CanonicalForm &f, const Variable &v)
    222 {
    223   if (f.inBaseDomain()) return 0;
    224   if (f.inCoeffDomain())
    225   {
    226     if (f.mvar()==v) return 1;
    227     return hasAlgVar(f.LC(),v);
    228   }
    229   if (f.inPolyDomain())
    230   {
    231     if (f.mvar()==v) return 1;
    232     if (hasVar(f.LC(),v)) return 1;
    233     for( CFIterator i=f; i.hasTerms(); i++)
    234     {
    235       if (hasVar(i.coeff(),v)) return 1;
    236     }
    237   }
    238   return 0;
    239 }
    240 
    241 int hasAlgVar(const CanonicalForm &f)
    242 {
    243   if (f.inBaseDomain()) return 0;
    244   if (f.inCoeffDomain())
    245   {
    246     if (f.level()!=0)
    247       return 1;
    248     return hasAlgVar(f.LC());
    249   }
    250   if (f.inPolyDomain())
    251   {
    252     if (hasAlgVar(f.LC())) return 1;
    253     for( CFIterator i=f; i.hasTerms(); i++)
    254     {
    255       if (hasAlgVar(i.coeff())) return 1;
    256     }
    257   }
    258   return 0;
    259 }
    260 
    261 /// pseudo division of f and g wrt. x s.t. multiplier*f=q*g+r
    262 void
    263 psqr (const CanonicalForm & f, const CanonicalForm & g, CanonicalForm & q,
    264       CanonicalForm & r, CanonicalForm& multiplier, const Variable& x)
    265 {
    266     ASSERT( x.level() > 0, "type error: polynomial variable expected" );
    267     ASSERT( ! g.isZero(), "math error: division by zero" );
    268 
    269     // swap variables such that x's level is larger or equal
    270     // than both f's and g's levels.
    271     Variable X;
    272     if (f.level() > g.level())
    273       X= f.mvar();
    274     else
    275       X= g.mvar();
    276     if (X.level() < x.level())
    277       X= x;
    278     CanonicalForm F= swapvar (f, x, X);
    279     CanonicalForm G= swapvar (g, x, X);
    280 
    281     // now, we have to calculate the pseudo remainder of F and G
    282     // w.r.t. X
    283     int fDegree= degree (F, X);
    284     int gDegree= degree (G, X);
    285     if (fDegree < 0 || fDegree < gDegree)
    286     {
    287       q= 0;
    288       r= f;
    289     }
    290     else
    291     {
    292       CanonicalForm LCG= LC (G, X);
    293       multiplier= power (LCG, fDegree - gDegree + 1);
    294       divrem (multiplier*F, G, q, r);
    295       q= swapvar (q, x, X);
    296       r= swapvar (r, x, X);
    297     }
    298 }
    299 
    300 static CanonicalForm
    301 Sprem ( const CanonicalForm &f, const CanonicalForm &g, CanonicalForm & m, CanonicalForm & q )
    302 {
    303   CanonicalForm ff, gg, l, test, retvalue;
    304   int df, dg,n;
    305   bool reord;
    306   Variable vf, vg, v;
    307 
    308   if ( (vf = f.mvar()) < (vg = g.mvar()) )
    309   {
    310     m=CanonicalForm(0); q=CanonicalForm(0);
    311     return f;
    312   }
    313   else
    314   {
    315     if ( vf == vg )
    316     {
    317       ff = f; gg = g;
    318       reord = false;
    319       v = vg; // == x
    320     }
    321     else
    322     {
    323       v = Variable(level(f.mvar()) + 1);
    324       ff = swapvar(f,vg,v); // == r
    325       gg = swapvar(g,vg,v); // == v
    326       reord=true;
    327     }
    328     dg = degree( gg, v ); // == dv
    329     df = degree( ff, v ); // == dr
    330     if (dg <= df) {l=LC(gg); gg = gg -LC(gg)*power(v,dg);}
    331     else { l = 1; }
    332     n= 0;
    333     while ( ( dg <= df  ) && ( !ff.isZero()) )
    334     {
    335       test= power(v,df-dg) * gg * LC(ff);
    336       if ( df == 0 ){ff= ff.genZero();}
    337       else {ff= ff - LC(ff)*power(v,df);}
    338       ff = l*ff-test;
    339       df= degree(ff,v);
    340       n++;
    341     }
    342     if ( reord )
    343     {
    344       retvalue= swapvar( ff, vg, v );
    345     }
    346     else
    347     {
    348       retvalue= ff;
    349     }
    350     m= power(l,n);
    351     if ( fdivides(g,m*f-retvalue) )
    352       q= (m*f-retvalue)/g;
    353     else
    354       q= CanonicalForm(0);
    355     return retvalue;
    356   }
    357 }
    358 
    359 CanonicalForm
    360 divide( const CanonicalForm & ff, const CanonicalForm & f, const CFList & as)
    361 {
    362   CanonicalForm r,m,q;
    363 
    364   if (f.inCoeffDomain())
    365   {
    366     bool isRat=isOn(SW_RATIONAL);
    367     if (getCharacteristic() == 0)
    368       On(SW_RATIONAL);
    369     q=ff/f;
    370     if (!isRat && getCharacteristic() == 0)
    371       Off(SW_RATIONAL);
    372   }
    373   else
    374     r= Sprem(ff,f,m,q);
    375 
    376   r= Prem(q,as);
    377   return r;
    378 }
    37940
    38041CanonicalForm
    … …  
    491152  while (degree (g, x) > 0)
    492153  {
    493     r= Prem (f, g, as);
     154    r= Prem (f, g);
    494155    r= Prem (r, as);
    495156    if (!r.isZero())
    … …  
    549210// Input: f(x, alpha) a square free polynomial over K(alpha),
    550211// alpha is defined by the minimal polynomial Palpha
    551 // K has more than S elements (S is defined in thesis; look getextension)
     212// K has more than S elements (S is defined in thesis; look getDegOfExt)
    552213static void
    553214sqrf_norm_sub( const CanonicalForm & f, const CanonicalForm & PPalpha,
    … …  
    692353}
    693354
    694 static Varlist
    695 Var_is_in_AS(const Varlist & uord, const CFList & Astar){
    696   Varlist output;
    697   CanonicalForm elem;
    698   Variable x;
    699 
    700   for ( VarlistIterator i=uord; i.hasItem(); i++)
    701   {
    702     x=i.getItem();
    703     for ( CFListIterator j=Astar; j.hasItem(); j++ )
    704     {
    705       elem= j.getItem();
    706       if ( degree(elem,x) > 0 ) // x actually occures in Astar
    707       {
    708         output.append(x);
    709         break;
    710       }
    711     }
    712   }
    713   return output;
    714 }
    715 
    716 // Look if Minimalpolynomials in Astar define seperable Extensions
    717 // Must be a power of p: i.e. y^{p^e}-x
    718 static int
    719 inseperable(const CFList & Astar)
    720 {
    721   CanonicalForm elem;
    722   int Counter= 1;
    723 
    724   if ( Astar.length() == 0 ) return 0;
    725   for ( CFListIterator i=Astar; i.hasItem(); i++)
    726   {
    727     elem= i.getItem();
    728     if ( elem.deriv() == elem.genZero() ) return Counter;
    729     else Counter += 1;
    730   }
    731   return 0;
    732 }
    733 
    734 // calculate big enough extension for finite fields
    735 // Idea: first calculate k, such that q^k > S (->thesis, -> getextension)
    736 // Second, search k with gcd(k,m_i)=1, where m_i is the degree of the i'th
    737 // minimal polynomial. Then the minpoly f_i remains irrd. over q^k and we
    738 // have enough elements to plug in.
    739 static int
    740 getextension( IntList & degreelist, int n)
    741 {
    742   int charac= getCharacteristic();
    743   setCharacteristic(0); // need it for k !
    744   int k=1, m=1, length=degreelist.length();
    745   IntListIterator i;
    746 
    747   for (i=degreelist; i.hasItem(); i++) m= m*i.getItem();
    748   int q=charac;
    749   while (q <= ((n*m)*(n*m)/2)) { k= k+1; q= q*charac;}
    750   int l=0;
    751   do {
    752     for (i=degreelist; i.hasItem(); i++){
    753       l= l+1;
    754       if ( igcd(k,i.getItem()) == 1){
    755         if ( l==length ){ setCharacteristic(charac);  return k; }
    756       }
    757       else { break; }
    758     }
    759     k= k+1; l=0;
    760   }
    761   while ( 1 );
    762 }
    763 
    764 CanonicalForm
    765 QuasiInverse (const CanonicalForm& f, const CanonicalForm& g,
    766               const Variable& x)
    767 {
    768   CanonicalForm pi, pi1, q, t0, t1, Hi, bi, pi2;
    769   bool isRat= isOn (SW_RATIONAL);
    770   CanonicalForm m,tmp;
    771   if (isRat && getCharacteristic() == 0)
    772     Off (SW_RATIONAL);
    773   pi= f/content (f,x);
    774   pi1= g/content (g,x);
    775 
    776   t0= 0;
    777   t1= 1;
    778   bi= 1;
    779 
    780   int delta= degree (f, x) - degree (g, x);
    781   Hi= power (LC (pi1, x), delta);
    782   if ( (delta+1) % 2 )
    783       bi = 1;
    784   else
    785       bi = -1;
    786 
    787   while (degree (pi1,x) > 0)
    788   {
    789     psqr( pi, pi1, q, pi2, m, x);
    790     pi2 /= bi;
    791 
    792     tmp= t1;
    793     t1= t0*m - t1*q;
    794     t0= tmp;
    795     t1 /= bi;
    796     pi = pi1; pi1 = pi2;
    797     if ( degree ( pi1, x ) > 0 )
    798     {
    799       delta = degree( pi, x ) - degree( pi1, x );
    800       if ( (delta+1) % 2 )
    801         bi = LC( pi, x ) * power( Hi, delta );
    802       else
    803         bi = -LC( pi, x ) * power( Hi, delta );
    804       Hi = power( LC( pi1, x ), delta ) / power( Hi, delta-1 );
    805     }
    806   }
    807   t1 /= gcd (pi1, t1);
    808   if (!isRat && getCharacteristic() == 0)
    809     Off (SW_RATIONAL);
    810   return t1;
    811 }
    812 
    813 CanonicalForm
    814 evaluate (const CanonicalForm& f, const CanonicalForm& g, const CanonicalForm& h, const CanonicalForm& powH)
    815 {
    816   if (f.inCoeffDomain())
    817     return f;
    818   CFIterator i= f;
    819   int lastExp = i.exp();
    820   CanonicalForm result = i.coeff()*powH;
    821   i++;
    822   while (i.hasTerms())
    823   {
    824     int i_exp= i.exp();
    825     if ((lastExp - i_exp) == 1)
    826     {
    827       result *= g;
    828       result /= h;
    829     }
    830     else
    831     {
    832       result *= power (g, lastExp - i_exp);
    833       result /= power (h, lastExp - i_exp);
    834     }
    835     result += i.coeff()*powH;
    836     lastExp = i_exp;
    837     i++;
    838   }
    839   if (lastExp != 0)
    840   {
    841     result *= power (g, lastExp);
    842     result /= power (h, lastExp);
    843   }
    844   return result;
    845 }
    846 
    847 
    848 /// evaluate f at g/h at v such that powH*f is integral i.e. powH is assumed to be h^degree(f,v)
    849 CanonicalForm
    850 evaluate (const CanonicalForm& f, const CanonicalForm& g,
    851           const CanonicalForm& h, const CanonicalForm& powH,
    852           const Variable& v)
    853 {
    854   if (f.inCoeffDomain())
    855   {
    856     return f*powH;
    857   }
    858 
    859   Variable x = f.mvar();
    860   if ( v > x )
    861     return f*powH;
    862   else  if ( v == x )
    863     return evaluate (f, g, h, powH);
    864 
    865   // v is less than main variable of f
    866   CanonicalForm result= 0;
    867   for (CFIterator i= f; i.hasTerms(); i++)
    868     result += evaluate (i.coeff(), g, h, powH, v)*power (x, i.exp());
    869   return result;
    870 }
    871 
    872355// calculate a "primitive element"
    873 // K must have more than S elements (->thesis, -> getextension)
     356// K must have more than S elements (->thesis, -> getDegOfExt)
    874357static CFList
    875 simpleextension(CFList& backSubst, const CFList & Astar,
     358simpleExtension(CFList& backSubst, const CFList & Astar,
    876359                const Variable & Extension, bool& isFunctionField,
    877360                CanonicalForm & R)
    … …  
    984467}
    985468
    986 CanonicalForm alg_lc(const CanonicalForm &f)
    987 {
    988   if (f.level()>0)
    989   {
    990     return alg_lc(f.LC());
    991   }
    992 
    993   return f;
    994 }
    995 
    996 CanonicalForm alg_LC (const CanonicalForm& f, int lev)
    997 {
    998   CanonicalForm result= f;
    999   while (result.level() > lev)
    1000     result= LC (result);
    1001   return result;
    1002 }
    1003 
    1004 CanonicalForm
    1005 subst (const CanonicalForm& f, const CFList& a, const CFList& b,
    1006        const CanonicalForm& Rstar, bool isFunctionField)
    1007 {
    1008   if (isFunctionField)
    1009     ASSERT (2*a.length() == b.length(), "wrong length of lists");
    1010   else
    1011     ASSERT (a.length() == b.length(), "lists of equal length expected");
    1012   CFListIterator j= b;
    1013   CanonicalForm result= f, tmp, powj;
    1014   for (CFListIterator i= a; i.hasItem() && j.hasItem(); i++, j++)
    1015   {
    1016     if (!isFunctionField)
    1017       result= result (j.getItem(), i.getItem().mvar());
    1018     else
    1019     {
    1020       tmp= j.getItem();
    1021       j++;
    1022       powj= power (j.getItem(), degree (result, i.getItem().mvar()));
    1023       result= evaluate (result, tmp, j.getItem(), powj, i.getItem().mvar());
    1024 
    1025       if (fdivides (powj, result, tmp))
    1026         result= tmp;
    1027 
    1028       result /= vcontent (result, Variable (i.getItem().level() + 1));
    1029     }
    1030   }
    1031   result= reduce (result, Rstar);
    1032   result /= vcontent (result, Variable (Rstar.level() + 1));
    1033   return result;
    1034 }
    1035 
    1036 CanonicalForm
    1037 backSubst (const CanonicalForm& F, const CFList& a, const CFList& b)
    1038 {
    1039   ASSERT (a.length() == b.length() - 1, "wrong length of lists in backSubst");
    1040   CanonicalForm result= F;
    1041   Variable tmp;
    1042   CFList tmp2= b;
    1043   tmp= tmp2.getLast().mvar();
    1044   tmp2.removeLast();
    1045   for (CFListIterator iter= a; iter.hasItem(); iter++)
    1046   {
    1047     result= result (tmp+iter.getItem()*tmp2.getLast().mvar(), tmp);
    1048     tmp= tmp2.getLast().mvar();
    1049     tmp2.removeLast();
    1050   }
    1051   return result;
    1052 }
    1053 
    1054 void deflateDegree (const CanonicalForm & F, int & pExp, int n)
    1055 {
    1056   if (n == 0 || n > F.level())
    1057   {
    1058     pExp= -1;
    1059     return;
    1060   }
    1061   if (F.level() == n)
    1062   {
    1063     ASSERT (F.deriv().isZero(), "derivative of F is not zero");
    1064     int termCount=0;
    1065     CFIterator i= F;
    1066     for (; i.hasTerms(); i++)
    1067     {
    1068       if (i.exp() != 0)
    1069         termCount++;
    1070     }
    1071 
    1072     int j= 1;
    1073     i= F;
    1074     for (;j < termCount; j++, i++)
    1075       ;
    1076 
    1077     int exp= i.exp();
    1078     int count= 0;
    1079     int p= getCharacteristic();
    1080     while ((exp >= p) && (exp != 0) && (exp % p == 0))
    1081     {
    1082       exp /= p;
    1083       count++;
    1084     }
    1085     pExp= count;
    1086   }
    1087   else
    1088   {
    1089     CFIterator i= F;
    1090     deflateDegree (i.coeff(), pExp, n);
    1091     i++;
    1092     int tmp= pExp;
    1093     for (; i.hasTerms(); i++)
    1094     {
    1095       deflateDegree (i.coeff(), pExp, n);
    1096       if (tmp == -1)
    1097         tmp= pExp;
    1098       else if (tmp != -1 && pExp != -1)
    1099         pExp= (pExp < tmp) ? pExp : tmp;
    1100       else
    1101         pExp= tmp;
    1102     }
    1103   }
    1104 }
    1105 
    1106 CanonicalForm deflatePoly (const CanonicalForm & F, int exp)
    1107 {
    1108   if (exp == 0)
    1109     return F;
    1110   int p= getCharacteristic();
    1111   int pToExp= ipower (p, exp);
    1112   Variable x=F.mvar();
    1113   CanonicalForm result= 0;
    1114   for (CFIterator i= F; i.hasTerms(); i++)
    1115     result += i.coeff()*power (x, i.exp()/pToExp);
    1116   return result;
    1117 }
    1118 
    1119 CanonicalForm deflatePoly (const CanonicalForm & F, int exps, int n)
    1120 {
    1121   if (n == 0 || exps <= 0 || F.level() < n)
    1122     return F;
    1123   if (F.level() == n)
    1124     return deflatePoly (F, exps);
    1125   else
    1126   {
    1127     CanonicalForm result= 0;
    1128     for (CFIterator i= F; i.hasTerms(); i++)
    1129       result += deflatePoly (i.coeff(), exps, n)*power(F.mvar(), i.exp());
    1130     return result;
    1131   }
    1132 }
    1133 
    1134 CanonicalForm inflatePoly (const CanonicalForm & F, int exp)
    1135 {
    1136   if (exp == 0)
    1137     return F;
    1138   int p= getCharacteristic();
    1139   int pToExp= ipower (p, exp);
    1140   Variable x=F.mvar();
    1141   CanonicalForm result= 0;
    1142   for (CFIterator i= F; i.hasTerms(); i++)
    1143     result += i.coeff()*power (x, i.exp()*pToExp);
    1144   return result;
    1145 }
    1146 
    1147 CanonicalForm inflatePoly (const CanonicalForm & F, int exps, int n)
    1148 {
    1149   if (n == 0 || exps <= 0 || F.level() < n)
    1150     return F;
    1151   if (F.level() == n)
    1152     return inflatePoly (F, exps);
    1153   else
    1154   {
    1155     CanonicalForm result= 0;
    1156     for (CFIterator i= F; i.hasTerms(); i++)
    1157       result += inflatePoly (i.coeff(), exps, n)*power(F.mvar(), i.exp());
    1158     return result;
    1159   }
    1160 }
    1161 
    1162 // the heart of the algorithm: the one from Trager
     469/// Trager's algorithm, i.e. convert to one field extension and
     470/// factorize over this field extension
    1163471static CFFList
    1164 alg_factor( const CanonicalForm & F, const CFList & Astar, const Variable & vminpoly, const Varlist & oldord, const CFList & as, bool isFunctionField)
     472Trager (const CanonicalForm & F, const CFList & Astar,
     473            const Variable & vminpoly, const Varlist & oldord,
     474            const CFList & as, bool isFunctionField)
    1165475{
    1166476  bool isRat= isOn (SW_RATIONAL);
    … …  
    1169479  CFList substlist, backSubsts;
    1170480
    1171   substlist= simpleextension (backSubsts, Astar, vminpoly, isFunctionField, Rstar);
     481  substlist= simpleExtension (backSubsts, Astar, vminpoly, isFunctionField, Rstar);
    1172482
    1173483  f= subst (f, Astar, substlist, Rstar, isFunctionField);
    … …  
    1516826    i.getItem() /= content (i.getItem());
    1517827
    1518   j= 0;
    1519   tmp= newcfactor (F, asnew, j);
     828  tmp= facAlgFunc (F, asnew);
    1520829
    1521830  // transform back
    … …  
    1577886}
    1578887
    1579 void
    1580 multiplicity (CFFList& factors, const CanonicalForm& F, const CFList& as)
    1581 {
    1582   CanonicalForm G= F;
    1583   Variable x= F.mvar();
    1584   CanonicalForm q, r;
    1585   int count= -1;
    1586   for (CFFListIterator iter=factors; iter.hasItem(); iter++)
    1587   {
    1588     count= -1;
    1589     if (iter.getItem().factor().inCoeffDomain())
    1590       continue;
    1591     while (1)
    1592     {
    1593       psqr (G, iter.getItem().factor(), q, r, x);
    1594 
    1595       q= Prem (q, as);
    1596       r= Prem (r, as);
    1597       if (!r.isZero())
    1598         break;
    1599       count++;
    1600       G= q;
    1601     }
    1602     iter.getItem()= CFFactor (iter.getItem().factor(), iter.getItem().exp()+count);
    1603   }
    1604 }
     888/// factorize a polynomial that is irreducible over the ground field modulo an
     889/// extension given by an irreducible characteristic set
    1605890
    1606891// 1) prepares data
    1607892// 2) for char=p we distinguish 3 cases:
    1608 //           no transcendentals, seperable and inseperable extensions
     893//           no transcendentals, separable and inseparable extensions
    1609894CFFList
    1610 newfactoras( const CanonicalForm & f, const CFList & as, int &success)
     895facAlgFunc2 (const CanonicalForm & f, const CFList & as)
    1611896{
    1612897  bool isRat= isOn (SW_RATIONAL);
    … …  
    1619904  CFFList result;
    1620905
    1621   success=1;
    1622 
    1623906// F1: [Test trivial cases]
    1624907// 1) first trivial cases:
    … …  
    1665948//    polynomials. If no element of uord occures in any of the minimal
    1666949//   polynomials, we don't have transzendentals.
    1667   Varlist newuord=Var_is_in_AS(uord,Astar);
     950  Varlist newuord= varsInAs (uord, Astar);
    1668951
    1669952  CFFList Factorlist;
    1670   Varlist gcdord= Union(ord,newuord); gcdord.append(f.mvar());
     953  Varlist gcdord= Union(ord,newuord);
     954  gcdord.append(f.mvar());
    1671955  bool isFunctionField= (newuord.length() > 0);
    1672956
    … …  
    1674958  CanonicalForm Fgcd= 0;
    1675959  if (isFunctionField)
    1676     Fgcd= alg_gcd(f,f.deriv(),Astar);
     960    Fgcd= alg_gcd (f, f.deriv(), Astar);
    1677961
    1678962  bool derivZero= f.deriv().isZero();
    … …  
    1682966    if (getCharacteristic() == 0)
    1683967    {
    1684       CFFList result= newfactoras (Ggcd,as,success); //Ggcd is the squarefree part of f
     968      CFFList result= facAlgFunc2 (Ggcd, as); //Ggcd is the squarefree part of f
    1685969      multiplicity (result, f, Astar);
    1686970      if (!isRat && getCharacteristic() == 0)
    … …  
    1692976    if (!isRat && getCharacteristic() == 0)
    1693977      Off (SW_RATIONAL);
    1694     return myUnion(newfactoras(Fgcd,as,success) , newfactoras(Ggcd,as,success));
     978    return merge (facAlgFunc2 (Fgcd, as), facAlgFunc2 (Ggcd, as));
    1695979  }
    1696980
    … …  
    1701985    Variable vminpoly;
    1702986    for (i=Astar; i.hasItem(); i++){degreelist.append(degree(i.getItem()));}
    1703     int extdeg= getextension(degreelist, degree(f));
     987    int extdeg= getDegOfExt (degreelist, degree(f));
    1704988
    1705989    // Now the real stuff!
    … …  
    1707991    {
    1708992      if ( extdeg > 1 ){
    1709         CanonicalForm MIPO= generate_mipo( extdeg, vminpoly);
     993        CanonicalForm MIPO= generateMipo (extdeg);
    1710994        vminpoly= rootOf(MIPO);
    1711995      }
    1712       Factorlist= alg_factor(f, Astar, vminpoly, oldord, as, isFunctionField);
     996      Factorlist= Trager(f, Astar, vminpoly, oldord, as, isFunctionField);
    1713997      return Factorlist;
    1714998    }
    1715     else if ( inseperable(Astar) > 0 || derivZero) // Look if extensions are seperable
     999    else if (isInseparable(Astar) || derivZero) // Look if extensions are separable
    17161000    {
    17171001      Factorlist= SteelTrager(f, Astar, newuord);
    … …  
    17201004    else{ // we are on the save side: Use trager
    17211005      if (extdeg > 1 ){
    1722         CanonicalForm MIPO=generate_mipo(extdeg, vminpoly );
     1006        CanonicalForm MIPO=generateMipo (extdeg);
    17231007        vminpoly= rootOf(MIPO);
    17241008      }
    1725       Factorlist= alg_factor(f, Astar, vminpoly, oldord, as, isFunctionField);
     1009      Factorlist= Trager(f, Astar, vminpoly, oldord, as, isFunctionField);
    17261010      return Factorlist;
    17271011    }
    … …  
    17291013  else{ // char=0 apply trager directly
    17301014    Variable vminpoly;
    1731     Factorlist= alg_factor(f, Astar, vminpoly, oldord, as, isFunctionField);
     1015    Factorlist= Trager(f, Astar, vminpoly, oldord, as, isFunctionField);
    17321016    if (!isRat && getCharacteristic() == 0)
    17331017      Off (SW_RATIONAL);
    … …  
    17351019  }
    17361020
    1737   return CFFList(CFFactor(f,1));
     1021  return CFFList (CFFactor(f,1));
    17381022}
    17391023
     1024
     1025/// factorize a polynomial modulo an extension given by an irreducible
     1026/// characteristic set
    17401027CFFList
    1741 newcfactor(const CanonicalForm & f, const CFList & as, int & success )
     1028facAlgFunc (const CanonicalForm & f, const CFList & as)
    17421029{
    17431030  bool isRat= isOn (SW_RATIONAL);
    … …  
    17521039    if (!isRat && getCharacteristic() == 0)
    17531040      Off (SW_RATIONAL);
    1754     success=1;
    17551041    return Factors;
    17561042  }
    … …  
    17591045    if (!isRat && getCharacteristic() == 0)
    17601046      Off (SW_RATIONAL);
    1761     success=1;
    17621047    return Factors;
    17631048  }
    17641049
    1765   success=1;
    17661050  for ( CFFListIterator i=Factors; i.hasItem(); i++ )
    17671051  {
    17681052    if (i.getItem().factor().level() > as.getLast().level())
    17691053    {
    1770       output=newfactoras(i.getItem().factor(),as, success);
     1054      output=facAlgFunc2(i.getItem().factor(), as);
    17711055      for ( CFFListIterator j=output; j.hasItem(); j++)
    1772         Output = myappend(Output,CFFactor(j.getItem().factor(),j.getItem().exp()*i.getItem().exp()));
     1056        Output = append(Output,CFFactor(j.getItem().factor(),j.getItem().exp()*i.getItem().exp()));
    17731057    }
    17741058  }

  • factory/facAlgFunc.h

    r6bf0b4 rc514f7  
    1919
    2020#include "canonicalform.h"
    21 #include "cf_generator.h"
    22 
    23 // missing class: IntGenerator:
    24 class IntGenerator : public CFGenerator
    25 {
    26 private:
    27     int current;
    28 public:
    29     IntGenerator() : current(0) {}
    30     ~IntGenerator() {}
    31     bool hasItems() const;
    32     void reset() { current = 0; }
    33     CanonicalForm item() const;
    34     void next();
    35     void operator++ () { next(); }
    36     void operator++ ( int ) { next(); }
    37 };
    3821
    3922CanonicalForm alg_gcd(const CanonicalForm &, const CanonicalForm &, const CFList &);
    4023/*BEGINPUBLIC*/
    41 CFFList newfactoras( const CanonicalForm & f, const CFList & as, int &success);
    42 CFFList newcfactor(const CanonicalForm & f, const CFList & as, int & success );
     24CFFList facAlgFunc2 (const CanonicalForm & f, const CFList & as);
     25CFFList facAlgFunc (const CanonicalForm & f, const CFList & as);
    4326/*ENDPUBLIC*/
    4427
Note: See TracChangeset for help on using the changeset viewer.