cf_algorithm.h
Go to the documentation of this file.
1 /* emacs edit mode for this file is -*- C++ -*- */
2 
3 /**
4  * @file cf_algorithm.h
5  * declarations of higher level algorithms.
6  *
7  * Header file corresponds to: cf_algorithm.cc, cf_chinese.cc,
8  * cf_factor.cc, cf_linsys.cc, cf_resultant.cc
9  *
10  * Hierarchy: mathematical algorithms on canonical forms
11  *
12  * Developers note:
13  * ----------------
14  * This header file collects declarations of most of the
15  * functions in Factory which implement higher level algorithms
16  * on canonical forms (factorization, gcd, etc.) and declarations
17  * of some low level mathematical functions, too (absolute value,
18  * euclidean norm, etc.).
19  *
20 **/
21 
22 #ifndef INCL_CF_ALGORITHM_H
23 #define INCL_CF_ALGORITHM_H
24 
25 // #include "config.h"
26 
27 #include "canonicalform.h"
28 #include "variable.h"
29 
30 /*BEGINPUBLIC*/
31 
32 //{{{ function declarations from cf_algorithm.cc
33 CanonicalForm psr ( const CanonicalForm & f, const CanonicalForm & g, const Variable & x );
34 
35 CanonicalForm psq ( const CanonicalForm & f, const CanonicalForm & g, const Variable & x );
36 
37 void psqr ( const CanonicalForm & f, const CanonicalForm & g, CanonicalForm & q, CanonicalForm & r, const Variable & x );
38 
40 
41 bool fdivides ( const CanonicalForm & f, const CanonicalForm & g );
42 
43 bool fdivides ( const CanonicalForm & f, const CanonicalForm & g, CanonicalForm& quot );
44 
45 bool tryFdivides ( const CanonicalForm & f, const CanonicalForm & g, const CanonicalForm& M, bool& fail );
46 
48 
50 //}}}
51 
52 //{{{ function declarations from cf_chinese.cc
53 void chineseRemainder ( const CanonicalForm & x1, const CanonicalForm & q1, const CanonicalForm & x2, const CanonicalForm & q2, CanonicalForm & xnew, CanonicalForm & qnew );
54 
55 void chineseRemainder ( const CFArray & x, const CFArray & q, CanonicalForm & xnew, CanonicalForm & qnew );
56 
58 
59 
60 CanonicalForm Farey ( const CanonicalForm & f, const CanonicalForm & q );
61 //}}}
62 
63 //{{{ function declarations from cf_factor.cc
64 extern int singular_homog_flag;
65 
66 bool isPurePoly(const CanonicalForm & f);
67 
68 bool isPurePoly_m(const CanonicalForm & f);
69 
70 CFFList factorize ( const CanonicalForm & f, bool issqrfree = false );
71 
72 CFFList factorize ( const CanonicalForm & f, const Variable & alpha );
73 
74 CFFList sqrFree ( const CanonicalForm & f, bool sort= false );
75 
78  const Variable & v1, const Variable & v2);
80 CFList get_Terms( const CanonicalForm & f );
81 void getTerms( const CanonicalForm & f, const CanonicalForm & t, CFList & result );
82 
83 
84 //}}}
85 
86 //{{{ function declarations from cf_linsys.cc
87 bool linearSystemSolve ( CFMatrix & M );
88 
89 CanonicalForm determinant ( const CFMatrix & M, int n );
90 //}}}
91 
92 //{{{ function declarations from cf_resultant.cc
93 CFArray subResChain ( const CanonicalForm & f, const CanonicalForm & g, const Variable & x );
94 
95 CanonicalForm resultant ( const CanonicalForm & f, const CanonicalForm & g, const Variable & x );
96 //}}}
97 
98 /** inline CanonicalForm abs ( const CanonicalForm & f )
99  *
100  * abs() - return absolute value of `f'.
101  *
102  * The absolute value is defined in terms of the function
103  * `sign()'. If it reports negative sign for `f' than -`f' is
104  * returned, otherwise `f'.
105  *
106  * This behaviour is most useful for integers and rationals. But
107  * it may be used to sign-normalize the leading coefficient of
108  * arbitrary polynomials, too.
109  *
110  * Type info:
111  * ----------
112  * f: CurrentPP
113  *
114 **/
115 inline CanonicalForm
116 abs ( const CanonicalForm & f )
117 {
118  // it is not only more general to use `sign()' instead of a
119  // direct comparison `f < 0', it is faster, too
120  if ( sign( f ) < 0 )
121  return -f;
122  else
123  return f;
124 }
125 //}}}
126 
127 /*ENDPUBLIC*/
128 
129 #endif /* ! INCL_CF_ALGORITHM_H */
const poly a
Definition: syzextra.cc:212
bool isPurePoly_m(const CanonicalForm &f)
Definition: cf_factor.cc:219
void psqr(const CanonicalForm &f, const CanonicalForm &g, CanonicalForm &q, CanonicalForm &r, const Variable &x)
void psqr ( const CanonicalForm & f, const CanonicalForm & g, CanonicalForm & q, CanonicalForm & r...
CanonicalForm psq(const CanonicalForm &f, const CanonicalForm &g, const Variable &x)
CanonicalForm psq ( const CanonicalForm & f, const CanonicalForm & g, const Variable & x ) ...
factory's class for variables
Definition: variable.h:32
CanonicalForm homogenize(const CanonicalForm &f, const Variable &x)
homogenize homogenizes f with Variable x
Definition: cf_factor.cc:298
CanonicalForm maxNorm(const CanonicalForm &f)
CanonicalForm maxNorm ( const CanonicalForm & f )
const CanonicalForm CFMap CFMap int &both_non_zero int n
Definition: cfEzgcd.cc:52
factory's main class
Definition: canonicalform.h:75
g
Definition: cfModGcd.cc:4031
Variable alpha
Definition: facAbsBiFact.cc:52
CFArray subResChain(const CanonicalForm &f, const CanonicalForm &g, const Variable &x)
CFArray subResChain ( const CanonicalForm & f, const CanonicalForm & g, const Variable & x ) ...
Definition: cf_resultant.cc:42
bool linearSystemSolve(CFMatrix &M)
Definition: cf_linsys.cc:78
bool tryFdivides(const CanonicalForm &f, const CanonicalForm &g, const CanonicalForm &M, bool &fail)
same as fdivides but handles zero divisors in Z_p[t]/(f)[x1,...,xn] for reducible f ...
#define M
Definition: sirandom.c:24
CFFList factorize(const CanonicalForm &f, bool issqrfree=false)
factorization over or
Definition: cf_factor.cc:390
CanonicalForm Farey(const CanonicalForm &f, const CanonicalForm &q)
Farey rational reconstruction.
Definition: cf_chinese.cc:197
const ring r
Definition: syzextra.cc:208
CanonicalForm bCommonDen(const CanonicalForm &f)
CanonicalForm bCommonDen ( const CanonicalForm & f )
CFList get_Terms(const CanonicalForm &f)
Definition: cf_factor.cc:274
bool isPurePoly(const CanonicalForm &f)
Definition: cf_factor.cc:229
FILE * f
Definition: checklibs.c:7
int singular_homog_flag
Definition: cf_factor.cc:377
void chineseRemainderCached(CFArray &a, CFArray &n, CanonicalForm &xnew, CanonicalForm &prod, CFArray &inv)
Definition: cf_chinese.cc:264
operations on variables
void chineseRemainder(const CanonicalForm &x1, const CanonicalForm &q1, const CanonicalForm &x2, const CanonicalForm &q2, CanonicalForm &xnew, CanonicalForm &qnew)
void chineseRemainder ( const CanonicalForm & x1, const CanonicalForm & q1, const CanonicalForm & x2...
Definition: cf_chinese.cc:52
bool fdivides(const CanonicalForm &f, const CanonicalForm &g)
bool fdivides ( const CanonicalForm & f, const CanonicalForm & g )
CanonicalForm euclideanNorm(const CanonicalForm &f)
CanonicalForm euclideanNorm ( const CanonicalForm & f )
void getTerms(const CanonicalForm &f, const CanonicalForm &t, CFList &result)
get_Terms: Split the polynomial in the containing terms.
Definition: cf_factor.cc:264
CanonicalForm psr(const CanonicalForm &f, const CanonicalForm &g, const Variable &x)
CanonicalForm psr ( const CanonicalForm & f, const CanonicalForm & g, const Variable & x ) ...
fq_nmod_poly_t prod
Definition: facHensel.cc:95
CanonicalForm abs(const CanonicalForm &f)
inline CanonicalForm abs ( const CanonicalForm & f )
Definition: cf_algorithm.h:116
CanonicalForm determinant(const CFMatrix &M, int n)
Definition: cf_linsys.cc:222
Variable x
Definition: cfModGcd.cc:4023
void sort(CFArray &A, int l=0)
quick sort A
CanonicalForm resultant(const CanonicalForm &f, const CanonicalForm &g, const Variable &x)
CanonicalForm resultant ( const CanonicalForm & f, const CanonicalForm & g, const Variable & x ) ...
CFFList sqrFree(const CanonicalForm &f, bool sort=false)
squarefree factorization
Definition: cf_factor.cc:757
Variable get_max_degree_Variable(const CanonicalForm &f)
get_max_degree_Variable returns Variable with highest degree.
Definition: cf_factor.cc:245
return result
Definition: facAbsBiFact.cc:76
int sign(const CanonicalForm &a)
Header for factory's main class CanonicalForm.