My Project  debian-1:4.1.2-p1+ds-2
gen_maps.cc
Go to the documentation of this file.
1 /****************************************
2 * Computer Algebra System SINGULAR *
3 ****************************************/
4 #include "kernel/mod2.h"
5 #include "misc/options.h"
7 #include "polys/prCopy.h"
8 #include "kernel/ideals.h"
9 #include "polys/monomials/ring.h"
10 #include "polys/monomials/maps.h"
11 #include "polys/sbuckets.h"
12 #include "kernel/maps/fast_maps.h"
13 #include "kernel/maps/find_perm.h"
14 #include "kernel/maps/gen_maps.h"
15 
16 static void find_subst_for_map(const ring preimage_r, const ring image_r, const ideal image, int &var,poly &p)
17 {
18  p=NULL;
19  var=0;
20  int i,v;
21  for (i=si_min(IDELEMS(image),preimage_r->N)-1; i>=0; i--)
22  {
23  if (image->m[i]!=NULL)
24  {
25  if ((pNext(image->m[i])==NULL)
26  && (n_IsOne(pGetCoeff(image->m[i]),image_r->cf)))
27  {
28  v=p_IsUnivariate(image->m[i],image_r);
29  if ((v<=0) /*not univariate */
30  || (v!=i+1) /* non-trivial */
31  || (p_GetExp(image->m[i],v,image_r)!=1))
32  {
33  if (var==0)
34  {
35  var=i+1;
36  p=image->m[i];
37  }
38  else /* found second non-trivial entry */
39  {
40  goto non_trivial;
41  }
42  }
43  }
44  else
45  {
46  if (var==0)
47  {
48  var=i+1;
49  p=image->m[i];
50  }
51  else /* found second non-trivial entry */
52  {
53  goto non_trivial;
54  }
55  }
56  }
57  else
58  {
59  if (var==0)
60  {
61  var=i+1;
62  p=image->m[i];
63  }
64  else /* found second non-trivial entry */
65  {
66  goto non_trivial;
67  }
68  }
69  }
70  //Print("elms:%d, N:%d\n",IDELEMS(image),preimage_r->N);
71  //iiWriteMatrix((matrix)image,"_",1,image_r,0);
72  //PrintS("\npreimage:\n");rWrite(preimage_r);
73  //PrintS("image:\n");rWrite(image_r);
74  //Print("\nsusbt: v%d -> ",var);
75  //p_wrp(p,image_r,image_r);
76 non_trivial:
77  var=0;
78  p=NULL;
79 }
80 
81 // polynomial map for ideals/module/matrix
82 // map_id: the ideal to map
83 // preimage_r: the base ring for map_id
84 // image_id: the image of the variables
85 // image_r: the base ring for image_id
86 // nMap: map for coefficients
87 ideal maMapIdeal(const ideal map_id, const ring preimage_r,const ideal image_id, const ring image_r, const nMapFunc nMap)
88 {
89  if(!rIsPluralRing(image_r))
90  {
91  // heuristic:
92  // is the map a permutation ?
93  matrix m=ma_ApplyPermForMap((matrix)map_id,preimage_r,image_id,image_r,nMap);
94  if (m!=NULL)
95  {
96  if (TEST_OPT_PROT) PrintS("map is a permutation\n");
97  return (ideal)m;
98  }
99  // ----------------------------------------------------------
100  // is it a substitution of one variable ?
101  {
102  poly p;
103  int var;
104  find_subst_for_map(preimage_r,image_r,image_id,var,p);
105  if (var!=0)
106  {
107  return id_SubstPoly(map_id,var,p,preimage_r,image_r,nMap);
108  }
109  }
110  // ----------------------------------------------------------
111  // long polys in the image ?: possiblity of many common subexpressions
112  if ((nMap==ndCopyMap) /* and !rIsPluralRing(image_r) */
113  && (map_id->nrows==1) /* i.e. only for ideal/map */
114  && (map_id->rank==1))
115  {
116  int sz=IDELEMS(map_id);
117  int sz_l=0;
118  int sz_more=0;
119  int t,i;
120  for(i=sz-1;i>=0;i--)
121  {
122  sz_l+=pLength(map_id->m[i]);
123  }
124  for(i=IDELEMS(image_id)-1;i>=0;i--)
125  {
126  t=pLength(image_id->m[i]);
127  if ((t==0) || (t>1)) sz_more++;
128  }
129  if (((sz_l > sz*2) && (sz_more != 1))||(sz<5))
130  {
131  if (TEST_OPT_PROT) PrintS("map via common subexpressions\n");
132  return fast_map_common_subexp(map_id, preimage_r, image_id, image_r);
133  }
134  }
135  }
136  // ----------------------------------------------------------
137  // otherwise: try the generic method (generic map with cache)
138  if (TEST_OPT_PROT) PrintS("map with cache\n");
139  int C=((matrix)map_id)->cols();
140  int R=((matrix)map_id)->rows();
141  matrix m=mpNew(R,C);
142  int N = preimage_r->N;
143  matrix cache=mpNew(N,maMaxDeg_Ma(map_id,preimage_r));
144  int i;
145  for (i=R*C-1;i>=0;i--)
146  {
147  if (map_id->m[i]!=NULL)
148  {
149  m->m[i]=maEval((map)image_id, map_id->m[i], preimage_r, nMap, (ideal)cache, image_r);
150  p_Test(m->m[i],image_r);
151  }
152  }
153  idDelete((ideal *)&cache);
154  ideal ii=(ideal)m;
155  ii->rank=((ideal)map_id)->rank;
156  return (ideal)m;
157 }
158 
159 poly maMapPoly(const poly map_p, const ring map_r,const ideal image_id, const ring image_r, const nMapFunc nMap)
160 {
161  matrix s=mpNew(map_r->N,maMaxDeg_P(map_p, map_r));
162  poly p=maEval((map)image_id, map_p, map_r, nMap, (ideal)s, image_r);
163  id_Delete((ideal*)&s,image_r);
164  return p;
165 }
166 
167 number maEvalAt(const poly p,const number* pt, const ring r)
168 {
169  ideal map=idInit(r->N,1);
170  for(int i=r->N-1;i>=0;i--)
171  {
172  map->m[i]=p_NSet(n_Copy(pt[i],r->cf),r);
173  }
174  poly v=maMapPoly(p,r,map,r,ndCopyMap);
175  id_Delete(&map,r);
176  number vv=pGetCoeff(v);
177  p_LmFree(&v,r);
178  return vv;
179 }
static int si_min(const int a, const int b)
Definition: auxiliary.h:141
const CanonicalForm CFMap CFMap & N
Definition: cfEzgcd.cc:49
int m
Definition: cfEzgcd.cc:121
int i
Definition: cfEzgcd.cc:125
int p
Definition: cfModGcd.cc:4019
CanonicalForm map(const CanonicalForm &primElem, const Variable &alpha, const CanonicalForm &F, const Variable &beta)
map from to such that is mapped onto
Definition: cf_map_ext.cc:400
int nrows
Definition: matpol.h:20
long rank
Definition: matpol.h:19
poly * m
Definition: matpol.h:18
static FORCE_INLINE number n_Copy(number n, const coeffs r)
return a copy of 'n'
Definition: coeffs.h:451
number(* nMapFunc)(number a, const coeffs src, const coeffs dst)
maps "a", which lives in src, into dst
Definition: coeffs.h:73
static FORCE_INLINE BOOLEAN n_IsOne(number n, const coeffs r)
TRUE iff 'n' represents the one element.
Definition: coeffs.h:468
const CanonicalForm int s
Definition: facAbsFact.cc:55
const Variable & v
< [in] a sqrfree bivariate poly
Definition: facBivar.h:37
ideal fast_map_common_subexp(const ideal map_id, const ring map_r, const ideal image_id, const ring image_r)
Definition: fast_maps.cc:353
matrix ma_ApplyPermForMap(const matrix to_map, const ring preimage_r, const ideal image, const ring image_r, const nMapFunc nMap)
helper function for maMapIdeal mapping ideal/matrix/module for the case of a permutation: maps the id...
Definition: find_perm.cc:69
ideal maMapIdeal(const ideal map_id, const ring preimage_r, const ideal image_id, const ring image_r, const nMapFunc nMap)
polynomial map for ideals/module/matrix map_id: the ideal to map map_r: the base ring for map_id imag...
Definition: gen_maps.cc:87
static void find_subst_for_map(const ring preimage_r, const ring image_r, const ideal image, int &var, poly &p)
Definition: gen_maps.cc:16
poly maMapPoly(const poly map_p, const ring map_r, const ideal image_id, const ring image_r, const nMapFunc nMap)
polynomial map for poly (vector) map_p: the poly (vector) to map map_r: the base ring for map_p image...
Definition: gen_maps.cc:159
number maEvalAt(const poly p, const number *pt, const ring r)
evaluate the polynomial p at the pt given by the array pt
Definition: gen_maps.cc:167
ideal id_SubstPoly(ideal id, int var, poly image, const ring preimage_r, const ring image_r, const nMapFunc nMap)
Definition: subst_maps.cc:68
#define idDelete(H)
delete an ideal
Definition: ideals.h:29
poly maEval(map theMap, poly p, ring preimage_r, nMapFunc nMap, ideal s, const ring dst_r)
Definition: maps.cc:115
int maMaxDeg_P(poly p, ring preimage_r)
Definition: maps.cc:367
int maMaxDeg_Ma(ideal a, ring preimage_r)
Definition: maps.cc:329
matrix mpNew(int r, int c)
create a r x c zero-matrix
Definition: matpol.cc:37
ip_smatrix * matrix
Definition: matpol.h:43
#define pNext(p)
Definition: monomials.h:36
static number & pGetCoeff(poly p)
return an alias to the leading coefficient of p assumes that p != NULL NOTE: not copy
Definition: monomials.h:44
number ndCopyMap(number a, const coeffs aRing, const coeffs r)
Definition: numbers.cc:251
#define NULL
Definition: omList.c:12
#define TEST_OPT_PROT
Definition: options.h:101
int p_IsUnivariate(poly p, const ring r)
return i, if poly depends only on var(i)
Definition: p_polys.cc:1237
poly p_NSet(number n, const ring r)
returns the poly representing the number n, destroys n
Definition: p_polys.cc:1455
static long p_GetExp(const poly p, const unsigned long iBitmask, const int VarOffset)
get a single variable exponent @Note: the integer VarOffset encodes:
Definition: p_polys.h:468
static unsigned pLength(poly a)
Definition: p_polys.h:191
static void p_LmFree(poly p, ring)
Definition: p_polys.h:682
#define p_Test(p, r)
Definition: p_polys.h:162
void PrintS(const char *s)
Definition: reporter.cc:284
static BOOLEAN rIsPluralRing(const ring r)
we must always have this test!
Definition: ring.h:397
ideal idInit(int idsize, int rank)
initialise an ideal / module
Definition: simpleideals.cc:35
void id_Delete(ideal *h, ring r)
deletes an ideal/module/matrix
#define IDELEMS(i)
Definition: simpleideals.h:23
#define R
Definition: sirandom.c:27