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 30 of file kspoly.cc.

Function Documentation

◆ ksCreateShortSpoly()

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

Definition at line 1453 of file kspoly.cc.

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

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

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

◆ ksReducePolyBound()

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

Definition at line 595 of file kspoly.cc.

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

◆ ksReducePolyLC()

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

Definition at line 481 of file kspoly.cc.

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

◆ ksReducePolySig()

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

Definition at line 742 of file kspoly.cc.

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

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

1358{
1359 BOOLEAN ret;
1360 number coef;
1361 poly Lp = PR->GetLmCurrRing();
1362 poly Save = PW->GetLmCurrRing();
1363
1364 pAssume(pIsMonomOf(Lp, Current));
1365
1366 assume(Lp != NULL && Current != NULL && pNext(Current) != NULL);
1367 assume(PR->bucket == NULL);
1368
1369 LObject Red(pNext(Current), PR->tailRing);
1370 TObject With(PW, Lp == Save);
1371
1372 pAssume(!pHaveCommonMonoms(Red.p, With.p));
1373 ret = ksReducePoly(&Red, &With, spNoether, &coef);
1374
1375 if (!ret)
1376 {
1377 if (! n_IsOne(coef, currRing->cf))
1378 {
1379 pNext(Current) = NULL;
1380 if (Current == PR->p && PR->t_p != NULL)
1381 pNext(PR->t_p) = NULL;
1382 PR->Mult_nn(coef);
1383 }
1384
1385 n_Delete(&coef, currRing->cf);
1386 pNext(Current) = Red.GetLmTailRing();
1387 if (Current == PR->p && PR->t_p != NULL)
1388 pNext(PR->t_p) = pNext(Current);
1389 }
1390
1391 if (Lp == Save)
1392 With.Delete();
1393
1394 return ret;
1395}
int ksReducePoly(LObject *PR, TObject *PW, poly spNoether, number *coef, poly *mon, kStrategy strat, BOOLEAN reduce)
Definition: kspoly.cc:189
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:168
BOOLEAN pHaveCommonMonoms(poly p, poly q)
Definition: pDebug.cc:178

◆ ksReducePolyTailBound()

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

Definition at line 1397 of file kspoly.cc.

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

Variable Documentation

◆ create_count

VAR int create_count = 0

Definition at line 28 of file kspoly.cc.

◆ red_count

VAR int red_count = 0

Definition at line 27 of file kspoly.cc.