My Project
Loading...
Searching...
No Matches
kspoly.cc File Reference
#include "kernel/mod2.h"
#include "misc/options.h"
#include "kernel/GBEngine/kutil.h"
#include "coeffs/numbers.h"
#include "polys/monomials/p_polys.h"
#include "polys/templates/p_Procs.h"
#include "polys/nc/nc.h"
#include "kernel/polys.h"
#include "polys/shiftop.h"

Go to the source code of this file.

Macros

#define TEST_OPT_DEBUG_RED
 

Functions

int ksReducePoly (LObject *PR, TObject *PW, poly spNoether, number *coef, poly *mon, kStrategy strat, BOOLEAN reduce)
 
int ksReducePolyLC (LObject *PR, TObject *PW, poly spNoether, number *coef, kStrategy strat)
 
int ksReducePolyBound (LObject *PR, TObject *PW, int, poly spNoether, number *coef, kStrategy strat)
 
int ksReducePolySig (LObject *PR, TObject *PW, long, poly spNoether, number *coef, kStrategy strat)
 
int ksReducePolySigRing (LObject *PR, TObject *PW, long, poly spNoether, number *coef, kStrategy strat)
 
void ksCreateSpoly (LObject *Pair, poly spNoether, int use_buckets, ring tailRing, poly m1, poly m2, TObject **R)
 
int ksReducePolyTail (LObject *PR, TObject *PW, poly Current, poly spNoether)
 
int ksReducePolyTailBound (LObject *PR, TObject *PW, int bound, poly Current, poly spNoether)
 
poly ksCreateShortSpoly (poly p1, poly p2, ring tailRing)
 

Variables

VAR int red_count = 0
 
VAR int create_count = 0
 

Macro Definition Documentation

◆ TEST_OPT_DEBUG_RED

#define TEST_OPT_DEBUG_RED

Definition at line 28 of file kspoly.cc.

Function Documentation

◆ ksCreateShortSpoly()

poly ksCreateShortSpoly ( poly p1,
poly p2,
ring tailRing )

Definition at line 1446 of file kspoly.cc.

1447{
1448 poly a1 = pNext(p1), a2 = pNext(p2);
1449#ifdef HAVE_SHIFTBBA
1450 int shift1, shift2;
1451 if (tailRing->isLPring)
1452 {
1453 // assume: LM is shifted, tail unshifted
1454 assume(p_FirstVblock(a1, tailRing) <= 1);
1455 assume(p_FirstVblock(a2, tailRing) <= 1);
1456 // save the shift of the LM so we can shift the other monomials on demand
1457 shift1 = p_mFirstVblock(p1, tailRing) - 1;
1458 shift2 = p_mFirstVblock(p2, tailRing) - 1;
1459 }
1460#endif
1461 long c1=p_GetComp(p1, currRing),c2=p_GetComp(p2, currRing);
1462 long c;
1463 poly m1,m2;
1464 number t1 = NULL,t2 = NULL;
1465 int cm,i;
1466 BOOLEAN equal;
1467
1469 number lc1 = pGetCoeff(p1), lc2 = pGetCoeff(p2);
1470 if (is_Ring)
1471 {
1472 ksCheckCoeff(&lc1, &lc2, currRing->cf); // gcd and zero divisors
1473 if (a1 != NULL) t2 = nMult(pGetCoeff(a1),lc2);
1474 if (a2 != NULL) t1 = nMult(pGetCoeff(a2),lc1);
1475 while (a1 != NULL && nIsZero(t2))
1476 {
1477 pIter(a1);
1478 nDelete(&t2);
1479 if (a1 != NULL) t2 = nMult(pGetCoeff(a1),lc2);
1480 }
1481 while (a2 != NULL && nIsZero(t1))
1482 {
1483 pIter(a2);
1484 nDelete(&t1);
1485 if (a2 != NULL) t1 = nMult(pGetCoeff(a2),lc1);
1486 }
1487 }
1488
1489#ifdef HAVE_SHIFTBBA
1490 // shift the next monomial on demand
1491 if (tailRing->isLPring)
1492 {
1493 a1 = p_LPCopyAndShiftLM(a1, shift1, tailRing);
1494 a2 = p_LPCopyAndShiftLM(a2, shift2, tailRing);
1495 }
1496#endif
1497 if (a1==NULL)
1498 {
1499 if(a2!=NULL)
1500 {
1501 m2=p_Init(currRing);
1502x2:
1503 for (i = (currRing->N); i; i--)
1504 {
1505 c = p_GetExpDiff(p1, p2,i, currRing);
1506 if (c>0)
1507 {
1508 p_SetExp(m2,i,(c+p_GetExp(a2,i,tailRing)),currRing);
1509 }
1510 else
1511 {
1512 p_SetExp(m2,i,p_GetExp(a2,i,tailRing),currRing);
1513 }
1514 }
1515 if ((c1==c2)||(c2!=0))
1516 {
1517 p_SetComp(m2,p_GetComp(a2,tailRing), currRing);
1518 }
1519 else
1520 {
1521 p_SetComp(m2,c1,currRing);
1522 }
1523 p_Setm(m2, currRing);
1524 if (is_Ring)
1525 {
1526 nDelete(&lc1);
1527 nDelete(&lc2);
1528 nDelete(&t2);
1529 pSetCoeff0(m2, t1);
1530 }
1531#ifdef HAVE_SHIFTBBA
1532 if (tailRing->isLPring && (shift2!=0)) /*a1==NULL*/
1533 {
1534 p_LmDelete(a2, tailRing);
1535 }
1536#endif
1537 return m2;
1538 }
1539 else
1540 {
1541 if (is_Ring)
1542 {
1543 nDelete(&lc1);
1544 nDelete(&lc2);
1545 nDelete(&t1);
1546 nDelete(&t2);
1547 }
1548 return NULL;
1549 }
1550 }
1551 if (a2==NULL)
1552 {
1553 m1=p_Init(currRing);
1554x1:
1555 for (i = (currRing->N); i; i--)
1556 {
1557 c = p_GetExpDiff(p2, p1,i,currRing);
1558 if (c>0)
1559 {
1560 p_SetExp(m1,i,(c+p_GetExp(a1,i, tailRing)),currRing);
1561 }
1562 else
1563 {
1564 p_SetExp(m1,i,p_GetExp(a1,i, tailRing), currRing);
1565 }
1566 }
1567 if ((c1==c2)||(c1!=0))
1568 {
1569 p_SetComp(m1,p_GetComp(a1,tailRing),currRing);
1570 }
1571 else
1572 {
1573 p_SetComp(m1,c2,currRing);
1574 }
1575 p_Setm(m1, currRing);
1576 if (is_Ring)
1577 {
1578 pSetCoeff0(m1, t2);
1579 nDelete(&lc1);
1580 nDelete(&lc2);
1581 nDelete(&t1);
1582 }
1583#ifdef HAVE_SHIFTBBA
1584 if (tailRing->isLPring && (shift1!=0)) /*a2==NULL*/
1585 {
1586 p_LmDelete(a1, tailRing);
1587 }
1588#endif
1589 return m1;
1590 }
1591 m1 = p_Init(currRing);
1592 m2 = p_Init(currRing);
1593 loop
1594 {
1595 for (i = (currRing->N); i; i--)
1596 {
1597 c = p_GetExpDiff(p1, p2,i,currRing);
1598 if (c > 0)
1599 {
1600 p_SetExp(m2,i,(c+p_GetExp(a2,i,tailRing)), currRing);
1601 p_SetExp(m1,i,p_GetExp(a1,i, tailRing), currRing);
1602 }
1603 else
1604 {
1605 p_SetExp(m1,i,(p_GetExp(a1,i,tailRing)-c), currRing);
1606 p_SetExp(m2,i,p_GetExp(a2,i, tailRing), currRing);
1607 }
1608 }
1609 if(c1==c2)
1610 {
1611 p_SetComp(m1,p_GetComp(a1, tailRing), currRing);
1612 p_SetComp(m2,p_GetComp(a2, tailRing), currRing);
1613 }
1614 else
1615 {
1616 if(c1!=0)
1617 {
1618 p_SetComp(m1,p_GetComp(a1, tailRing), currRing);
1619 p_SetComp(m2,c1, currRing);
1620 }
1621 else
1622 {
1623 p_SetComp(m2,p_GetComp(a2, tailRing), currRing);
1624 p_SetComp(m1,c2, currRing);
1625 }
1626 }
1627 p_Setm(m1,currRing);
1628 p_Setm(m2,currRing);
1629 cm = p_LmCmp(m1, m2,currRing);
1630 if (cm!=0)
1631 {
1632 if(cm==1)
1633 {
1634 p_LmFree(m2,currRing);
1635 if (is_Ring)
1636 {
1637 pSetCoeff0(m1, t2);
1638 nDelete(&lc1);
1639 nDelete(&lc2);
1640 nDelete(&t1);
1641 }
1642#ifdef HAVE_SHIFTBBA
1643 if (tailRing->isLPring)
1644 {
1645 if (shift1!=0) p_LmDelete(a1, tailRing);
1646 if (shift2!=0) p_LmDelete(a2, tailRing);
1647 }
1648#endif
1649 return m1;
1650 }
1651 else
1652 {
1653 p_LmFree(m1,currRing);
1654 if (is_Ring)
1655 {
1656 pSetCoeff0(m2, t1);
1657 nDelete(&lc1);
1658 nDelete(&lc2);
1659 nDelete(&t2);
1660 }
1661#ifdef HAVE_SHIFTBBA
1662 if (tailRing->isLPring)
1663 {
1664 if (shift1!=0) p_LmDelete(a1, tailRing);
1665 if (shift2!=0) p_LmDelete(a2, tailRing);
1666 }
1667#endif
1668 return m2;
1669 }
1670 }
1671 if (is_Ring)
1672 {
1673 equal = nEqual(t1,t2);
1674 }
1675 else
1676 {
1677 t1 = nMult(pGetCoeff(a2),pGetCoeff(p1));
1678 t2 = nMult(pGetCoeff(a1),pGetCoeff(p2));
1679 equal = nEqual(t1,t2);
1680 nDelete(&t2);
1681 nDelete(&t1);
1682 }
1683 if (!equal)
1684 {
1685 p_LmFree(m2,currRing);
1686 if (is_Ring)
1687 {
1688 pSetCoeff0(m1, nSub(t1, t2));
1689 nDelete(&lc1);
1690 nDelete(&lc2);
1691 nDelete(&t1);
1692 nDelete(&t2);
1693 }
1694#ifdef HAVE_SHIFTBBA
1695 if (tailRing->isLPring)
1696 {
1697 if (shift1!=0) p_LmDelete(a1, tailRing);
1698 if (shift2!=0) p_LmDelete(a2, tailRing);
1699 }
1700#endif
1701 return m1;
1702 }
1703 pIter(a1);
1704 pIter(a2);
1705 if (is_Ring)
1706 {
1707 if (a2 != NULL)
1708 {
1709 nDelete(&t1);
1710 t1 = nMult(pGetCoeff(a2),lc1);
1711 }
1712 if (a1 != NULL)
1713 {
1714 nDelete(&t2);
1715 t2 = nMult(pGetCoeff(a1),lc2);
1716 }
1717 while ((a1 != NULL) && nIsZero(t2))
1718 {
1719 pIter(a1);
1720 if (a1 != NULL)
1721 {
1722 nDelete(&t2);
1723 t2 = nMult(pGetCoeff(a1),lc2);
1724 }
1725 }
1726 while ((a2 != NULL) && nIsZero(t1))
1727 {
1728 pIter(a2);
1729 if (a2 != NULL)
1730 {
1731 nDelete(&t1);
1732 t1 = nMult(pGetCoeff(a2),lc1);
1733 }
1734 }
1735 }
1736#ifdef HAVE_SHIFTBBA
1737 if (tailRing->isLPring)
1738 {
1739 a1 = p_LPCopyAndShiftLM(a1, shift1, tailRing);
1740 a2 = p_LPCopyAndShiftLM(a2, shift2, tailRing);
1741 }
1742#endif
1743 if (a2==NULL)
1744 {
1745 p_LmFree(m2,currRing);
1746 if (a1==NULL)
1747 {
1748 if (is_Ring)
1749 {
1750 nDelete(&lc1);
1751 nDelete(&lc2);
1752 nDelete(&t1);
1753 nDelete(&t2);
1754 }
1755 p_LmFree(m1,currRing);
1756 return NULL;
1757 }
1758 goto x1;
1759 }
1760 if (a1==NULL)
1761 {
1762 p_LmFree(m1,currRing);
1763 goto x2;
1764 }
1765 }
1766}
int BOOLEAN
Definition auxiliary.h:88
int i
Definition cfEzgcd.cc:132
bool equal
Definition cfModGcd.cc:4134
int ksCheckCoeff(number *a, number *b, const coeffs r)
Definition kbuckets.cc:1504
#define assume(x)
Definition mod2.h:389
#define p_GetComp(p, r)
Definition monomials.h:64
#define pIter(p)
Definition monomials.h:37
#define pNext(p)
Definition monomials.h:36
#define pSetCoeff0(p, n)
Definition monomials.h:59
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
#define nDelete(n)
Definition numbers.h:16
#define nIsZero(n)
Definition numbers.h:19
#define nEqual(n1, n2)
Definition numbers.h:20
#define nSub(n1, n2)
Definition numbers.h:22
#define nMult(n1, n2)
Definition numbers.h:17
#define NULL
Definition omList.c:12
static long p_GetExpDiff(poly p1, poly p2, int i, ring r)
Definition p_polys.h:637
static void p_LmDelete(poly p, const ring r)
Definition p_polys.h:725
static unsigned long p_SetExp(poly p, const unsigned long e, const unsigned long iBitmask, const int VarOffset)
set a single variable exponent @Note: VarOffset encodes the position in p->exp
Definition p_polys.h:490
static unsigned long p_SetComp(poly p, unsigned long c, ring r)
Definition p_polys.h:249
static void p_Setm(poly p, const ring r)
Definition p_polys.h:235
static int p_LmCmp(poly p, poly q, const ring r)
Definition p_polys.h:1596
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
static void p_LmFree(poly p, ring)
Definition p_polys.h:685
static poly p_Init(const ring r, omBin bin)
Definition p_polys.h:1336
VAR ring currRing
Widely used global variable which specifies the current polynomial ring for Singular interpreter and ...
Definition polys.cc:13
#define rField_is_Ring(R)
Definition ring.h:491
poly p_LPCopyAndShiftLM(poly p, int sh, const ring r)
Definition shiftgb.cc:35
int p_mFirstVblock(poly p, const ring ri)
Definition shiftop.cc:478
int p_FirstVblock(poly p, const ring r)
Definition shiftop.cc:456
#define loop
Definition structs.h:71

◆ ksCreateSpoly()

void ksCreateSpoly ( LObject * Pair,
poly spNoether,
int use_buckets,
ring tailRing,
poly m1,
poly m2,
TObject ** R )

Definition at line 1203 of file kspoly.cc.

1206{
1207#ifdef KDEBUG
1208 create_count++;
1209#endif
1210 poly p1 = Pair->p1;
1211 poly p2 = Pair->p2;
1212 Pair->tailRing = tailRing;
1213
1214 assume(p1 != NULL);
1215 assume(p2 != NULL);
1216 assume(tailRing != NULL);
1217
1218 poly a1 = pNext(p1), a2 = pNext(p2);
1219 number lc1 = pGetCoeff(p1), lc2 = pGetCoeff(p2);
1220 int co=0/*, ct = ksCheckCoeff(&lc1, &lc2, currRing->cf)*/; // gcd and zero divisors
1221 (void) ksCheckCoeff(&lc1, &lc2, currRing->cf);
1222
1223 int l1=0, l2=0;
1224
1225 if (currRing->pCompIndex >= 0)
1226 {
1228 {
1229 if (__p_GetComp(p1, currRing)==0)
1230 {
1231 co=1;
1232 p_SetCompP(p1,__p_GetComp(p2, currRing), currRing, tailRing);
1233 }
1234 else
1235 {
1236 co=2;
1237 p_SetCompP(p2, __p_GetComp(p1, currRing), currRing, tailRing);
1238 }
1239 }
1240 }
1241
1242 // get m1 = LCM(LM(p1), LM(p2))/LM(p1)
1243 // m2 = LCM(LM(p1), LM(p2))/LM(p2)
1244 if (m1 == NULL)
1245 k_GetLeadTerms(p1, p2, currRing, m1, m2, tailRing);
1246
1247#ifdef HAVE_SHIFTBBA
1248 poly m12, m22;
1249 if (tailRing->isLPring)
1250 {
1251 assume(p_mFirstVblock(p1, tailRing) <= 1 || p_mFirstVblock(p2, tailRing) <= 1);
1252 k_SplitFrame(m1, m12, si_max(p_mFirstVblock(p1, tailRing), 1), tailRing);
1253 k_SplitFrame(m2, m22, si_max(p_mFirstVblock(p2, tailRing), 1), tailRing);
1254 // coeffs of m1,m2 are NULL here
1255 }
1256#endif
1257
1258 pSetCoeff0(m1, lc2);
1259 pSetCoeff0(m2, lc1); // and now, m1 * LT(p1) == m2 * LT(p2)
1260
1261 if (R != NULL)
1262 {
1263 if (Pair->i_r1 == -1)
1264 {
1265 l1 = pLength(p1) - 1;
1266 }
1267 else
1268 {
1269 l1 = (R[Pair->i_r1])->GetpLength() - 1;
1270 }
1271 if ((Pair->i_r2 == -1)||(R[Pair->i_r2]==NULL))
1272 {
1273 l2 = pLength(p2) - 1;
1274 }
1275 else
1276 {
1277 l2 = (R[Pair->i_r2])->GetpLength() - 1;
1278 }
1279 }
1280
1281 // get m2 * a2
1282#ifdef HAVE_SHIFTBBA
1283 if (tailRing->isLPring)
1284 {
1285 // m2*a2*m22
1286 poly tmp= tailRing->p_Procs->pp_mm_Mult(a2, m2, tailRing);
1287 a2 = tailRing->p_Procs->pp_Mult_mm(tmp, m22, tailRing);
1288 p_Delete(&tmp,tailRing);
1289 }
1290 else
1291#endif
1292 if (spNoether != NULL)
1293 {
1294 l2 = -1;
1295 a2 = tailRing->p_Procs->pp_Mult_mm_Noether(a2, m2, spNoether, l2, tailRing);
1296 assume(l2 == (int)pLength(a2));
1297 }
1298 else
1299 {
1300 a2 = tailRing->p_Procs->pp_Mult_mm(a2, m2, tailRing);
1301 }
1302 if (!(rField_is_Domain(currRing))) l2 = pLength(a2);
1303
1304 Pair->SetLmTail(m2, a2, l2, use_buckets, tailRing);
1305
1306#ifdef HAVE_SHIFTBBA
1307 if (tailRing->isLPring)
1308 {
1309 // get m2*a2*m22 - m1*a1*m12
1310 poly tmp=tailRing->p_Procs->pp_Mult_mm(a1, m12, tailRing);
1311 Pair->Tail_Minus_mm_Mult_qq(m1, tmp, l1, spNoether);
1312 p_Delete(&tmp,tailRing);
1313 }
1314 else
1315#endif
1316 {
1317 // get m2*a2 - m1*a1
1318 Pair->Tail_Minus_mm_Mult_qq(m1, a1, l1, spNoether);
1319 }
1320
1321 // Clean-up time
1322 Pair->LmDeleteAndIter();
1323 p_LmDelete(m1, tailRing);
1324#ifdef HAVE_SHIFTBBA
1325 if (tailRing->isLPring)
1326 {
1327 // just to be sure, check that the shift is correct
1328 assume(Pair->shift == 0);
1329 assume(si_max(p_mFirstVblock(Pair->p, tailRing) - 1, 0) == Pair->shift); // == 0
1330
1331 p_LmDelete(m12, tailRing);
1332 p_LmDelete(m22, tailRing);
1333 // m2 is already deleted
1334 }
1335#endif
1336
1337 if (co != 0)
1338 {
1339 if (co==1)
1340 {
1341 p_SetCompP(p1,0, currRing, tailRing);
1342 }
1343 else
1344 {
1345 p_SetCompP(p2,0, currRing, tailRing);
1346 }
1347 }
1348}
static int si_max(const int a, const int b)
Definition auxiliary.h:125
KINLINE BOOLEAN k_GetLeadTerms(const poly p1, const poly p2, const ring p_r, poly &m1, poly &m2, const ring m_r)
Definition kInline.h:1015
VAR int create_count
Definition kspoly.cc:26
#define __p_GetComp(p, r)
Definition monomials.h:63
static int pLength(poly a)
Definition p_polys.h:190
static void p_SetCompP(poly p, int i, ring r)
Definition p_polys.h:256
static void p_Delete(poly *p, const ring r)
Definition p_polys.h:903
static BOOLEAN rField_is_Domain(const ring r)
Definition ring.h:493
void k_SplitFrame(poly &m1, poly &m2, int at, const ring r)
Definition shiftop.cc:600
#define R
Definition sirandom.c:27

◆ ksReducePoly()

int ksReducePoly ( LObject * PR,
TObject * PW,
poly spNoether,
number * coef,
poly * mon,
kStrategy strat,
BOOLEAN reduce )

Definition at line 187 of file kspoly.cc.

194{
195#ifdef KDEBUG
196 red_count++;
197#ifdef TEST_OPT_DEBUG_RED
198// if (TEST_OPT_DEBUG)
199// {
200// Print("Red %d:", red_count); PR->wrp(); Print(" with:");
201// PW->wrp();
202// //printf("\necart(PR)-ecart(PW): %i\n",PR->ecart-PW->ecart);
203// //pWrite(PR->p);
204// }
205#endif
206#endif
207 int ret = 0;
208 ring tailRing = PR->tailRing;
209 if (strat!=NULL)
210 {
211 kTest_L(PR,strat);
212 kTest_T(PW,strat);
213 }
214
215 poly p1 = PR->GetLmTailRing(); // p2 | p1
216 poly p2 = PW->GetLmTailRing(); // i.e. will reduce p1 with p2; lm = LT(p1) / LM(p2)
217 poly t2 = pNext(p2), lm = p1; // t2 = p2 - LT(p2); really compute P = LC(p2)*p1 - LT(p1)/LM(p2)*p2
218 assume(p1 != NULL && p2 != NULL);// Attention, we have rings and there LC(p2) and LC(p1) are special
219 p_CheckPolyRing(p1, tailRing);
220 p_CheckPolyRing(p2, tailRing);
221
222 pAssume1(p2 != NULL && p1 != NULL &&
223 p_DivisibleBy(p2, p1, tailRing));
224
225 pAssume1(p_GetComp(p1, tailRing) == p_GetComp(p2, tailRing) ||
226 (p_GetComp(p2, tailRing) == 0 &&
227 p_MaxComp(pNext(p2),tailRing) == 0));
228
229#ifdef HAVE_PLURAL
231 {
232 // for the time being: we know currRing==strat->tailRing
233 // no exp-bound checking needed
234 // (only needed if exp-bound(tailring)<exp-b(currRing))
235 if (PR->bucket!=NULL) nc_kBucketPolyRed_Z(PR->bucket, p2,coef,reduce);
236 else
237 {
238 poly _p = (PR->t_p != NULL ? PR->t_p : PR->p);
239 assume(_p != NULL);
240 nc_PolyPolyRed(_p, p2,coef, currRing);
241 if (PR->t_p!=NULL) PR->t_p=_p; else PR->p=_p;
242 PR->pLength=0; // usually not used, GetpLength re-computes it if needed
243 }
244 return 0;
245 }
246#endif
247
248 if ((t2==NULL)&&(mon==NULL)) // Divisor is just one term, therefore it will
249 { // just cancel the leading term
250 PR->LmDeleteAndIter();
251 if (coef != NULL) *coef = n_Init(1, tailRing->cf);
252 return 0;
253 }
254
255 p_ExpVectorSub(lm, p2, tailRing); // Calculate the Monomial we must multiply to p2
256
257 if (tailRing != currRing)
258 {
259 // check that reduction does not violate exp bound
260 while (PW->max_exp != NULL && !p_LmExpVectorAddIsOk(lm, PW->max_exp, tailRing))
261 {
262 // undo changes of lm
263 p_ExpVectorAdd(lm, p2, tailRing);
264 if (strat == NULL) return 2;
265 if (! kStratChangeTailRing(strat, PR, PW)) return -1;
266 tailRing = strat->tailRing;
267 p1 = PR->GetLmTailRing();
268 p2 = PW->GetLmTailRing();
269 t2 = pNext(p2);
270 lm = p1;
271 p_ExpVectorSub(lm, p2, tailRing);
272 ret = 1;
273 }
274 }
275
276#ifdef HAVE_SHIFTBBA
277 poly lmRight=NULL;
278 if (tailRing->isLPring)
279 {
280 assume(PR->shift == 0);
281 assume(PW->shift == si_max(p_mFirstVblock(PW->p, tailRing) - 1, 0));
282 k_SplitFrame(lm, lmRight, PW->shift + 1, tailRing);
283 }
284#endif
285
286 // take care of coef business
287 if (! n_IsOne(pGetCoeff(p2), tailRing->cf))
288 {
289 number bn = pGetCoeff(lm);
290 number an = pGetCoeff(p2);
291 int ct = ksCheckCoeff(&an, &bn, tailRing->cf); // Calculate special LC
292 if (reduce)
293 {
294 if(n_IsMOne(an, tailRing->cf))
295 {
296 an=n_InpNeg(an, tailRing->cf);
297 bn=n_InpNeg(bn, tailRing->cf);
298 ct+=1;
299 }
300#ifdef KDEBUG
301 else if(!n_IsOne(an,tailRing->cf))
302 {
303 StringSetS("ksReducePoly: ");n_Write(an,tailRing->cf);
304 StringAppendS("\n");
306 }
307#endif
308 }
309 // in case of reduce, do not multiply PR
310 p_SetCoeff(lm, bn, tailRing);
311 if ((ct == 0) || (ct == 2))
312 PR->Tail_Mult_nn(an);
313 if (coef != NULL) *coef = an;
314 else n_Delete(&an, tailRing->cf);
315 }
316 else
317 {
318 if (coef != NULL) *coef = n_Init(1, tailRing->cf);
319 }
320 if(mon!=NULL) *mon=pHead(lm);
321
322 // and finally,
323#ifdef HAVE_SHIFTBBA
324 if (tailRing->isLPring)
325 {
326 poly tmp=tailRing->p_Procs->pp_Mult_mm(t2, lmRight, tailRing);
327 PR->Tail_Minus_mm_Mult_qq(lm, tmp, pLength(t2), spNoether);
328 p_Delete(&tmp,tailRing);
329 p_Delete(&lm,tailRing);
330 p_Delete(&lmRight,tailRing);
331 }
332 else
333#endif
334 {
335 PR->Tail_Minus_mm_Mult_qq(lm, t2, pLength(t2) /*PW->GetpLength() - 1*/, spNoether);
336 }
337 assume(PW->GetpLength() == pLength(PW->p != NULL ? PW->p : PW->t_p));
338 PR->LmDeleteAndIter();
339
340 return ret;
341}
CanonicalForm reduce(const CanonicalForm &f, const CanonicalForm &M)
polynomials in M.mvar() are considered coefficients M univariate monic polynomial the coefficients of...
Definition cf_ops.cc:660
ring tailRing
Definition kutil.h:344
static FORCE_INLINE BOOLEAN n_IsMOne(number n, const coeffs r)
TRUE iff 'n' represents the additive inverse of the one element, i.e. -1.
Definition coeffs.h:476
static FORCE_INLINE number n_InpNeg(number n, const coeffs r)
in-place negation of n MUST BE USED: n = n_InpNeg(n) (no copy is returned)
Definition coeffs.h:558
static FORCE_INLINE void n_Delete(number *p, const coeffs r)
delete 'p'
Definition coeffs.h:459
static FORCE_INLINE void n_Write(number n, const coeffs r, const BOOLEAN bShortOut=TRUE)
Definition coeffs.h:592
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:539
static FORCE_INLINE BOOLEAN n_IsOne(number n, const coeffs r)
TRUE iff 'n' represents the one element.
Definition coeffs.h:472
VAR int red_count
Definition kspoly.cc:25
BOOLEAN kStratChangeTailRing(kStrategy strat, LObject *L, TObject *T, unsigned long expbound)
Definition kutil.cc:10961
BOOLEAN kTest_L(LObject *L, kStrategy strat, BOOLEAN testp, int lpos, TSet T, int tlength)
Definition kutil.cc:923
BOOLEAN kTest_T(TObject *T, kStrategy strat, int i, char TN)
Definition kutil.cc:796
static void nc_kBucketPolyRed_Z(kBucket_pt b, poly p, number *c, BOOLEAN reduce)
Definition nc.h:284
void nc_PolyPolyRed(poly &b, poly p, number *c, const ring r)
#define pAssume1(cond)
Definition monomials.h:171
static void p_ExpVectorAdd(poly p1, poly p2, const ring r)
Definition p_polys.h:1427
static void p_ExpVectorSub(poly p1, poly p2, const ring r)
Definition p_polys.h:1456
static number p_SetCoeff(poly p, number n, ring r)
Definition p_polys.h:414
static BOOLEAN p_DivisibleBy(poly a, poly b, const ring r)
Definition p_polys.h:1916
static long p_MaxComp(poly p, ring lmRing, ring tailRing)
Definition p_polys.h:294
BOOLEAN p_CheckPolyRing(poly p, ring r)
Definition pDebug.cc:115
static BOOLEAN p_LmExpVectorAddIsOk(const poly p1, const poly p2, const ring r)
Definition p_polys.h:2015
#define pHead(p)
returns newly allocated copy of Lm(p), coef is copied, next=NULL, p might be NULL
Definition polys.h:68
void StringSetS(const char *st)
Definition reporter.cc:128
void StringAppendS(const char *st)
Definition reporter.cc:107
void PrintS(const char *s)
Definition reporter.cc:284
char * StringEndS()
Definition reporter.cc:151
static BOOLEAN rIsPluralRing(const ring r)
we must always have this test!
Definition ring.h:406

◆ ksReducePolyBound()

int ksReducePolyBound ( LObject * PR,
TObject * PW,
int bound,
poly spNoether,
number * coef,
kStrategy strat )

Definition at line 590 of file kspoly.cc.

596{
597#ifdef KDEBUG
598 red_count++;
599#ifdef TEST_OPT_DEBUG_RED
600 if (TEST_OPT_DEBUG)
601 {
602 Print("Red %d:", red_count); PR->wrp(); Print(" with:");
603 PW->wrp();
604 //printf("\necart(PR)-ecart(PW): %i\n",PR->ecart-PW->ecart);
605 //pWrite(PR->p);
606 }
607#endif
608#endif
609 int ret = 0;
610 ring tailRing = PR->tailRing;
611 if (strat!=NULL)
612 {
613 kTest_L(PR,strat);
614 kTest_T(PW,strat);
615 }
616
617 poly p1 = PR->GetLmTailRing(); // p2 | p1
618 poly p2 = PW->GetLmTailRing(); // i.e. will reduce p1 with p2; lm = LT(p1) / LM(p2)
619 poly t2 = pNext(p2), lm = p1; // t2 = p2 - LT(p2); really compute P = LC(p2)*p1 - LT(p1)/LM(p2)*p2
620 assume(p1 != NULL && p2 != NULL);// Attention, we have rings and there LC(p2) and LC(p1) are special
621 p_CheckPolyRing(p1, tailRing);
622 p_CheckPolyRing(p2, tailRing);
623
624 pAssume1(p2 != NULL && p1 != NULL &&
625 p_DivisibleBy(p2, p1, tailRing));
626
627 pAssume1(p_GetComp(p1, tailRing) == p_GetComp(p2, tailRing) ||
628 (p_GetComp(p2, tailRing) == 0 &&
629 p_MaxComp(pNext(p2),tailRing) == 0));
630
631#ifdef HAVE_PLURAL
633 {
634 // for the time being: we know currRing==strat->tailRing
635 // no exp-bound checking needed
636 // (only needed if exp-bound(tailring)<exp-b(currRing))
637 if (PR->bucket!=NULL) nc_kBucketPolyRed_Z(PR->bucket, p2,coef,FALSE);
638 else
639 {
640 poly _p = (PR->t_p != NULL ? PR->t_p : PR->p);
641 assume(_p != NULL);
642 nc_PolyPolyRed(_p, p2,coef, currRing);
643 if (PR->t_p!=NULL) PR->t_p=_p; else PR->p=_p;
644 PR->pLength=0; // usually not used, GetpLength re-computes it if needed
645 }
646 return 0;
647 }
648#endif
649
650 if (t2==NULL) // Divisor is just one term, therefore it will
651 { // just cancel the leading term
652 PR->LmDeleteAndIter();
653 if (coef != NULL) *coef = n_Init(1, tailRing->cf);
654 return 0;
655 }
656
657 p_ExpVectorSub(lm, p2, tailRing); // Calculate the Monomial we must multiply to p2
658
659 if (tailRing != currRing)
660 {
661 // check that reduction does not violate exp bound
662 while (PW->max_exp != NULL && !p_LmExpVectorAddIsOk(lm, PW->max_exp, tailRing))
663 {
664 // undo changes of lm
665 p_ExpVectorAdd(lm, p2, tailRing);
666 if (strat == NULL) return 2;
667 if (! kStratChangeTailRing(strat, PR, PW)) return -1;
668 tailRing = strat->tailRing;
669 p1 = PR->GetLmTailRing();
670 p2 = PW->GetLmTailRing();
671 t2 = pNext(p2);
672 lm = p1;
673 p_ExpVectorSub(lm, p2, tailRing);
674 ret = 1;
675 }
676 }
677
678#ifdef HAVE_SHIFTBBA
679 poly lmRight;
680 if (tailRing->isLPring)
681 {
682 assume(PR->shift == 0);
683 assume(PW->shift == si_max(p_mFirstVblock(PW->p, tailRing) - 1, 0));
684 k_SplitFrame(lm, lmRight, PW->shift + 1, tailRing);
685 }
686#endif
687
688 // take care of coef business
689 if (! n_IsOne(pGetCoeff(p2), tailRing->cf))
690 {
691 number bn = pGetCoeff(lm);
692 number an = pGetCoeff(p2);
693 int ct = ksCheckCoeff(&an, &bn, tailRing->cf); // Calculate special LC
694 p_SetCoeff(lm, bn, tailRing);
695 if ((ct == 0) || (ct == 2))
696 PR->Tail_Mult_nn(an);
697 if (coef != NULL) *coef = an;
698 else n_Delete(&an, tailRing->cf);
699 }
700 else
701 {
702 if (coef != NULL) *coef = n_Init(1, tailRing->cf);
703 }
704
705
706 // and finally,
707#ifdef HAVE_SHIFTBBA
708 if (tailRing->isLPring)
709 {
710 PR->Tail_Minus_mm_Mult_qq(lm, tailRing->p_Procs->pp_Mult_mm(t2, lmRight, tailRing), pLength(t2), spNoether);
711 }
712 else
713#endif
714 {
715 PR->Tail_Minus_mm_Mult_qq(lm, t2, pLength(t2) /*PW->GetpLength() - 1*/, spNoether);
716 }
717 assume(PW->GetpLength() == pLength(PW->p != NULL ? PW->p : PW->t_p));
718 PR->LmDeleteAndIter();
719
720#if defined(KDEBUG) && defined(TEST_OPT_DEBUG_RED)
721 if (TEST_OPT_DEBUG)
722 {
723 Print(" to: "); PR->wrp(); Print("\n");
724 //printf("\nt^%i ", PR->ecart);pWrite(pHead(PR->p));
725 }
726#endif
727 return ret;
728}
#define FALSE
Definition auxiliary.h:97
#define Print
Definition emacs.cc:80
#define TEST_OPT_DEBUG
Definition options.h:110

◆ ksReducePolyLC()

int ksReducePolyLC ( LObject * PR,
TObject * PW,
poly spNoether,
number * coef,
kStrategy strat )

Definition at line 477 of file kspoly.cc.

482{
483#ifdef KDEBUG
484 red_count++;
485#ifdef TEST_OPT_DEBUG_RED
486// if (TEST_OPT_DEBUG)
487// {
488// Print("Red %d:", red_count); PR->wrp(); Print(" with:");
489// PW->wrp();
490// //printf("\necart(PR)-ecart(PW): %i\n",PR->ecart-PW->ecart);
491// //pWrite(PR->p);
492// }
493#endif
494#endif
495 /* printf("PR->P: ");
496 * p_Write(PR->p, currRing, PR->tailRing); */
497 int ret = 0;
498 ring tailRing = PR->tailRing;
499 if (strat!=NULL)
500 {
501 kTest_L(PR,strat);
502 kTest_T(PW,strat);
503 }
504
505 poly p1 = PR->GetLmTailRing(); // p2 | p1
506 poly p2 = PW->GetLmTailRing(); // i.e. will reduce p1 with p2; lm = LT(p1) / LM(p2)
507 poly lm = p1; // really compute P = LC(p2)*p1 - LT(p1)/LM(p2)*p2
508 assume(p1 != NULL && p2 != NULL);// Attention, we have rings and there LC(p2) and LC(p1) are special
509 p_CheckPolyRing(p1, tailRing);
510 p_CheckPolyRing(p2, tailRing);
511
512 pAssume1(p2 != NULL && p1 != NULL &&
513 p_DivisibleBy(p2, p1, tailRing));
514
515 pAssume1(p_GetComp(p1, tailRing) == p_GetComp(p2, tailRing) ||
516 (p_GetComp(p2, tailRing) == 0 &&
517 p_MaxComp(pNext(p2),tailRing) == 0));
518
519#ifdef HAVE_PLURAL
521 {
522 // for the time being: we know currRing==strat->tailRing
523 // no exp-bound checking needed
524 // (only needed if exp-bound(tailring)<exp-b(currRing))
525 if (PR->bucket!=NULL) nc_kBucketPolyRed_Z(PR->bucket, p2,coef,FALSE);
526 else
527 {
528 poly _p = (PR->t_p != NULL ? PR->t_p : PR->p);
529 assume(_p != NULL);
530 nc_PolyPolyRed(_p, p2,coef, currRing);
531 if (PR->t_p!=NULL) PR->t_p=_p; else PR->p=_p;
532 PR->pLength=0; // usually not used, GetpLength re-computes it if needed
533 }
534 return 0;
535 }
536#endif
537
538 p_ExpVectorSub(lm, p2, tailRing); // Calculate the Monomial we must multiply to p2
539 p_SetCoeff(lm, n_Init(1, tailRing->cf), tailRing);
540 while (PW->max_exp != NULL && !p_LmExpVectorAddIsOk(lm, PW->max_exp, tailRing))
541 {
542 // undo changes of lm
543 p_ExpVectorAdd(lm, p2, tailRing);
544 if (strat == NULL) return 2;
545 /* if (! kStratChangeTailRing(strat, PR, PW)) return -1; */
546 tailRing = strat->tailRing;
547 p1 = PR->GetLmTailRing();
548 p2 = PW->GetLmTailRing();
549 lm = p1;
550 p_ExpVectorSub(lm, p2, tailRing);
551 ret = 1;
552 }
553
554#ifdef HAVE_SHIFTBBA
555 poly lmRight;
556 if (tailRing->isLPring)
557 {
558 assume(PR->shift == 0);
559 assume(PW->shift == si_max(p_mFirstVblock(PW->p, tailRing) - 1, 0));
560 k_SplitFrame(lm, lmRight, PW->shift + 1, tailRing);
561 }
562#endif
563
564 // and finally,
565#ifdef HAVE_SHIFTBBA
566 if (tailRing->isLPring)
567 {
568 PR->Tail_Minus_mm_Mult_qq(lm, tailRing->p_Procs->pp_Mult_mm(p2, lmRight, tailRing), pLength(p2), spNoether);
569 }
570 else
571#endif
572 {
573 PR->Tail_Minus_mm_Mult_qq(lm, p2, pLength(p2) /*PW->GetpLength() - 1*/, spNoether);
574 }
575 assume(PW->GetpLength() == pLength(PW->p != NULL ? PW->p : PW->t_p));
576
577 PR->LmDeleteAndIter();
578 p_SetCoeff(PR->p, *coef, currRing);
579
580#if defined(KDEBUG) && defined(TEST_OPT_DEBUG_RED)
581 if (TEST_OPT_DEBUG)
582 {
583 Print(" to: "); PR->wrp(); Print("\n");
584 //printf("\nt^%i ", PR->ecart);pWrite(pHead(PR->p));
585 }
586#endif
587 return ret;
588}

◆ ksReducePolySig()

int ksReducePolySig ( LObject * PR,
TObject * PW,
long idx,
poly spNoether,
number * coef,
kStrategy strat )

Definition at line 737 of file kspoly.cc.

743{
744#ifdef KDEBUG
745 red_count++;
746#ifdef TEST_OPT_DEBUG_RED
747 if (TEST_OPT_DEBUG)
748 {
749 Print("Red %d:", red_count); PR->wrp(); Print(" with:");
750 PW->wrp();
751 }
752#endif
753#endif
754 int ret = 0;
755 ring tailRing = PR->tailRing;
756 if (strat!=NULL)
757 {
758 kTest_L(PR,strat);
759 kTest_T(PW,strat);
760 }
761
762 // signature-based stuff:
763 // checking for sig-safeness first
764 // NOTE: This has to be done in the current ring
765 //
766 /**********************************************
767 *
768 * TODO:
769 * --------------------------------------------
770 * if strat->sbaOrder == 1
771 * Since we are subdividing lower index and
772 * current index reductions it is enough to
773 * look at the polynomial part of the signature
774 * for a check. This should speed-up checking
775 * a lot!
776 * if !strat->sbaOrder == 0
777 * We are not subdividing lower and current index
778 * due to the fact that we are using the induced
779 * Schreyer order
780 *
781 * nevertheless, this different behaviour is
782 * taken care of by is_sigsafe
783 * => one reduction procedure can be used for
784 * both, the incremental and the non-incremental
785 * attempt!
786 * --------------------------------------------
787 *
788 *********************************************/
789 //printf("COMPARE IDX: %ld -- %ld\n",idx,strat->currIdx);
790 if (!PW->is_sigsafe)
791 {
792 poly sigMult = pCopy(PW->sig); // copy signature of reducer
793//#if 1
794#ifdef DEBUGF5
795 printf("IN KSREDUCEPOLYSIG: \n");
796 pWrite(pHead(f1));
797 pWrite(pHead(f2));
798 pWrite(sigMult);
799 printf("--------------\n");
800#endif
801 p_ExpVectorAddSub(sigMult,PR->GetLmCurrRing(),PW->GetLmCurrRing(),currRing);
802//#if 1
803#ifdef DEBUGF5
804 printf("------------------- IN KSREDUCEPOLYSIG: --------------------\n");
805 pWrite(pHead(f1));
806 pWrite(pHead(f2));
807 pWrite(sigMult);
808 pWrite(PR->sig);
809 printf("--------------\n");
810#endif
811 int sigSafe = p_LmCmp(PR->sig,sigMult,currRing);
812 // now we can delete the copied polynomial data used for checking for
813 // sig-safeness of the reduction step
814//#if 1
815#ifdef DEBUGF5
816 printf("%d -- %d sig\n",sigSafe,PW->is_sigsafe);
817
818#endif
819 //pDelete(&f1);
820 pDelete(&sigMult);
821 // go on with the computations only if the signature of p2 is greater than the
822 // signature of fm*p1
823 if(sigSafe != 1)
824 {
825 PR->is_redundant = TRUE;
826 return 3;
827 }
828 //PW->is_sigsafe = TRUE;
829 }
830 PR->is_redundant = FALSE;
831 poly p1 = PR->GetLmTailRing(); // p2 | p1
832 poly p2 = PW->GetLmTailRing(); // i.e. will reduce p1 with p2; lm = LT(p1) / LM(p2)
833 poly t2 = pNext(p2), lm = p1; // t2 = p2 - LT(p2); really compute P = LC(p2)*p1 - LT(p1)/LM(p2)*p2
834 assume(p1 != NULL && p2 != NULL);// Attention, we have rings and there LC(p2) and LC(p1) are special
835 p_CheckPolyRing(p1, tailRing);
836 p_CheckPolyRing(p2, tailRing);
837
838 pAssume1(p2 != NULL && p1 != NULL &&
839 p_DivisibleBy(p2, p1, tailRing));
840
841 pAssume1(p_GetComp(p1, tailRing) == p_GetComp(p2, tailRing) ||
842 (p_GetComp(p2, tailRing) == 0 &&
843 p_MaxComp(pNext(p2),tailRing) == 0));
844
845#ifdef HAVE_PLURAL
847 {
848 // for the time being: we know currRing==strat->tailRing
849 // no exp-bound checking needed
850 // (only needed if exp-bound(tailring)<exp-b(currRing))
851 if (PR->bucket!=NULL) nc_kBucketPolyRed_Z(PR->bucket, p2,coef,FALSE);
852 else
853 {
854 poly _p = (PR->t_p != NULL ? PR->t_p : PR->p);
855 assume(_p != NULL);
856 nc_PolyPolyRed(_p, p2, coef, currRing);
857 if (PR->t_p!=NULL) PR->t_p=_p; else PR->p=_p;
858 PR->pLength=0; // usaully not used, GetpLength re-comoutes it if needed
859 }
860 return 0;
861 }
862#endif
863
864 if (t2==NULL) // Divisor is just one term, therefore it will
865 { // just cancel the leading term
866 PR->LmDeleteAndIter();
867 if (coef != NULL) *coef = n_Init(1, tailRing->cf);
868 return 0;
869 }
870
871 p_ExpVectorSub(lm, p2, tailRing); // Calculate the Monomial we must multiply to p2
872
873 if (tailRing != currRing)
874 {
875 // check that reduction does not violate exp bound
876 while (PW->max_exp != NULL && !p_LmExpVectorAddIsOk(lm, PW->max_exp, tailRing))
877 {
878 // undo changes of lm
879 p_ExpVectorAdd(lm, p2, tailRing);
880 if (strat == NULL) return 2;
881 if (! kStratChangeTailRing(strat, PR, PW)) return -1;
882 tailRing = strat->tailRing;
883 p1 = PR->GetLmTailRing();
884 p2 = PW->GetLmTailRing();
885 t2 = pNext(p2);
886 lm = p1;
887 p_ExpVectorSub(lm, p2, tailRing);
888 ret = 1;
889 }
890 }
891
892#ifdef HAVE_SHIFTBBA
893 poly lmRight;
894 if (tailRing->isLPring)
895 {
896 assume(PR->shift == 0);
897 assume(PW->shift == si_max(p_mFirstVblock(PW->p, tailRing) - 1, 0));
898 k_SplitFrame(lm, lmRight, PW->shift + 1, tailRing);
899 }
900#endif
901
902 // take care of coef business
903 if (! n_IsOne(pGetCoeff(p2), tailRing->cf))
904 {
905 number bn = pGetCoeff(lm);
906 number an = pGetCoeff(p2);
907 int ct = ksCheckCoeff(&an, &bn, tailRing->cf); // Calculate special LC
908 p_SetCoeff(lm, bn, tailRing);
909 if ((ct == 0) || (ct == 2))
910 PR->Tail_Mult_nn(an);
911 if (coef != NULL) *coef = an;
912 else n_Delete(&an, tailRing->cf);
913 }
914 else
915 {
916 if (coef != NULL) *coef = n_Init(1, tailRing->cf);
917 }
918
919
920 // and finally,
921#ifdef HAVE_SHIFTBBA
922 if (tailRing->isLPring)
923 {
924 PR->Tail_Minus_mm_Mult_qq(lm, tailRing->p_Procs->pp_Mult_mm(t2, lmRight, tailRing), pLength(t2), spNoether);
925 }
926 else
927#endif
928 {
929 PR->Tail_Minus_mm_Mult_qq(lm, t2, PW->GetpLength() - 1, spNoether);
930 }
931 assume(PW->GetpLength() == (int)pLength(PW->p != NULL ? PW->p : PW->t_p));
932 PR->LmDeleteAndIter();
933
934#if defined(KDEBUG) && defined(TEST_OPT_DEBUG_RED)
935 if (TEST_OPT_DEBUG)
936 {
937 Print(" to: "); PR->wrp(); Print("\n");
938 }
939#endif
940 return ret;
941}
#define TRUE
Definition auxiliary.h:101
static void p_ExpVectorAddSub(poly p1, poly p2, poly p3, const ring r)
Definition p_polys.h:1472
#define pDelete(p_ptr)
Definition polys.h:187
void pWrite(poly p)
Definition polys.h:309
#define pCopy(p)
return a copy of the poly
Definition polys.h:186

◆ ksReducePolySigRing()

int ksReducePolySigRing ( LObject * PR,
TObject * PW,
long idx,
poly spNoether,
number * coef,
kStrategy strat )

Definition at line 943 of file kspoly.cc.

949{
950#ifdef KDEBUG
951 red_count++;
952#ifdef TEST_OPT_DEBUG_RED
953 if (TEST_OPT_DEBUG)
954 {
955 Print("Red %d:", red_count); PR->wrp(); Print(" with:");
956 PW->wrp();
957 }
958#endif
959#endif
960 int ret = 0;
961 ring tailRing = PR->tailRing;
962 if (strat!=NULL)
963 {
964 kTest_L(PR,strat);
965 kTest_T(PW,strat);
966 }
967
968 // signature-based stuff:
969 // checking for sig-safeness first
970 // NOTE: This has to be done in the current ring
971 //
972 /**********************************************
973 *
974 * TODO:
975 * --------------------------------------------
976 * if strat->sbaOrder == 1
977 * Since we are subdividing lower index and
978 * current index reductions it is enough to
979 * look at the polynomial part of the signature
980 * for a check. This should speed-up checking
981 * a lot!
982 * if !strat->sbaOrder == 0
983 * We are not subdividing lower and current index
984 * due to the fact that we are using the induced
985 * Schreyer order
986 *
987 * nevertheless, this different behaviour is
988 * taken care of by is_sigsafe
989 * => one reduction procedure can be used for
990 * both, the incremental and the non-incremental
991 * attempt!
992 * --------------------------------------------
993 *
994 *********************************************/
995 //printf("COMPARE IDX: %ld -- %ld\n",idx,strat->currIdx);
996 if (!PW->is_sigsafe)
997 {
998 poly sigMult = pCopy(PW->sig); // copy signature of reducer
999//#if 1
1000#ifdef DEBUGF5
1001 printf("IN KSREDUCEPOLYSIG: \n");
1002 pWrite(pHead(f1));
1003 pWrite(pHead(f2));
1004 pWrite(sigMult);
1005 printf("--------------\n");
1006#endif
1007 p_ExpVectorAddSub(sigMult,PR->GetLmCurrRing(),PW->GetLmCurrRing(),currRing);
1008 //I have also to set the leading coefficient for sigMult (in the case of rings)
1010 {
1011 pSetCoeff(sigMult,nMult(nDiv(pGetCoeff(PR->p),pGetCoeff(PW->p)), pGetCoeff(sigMult)));
1012 if(nIsZero(pGetCoeff(sigMult)))
1013 {
1014 sigMult = NULL;
1015 }
1016 }
1017//#if 1
1018#ifdef DEBUGF5
1019 printf("------------------- IN KSREDUCEPOLYSIG: --------------------\n");
1020 pWrite(pHead(f1));
1021 pWrite(pHead(f2));
1022 pWrite(sigMult);
1023 pWrite(PR->sig);
1024 printf("--------------\n");
1025#endif
1026 int sigSafe;
1028 sigSafe = p_LmCmp(PR->sig,sigMult,currRing);
1029 // now we can delete the copied polynomial data used for checking for
1030 // sig-safeness of the reduction step
1031//#if 1
1032#ifdef DEBUGF5
1033 printf("%d -- %d sig\n",sigSafe,PW->is_sigsafe);
1034
1035#endif
1037 {
1038 // Set the sig
1039 poly origsig = pCopy(PR->sig);
1040 if(sigMult != NULL)
1041 PR->sig = pHead(pSub(PR->sig, sigMult));
1042 //The sigs have the same lm, have to subtract
1043 //It may happen that now the signature is 0 (drop)
1044 if(PR->sig == NULL)
1045 {
1046 strat->sigdrop=TRUE;
1047 }
1048 else
1049 {
1050 if(pLtCmp(PR->sig,origsig) == 1)
1051 {
1052 // do not allow this reduction - it will increase it's signature
1053 // and the partially standard basis is just till the old sig, not the new one
1054 PR->is_redundant = TRUE;
1055 pDelete(&PR->sig);
1056 PR->sig = origsig;
1057 strat->blockred++;
1058 return 3;
1059 }
1060 if(pLtCmp(PR->sig,origsig) == -1)
1061 {
1062 strat->sigdrop=TRUE;
1063 }
1064 }
1065 pDelete(&origsig);
1066 }
1067 //pDelete(&f1);
1068 // go on with the computations only if the signature of p2 is greater than the
1069 // signature of fm*p1
1070 if(sigSafe != 1 && !rField_is_Ring(currRing))
1071 {
1072 PR->is_redundant = TRUE;
1073 return 3;
1074 }
1075 //PW->is_sigsafe = TRUE;
1076 }
1077 PR->is_redundant = FALSE;
1078 poly p1 = PR->GetLmTailRing(); // p2 | p1
1079 poly p2 = PW->GetLmTailRing(); // i.e. will reduce p1 with p2; lm = LT(p1) / LM(p2)
1080 poly t2 = pNext(p2), lm = p1; // t2 = p2 - LT(p2); really compute P = LC(p2)*p1 - LT(p1)/LM(p2)*p2
1081 assume(p1 != NULL && p2 != NULL);// Attention, we have rings and there LC(p2) and LC(p1) are special
1082 p_CheckPolyRing(p1, tailRing);
1083 p_CheckPolyRing(p2, tailRing);
1084
1085 pAssume1(p2 != NULL && p1 != NULL &&
1086 p_DivisibleBy(p2, p1, tailRing));
1087
1088 pAssume1(p_GetComp(p1, tailRing) == p_GetComp(p2, tailRing) ||
1089 (p_GetComp(p2, tailRing) == 0 &&
1090 p_MaxComp(pNext(p2),tailRing) == 0));
1091
1092#ifdef HAVE_PLURAL
1094 {
1095 // for the time being: we know currRing==strat->tailRing
1096 // no exp-bound checking needed
1097 // (only needed if exp-bound(tailring)<exp-b(currRing))
1098 if (PR->bucket!=NULL) nc_kBucketPolyRed_Z(PR->bucket, p2,coef,FALSE);
1099 else
1100 {
1101 poly _p = (PR->t_p != NULL ? PR->t_p : PR->p);
1102 assume(_p != NULL);
1103 nc_PolyPolyRed(_p, p2, coef, currRing);
1104 if (PR->t_p!=NULL) PR->t_p=_p; else PR->p=_p;
1105 PR->pLength=0; // usaully not used, GetpLength re-comoutes it if needed
1106 }
1107 return 0;
1108 }
1109#endif
1110
1111 if (t2==NULL) // Divisor is just one term, therefore it will
1112 { // just cancel the leading term
1113 PR->LmDeleteAndIter();
1114 if (coef != NULL) *coef = n_Init(1, tailRing->cf);
1115 return 0;
1116 }
1117
1118 p_ExpVectorSub(lm, p2, tailRing); // Calculate the Monomial we must multiply to p2
1119
1120 if (tailRing != currRing)
1121 {
1122 // check that reduction does not violate exp bound
1123 while (PW->max_exp != NULL && !p_LmExpVectorAddIsOk(lm, PW->max_exp, tailRing))
1124 {
1125 // undo changes of lm
1126 p_ExpVectorAdd(lm, p2, tailRing);
1127 if (strat == NULL) return 2;
1128 if (! kStratChangeTailRing(strat, PR, PW)) return -1;
1129 tailRing = strat->tailRing;
1130 p1 = PR->GetLmTailRing();
1131 p2 = PW->GetLmTailRing();
1132 t2 = pNext(p2);
1133 lm = p1;
1134 p_ExpVectorSub(lm, p2, tailRing);
1135 ret = 1;
1136 }
1137 }
1138
1139#ifdef HAVE_SHIFTBBA
1140 poly lmRight;
1141 if (tailRing->isLPring)
1142 {
1143 assume(PR->shift == 0);
1144 assume(PW->shift == si_max(p_mFirstVblock(PW->p, tailRing) - 1, 0));
1145 k_SplitFrame(lm, lmRight, PW->shift + 1, tailRing);
1146 }
1147#endif
1148
1149 // take care of coef business
1151 {
1152 p_SetCoeff(lm, nDiv(pGetCoeff(lm),pGetCoeff(p2)), tailRing);
1153 if (coef != NULL) *coef = n_Init(1, tailRing->cf);
1154 }
1155 else
1156 {
1157 if (! n_IsOne(pGetCoeff(p2), tailRing->cf))
1158 {
1159 number bn = pGetCoeff(lm);
1160 number an = pGetCoeff(p2);
1161 int ct = ksCheckCoeff(&an, &bn, tailRing->cf); // Calculate special LC
1162 p_SetCoeff(lm, bn, tailRing);
1163 if (((ct == 0) || (ct == 2)))
1164 PR->Tail_Mult_nn(an);
1165 if (coef != NULL) *coef = an;
1166 else n_Delete(&an, tailRing->cf);
1167 }
1168 else
1169 {
1170 if (coef != NULL) *coef = n_Init(1, tailRing->cf);
1171 }
1172 }
1173
1174 // and finally,
1175#ifdef HAVE_SHIFTBBA
1176 if (tailRing->isLPring)
1177 {
1178 PR->Tail_Minus_mm_Mult_qq(lm, tailRing->p_Procs->pp_Mult_mm(t2, lmRight, tailRing), pLength(t2), spNoether);
1179 }
1180 else
1181#endif
1182 {
1183 PR->Tail_Minus_mm_Mult_qq(lm, t2, PW->GetpLength() - 1, spNoether);
1184 }
1185 assume(PW->GetpLength() == (int)pLength(PW->p != NULL ? PW->p : PW->t_p));
1186 PR->LmDeleteAndIter();
1187
1188#if defined(KDEBUG) && defined(TEST_OPT_DEBUG_RED)
1189 if (TEST_OPT_DEBUG)
1190 {
1191 Print(" to: "); PR->wrp(); Print("\n");
1192 }
1193#endif
1194 return ret;
1195}
bool sigdrop
Definition kutil.h:359
int blockred
Definition kutil.h:364
#define nDiv(a, b)
Definition numbers.h:32
#define pLtCmp(p, q)
Definition polys.h:124
#define pSetCoeff(p, n)
deletes old coeff before setting the new one
Definition polys.h:32
#define pSub(a, b)
Definition polys.h:288

◆ ksReducePolyTail()

int ksReducePolyTail ( LObject * PR,
TObject * PW,
poly Current,
poly spNoether )

Definition at line 1350 of file kspoly.cc.

1351{
1352 BOOLEAN ret;
1353 number coef;
1354 poly Lp = PR->GetLmCurrRing();
1355 poly Save = PW->GetLmCurrRing();
1356
1357 pAssume(pIsMonomOf(Lp, Current));
1358
1359 assume(Lp != NULL && Current != NULL && pNext(Current) != NULL);
1360 assume(PR->bucket == NULL);
1361
1362 LObject Red(pNext(Current), PR->tailRing);
1363 TObject With(PW, Lp == Save);
1364
1365 pAssume(!pHaveCommonMonoms(Red.p, With.p));
1366 ret = ksReducePoly(&Red, &With, spNoether, &coef);
1367
1368 if (!ret)
1369 {
1370 if (! n_IsOne(coef, currRing->cf))
1371 {
1372 pNext(Current) = NULL;
1373 if (Current == PR->p && PR->t_p != NULL)
1374 pNext(PR->t_p) = NULL;
1375 PR->Mult_nn(coef);
1376 }
1377
1378 n_Delete(&coef, currRing->cf);
1379 pNext(Current) = Red.GetLmTailRing();
1380 if (Current == PR->p && PR->t_p != NULL)
1381 pNext(PR->t_p) = pNext(Current);
1382 }
1383
1384 if (Lp == Save)
1385 With.Delete();
1386
1387 return ret;
1388}
int ksReducePoly(LObject *PR, TObject *PW, poly spNoether, number *coef, poly *mon, kStrategy strat, BOOLEAN reduce)
Definition kspoly.cc:187
class sTObject TObject
Definition kutil.h:58
class sLObject LObject
Definition kutil.h:59
#define pAssume(cond)
Definition monomials.h:90
BOOLEAN pIsMonomOf(poly p, poly m)
Definition pDebug.cc:164
BOOLEAN pHaveCommonMonoms(poly p, poly q)
Definition pDebug.cc:174

◆ ksReducePolyTailBound()

int ksReducePolyTailBound ( LObject * PR,
TObject * PW,
int bound,
poly Current,
poly spNoether )

Definition at line 1390 of file kspoly.cc.

1391{
1392 BOOLEAN ret;
1393 number coef;
1394 poly Lp = PR->GetLmCurrRing();
1395 poly Save = PW->GetLmCurrRing();
1396
1397 pAssume(pIsMonomOf(Lp, Current));
1398
1399 assume(Lp != NULL && Current != NULL && pNext(Current) != NULL);
1400 assume(PR->bucket == NULL);
1401
1402 LObject Red(pNext(Current), PR->tailRing);
1403 TObject With(PW, Lp == Save);
1404
1405 pAssume(!pHaveCommonMonoms(Red.p, With.p));
1406 ret = ksReducePolyBound(&Red, &With,bound, spNoether, &coef);
1407
1408 if (!ret)
1409 {
1410 if (! n_IsOne(coef, currRing->cf))
1411 {
1412 pNext(Current) = NULL;
1413 if (Current == PR->p && PR->t_p != NULL)
1414 pNext(PR->t_p) = NULL;
1415 PR->Mult_nn(coef);
1416 }
1417
1418 n_Delete(&coef, currRing->cf);
1419 pNext(Current) = Red.GetLmTailRing();
1420 if (Current == PR->p && PR->t_p != NULL)
1421 pNext(PR->t_p) = pNext(Current);
1422 }
1423
1424 if (Lp == Save)
1425 With.Delete();
1426
1427 return ret;
1428}
static CanonicalForm bound(const CFMatrix &M)
Definition cf_linsys.cc:460
int ksReducePolyBound(LObject *PR, TObject *PW, int, poly spNoether, number *coef, kStrategy strat)
Definition kspoly.cc:590

Variable Documentation

◆ create_count

VAR int create_count = 0

Definition at line 26 of file kspoly.cc.

◆ red_count

VAR int red_count = 0

Definition at line 25 of file kspoly.cc.