1 | /**************************************** |
---|
2 | * Computer Algebra System SINGULAR * |
---|
3 | ****************************************/ |
---|
4 | #include "kernel/mod2.h" |
---|
5 | #include "misc/options.h" |
---|
6 | #include "polys/monomials/p_polys.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(!rIsNCRing(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; |
---|
177 | if (v==NULL) |
---|
178 | vv=n_Init(0,r->cf); |
---|
179 | else |
---|
180 | { |
---|
181 | vv=pGetCoeff(v); |
---|
182 | p_LmFree(&v,r); |
---|
183 | } |
---|
184 | return vv; |
---|
185 | } |
---|