source: git/libfac/factor/homogfactor.cc @ 18500b

jengelh-datetimespielwiese
Last change on this file since 18500b was 18500b, checked in by Martin Lee <martinlee84@…>, 11 years ago
chg: moved libfac back
  • Property mode set to 100644
File size: 5.6 KB
Line 
1////////////////////////////////////////////////////////////
2////////////////////////////////////////////////////////////
3// FACTORY - Includes
4#include <factory.h>
5#ifdef HAVE_IOSTREAM
6#include <iostream>
7#define OSTREAM std::ostream
8#define ISTREAM std::istream
9#define CERR std::cerr
10#define CIN std::cin
11#elif defined(HAVE_IOSTREAM_H)
12#include <iostream.h>
13#define OSTREAM ostream
14#define ISTREAM istream
15#define CERR cerr
16#define CIN cin
17#endif
18
19// Factor - Includes
20#include "tmpl_inst.h"
21#include "Factor.h"
22// some CC's need it:
23#include "homogfactor.h"
24
25void out_cf(char *s1,const CanonicalForm &f,char *s2);
26
27#ifdef HFACTORDEBUG
28#  define DEBUGOUTPUT
29#else
30#  undef DEBUGOUTPUT
31#endif
32
33#include <libfac/factor/debug.h>
34#include "timing.h"
35TIMING_DEFINE_PRINT(hfactorize_time)
36
37#if 0
38///////////////////////////////////////////////////////////////
39// get_Terms: Split the polynomial in the containing terms.  //
40// getTerms: the real work is done here.                     //
41///////////////////////////////////////////////////////////////
42static void
43getTerms( const CanonicalForm & f, const CanonicalForm & t, CFList & result ){
44
45  if ( getNumVars(f) == 0 ) result.append(f*t);
46  else{
47    Variable x(level(f));
48    for ( CFIterator i=f; i.hasTerms(); i++ )
49      getTerms( i.coeff(), t*power(x,i.exp()), result);
50  }
51}
52
53CFList
54get_Terms( const CanonicalForm & f ){
55  CFList result,dummy,dummy2;
56  CFIterator i;
57  CFListIterator j;
58
59  if ( getNumVars(f) == 0 ) result.append(f);
60  else{
61    Variable _x(level(f));
62    for ( i=f; i.hasTerms(); i++ ){
63      getTerms(i.coeff(), 1, dummy);
64      for ( j=dummy; j.hasItem(); j++ )
65        result.append(j.getItem() * power(_x, i.exp()));
66
67      dummy= dummy2; // have to initalize new
68    }
69  }
70  return result;
71}
72#endif
73
74#if 0
75///////////////////////////////////////////////////////////////
76// is_homogeneous returns 1 iff f is homogeneous, 0 otherwise//
77///////////////////////////////////////////////////////////////
78bool
79is_homogeneous( const CanonicalForm & f){
80  CFList termlist= get_Terms(f);
81  CFListIterator i;
82  int deg= totaldegree(termlist.getFirst());
83
84  for ( i=termlist; i.hasItem(); i++ )
85    if ( totaldegree(i.getItem()) != deg ) return 0;
86  return 1;
87  // now: return f.isHomogeneous();
88}
89#endif
90
91#if 0
92///////////////////////////////////////////////////////////////
93// get_max_degree_Variable returns Variable with             //
94// highest degree. We assume f is *not* a constant!          //
95///////////////////////////////////////////////////////////////
96static Variable
97get_max_degree_Variable(const CanonicalForm & f){
98  ASSERT( ( ! f.inCoeffDomain() ), "no constants" );
99  int max=0, maxlevel=0, n=level(f);
100  for ( int i=1; i<=n; i++ )
101    if (degree(f,Variable(i)) >= max) {
102      max= degree(f,Variable(i)); maxlevel= i;
103    }
104  return Variable(maxlevel);
105}
106#endif
107
108#if 0
109///////////////////////////////////////////////////////////////
110// homogenize homogenizes f with Variable x                  //
111///////////////////////////////////////////////////////////////
112static CanonicalForm
113homogenize( const CanonicalForm & f, const Variable & x){
114  CFList Newlist, Termlist= get_Terms(f);
115  int maxdeg=totaldegree(f), deg;
116  CFListIterator i;
117  CanonicalForm elem, result=f.genZero();
118 
119  for (i=Termlist; i.hasItem(); i++){
120    elem= i.getItem();
121    deg = totaldegree(elem);
122    if ( deg < maxdeg )
123      Newlist.append(elem * power(x,maxdeg-deg));
124    else
125      Newlist.append(elem);
126  }
127  for (i=Newlist; i.hasItem(); i++) // rebuild
128    result += i.getItem();
129   
130  return result;
131}
132#endif
133
134// we assume g is square-free
135CFFList
136HomogFactor( const CanonicalForm & g, const CanonicalForm  & minpoly, const int Mainvar )
137{
138  DEBINCLEVEL(CERR, "HomogFactor");
139  Variable xn = get_max_degree_Variable(g);
140  //out_cf("HomogFactor:",g,"\n");
141  int d_xn = degree(g,xn);
142  CanonicalForm F = g(1,xn);
143
144  DEBOUTLN(CERR, "xn= ", xn);
145  DEBOUTLN(CERR, "d_xn=   ", d_xn);
146  DEBOUTLN(CERR, "F= ", F); 
147  //out_cf("HomogFactor:subst ",F,"\n");
148
149  // should we do this for low degree polys g ? e.g. quadratic?
150  //
151  CFFList Homoglist;
152  CFFListIterator j;
153  if (minpoly.isZero())
154    Homoglist = factorize(F, 1);
155  else
156  {
157    CFFList Intermediatelist;
158    CFMap n;
159    Intermediatelist = Factorized(compress(F,n), minpoly, Mainvar);
160    for ( j=Intermediatelist; j.hasItem(); j++ )
161      Homoglist.append(CFFactor( n(j.getItem().factor()), j.getItem().exp()) );
162  }
163  // Now we have uncompressed factors in Homoglist
164  DEBOUTLN(CERR, "F factors as: ", Homoglist);
165  CFFList Unhomoglist;
166  CanonicalForm unhomogelem;
167  if ((!(minpoly.isZero())) &&(getCharacteristic() == 0) )
168  {
169    for ( j=Homoglist; j.hasItem(); j++ )
170    {
171      // assume that minpoly.level() < level of all "real" variables of g
172      DEBOUTLN(CERR, "Homogenizing ",j.getItem().factor()); 
173      unhomogelem= homogenize(j.getItem().factor(),xn,
174                         Variable(minpoly.level()+1),g.mvar());
175      DEBOUTLN(CERR, "      that is ", unhomogelem);
176      Unhomoglist.append(CFFactor(unhomogelem,j.getItem().exp()));
177      d_xn -= degree(unhomogelem,xn)*j.getItem().exp();
178    }
179  }
180  else
181  {
182    for ( j=Homoglist; j.hasItem(); j++ )
183    {
184      DEBOUTLN(CERR, "Homogenizing ",j.getItem().factor()); 
185      unhomogelem= homogenize(j.getItem().factor(),xn);
186      DEBOUTLN(CERR, "      that is ", unhomogelem);
187      //out_cf("unhomogelem:",unhomogelem,"\n");
188      Unhomoglist.append(CFFactor(unhomogelem,j.getItem().exp()));
189      d_xn -= degree(unhomogelem,xn)*j.getItem().exp();
190    }
191  }
192  DEBOUTLN(CERR, "Power of xn to append is ", d_xn);
193  if ( d_xn != 0 ) // have to append xn^(d_xn)
194    Unhomoglist.append(CFFactor(CanonicalForm(xn),d_xn));
195
196  DEBDECLEVEL(CERR, "HomogFactor");
197  return Unhomoglist;
198}
199
Note: See TracBrowser for help on using the repository browser.