Loading...
Searching...
No Matches
gen_maps.cc
Go to the documentation of this file.
/****************************************
* Computer Algebra System SINGULAR *
****************************************/
#include "kernel/mod2.h"
#include "misc/options.h"
#include "polys/monomials/p_polys.h"
#include "polys/prCopy.h"
#include "kernel/ideals.h"
#include "polys/monomials/ring.h"
#include "polys/monomials/maps.h"
#include "polys/sbuckets.h"
#include "kernel/maps/fast_maps.h"
#include "kernel/maps/find_perm.h"
#include "kernel/maps/gen_maps.h"
static void find_subst_for_map(const ring preimage_r, const ring image_r, const ideal image, int &var,poly &p)
{
p=NULL;
var=0;
int i,v;
for (i=si_min(IDELEMS(image),preimage_r->N)-1; i>=0; i--)
{
if (image->m[i]!=NULL)
{
if ((pNext(image->m[i])==NULL)
&& (n_IsOne(pGetCoeff(image->m[i]),image_r->cf)))
{
v=p_IsUnivariate(image->m[i],image_r);
if ((v<=0) /*not univariate */
|| (v!=i+1) /* non-trivial */
|| (p_GetExp(image->m[i],v,image_r)!=1))
{
if (var==0)
{
var=i+1;
p=image->m[i];
}
else /* found second non-trivial entry */
{
goto non_trivial;
}
}
}
else
{
if (var==0)
{
var=i+1;
p=image->m[i];
}
else /* found second non-trivial entry */
{
goto non_trivial;
}
}
}
else
{
if (var==0)
{
var=i+1;
p=image->m[i];
}
else /* found second non-trivial entry */
{
goto non_trivial;
}
}
}
return;
//Print("elms:%d, N:%d\n",IDELEMS(image),preimage_r->N);
//iiWriteMatrix((matrix)image,"_",1,image_r,0);
//PrintS("\npreimage:\n");rWrite(preimage_r);
//PrintS("image:\n");rWrite(image_r);
//Print("\nsusbt: v%d -> ",var);
//p_wrp(p,image_r,image_r);
non_trivial:
var=0;
p=NULL;
}
// polynomial map for ideals/module/matrix
// map_id: the ideal to map
// preimage_r: the base ring for map_id
// image_id: the image of the variables
// image_r: the base ring for image_id
// nMap: map for coefficients
ideal maMapIdeal(const ideal map_id, const ring preimage_r,const ideal image_id, const ring image_r, const nMapFunc nMap)
{
// handle special cases
if (IDELEMS(map_id)<=0)
return idInit(0,map_id->rank);
if(!rIsNCRing(image_r))
{
// heuristic:
// is the map a permutation ?
matrix m=ma_ApplyPermForMap((matrix)map_id,preimage_r,image_id,image_r,nMap);
if (m!=NULL)
{
if (TEST_OPT_PROT) PrintS("map is a permutation\n");
return (ideal)m;
}
// ----------------------------------------------------------
// is it a substitution of one variable ?
{
poly p;
int var;
find_subst_for_map(preimage_r,image_r,image_id,var,p);
if (var!=0)
{
if (TEST_OPT_PROT) PrintS("map is a substitution\n");
return id_SubstPoly(map_id,var,p,preimage_r,image_r,nMap);
}
}
// ----------------------------------------------------------
// long polys in the image ?: possibility of many common subexpressions
if ((nMap==ndCopyMap) /* and !rIsPluralRing(image_r) */
&& (map_id->nrows==1) /* i.e. only for ideal/map */
&& (map_id->rank==1))
{
int sz=IDELEMS(image_id);
int sz_l=0;
int i;
int sz_source=0;
for(i=IDELEMS(map_id)-1;i>=0;i--)
{
sz_source+=pLength(map_id->m[i]);
}
for(i=IDELEMS(image_id)-1;i>=0;i--)
{
sz_l+=pLength(image_id->m[i]);
}
// few, but complex terms: sz_l/sz large, or few variables,
// or sz_source small
//printf("avg term len map:%d,N=%d, avg.image len:%d, im.len:%d\n",sz_l/sz,sz,sz_source/IDELEMS(image_id),sz_source);
if ((sz_l > sz*5)||(sz<5)||(sz_source<100))
{
if (TEST_OPT_PROT) PrintS("map via common subexpressions\n");
return fast_map_common_subexp(map_id, preimage_r, image_id, image_r);
}
}
}
// ----------------------------------------------------------
// otherwise: try the generic method (generic map with cache)
if (TEST_OPT_PROT) PrintS("map with cache\n");
int C=((matrix)map_id)->cols();
int R=((matrix)map_id)->rows();
matrix m=mpNew(R,C);
int N = preimage_r->N;
matrix cache=mpNew(N,maMaxDeg_Ma(map_id,preimage_r));
int i;
for (i=R*C-1;i>=0;i--)
{
if (map_id->m[i]!=NULL)
{
m->m[i]=maEval((map)image_id, map_id->m[i], preimage_r, nMap, (ideal)cache, image_r);
p_Test(m->m[i],image_r);
}
}
idDelete((ideal *)&cache);
ideal ii=(ideal)m;
ii->rank=((ideal)map_id)->rank;
return (ideal)m;
}
poly maMapPoly(const poly map_p, const ring map_r,const ideal image_id, const ring image_r, const nMapFunc nMap)
{
matrix s=mpNew(map_r->N,maMaxDeg_P(map_p, map_r));
poly p=maEval((map)image_id, map_p, map_r, nMap, (ideal)s, image_r);
id_Delete((ideal*)&s,image_r);
return p;
}
number maEvalAt(const poly p,const number* pt, const ring r)
{
ideal map=idInit(r->N,1);
for(int i=r->N-1;i>=0;i--)
{
map->m[i]=p_NSet(n_Copy(pt[i],r->cf),r);
}
poly v=maMapPoly(p,r,map,r,ndCopyMap);
id_Delete(&map,r);
number vv;
if (v==NULL)
vv=n_Init(0,r->cf);
else
{
vv=pGetCoeff(v);
p_LmFree(&v,r);
}
return vv;
}
si_min
static int si_min(const int a, const int b)
Definition auxiliary.h:126
N
const CanonicalForm CFMap CFMap & N
Definition cfEzgcd.cc:56
m
int m
Definition cfEzgcd.cc:128
i
int i
Definition cfEzgcd.cc:132
p
int p
Definition cfModGcd.cc:4086
map
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:505
ip_smatrix::nrows
int nrows
Definition matpol.h:20
ip_smatrix::rank
long rank
Definition matpol.h:19
ip_smatrix::m
poly * m
Definition matpol.h:18
n_Copy
static FORCE_INLINE number n_Copy(number n, const coeffs r)
return a copy of 'n'
Definition coeffs.h:457
ndCopyMap
number ndCopyMap(number a, const coeffs src, const coeffs dst)
Definition numbers.cc:293
n_Init
static FORCE_INLINE number n_Init(long i, const coeffs r)
a number representing i in the given coeff field/ring r
Definition coeffs.h:541
nMapFunc
number(* nMapFunc)(number a, const coeffs src, const coeffs dst)
maps "a", which lives in src, into dst
Definition coeffs.h:80
n_IsOne
static FORCE_INLINE BOOLEAN n_IsOne(number n, const coeffs r)
TRUE iff 'n' represents the one element.
Definition coeffs.h:474
s
const CanonicalForm int s
Definition facAbsFact.cc:51
v
const Variable & v
< [in] a sqrfree bivariate poly
Definition facBivar.h:39
fast_map_common_subexp
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:354
fast_maps.h
ma_ApplyPermForMap
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
find_perm.h
maMapIdeal
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:88
find_subst_for_map
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
maMapPoly
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:166
maEvalAt
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:174
gen_maps.h
id_SubstPoly
ideal id_SubstPoly(ideal id, int var, poly image, const ring preimage_r, const ring image_r, const nMapFunc nMap)
Definition subst_maps.cc:78
ideals.h
idDelete
#define idDelete(H)
delete an ideal
Definition ideals.h:29
maEval
poly maEval(map theMap, poly p, ring preimage_r, nMapFunc nMap, ideal s, const ring dst_r)
Definition maps.cc:117
maMaxDeg_P
int maMaxDeg_P(poly p, ring preimage_r)
Definition maps.cc:390
maMaxDeg_Ma
int maMaxDeg_Ma(ideal a, ring preimage_r)
Definition maps.cc:352
maps.h
mpNew
matrix mpNew(int r, int c)
create a r x c zero-matrix
Definition matpol.cc:37
matrix
ip_smatrix * matrix
Definition matpol.h:43
mod2.h
pNext
#define pNext(p)
Definition monomials.h:36
pGetCoeff
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
NULL
#define NULL
Definition omList.c:12
options.h
TEST_OPT_PROT
#define TEST_OPT_PROT
Definition options.h:105
p_IsUnivariate
int p_IsUnivariate(poly p, const ring r)
return i, if poly depends only on var(i)
Definition p_polys.cc:1248
p_NSet
poly p_NSet(number n, const ring r)
returns the poly representing the number n, destroys n
Definition p_polys.cc:1474
p_polys.h
pLength
static int pLength(poly a)
Definition p_polys.h:190
p_GetExp
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:471
p_LmFree
static void p_LmFree(poly p, ring)
Definition p_polys.h:685
p_Test
#define p_Test(p, r)
Definition p_polys.h:161
prCopy.h
PrintS
void PrintS(const char *s)
Definition reporter.cc:288
ring.h
rIsNCRing
static BOOLEAN rIsNCRing(const ring r)
Definition ring.h:427
sbuckets.h
idInit
ideal idInit(int idsize, int rank)
initialise an ideal / module
Definition simpleideals.cc:35
id_Delete
void id_Delete(ideal *h, ring r)
deletes an ideal/module/matrix
Definition simpleideals.cc:123
IDELEMS
#define IDELEMS(i)
Definition simpleideals.h:23
R
#define R
Definition sirandom.c:27