canonicalform.cc
Go to the documentation of this file.
1 /* emacs edit mode for this file is -*- C++ -*- */
2 
3 
4 #include "config.h"
5 
6 
7 #include "cf_assert.h"
8 #include "cf_factory.h"
9 
10 #include "cf_defs.h"
11 #include "cf_globals.h"
12 #include "canonicalform.h"
13 #include "cf_iter.h"
14 #include "int_cf.h"
15 #include "cf_algorithm.h"
16 #include "imm.h"
17 #include "gfops.h"
18 #include "facMul.h"
19 #include "FLINTconvert.h"
20 
21 #include <factory/cf_gmp.h>
22 
23 #ifndef NOSTREAMIO
24 CanonicalForm readCF( ISTREAM& );
25 #endif /* NOSTREAMIO */
26 
27 /** constructors, destructors, selectors **/
28 CanonicalForm::CanonicalForm( const char * str, const int base ) : value( CFFactory::basic( str, base ) )
29 {
30 }
31 
32 InternalCF*
33 CanonicalForm::getval() const
34 {
35  if ( is_imm( value ) )
36  return value;
37  else
38  return value->copyObject();
39 }
40 
41 CanonicalForm
42 CanonicalForm::deepCopy() const
43 {
44  if ( is_imm( value ) )
45  return *this;
46  else
47  return CanonicalForm( value->deepCopyObject() );
48 }
49 
50 void
51 CanonicalForm::mpzval(mpz_t val) const
52 {
53  ASSERT (!is_imm (value) && value->levelcoeff() == IntegerDomain, "non-immediate integer expected");
54  getmpi (value, val);
55 }
56 
57 
58 /** predicates **/
59 #if 0
60 bool
61 CanonicalForm::isImm() const
62 {
63  return is_imm( value );
64 }
65 #endif
66 
67 bool
68 CanonicalForm::inZ() const
69 {
70  if ( is_imm( value ) == INTMARK )
71  return true;
72  else if ( is_imm( value ) )
73  return false;
74  else
75  return value->levelcoeff() == IntegerDomain;
76 }
77 
78 bool
79 CanonicalForm::inQ() const
80 {
81  if ( is_imm( value ) == INTMARK )
82  return true;
83  else if ( is_imm( value ) )
84  return false;
85  else
86  return value->levelcoeff() == IntegerDomain ||
87  value->levelcoeff() == RationalDomain;
88 }
89 
90 bool
91 CanonicalForm::inFF() const
92 {
93  return is_imm( value ) == FFMARK;
94 }
95 
96 bool
97 CanonicalForm::inGF() const
98 {
99  return is_imm( value ) == GFMARK;
100 }
101 
102 bool
103 CanonicalForm::inBaseDomain() const
104 {
105  if ( is_imm( value ) )
106  return true;
107  else
108  return value->inBaseDomain();
109 }
110 
111 bool
112 CanonicalForm::inExtension() const
113 {
114  if ( is_imm( value ) )
115  return false;
116  else
117  return value->inExtension();
118 }
119 
120 bool
121 CanonicalForm::inCoeffDomain() const
122 {
123  if ( is_imm( value ) )
124  return true;
125  else
126  return value->inCoeffDomain();
127 }
128 
129 bool
130 CanonicalForm::inPolyDomain() const
131 {
132  if ( is_imm( value ) )
133  return false;
134  else
135  return value->inPolyDomain();
136 }
137 
138 bool
139 CanonicalForm::inQuotDomain() const
140 {
141  if ( is_imm( value ) )
142  return false;
143  else
144  return value->inQuotDomain();
145 }
146 
147 bool
148 CanonicalForm::isFFinGF() const
149 {
150  return is_imm( value ) == GFMARK && gf_isff( imm2int( value ) );
151 }
152 
153 bool
154 CanonicalForm::isUnivariate() const
155 {
156  if ( is_imm( value ) )
157  return false;
158  else
159  return value->isUnivariate();
160 }
161 
162 // is_homogeneous returns 1 iff f is homogeneous, 0 otherwise//
163 bool
164 CanonicalForm::isHomogeneous() const
165 {
166  if (this->isZero()) return true;
167  else if (this->inCoeffDomain()) return true;
168  else
169  {
170 #if 0
171  CFIterator i;
172  int cdeg = -2, dummy;
173  for ( i = *this; i.hasTerms(); i++ )
174  {
175  if (!(i.coeff().isHomogeneous())) return false;
176  if ( (dummy = totaldegree( i.coeff() ) + i.exp()) != cdeg )
177  {
178  if (cdeg == -2) cdeg = dummy;
179  else return false;
180  }
181  }
182  return true;
183 #else
184  CFList termlist= get_Terms(*this);
185  CFListIterator i;
186  int deg= totaldegree(termlist.getFirst());
187 
188  for ( i=termlist; i.hasItem(); i++ )
189  if ( totaldegree(i.getItem()) != deg ) return false;
190  return true;
191 #endif
192  }
193 }
194 
195 
196 
197 /** conversion functions **/
198 long
199 CanonicalForm::intval() const
200 {
201  if ( is_imm( value ) )
202  return imm_intval( value );
203  else
204  return value->intval();
205 }
206 
207 CanonicalForm
208 CanonicalForm::mapinto () const
209 {
210  //ASSERT( is_imm( value ) || ! value->inExtension(), "cannot map into different Extension" );
211  if ( is_imm( value ) )
212  if ( getCharacteristic() == 0 )
213  if ( is_imm( value ) == FFMARK )
214  return CanonicalForm( int2imm( ff_symmetric( imm2int( value ) ) ) );
215  else if ( is_imm( value ) == GFMARK )
216  return CanonicalForm( int2imm( ff_symmetric( gf_gf2ff( imm2int( value ) ) ) ) );
217  else
218  return *this;
219  else if ( getGFDegree() == 1 )
220  return CanonicalForm( int2imm_p( ff_norm( imm2int( value ) ) ) );
221  else
222  return CanonicalForm( int2imm_gf( gf_int2gf( imm2int( value ) ) ) );
223  else if ( value->inBaseDomain() )
224  if ( getCharacteristic() == 0 )
225  return *this;
226  else
227  {
228  int val;
229  if ( value->levelcoeff() == IntegerDomain )
230  val = value->intmod( ff_prime );
231  else if ( value->levelcoeff() == RationalDomain )
232  return num().mapinto() / den().mapinto();
233  else {
234  ASSERT( 0, "illegal domain" );
235  return 0;
236  }
237  if ( getGFDegree() > 1 )
238  return CanonicalForm( int2imm_gf( gf_int2gf( val ) ) );
239  else
240  return CanonicalForm( int2imm_p( val ) );
241  }
242  else
243  {
244  Variable x = value->variable();
245  CanonicalForm result;
246  for ( CFIterator i = *this; i.hasTerms(); i++ )
247  result += (power( x, i.exp() ) * i.coeff().mapinto());
248  return result;
249  }
250 }
251 
252 /** CanonicalForm CanonicalForm::lc (), Lc (), LC (), LC ( v ) const
253  *
254  * lc(), Lc(), LC() - leading coefficient functions.
255  *
256  * All methods return CO if CO is in a base domain.
257  *
258  * lc() returns the leading coefficient of CO with respect to
259  * lexicographic ordering. Elements in an algebraic extension
260  * are considered polynomials so lc() always returns a leading
261  * coefficient in a base domain. This method is useful to get
262  * the base domain over which CO is defined.
263  *
264  * Lc() returns the leading coefficient of CO with respect to
265  * lexicographic ordering. In contrast to lc() elements in an
266  * algebraic extension are considered coefficients so Lc() always
267  * returns a leading coefficient in a coefficient domain.
268  *
269  * LC() returns the leading coefficient of CO where CO is
270  * considered a univariate polynomial in its main variable. An
271  * element of an algebraic extension is considered an univariate
272  * polynomial, too.
273  *
274  * LC( v ) returns the leading coefficient of CO where CO is
275  * considered an univariate polynomial in the polynomial variable
276  * v.
277  * Note: If v is less than the main variable of CO we have to
278  * swap variables which may be quite expensive.
279  *
280  * Examples:
281  * > Let x < y be polynomial variables, a an algebraic variable.
282  *
283  * > (3*a*x*y^2+y+x).lc() = 3
284  *
285  * > (3*a*x*y^2+y+x).Lc() = 3*a
286  *
287  * > (3*a*x*y^2+y+x).LC() = 3*a*x
288  *
289  * > (3*a*x*y^2+y+x).LC( x ) = 3*a*y^2+1
290  *
291  *
292  * > (3*a^2+4*a).lc() = 3
293  *
294  * > (3*a^2+4*a).Lc() = 3*a^2+4*a
295  *
296  * > (3*a^2+4*a).LC() = 3
297  *
298  * > (3*a^2+4*a).LC( x ) = 3*a^2+4*a
299  *
300  * @sa InternalCF::lc(), InternalCF::Lc(), InternalCF::LC(),
301  * InternalPoly::lc(), InternalPoly::Lc(), InternalPoly::LC(),
302  * ::lc(), ::Lc(), ::LC(), ::LC( v )
303  *
304 **/
305 CanonicalForm
306 CanonicalForm::lc () const
307 {
308  if ( is_imm( value ) )
309  return *this;
310  else
311  return value->lc();
312 }
313 
314 /**
315  * @sa CanonicalForm::lc(), CanonicalForm::LC(), InternalCF::lc(),
316  * InternalCF::Lc(), InternalCF::LC(),
317  * InternalPoly::lc(), InternalPoly::Lc(), InternalPoly::LC(),
318  * ::lc(), ::Lc(), ::LC(), ::LC( v )
319 **/
320 CanonicalForm
321 CanonicalForm::Lc () const
322 {
323  if ( is_imm( value ) || value->inCoeffDomain() )
324  return *this;
325  else
326  return value->Lc();
327 }
328 
329 /**
330  * @sa CanonicalForm::lc(), CanonicalForm::Lc(), InternalCF::lc(),
331  * InternalCF::Lc(), InternalCF::LC(),
332  * InternalPoly::lc(), InternalPoly::Lc(), InternalPoly::LC(),
333  * ::lc(), ::Lc(), ::LC(), ::LC( v )
334 **/
335 CanonicalForm
336 CanonicalForm::LC () const
337 {
338  if ( is_imm( value ) )
339  return *this;
340  else
341  return value->LC();
342 }
343 
344 /**
345  * @sa CanonicalForm::lc(), CanonicalForm::Lc(), InternalCF::lc(),
346  * InternalCF::Lc(), InternalCF::LC(),
347  * InternalPoly::lc(), InternalPoly::Lc(), InternalPoly::LC(),
348  * ::lc(), ::Lc(), ::LC(), ::LC( v )
349 **/
350 CanonicalForm
351 CanonicalForm::LC ( const Variable & v ) const
352 {
353  if ( is_imm( value ) || value->inCoeffDomain() )
354  return *this;
355 
356  Variable x = value->variable();
357  if ( v > x )
358  return *this;
359  else if ( v == x )
360  return value->LC();
361  else {
362  CanonicalForm f = swapvar( *this, v, x );
363  if ( f.mvar() == x )
364  return swapvar( f.value->LC(), v, x );
365  else
366  // v did not occur in f
367  return *this;
368  }
369 }
370 
371 /**
372  * Returns -1 for the zero polynomial and 0 if
373  * CO is in a base domain.
374  *
375  * degree() returns the degree of CO in its main variable.
376  * Elements in an algebraic extension are considered polynomials.
377  *
378  * @sa InternalCF::degree(), InternalPoly::degree(),
379  * ::degree(), ::degree( v )
380  *
381 **/
382 int
383 CanonicalForm::degree() const
384 {
385  int what = is_imm( value );
386  if ( what )
387  if ( what == FFMARK )
388  return imm_iszero_p( value ) ? -1 : 0;
389  else if ( what == INTMARK )
390  return imm_iszero( value ) ? -1 : 0;
391  else
392  return imm_iszero_gf( value ) ? -1 : 0;
393  else
394  return value->degree();
395 }
396 
397 /**
398  * returns -1 for the zero polynomial and 0 if
399  * CO is in a base domain.
400  *
401  * degree( v ) returns the degree of CO with respect to v.
402  * Elements in an algebraic extension are considered polynomials,
403  * and v may be algebraic.
404  *
405  * @sa InternalCF::degree(), InternalPoly::degree(),
406  * ::degree(), ::degree( v )
407 **/
408 int
409 CanonicalForm::degree( const Variable & v ) const
410 {
411  int what = is_imm( value );
412 #if 0
413  if ( what )
414  if ( what == FFMARK )
415  return imm_iszero_p( value ) ? -1 : 0;
416  else if ( what == INTMARK )
417  return imm_iszero( value ) ? -1 : 0;
418  else
419  return imm_iszero_gf( value ) ? -1 : 0;
420  else if ( value->inBaseDomain() )
421  return value->degree();
422 #else
423  switch(what)
424  {
425  case FFMARK: return imm_iszero_p( value ) ? -1 : 0;
426  case INTMARK: return imm_iszero( value ) ? -1 : 0;
427  case GFMARK: return imm_iszero_gf( value ) ? -1 : 0;
428  case 0: if ( value->inBaseDomain() )
429  return value->degree();
430  break;
431  }
432 #endif
433 
434  Variable x = value->variable();
435  if ( v == x )
436  return value->degree();
437  else if ( v > x )
438  // relatively to v, f is in a coefficient ring
439  return 0;
440  else {
441  int coeffdeg, result = 0;
442  // search for maximum of coefficient degree
443  for ( CFIterator i = *this; i.hasTerms(); i++ ) {
444  coeffdeg = i.coeff().degree( v );
445  if ( coeffdeg > result )
446  result = coeffdeg;
447  }
448  return result;
449  }
450 }
451 
452 /**
453  *
454  * tailcoeff() - return least coefficient
455  *
456  * tailcoeff() returns the coefficient of the term with the least
457  * degree in CO where CO is considered an univariate polynomial
458  * in its main variable. Elements in an algebraic extension are
459  * considered coefficients.
460  *
461  * @sa CanonicalForm::taildegree(), InternalCF::tailcoeff(), InternalCF::tailcoeff(),
462  * InternalPoly::tailcoeff(), InternalPoly::taildegree,
463  * ::tailcoeff(), ::taildegree()
464  *
465 **/
466 CanonicalForm
467 CanonicalForm::tailcoeff () const
468 {
469  if ( is_imm( value ) || value->inCoeffDomain() )
470  return *this;
471  else
472  return value->tailcoeff();
473 }
474 
475 /**
476  * tailcoeff( v ) returns the tail coefficient of CO where CO is
477  * considered an univariate polynomial in the polynomial variable
478  * v.
479  * Note: If v is less than the main variable of CO we have to
480  * swap variables which may be quite expensive.
481  *
482  * @sa CanonicalForm::taildegree(), InternalCF::tailcoeff(), InternalCF::tailcoeff(),
483  * InternalPoly::tailcoeff(), InternalPoly::taildegree,
484  * ::tailcoeff(), ::taildegree()
485 **/
486 CanonicalForm
487 CanonicalForm::tailcoeff (const Variable& v) const
488 {
489  if ( is_imm( value ) || value->inCoeffDomain() )
490  return *this;
491 
492  Variable x = value->variable();
493  if ( v > x )
494  return *this;
495  else if ( v == x )
496  return value->tailcoeff();
497  else {
498  CanonicalForm f = swapvar( *this, v, x );
499  if ( f.mvar() == x )
500  return swapvar( f.value->tailcoeff(), v, x );
501  else
502  // v did not occur in f
503  return *this;
504  }
505 }
506 
507 
508 /**
509  * taildegree() returns -1 for the zero polynomial, 0 if CO is in
510  * a base domain, otherwise the least degree of CO where CO is
511  * considered a univariate polynomial in its main variable. In
512  * contrast to tailcoeff(), elements in an algebraic extension
513  * are considered polynomials, not coefficients, and such may
514  * have a taildegree larger than zero.
515  *
516  * @sa CanonicalForm::tailcoeff(), InternalCF::tailcoeff(), InternalCF::tailcoeff(),
517  * InternalPoly::tailcoeff(), InternalPoly::taildegree,
518  * ::tailcoeff(), ::taildegree()
519 **/
520 int
521 CanonicalForm::taildegree () const
522 {
523  int what = is_imm( value );
524  if ( what )
525  if ( what == FFMARK )
526  return imm_iszero_p( value ) ? -1 : 0;
527  else if ( what == INTMARK )
528  return imm_iszero( value ) ? -1 : 0;
529  else
530  return imm_iszero_gf( value ) ? -1 : 0;
531  else
532  return value->taildegree();
533 }
534 
535 /**
536  * level() returns the level of CO. For a list of the levels and
537  * their meanings, see cf_defs.h.
538  *
539  * @sa InternalCF::level(), InternalCF::variable(),
540  * InternalPoly::level(), InternalPoly::variable(), ::level(),
541  * ::mvar()
542  *
543 **/
544 int
545 CanonicalForm::level () const
546 {
547  if ( is_imm( value ) )
548  return LEVELBASE;
549  else
550span class="lineno"> 549  else
549  <82d8d2ab35871a5dc2838dba5942b7">jjLIST_PL
BOOLEAN jjLss="line">bool 9;operatoCanonicalForm.html#a2007b4d2829ad3c2434a2e1aeree()
{
2407  T->copySubmatInto(m, 1, 1, A->cols(), A->int_cf.h"
15 502 
polynomial, 0 if CO is in
*
482  * @sa CanonicalForm::tailde4ine"> 511ive.8cc_so3rce.html">blackbox.cc.

9> 482  * @sa CanonicalForm::tailde4ine"> 511  wordflow">else
="line lineno"> d165  if (bb->blackbox_Op1== 511ive.v, () codiv> 1971 #endif
if (!return 385  swapvar( *this, v, x );
bimMult(bigintmat *
532  css="line"4value-> 89 {
lass="lint 532="line"> 1629  1630  // special cases
16ba> 508orm.html#af5891a59ab02bed67e49a043ee02b5b8"> 521  1132&#pan> <2bed67e49a043ee02b5b8"> 521  1132&lassCav class="line">
.coeff().mlgebraic extension
Variable& 1629  1498e"> 503 
14992c8195c27dbcb705a8a535599">level() )
* * InternalPoly::tailcoeff(), InternalPoly::taildegree,
  gfan::ZMatrix lins = zclPoly::tailcoeff(), InternalPoly::taildegree,
512  () const
"fanFromString: unexpected parameters");return *this;
11c92b208796>return *this;
*thi€#b0f8imm( value );
412 #if 0
if ( what )
)
)
 k<=get_Terms(*this);
return 2641  numv>
468 
523  int what = * ::tailcoeff(), ::taildegree()
> 227  < class="comment"> * @sa InternalCF=2">i++)
1630< class="comment"> * @sa InternadCF=2">i++)
518  * ::tailcoef/span>  delete false;
176  963  *n claa class="code" href="classCanonicalForm.html#a2007b4d2829ad3c2434a2e1ae55c6f60">value;
37  else
else ifan>
else 496  return 523    }
1370ef="int__cf_8h.html">int_cf.h"
.coeff().mlgebraic extension
Variable& 1629  1498e">822ba7525e15951bcbe">
InternalCF::divremcoefft 533 }
InternalCF *, InternalCF *&, InternalCF *&amne">v, * ::tailcoeff(), ::taildegree()
485 <*this;
11c92b20879namn class="comment"> * their meanings, sp/div>basecoeffs());
*
sign()<=0)
"lineno"> 513  * are considered polynomials, not coefficients, and such may
514  * have a taildegno"> 544  13> imm_iszero( value ) ? -1 : 0;
imm_iszero( 362  * () 362< clasn>&#"> ass="comment"> *int what = is_imm( value );
#160; 1949-> 373&(5name="l01630"> 1lForm.a class="code" h
{
v, 4595n>
}v, 4595n>
}v, return imm_iszero_p( value ) ? -1 : 0;
274  * LC( v ) returns the leadinfor thesl6stupid
1630  CanonicalFlass="keywordflow">if ( f. 421="line lineno"> d165 return ( v > x )
358case * anonicalForm.html#a2007b4d2829ad3c2434a2>int
 **/
)
FFMARK: retu 97  21 = 464  *
  * degree() returns the degree of CO in its main variable./span>
376  * Elements in an algebraic extension are considered polynomials.
377 value ) )
return return value;
value;
379 if ( what )
414  if ( what ==(ordf4ow">if ( what )
if ( what ==
415  return imm_iszero_p( * contn class="lineno"> 13> imm_iszero( value<160; * swap variables w/a>
525  if ( wh9t ==   number tmp;
327  class="name="l00449">,0; number tmp;
327  class="name="l00449">,0; nuly::taildegree,
523  int what = * ::tailcoeff(), ::taildegree()
> 227  Definition: }
> 227  Definition: }
> 227  Definition: }
> 227  Definition:
() )
value;
444  coeffdeg = i.coeff else 464ame="l00478"> 478  * v.value );
 tml#9f8cea1 * are considered polynclass="code" h
{
q  "> 89 {
lass="lint 532="line"> 1629  css="line"4nCoeff_is_Extension
static FORCE_INLINE BOOLEAN nCoeff_is_Extension(coss="0662aeb">inCoeffDomain() )rtyp = v class="line"> *imm_iszerclass="memdoc">

exponentiation oc">a nalse *tlass="lineno"> 216  return CanonicalForm( ="lineno"> 352span> what = is_imm( {

Memname">iert zur Matrix den Skalar b hinzu.
Definition: const
bigintmat *  b, ¾^ 464îonsidered polynomials.
> 227 Definition: 274 <( *n claa class="code" href="classCanonicalForm.html#a2007b4d2829/a>#160; 1949->n_Z);
;
< *
{
v, 4595n>
}v, 4595n>
}
512>());
imm_iszero_p( value ) ? -1 : 0;
* @sa InternalCF=2">i++)
4595n>
}
512>());
imu83014412d_8cc.html#a745f6fc0aa651dfb38f2a8cb83b7608b">prod;
ss="code" href="classCanonicalForm.ha>( vallass="span class="k" href="classInternalCF.html#a9174405d3fa name="l01631"> * () 362< clasn>&#"4th7s;
> 13> 512 me="l00519">> 227  Definition: }
* have a tne"> 1629  1630  rm::tailcoeff(), InternalCF::taspand class="memItemLeft" align="reac4f445a8">swapvar( f. 1630  rm::tailcoeff(),5lasentsa enternalCF=2">iCanonicalForm
13> imm_iszero( value ) ? -1 : 0;
imm_iszero( (if ( v > x )
* :+9o"> 470  *n claa class="code" hrefv, ( value );
353false;
bigintmat.cc:1960
ifLC(), v,     * ()this;
="line lineno"> d165 );
#160; 1949 ly::
426me="l008h.html#a86c381aa8ff0c5354b} 468& 443  for ( CFIterator i = *this; ( what )
171  leaves p and q unmodified */
bigintmat *  x, imm_iszero( x, )9tr> ml#a428f99bbff1945f5d70d59ac0f2b3511">Canom_iszerclass="memdoc">

exponentiation oc">a nalse * 216  ( 37  else 377 value ) )

return
<4iv c"libparse_8cc.html#a25093e36lue ) )
return return value;
value;
464"fanFromString: unexpected parameters"); -> iv>
* Elements in an algebraict2immhtml#a5solve Ax=b, more precisely, find
2311  // number d
imm_iszero_pe/a>( > 227  return pan>  ifme="l00478"> 478  * v.value );f="clas00518"> 5 CO. For a list of the levels and