7 #include "factory/factory.h"
27 #define unsortedmatrix
30 #define modp_number int
39 return (
modp_number)(((
unsigned long)
x)*((
unsigned long)
y)%((
unsigned long)
myp));
139 static int maximal_size=0;
150 void WriteMonoList (mon_list_entry *list)
164 row_list_entry *curptr;
168 cout << endl <<
"quotient basis: ";
170 cout << endl <<
"leading terms: ";
172 cout << endl <<
"to be checked: ";
175 cout << endl <<
"Matrix:" << endl;
185 row=curptr->row_matrix;
186 solve=curptr->row_solve;
189 cout << *row <<
" , ";
195 cout << *
solve <<
" , ";
200 cout <<
"Special row: Solve row:" << endl;
204 cout << *row <<
" , ";
211 cout << *row <<
" , ";
217 cout << endl << endl;
223 long u,
v, u0, u1, u2, q, r;
238 if ((u1<0)||((u1*a)%
p!=1))
244 if ((a*
i)%
p==1)
return i;
273 if (m1[
i]!=m2[
i])
return false;;
300 mon_list_entry *curptr=list;
301 mon_list_entry *prevptr=
NULL;
302 mon_list_entry *temp;
306 if (
EqualMon (mon,(*curptr).mon))
return list;
307 if (
Greater ((*curptr).mon,mon))
break;
311 temp=(mon_list_entry*)
omAlloc0(
sizeof(mon_list_entry));
315 if (prevptr==
NULL)
return temp;
325 mon_list_entry *cur=list;
327 for (
i=0;
i<n;
i++) cur=cur->next;
416 for (pos_gen=2;pos_gen<
myp;pos_gen++)
421 gen_table[
i]=
modp_mul(gen_table[
i-1],pos_gen);
438 mon_list_entry *pptr;
504 row_list_entry *pptr;
567 mpz_set_si(mon_conv,mn[
k]);
568 mpz_mul(ev,ev,mon_conv);
631 mpz_set_si(big_myp,
myp);
698 row_list_entry *row_ptr;
707 #ifdef integerstrategy
712 while (row_ptr!=
NULL)
714 cur_row_ptr=row_ptr->row_matrix;
715 solve_row_ptr=row_ptr->row_solve;
718 first_col=row_ptr->first_col;
719 cur_row_ptr=cur_row_ptr+first_col;
720 my_row_ptr=my_row_ptr+first_col;
724 #ifdef integerstrategy
725 prep_val=*cur_row_ptr;
731 if (*m_row_ptr!=0) *m_row_ptr=
modp_mul(*m_row_ptr,prep_val);
737 if (*m_row_ptr!=0) *m_row_ptr=
modp_mul(*m_row_ptr,prep_val);
746 mul_val=
modp_mul(*cur_row_ptr,red_val);
747 *my_row_ptr=
modp_sub(*my_row_ptr,mul_val);
754 if (*solve_row_ptr!=0)
756 mul_val=
modp_mul(*solve_row_ptr,red_val);
757 *my_solve_row_ptr=
modp_sub(*my_solve_row_ptr,mul_val);
763 row_ptr=row_ptr->next;
765 PrintS(
"reduction by row ");
779 if (*row!=0) {zero=0;
break;}
789 if (m1[
i]>m2[
i])
return false;;
795 mon_list_entry *c_ptr;
796 mon_list_entry *p_ptr;
797 mon_list_entry *n_ptr;
807 p_ptr->next=c_ptr->next;
823 mon_list_entry *n_check_list;
859 row_list_entry *pptr;
860 row_list_entry *temp;
865 #ifndef unsortedmatrix
866 if ( first_col <= ptr->first_col )
break;
871 temp=(row_list_entry*)
omAlloc0(
sizeof(row_list_entry));
876 (*temp).first_col=first_col;
890 #ifdef integerstrategy
922 if (*row!=0) *row=
modp_mul(*row,red_val);
928 if (*row!=0) *row=
modp_mul(*row,red_val);
938 modp_result_entry *temp;
939 temp=(modp_result_entry*)
omAlloc0(
sizeof(modp_result_entry));
960 generator_entry *cur_gen;
961 generator_entry *next_gen;
962 cur_gen=e->generator;
963 while (cur_gen!=
NULL)
965 next_gen=cur_gen->next;
977 generator_entry *cur_ptr;
978 generator_entry *prev_ptr;
979 generator_entry *temp;
982 while (cur_ptr!=
NULL)
985 cur_ptr=cur_ptr->next;
987 temp=(generator_entry*)
omAlloc0(
sizeof(generator_entry));
989 else prev_ptr->next=temp;
1001 #ifndef integerstrategy
1003 generator_entry *cur_ptr;
1005 while (cur_ptr!=
NULL)
1010 cur_ptr=cur_ptr->next;
1015 void PresentGenerator (
int i)
1018 modp_result_entry *cur_ptr;
1019 generator_entry *cur_gen;
1021 while (cur_ptr!=
NULL)
1023 cur_gen=cur_ptr->generator;
1024 for (
j=0;
j<
i;
j++) cur_gen=cur_gen->next;
1027 Print(
"%d;", cur_gen->coef[
j]);
1030 WriteMono (cur_gen->lt);
1031 Print(
" ( %d ) prime = %d\n", cur_gen->ltcoef, cur_ptr->p);
1032 cur_ptr=cur_ptr->next;
1046 modp_result_entry *cur_ptr;
1053 while (cur_ptr!=
NULL)
1055 *congr_ptr=cur_ptr->p;
1056 cur_ptr=cur_ptr->next;
1079 bool first_gcd=
true;
1105 str=(
char*)
omAlloc0(
sizeof(
char)*1000);
1106 modp_result_entry *cur_ptr;
1107 generator_entry *cur_gen;
1121 while (cur_ptr!=
NULL)
1123 cur_gen=cur_ptr->generator;
1124 for (
j=0;
j<ngen;
j++) cur_gen=cur_gen->next;
1126 cur_ptr=cur_ptr->next;
1135 if (temp<0) temp=temp+
congr[
k];
1138 mpz_set_si(sol,
v[n-1]);
1139 for (
k=n-2;
k>=0;
k--)
1141 mpz_mul_ui(sol,sol,
congr[
k]);
1142 mpz_add_ui(sol,sol,
v[
k]);
1145 int s=mpz_cmpabs(sol,nsol);
1146 if (
s>0) mpz_set(sol,nsol);
1153 size=mpz_sizeinbase(sol,10);
1154 if (
size>maximal_size) maximal_size=
size;
1167 modp_result_entry *temp;
1186 PrintS(
"-discarding ALL.\n");
1189 modp_result_entry *ntfree;
1190 generator_entry *cur_gen;
1209 cur_gen=cur_gen->next;
1227 PrintS(
"wrong number of generators occurred");
1237 PrintS(
"denom of coef divisible by p");
1244 generator_entry *cur_gen;
1245 mon_list_entry *cur_mon;
1250 if (!
EqualMon(cur_mon->mon,cur_gen->lt))
1253 PrintS(
"wrong leading term occurred");
1260 cur_gen=cur_gen->next;
1261 cur_mon=cur_mon->next;
1268 PrintS(
"wrong seq of cols occurred");
1279 void WriteGenerator ()
1282 str=(
char*)
omAlloc0(
sizeof(
char)*1000);
1310 mpz_add(sum,sum,val);
1312 if (mpz_sgn(sum)!=0)
1326 gen_list_entry *temp;
1345 gen_list_entry *temp,*prev;
1364 temp=(gen_list_entry*)
omAlloc0(
sizeof(gen_list_entry));
1371 mpz_init(temp->polycoef[
i]);
1381 gen_list_entry *temp;
1384 str=(
char*)
omAlloc0(
sizeof(
char)*1000);
1391 str=mpz_get_str(str,10,temp->polycoef[
i]);
1394 WriteMono(temp->polyexp[
i]);
1420 cout <<
"row produced for monomial ";
1421 WriteMono (cur_mon);
1433 cout <<
"row is zero - linear dependence found (should be seen in my_solve_row)" << endl;
1434 cout <<
"monomial added to leading terms list" << endl;
1435 cout <<
"check list updated" << endl;
1445 cout <<
"row is non-zero" << endl;
1446 cout <<
"monomial added to quotient basis list" << endl;
1447 cout <<
"new monomials added to check list" << endl;
1448 cout <<
"check list reduced by monomials from leading term list" << endl;
1453 cout <<
"row prepared and put into matrix" << endl;
1466 mpq_set_si(c,m_val,1);
1472 mpz_set(mpq_numref(c),
m->z);
1473 mpz_set(mpq_denref(c),
m->n);
1474 mpq_canonicalize(c);
1492 WerrorS(
"coefficient field should be Zp or Q!");
1497 WerrorS(
"quotient ring not supported!");
1502 WerrorS(
"ordering must be global!");
1508 WerrorS(
"list and intvec must have the same length!");
1527 PrintS(
"multiplicities: ");
1539 for(
i=0;
i<L.size();
i++)
1554 Print(
"coordinate %d for point %d initialized twice!\n",pcvar+1,
i+1);
1579 PrintS(
"not a variable? ");
1598 Print(
"coordinate %d for point %d not known!\n",
j+1,
i+1);
1607 WerrorS(
"data structure is invalid");
1622 bool correct_gen=
false;
1629 Print(
"trying %d cycles mod p...\n",modp_cycles);
1665 PrintS(
"wrong generator!\n");
1678 Print(
"maximal size of output: %d, precision bound: %d.\n",maximalsize,mpz_sizeinbase(
bigcongr,10));
1681 modp_cycles=modp_cycles+10;
1691 PrintS(
"computations finished.\n");
1700 WerrorS(
"internal error - coefficient too big!");
1731 cur_gen=cur_gen->next;
1745 if (mpz_sgn(temp->polycoef[a])!=0)
1751 mpz_init_set(n->z,temp->polycoef[a]);
for(int i=0;i<=n;i++) degsf[i]
bool solve(int **extmat, int nrows, int ncols)
int cf_getNumSmallPrimes()
int cf_getSmallPrime(int i)
static FORCE_INLINE void n_Normalize(number &n, const coeffs r)
inplace-normalization of n; produces some canonical representation of n;
const CanonicalForm int s
const CanonicalForm int const CFList const Variable & y
const Variable & v
< [in] a sqrfree bivariate poly
void WerrorS(const char *s)
static void NewGenerator(mono_type mon)
static void TakeNextMonomial(mono_type mon)
static modp_number TakePrime(modp_number)
static modp_number * my_row
static poly comparizon_p2
static void ClearGenList()
static poly comparizon_p1
static modp_result_entry * modp_result
static modp_number modp_sub(modp_number x, modp_number y)
static void ReduceCheckListByMon(mono_type m)
static modp_number * modp_Reverse
static modp_number * my_solve_row
static void modp_Evaluate(modp_number *ev, mono_type mon, condition_type con)
static mono_type * generic_column_name
static mon_list_entry * base_list
static mon_list_entry * check_list
static mono_type ZeroMonomial()
static void UpdateGenList()
static mon_list_entry * lt_list
static mono_type MonListElement(mon_list_entry *list, int n)
static void FreeProcData()
static void ResolveCoeff(mpq_t c, number m)
static int final_base_dim
static modp_number modp_mul(modp_number x, modp_number y)
ideal interpolation(const std::vector< ideal > &L, intvec *v)
static coord_exist_table * coord_exist
static void IntegerPoints()
static bool EqualMon(mono_type m1, mono_type m2)
static int last_solve_column
struct modp_result_struct * prev
static void MakeConditions()
static void CloseChinese()
static void int_Evaluate(mpz_t ev, mono_type mon, condition_type con)
struct modp_result_struct * next
coordinate_products * coordinates
static void NewResultEntry()
static void PrepareChinese(int n)
static modp_coordinates * modp_points
static void ReduceCheckListByLTs()
static mon_list_entry * MonListAdd(mon_list_entry *list, mono_type mon)
static modp_number OneInverse(modp_number a, modp_number p)
static void ReconstructGenerator(int ngen, int n)
static int * multiplicity
static coordinates * points
static void modp_PrepareProducts()
static void PrepareRow(mono_type mon)
static bool CheckGenerator()
static mpz_t common_denom
static exponent MonDegree(mono_type mon)
static void InitProcData()
static modp_number * in_gamma
static mon_list_entry * FreeMonList(mon_list_entry *list)
static bool denom_divisible
static mono_type * polyexp
struct mon_list_entry_struct * next
static void ProduceRow(mono_type mon)
struct row_list_entry_struct * next
static void MultGenerators()
struct generator_struct * next
static void UpdateCheckList(mono_type m)
static void GeneralInit()
modp_number * modp_coordinates
static modp_result_entry * cur_result
static gen_list_entry * gen_list
static row_list_entry * row_list
static modp_number * congr
static int_coordinates * int_points
static void FreeResultEntry(modp_result_entry *e)
static void int_PrepareProducts()
static int generic_n_generators
struct gen_list_struct * next
static modp_number modp_denom
static void GeneralDone()
static void CheckColumnSequence()
static bool DivisibleMon(mono_type m1, mono_type m2)
generator_entry * generator
static void RowListAdd(int first_col, mono_type mon)
static mon_list_entry * generic_lt
static mono_type * column_name
modp_number * coordinate_products
static void modp_SetColumnNames()
static condition_type * condition_list
static bool Greater(mono_type m1, mono_type m2)
static q_coordinates * q_points
static number & pGetCoeff(poly p)
return an alias to the leading coefficient of p assumes that p != NULL NOTE: not copy
void * malloc(size_t size)
ring currRing
Widely used global variable which specifies the current polynomial ring for Singular interpreter and ...
Compatiblity layer for legacy polynomial operations (over currRing)
#define pHead(p)
returns newly allocated copy of Lm(p), coef is copied, next=NULL, p might be NULL
#define pLmCmp(p, q)
returns 0|1|-1 if p=q|p>q|p<q w.r.t monomial ordering
void PrintS(const char *s)
static BOOLEAN rField_is_Zp(const ring r)
static BOOLEAN rField_is_Q(const ring r)
ideal idInit(int idsize, int rank)
initialise an ideal / module