My Project
Loading...
Searching...
No Matches
Macros | Functions | Variables
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 1447 of file kspoly.cc.

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

◆ ksCreateSpoly()

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

Definition at line 1204 of file kspoly.cc.

1207{
1208#ifdef KDEBUG
1209 create_count++;
1210#endif
1211 poly p1 = Pair->p1;
1212 poly p2 = Pair->p2;
1213 Pair->tailRing = tailRing;
1214
1215 assume(p1 != NULL);
1216 assume(p2 != NULL);
1217 assume(tailRing != NULL);
1218
1219 poly a1 = pNext(p1), a2 = pNext(p2);
1220 number lc1 = pGetCoeff(p1), lc2 = pGetCoeff(p2);
1221 int co=0/*, ct = ksCheckCoeff(&lc1, &lc2, currRing->cf)*/; // gcd and zero divisors
1222 (void) ksCheckCoeff(&lc1, &lc2, currRing->cf);
1223
1224 int l1=0, l2=0;
1225
1226 if (currRing->pCompIndex >= 0)
1227 {
1229 {
1230 if (__p_GetComp(p1, currRing)==0)
1231 {
1232 co=1;
1233 p_SetCompP(p1,__p_GetComp(p2, currRing), currRing, tailRing);
1234 }
1235 else
1236 {
1237 co=2;
1238 p_SetCompP(p2, __p_GetComp(p1, currRing), currRing, tailRing);
1239 }
1240 }
1241 }
1242
1243 // get m1 = LCM(LM(p1), LM(p2))/LM(p1)
1244 // m2 = LCM(LM(p1), LM(p2))/LM(p2)
1245 if (m1 == NULL)
1246 k_GetLeadTerms(p1, p2, currRing, m1, m2, tailRing);
1247
1248#ifdef HAVE_SHIFTBBA
1249 poly m12, m22;
1250 if (tailRing->isLPring)
1251 {
1252 assume(p_mFirstVblock(p1, tailRing) <= 1 || p_mFirstVblock(p2, tailRing) <= 1);
1253 k_SplitFrame(m1, m12, si_max(p_mFirstVblock(p1, tailRing), 1), tailRing);
1254 k_SplitFrame(m2, m22, si_max(p_mFirstVblock(p2, tailRing), 1), tailRing);
1255 // coeffs of m1,m2 are NULL here
1256 }
1257#endif
1258
1259 pSetCoeff0(m1, lc2);
1260 pSetCoeff0(m2, lc1); // and now, m1 * LT(p1) == m2 * LT(p2)
1261
1262 if (R != NULL)
1263 {
1264 if (Pair->i_r1 == -1)
1265 {
1266 l1 = pLength(p1) - 1;
1267 }
1268 else
1269 {
1270 l1 = (R[Pair->i_r1])->GetpLength() - 1;
1271 }
1272 if ((Pair->i_r2 == -1)||(R[Pair->i_r2]==NULL))
1273 {
1274 l2 = pLength(p2) - 1;
1275 }
1276 else
1277 {
1278 l2 = (R[Pair->i_r2])->GetpLength() - 1;
1279 }
1280 }
1281
1282 // get m2 * a2
1283#ifdef HAVE_SHIFTBBA
1284 if (tailRing->isLPring)
1285 {
1286 // m2*a2*m22
1287 poly tmp= tailRing->p_Procs->pp_mm_Mult(a2, m2, tailRing);
1288 a2 = tailRing->p_Procs->pp_Mult_mm(tmp, m22, tailRing);
1289 p_Delete(&tmp,tailRing);
1290 }
1291 else
1292#endif
1293 if (spNoether != NULL)
1294 {
1295 l2 = -1;
1296 a2 = tailRing->p_Procs->pp_Mult_mm_Noether(a2, m2, spNoether, l2, tailRing);
1297 assume(l2 == (int)pLength(a2));
1298 }
1299 else
1300 {
1301 a2 = tailRing->p_Procs->pp_Mult_mm(a2, m2, tailRing);
1302 }
1303 if (!(rField_is_Domain(currRing))) l2 = pLength(a2);
1304
1305 Pair->SetLmTail(m2, a2, l2, use_buckets, tailRing);
1306
1307#ifdef HAVE_SHIFTBBA
1308 if (tailRing->isLPring)
1309 {
1310 // get m2*a2*m22 - m1*a1*m12
1311 poly tmp=tailRing->p_Procs->pp_Mult_mm(a1, m12, tailRing);
1312 Pair->Tail_Minus_mm_Mult_qq(m1, tmp, l1, spNoether);
1313 p_Delete(&tmp,tailRing);
1314 }
1315 else
1316#endif
1317 {
1318 // get m2*a2 - m1*a1
1319 Pair->Tail_Minus_mm_Mult_qq(m1, a1, l1, spNoether);
1320 }
1321
1322 // Clean-up time
1323 Pair->LmDeleteAndIter();
1324 p_LmDelete(m1, tailRing);
1325#ifdef HAVE_SHIFTBBA
1326 if (tailRing->isLPring)
1327 {
1328 // just to be sure, check that the shift is correct
1329 assume(Pair->shift == 0);
1330 assume(si_max(p_mFirstVblock(Pair->p, tailRing) - 1, 0) == Pair->shift); // == 0
1331
1332 p_LmDelete(m12, tailRing);
1333 p_LmDelete(m22, tailRing);
1334 // m2 is already deleted
1335 }
1336#endif
1337
1338 if (co != 0)
1339 {
1340 if (co==1)
1341 {
1342 p_SetCompP(p1,0, currRing, tailRing);
1343 }
1344 else
1345 {
1346 p_SetCompP(p2,0, currRing, tailRing);
1347 }
1348 }
1349}
static int si_max(const int a, const int b)
Definition auxiliary.h:124
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:254
static void p_Delete(poly *p, const ring r)
Definition p_polys.h:901
static BOOLEAN rField_is_Domain(const ring r)
Definition ring.h:492
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 {
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:343
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:10957
BOOLEAN kTest_L(LObject *L, kStrategy strat, BOOLEAN testp, int lpos, TSet T, int tlength)
Definition kutil.cc:924
BOOLEAN kTest_T(TObject *T, kStrategy strat, int i, char TN)
Definition kutil.cc:799
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:1425
static void p_ExpVectorSub(poly p1, poly p2, const ring r)
Definition p_polys.h:1454
static number p_SetCoeff(poly p, number n, ring r)
Definition p_polys.h:412
static BOOLEAN p_DivisibleBy(poly a, poly b, const ring r)
Definition p_polys.h:1914
static long p_MaxComp(poly p, ring lmRing, ring tailRing)
Definition p_polys.h:292
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:2013
#define pHead(p)
returns newly allocated copy of Lm(p), coef is copied, next=NULL, p might be NULL
Definition polys.h:67
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:405

◆ ksReducePolyBound()

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

Definition at line 591 of file kspoly.cc.

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

◆ 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 t2 = pNext(p2), lm = p1; // t2 = p2 - LT(p2); 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 t2 = pNext(p2);
550 lm = p1;
551 p_ExpVectorSub(lm, p2, tailRing);
552 ret = 1;
553 }
554
555#ifdef HAVE_SHIFTBBA
556 poly lmRight;
557 if (tailRing->isLPring)
558 {
559 assume(PR->shift == 0);
560 assume(PW->shift == si_max(p_mFirstVblock(PW->p, tailRing) - 1, 0));
561 k_SplitFrame(lm, lmRight, PW->shift + 1, tailRing);
562 }
563#endif
564
565 // and finally,
566#ifdef HAVE_SHIFTBBA
567 if (tailRing->isLPring)
568 {
569 PR->Tail_Minus_mm_Mult_qq(lm, tailRing->p_Procs->pp_Mult_mm(p2, lmRight, tailRing), pLength(p2), spNoether);
570 }
571 else
572#endif
573 {
574 PR->Tail_Minus_mm_Mult_qq(lm, p2, pLength(p2) /*PW->GetpLength() - 1*/, spNoether);
575 }
576 assume(PW->GetpLength() == pLength(PW->p != NULL ? PW->p : PW->t_p));
577
578 PR->LmDeleteAndIter();
579 p_SetCoeff(PR->p, *coef, currRing);
580
581#if defined(KDEBUG) && defined(TEST_OPT_DEBUG_RED)
582 if (TEST_OPT_DEBUG)
583 {
584 Print(" to: "); PR->wrp(); Print("\n");
585 //printf("\nt^%i ", PR->ecart);pWrite(pHead(PR->p));
586 }
587#endif
588 return ret;
589}

◆ ksReducePolySig()

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

Definition at line 738 of file kspoly.cc.

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

◆ ksReducePolySigRing()

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

Definition at line 944 of file kspoly.cc.

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

◆ ksReducePolyTail()

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

Definition at line 1351 of file kspoly.cc.

1352{
1353 BOOLEAN ret;
1354 number coef;
1355 poly Lp = PR->GetLmCurrRing();
1356 poly Save = PW->GetLmCurrRing();
1357
1358 pAssume(pIsMonomOf(Lp, Current));
1359
1360 assume(Lp != NULL && Current != NULL && pNext(Current) != NULL);
1361 assume(PR->bucket == NULL);
1362
1363 LObject Red(pNext(Current), PR->tailRing);
1364 TObject With(PW, Lp == Save);
1365
1367 ret = ksReducePoly(&Red, &With, spNoether, &coef);
1368
1369 if (!ret)
1370 {
1371 if (! n_IsOne(coef, currRing->cf))
1372 {
1373 pNext(Current) = NULL;
1374 if (Current == PR->p && PR->t_p != NULL)
1375 pNext(PR->t_p) = NULL;
1376 PR->Mult_nn(coef);
1377 }
1378
1379 n_Delete(&coef, currRing->cf);
1380 pNext(Current) = Red.GetLmTailRing();
1381 if (Current == PR->p && PR->t_p != NULL)
1382 pNext(PR->t_p) = pNext(Current);
1383 }
1384
1385 if (Lp == Save)
1386 With.Delete();
1387
1388 return ret;
1389}
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:57
class sLObject LObject
Definition kutil.h:58
#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 1391 of file kspoly.cc.

1392{
1393 BOOLEAN ret;
1394 number coef;
1395 poly Lp = PR->GetLmCurrRing();
1396 poly Save = PW->GetLmCurrRing();
1397
1398 pAssume(pIsMonomOf(Lp, Current));
1399
1400 assume(Lp != NULL && Current != NULL && pNext(Current) != NULL);
1401 assume(PR->bucket == NULL);
1402
1403 LObject Red(pNext(Current), PR->tailRing);
1404 TObject With(PW, Lp == Save);
1405
1408
1409 if (!ret)
1410 {
1411 if (! n_IsOne(coef, currRing->cf))
1412 {
1413 pNext(Current) = NULL;
1414 if (Current == PR->p && PR->t_p != NULL)
1415 pNext(PR->t_p) = NULL;
1416 PR->Mult_nn(coef);
1417 }
1418
1419 n_Delete(&coef, currRing->cf);
1420 pNext(Current) = Red.GetLmTailRing();
1421 if (Current == PR->p && PR->t_p != NULL)
1422 pNext(PR->t_p) = pNext(Current);
1423 }
1424
1425 if (Lp == Save)
1426 With.Delete();
1427
1428 return ret;
1429}
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:591

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.