Changeset 1bc7d4a in git


Ignore:
Timestamp:
Jul 2, 2012, 7:35:56 AM (12 years ago)
Author:
Christian Eder
Branches:
(u'fieker-DuVal', '117eb8c30fc9e991c4decca4832b1d19036c4c65')(u'spielwiese', 'b4f17ed1d25f93d46dbe29e4b499baecc2fd51bb')
Children:
fee33eddc902b0ad109daba1a48c0d83f7329667
Parents:
83be980908d4dc3e33ce00c36b4e4013e3251a00
git-author:
Christian Eder <ederc@mathematik.uni-kl.de>2012-07-02 07:35:56+02:00
git-committer:
Christian Eder <ederc@mathematik.uni-kl.de>2012-07-05 16:12:50+02:00
Message:
removes Galkins ssg implementations since there are too many dependencies
Location:
kernel
Files:
3 edited

Legend:

Unmodified
Added
Removed

  • kernel/kstd1.cc

    r83be980 r1bc7d4a  
    20052005        r=sba(F,Q,*w,hilb,strat);
    20062006      else
    2007                 if (arri == 2)
    2008                 {
    2009                         r=ssg(F,Q,NULL,hilb,strat);
    2010                 }
    2011                 if (arri == 3)
    2012                 {
    2013                         r=ssgnoninc(F,Q,NULL,hilb,strat);
    2014                 }
    2015                 if (arri == 4)
    2016                 {
    2017                         r=ssgincschreyer(F,Q,NULL,hilb,strat);
    2018                 }
    2019                 else
    2020                 {
    2021                         r=sba(F,Q,NULL,hilb,strat);
    2022                 }
     2007                          r=sba(F,Q,NULL,hilb,strat);
    20232008    }
    20242009  }

  • kernel/kstd2.cc

    r83be980 r1bc7d4a  
    14781478
    14791479  return (strat->Shdl);
    1480 }
    1481 ideal ssgincschreyer (ideal F, ideal Q,intvec *w,intvec *hilb,kStrategy strat)
    1482 {
    1483         int
    1484                 time_interred = 0, time_prepare = 0, time_reduction_search = 0, time_reduction = 0,
    1485                 time_add_r = 0, time_filter_b = 0, time_add_b1_testings = 0, time_add_b1_insertion = 0,
    1486                 time_add_b2 = 0;
    1487 
    1488         time_from_last_call();
    1489         int current_input_idx = 0;
    1490         while (F->m[current_input_idx] == NULL && current_input_idx < IDELEMS(F))
    1491         {
    1492                 ++current_input_idx;
    1493         }
    1494         ideal I0 = idInit(1);
    1495         if (current_input_idx >= IDELEMS(F))
    1496         {
    1497                 return I0;
    1498         }
    1499         I0->m[0] = pCopy(F->m[current_input_idx]);
    1500         int zero_reductions = 0;
    1501         LabeledPoly::GvwLess gvw_less;
    1502   poly pEins = pOne();
    1503         for (current_input_idx +=1; current_input_idx < IDELEMS(F); ++current_input_idx)
    1504         {
    1505                 if (!F->m[current_input_idx]) continue;
    1506                 idDelDiv(I0);
    1507                 idSkipZeroes(I0);
    1508 #ifndef SSG_NO_INTERRED
    1509                 std::sort(I0->m, I0->m+IDELEMS(I0), LmCompareForNonZeroPolys());
    1510                
    1511                 ideal I0_tail_reduced = idInit(IDELEMS(I0));
    1512                 //tail reducton
    1513                 for(int n0 = IDELEMS(I0) - 1; n0 > 0; --n0)
    1514                 {
    1515                         poly p_old = NULL;
    1516                         std::swap(p_old,I0->m[n0]);
    1517                         poly p_new = kNF(I0, Q, p_old);
    1518                         pDelete(&p_old);
    1519                         I0_tail_reduced->m[n0] = p_new;
    1520                 }
    1521                 std::swap(I0_tail_reduced->m[0], I0->m[0]);
    1522                 idDelete(&I0);
    1523                 I0 = I0_tail_reduced;
    1524 #endif
    1525                 time_interred += time_from_last_call();
    1526                 LPolysByGvw R;
    1527                 LPolysMuledBySig B;
    1528     //LabeledPoly* p = LabeledPoly::CreateOneSig(F->m[current_input_idx]);
    1529     LabeledPoly* p = LabeledPoly::CreateOneSig(F->m[current_input_idx],
    1530     current_input_idx);
    1531                 for(int n0 = IDELEMS(I0) - 1; n0 >=0; --n0)
    1532                 {
    1533                         R.push_back(LabeledPoly::CreateZeroSig(I0->m[n0]));
    1534                 }
    1535                 const LPolysByGvw::iterator first_zero_sig = R.begin();
    1536     /*
    1537                 for(int n0 = IDELEMS(I0) - 1; n0 >=0; --n0)
    1538                 {
    1539       for (int m0 = n0-1; m0>=0; --m0)
    1540       {
    1541                           R.push_front(LabeledPoly::CreateZeroPoly(I0->m[n0], n0, I0->m[m0], m0));
    1542       }
    1543                 }
    1544     */
    1545                 for(int n0 = IDELEMS(I0) - 1; n0 >=0; --n0)
    1546                 {
    1547       //R.push_front(LabeledPoly::CreateZeroPoly(I0->m[n0]));
    1548                         R.push_front(LabeledPoly::CreateZeroPoly(I0->m[n0],current_input_idx+1,F->m[current_input_idx]));
    1549                 }
    1550                                 /*
    1551         printf("\nR-init = \n");
    1552                                 for(LPolysByGvw::iterator ir = R.begin(); ir != R.end(); ++ir)
    1553                                 {
    1554                                         printf("p = ");pWrite((*ir)->p_);
    1555                                         printf("s = ");pWrite((*ir)->s_monom_);
    1556                                 }
    1557         */
    1558     LabeledPolyMuled bnew;
    1559     bnew.Init();
    1560     bnew.FillBy(pEins, *p);
    1561     LPolysByGvw::iterator known_gvw_greater_p = first_zero_sig;
    1562     /*
    1563     const LPolysByGvw::iterator p_insert_pos =
    1564       R.insert(known_gvw_greater_p, p);
    1565     */
    1566     bool rejected = false;
    1567                 SigMuledMinimumFinder b_min_finder(B);
    1568     /*
    1569     for(LPolysByGvw::const_iterator ir2 = R.begin();ir2 != p_insert_pos;++ir2)
    1570     {
    1571       if ((*ir2)->sig_divides(bnew))
    1572       {
    1573         rejected = true;
    1574         break;
    1575       }
    1576     }
    1577     */
    1578     if (!rejected)
    1579     {
    1580       B.push_back(bnew);
    1581       b_min_finder.UpdateBy(B.size() - 1);
    1582       bnew.Init();
    1583       //time_add_b1_insertion += time_from_last_call();
    1584     }
    1585     bnew.Release();
    1586                 time_prepare += time_from_last_call();
    1587     // first test in B
    1588                         if (b_min_finder.minimum_idx_ == SigMuledMinimumFinder::NO_ELEMENTS)
    1589                         {
    1590                                 break;
    1591                         }else{
    1592                                 p = LabeledPoly::ConvertFromAndRelease(B[b_min_finder.minimum_idx_]);
    1593                                 B.erase_and_move_from_back(b_min_finder.minimum_idx_);
    1594                         }
    1595                 while(1)
    1596                 {
    1597                         bool reduced_to_zero = false;
    1598                         LPolysByGvw::iterator known_gvw_greater_p = first_zero_sig;
    1599 #if 1
    1600       /*
    1601                         if (n ==  IDELEMS(F) - 1)
    1602                         {
    1603       */
    1604         /*
    1605         printf("\nR = \n");
    1606                                 for(LPolysByGvw::iterator ir = R.begin(); ir != R.end(); ++ir)
    1607                                 {
    1608                                         printf("p = ");pWrite((*ir)->p_);
    1609                                         printf("s = ");pWrite((*ir)->s_monom_);
    1610                                 }
    1611                                 printf("B = \n");
    1612                                 for(LPolysMuledBySig::iterator ib = B.begin(); ib != B.end(); ++ib)
    1613                                 {
    1614                                         printf("smuled = ");pWrite((*ib).smuled_monom_);
    1615           //printf("s = ");pWrite((*ib)->not_muled_.s_monom_);
    1616                                 }
    1617         */
    1618                         /*
    1619       }
    1620       */
    1621 #endif
    1622                         while(1)
    1623                         {
    1624         //printf("p to reduce = ");pWrite (p->p_);
    1625                                 bool was_reduced = false;
    1626                                 LPolysByGvw::iterator ir = --R.end();
    1627                                 while(1)
    1628                                 {
    1629                                         was_reduced = p->can_reduce_by(*ir);
    1630                                         if (was_reduced)
    1631                                         {
    1632                                                 time_reduction_search += time_from_last_call();
    1633                                                 p->reduce_by(*ir);
    1634                                                 time_reduction += time_from_last_call();
    1635                                                 break;
    1636                                         }
    1637                                         if (ir == known_gvw_greater_p) break;
    1638                                         --ir;
    1639                                 }
    1640                                 if (!was_reduced && ir != R.begin())
    1641                                 {
    1642                                         --ir;
    1643                                         while(1)
    1644                                         {
    1645                                                 if (!gvw_less(p, *ir))
    1646                                                 {
    1647                                                         ++ir;
    1648                                                         break;
    1649                                                 }
    1650                                                 was_reduced = p->can_reduce_by(*ir);
    1651                                                 if (was_reduced)
    1652                                                 {
    1653                                                         time_reduction_search += time_from_last_call();
    1654                                                         p->reduce_by(*ir);
    1655                                                         time_reduction += time_from_last_call();
    1656                                                         break;
    1657                                                 }
    1658                                                 if (ir == R.begin()) break;
    1659                                                 --ir;
    1660                                         }
    1661                                         known_gvw_greater_p = ir;
    1662                                 }
    1663                                 if (!was_reduced) break;
    1664                                 reduced_to_zero = p->p_ == NULL;
    1665                                 if (reduced_to_zero)
    1666                                 {
    1667                                         ++zero_reductions;
    1668                                         known_gvw_greater_p = R.begin();
    1669                                         break;
    1670                                 }
    1671                         }
    1672                         time_reduction_search += time_from_last_call();
    1673                         const LPolysByGvw::iterator p_insert_pos =
    1674                                 R.insert(known_gvw_greater_p, p);
    1675                         time_add_r += time_from_last_call();
    1676                         SigMuledMinimumFinder b_min_finder(B);
    1677                         for(int i=0;i<B.size();)
    1678                         {
    1679                                 LabeledPolyMuled& b = B[i];
    1680                                 if (p->sig_divides(b) && gvw_less(p,b.not_muled_))
    1681                                 {
    1682                                         b.Release();
    1683                                         B.erase_and_move_from_back(i);
    1684                                 }else
    1685                                 {
    1686                                         b_min_finder.UpdateBy(i);
    1687                                         ++i;
    1688                                 }
    1689                         }
    1690                         time_filter_b += time_from_last_call();
    1691                         if (!reduced_to_zero)
    1692                         {
    1693                                 LabeledPolyMuled bnew;
    1694                                 bnew.Init();
    1695                                 for(LPolysByGvw::const_iterator ir = --R.end();ir != p_insert_pos;--ir)
    1696                                 {
    1697                                         bnew.FillBy((*ir)->p_, *p);
    1698                                         bool rejected = false;
    1699                                         for(LPolysByGvw::const_iterator ir2 = R.begin();ir2 != p_insert_pos;++ir2)
    1700                                         {
    1701                                                 if ((*ir2)->sig_divides(bnew))
    1702                                                 {
    1703                                                         rejected = true;
    1704                                                         break;
    1705                                                 }
    1706                                         }
    1707                                         time_add_b1_testings += time_from_last_call();
    1708                                         if (!rejected)
    1709                                         {
    1710                                                 B.push_back(bnew);
    1711                                                 b_min_finder.UpdateBy(B.size() - 1);
    1712                                                 bnew.Init();
    1713                                                 time_add_b1_insertion += time_from_last_call();
    1714                                         }
    1715                                 }
    1716                                 for(LPolysByGvw::const_iterator ir = R.begin();ir != p_insert_pos;++ir)
    1717                                 {
    1718                                         if (!gvw_less(*ir, p)) break;
    1719                                         if ((*ir)->p_ == NULL) continue;
    1720                                         bool rejected = false;
    1721                                         bnew.FillBy(p->p_, *(*ir));
    1722                                         for(LPolysByGvw::const_iterator ir2 = R.begin();ir2 != ir;++ir2)
    1723                                         {
    1724                                                 if ((*ir2)->sig_divides(bnew))
    1725                                                 {
    1726                                                         rejected = true;
    1727                                                         break;
    1728                                                 }
    1729                                         }
    1730                                         if (!rejected)
    1731                                         {
    1732                                                 B.push_back(bnew);
    1733                                                 b_min_finder.UpdateBy(B.size() - 1);
    1734                                                 bnew.Init();
    1735                                         }
    1736                                 }
    1737                                 bnew.Release();
    1738                                 time_add_b2 += time_from_last_call();
    1739                         }
    1740       /*
    1741                                 printf("B = \n");
    1742                                 for(LPolysMuledBySig::iterator ib = B.begin(); ib != B.end(); ++ib)
    1743                                 {
    1744                                         printf("smuled = ");pWrite((*ib).smuled_monom_);
    1745           //printf("s = ");pWrite((*ib).not_muled_.s_monom_);
    1746                                 }
    1747         */
    1748                         if (b_min_finder.minimum_idx_ == SigMuledMinimumFinder::NO_ELEMENTS)
    1749                         {
    1750                                 break;
    1751                         }else{
    1752                                 p = LabeledPoly::ConvertFromAndRelease(B[b_min_finder.minimum_idx_]);
    1753                                 B.erase_and_move_from_back(b_min_finder.minimum_idx_);
    1754                         }
    1755                 }
    1756                 idDelete(&I0);
    1757                 I0 = idInit(R.size());
    1758                 int i0_idx = 0;
    1759                 for(LPolysByGvw::iterator ir = R.begin();ir != R.end();++ir,++i0_idx)
    1760                 {
    1761                         std::swap(I0->m[i0_idx], (*ir)->p_);
    1762                         delete (*ir);
    1763                        
    1764                 }
    1765                 R.clear();
    1766         }
    1767 
    1768         printf("time time_interred = %d\n", time_interred);
    1769         printf("time time_prepare = %d\n", time_prepare);
    1770         printf("time time_reduction_search = %d\n", time_reduction_search);
    1771         printf("time time_reduction = %d\n", time_reduction);
    1772         printf("time time_add_r = %d\n", time_add_r);
    1773         printf("time time_filter_b = %d\n", time_filter_b);
    1774         printf("time time_add_b1_testings = %d\n", time_add_b1_testings);
    1775         printf("time time_add_b1_insertion = %d\n", time_add_b1_insertion);
    1776         printf("time time_add_b2 = %d\n", time_add_b2);
    1777 
    1778         printf("ZERO REDUCTIONS: %d\n", zero_reductions);
    1779 
    1780         return I0;
    1781 }
    1782 ideal ssgnoninc (ideal F, ideal Q,intvec *w,intvec *hilb,kStrategy strat)
    1783 {
    1784   int
    1785     time_interred = 0, time_prepare = 0, time_reduction_search = 0, time_reduction = 0,
    1786                   time_add_r = 0, time_filter_b = 0, time_add_b1_testings = 0, time_add_b1_insertion = 0,
    1787                   time_add_b2 = 0;
    1788 
    1789   time_from_last_call();
    1790   int current_input_idx = 0;
    1791   while (F->m[current_input_idx] == NULL && current_input_idx < IDELEMS(F))
    1792   {
    1793     ++current_input_idx;
    1794   }
    1795   ideal I0 = idInit(1);
    1796   if (current_input_idx >= IDELEMS(F))
    1797   {
    1798     return I0;
    1799   }
    1800   I0->m[0] = pCopy(F->m[current_input_idx]);
    1801   int zero_reductions = 0;
    1802   LabeledPoly::GvwLess gvw_less;
    1803   poly pEins = pOne();
    1804   // made these global for non-incremental computation
    1805   // -------------------------------------------------
    1806   LPolysByGvw R;
    1807   LPolysMuledBySig B;
    1808   SigMuledMinimumFinder b_min_finder(B);
    1809   LabeledPoly* p;
    1810   LPolysByGvw::iterator first_zero_sig_temp = R.begin();
    1811   bool set_first_zero_sig                   = true;
    1812   // -------------------------------------------------
    1813   for (current_input_idx +=1; current_input_idx < IDELEMS(F); ++current_input_idx)
    1814   {
    1815     if (!F->m[current_input_idx]) continue;
    1816     idDelDiv(I0);
    1817     idSkipZeroes(I0);
    1818 #ifndef SSG_NO_INTERRED
    1819     std::sort(I0->m, I0->m+IDELEMS(I0), LmCompareForNonZeroPolys());
    1820 
    1821     ideal I0_tail_reduced = idInit(IDELEMS(I0));
    1822     //tail reducton
    1823     for(int n0 = IDELEMS(I0) - 1; n0 > 0; --n0)
    1824     {
    1825       poly p_old = NULL;
    1826       std::swap(p_old,I0->m[n0]);
    1827       poly p_new = kNF(I0, Q, p_old);
    1828       pDelete(&p_old);
    1829       I0_tail_reduced->m[n0] = p_new;
    1830     }
    1831     std::swap(I0_tail_reduced->m[0], I0->m[0]);
    1832     idDelete(&I0);
    1833     I0 = I0_tail_reduced;
    1834 #endif
    1835     time_interred += time_from_last_call();
    1836     //LPolysByGvw R;
    1837     //LPolysMuledBySig B;
    1838     //LabeledPoly* p = LabeledPoly::CreateOneSig(F->m[current_input_idx]);
    1839     p = LabeledPoly::CreateOneSig(F->m[current_input_idx],
    1840         current_input_idx);
    1841     for(int n0 = IDELEMS(I0) - 1; n0 >=0; --n0)
    1842     {
    1843       R.push_back(LabeledPoly::CreateZeroSig(I0->m[n0]));
    1844     }
    1845     //const LPolysByGvw::iterator first_zero_sig = R.begin();
    1846     if (set_first_zero_sig)
    1847     {
    1848       first_zero_sig_temp = R.begin();
    1849       set_first_zero_sig  = false;
    1850     }
    1851     /*
    1852        for(int n0 = IDELEMS(I0) - 1; n0 >=0; --n0)
    1853        {
    1854        for (int m0 = n0-1; m0>=0; --m0)
    1855        {
    1856        R.push_front(LabeledPoly::CreateZeroPoly(I0->m[n0], n0, I0->m[m0], m0));
    1857        }
    1858        }
    1859        */
    1860     for(int n0 = IDELEMS(I0) - 1; n0 >=0; --n0)
    1861     {
    1862       //R.push_front(LabeledPoly::CreateZeroPoly(I0->m[n0]));
    1863       R.push_front(LabeledPoly::CreateZeroPoly(I0->m[n0],current_input_idx+1,F->m[current_input_idx]));
    1864     }
    1865     /*
    1866        printf("\nR-init = \n");
    1867        for(LPolysByGvw::iterator ir = R.begin(); ir != R.end(); ++ir)
    1868        {
    1869        printf("p = ");pWrite((*ir)->p_);
    1870        printf("s = ");pWrite((*ir)->s_monom_);
    1871        }
    1872        */
    1873     LabeledPolyMuled bnew;
    1874     bnew.Init();
    1875     bnew.FillBy(pEins, *p);
    1876     LPolysByGvw::iterator known_gvw_greater_p = first_zero_sig_temp;
    1877     /*
    1878        const LPolysByGvw::iterator p_insert_pos =
    1879        R.insert(known_gvw_greater_p, p);
    1880        */
    1881     bool rejected = false;
    1882     //SigMuledMinimumFinder b_min_finder(B);
    1883     //SigMuledMinimumFinder b_min_finder(B);
    1884     /*
    1885        for(LPolysByGvw::const_iterator ir2 = R.begin();ir2 != p_insert_pos;++ir2)
    1886        {
    1887        if ((*ir2)->sig_divides(bnew))
    1888        {
    1889        rejected = true;
    1890        break;
    1891        }
    1892        }
    1893        */
    1894     if (!rejected)
    1895     {
    1896       B.push_back(bnew);
    1897       b_min_finder.UpdateBy(B.size() - 1);
    1898       bnew.Init();
    1899       //time_add_b1_insertion += time_from_last_call();
    1900     }
    1901     bnew.Release();
    1902   }
    1903   const LPolysByGvw::iterator first_zero_sig = first_zero_sig_temp;
    1904   //SigMuledMinimumFinder b_min_finder(B);
    1905   /*
    1906   printf("B = \n");
    1907   for(LPolysMuledBySig::iterator ib = B.begin(); ib != B.end(); ++ib)
    1908   {
    1909     printf("smuled = ");pWrite((*ib).smuled_monom_);
    1910     //printf("s = ");pWrite((ib)->not_muled_.s_monom_);
    1911   }
    1912   */
    1913   time_prepare += time_from_last_call();
    1914   // first test in B
    1915   if (b_min_finder.minimum_idx_ == SigMuledMinimumFinder::NO_ELEMENTS)
    1916   {
    1917     return I0;
    1918     //break;
    1919   }else{
    1920     p = LabeledPoly::ConvertFromAndRelease(B[b_min_finder.minimum_idx_]);
    1921     B.erase_and_move_from_back(b_min_finder.minimum_idx_);
    1922   }
    1923   while(1)
    1924   {
    1925     bool reduced_to_zero = false;
    1926     LPolysByGvw::iterator known_gvw_greater_p = first_zero_sig;
    1927 #if 1
    1928     /*
    1929        if (n ==  IDELEMS(F) - 1)
    1930        {
    1931        */
    1932     /*
    1933        printf("\nR = \n");
    1934        for(LPolysByGvw::iterator ir = R.begin(); ir != R.end(); ++ir)
    1935        {
    1936        printf("p = ");pWrite((*ir)->p_);
    1937        printf("s = ");pWrite((*ir)->s_monom_);
    1938        }
    1939        printf("B = \n");
    1940        for(LPolysMuledBySig::iterator ib = B.begin(); ib != B.end(); ++ib)
    1941        {
    1942        printf("smuled = ");pWrite((*ib).smuled_monom_);
    1943     //printf("s = ");pWrite((*ib)->not_muled_.s_monom_);
    1944     }
    1945     */
    1946     /*
    1947        }
    1948        */
    1949 #endif
    1950     while(1)
    1951     {
    1952       //printf("p to reduce = ");pWrite (p->p_);
    1953       bool was_reduced = false;
    1954       LPolysByGvw::iterator ir = --R.end();
    1955       while(1)
    1956       {
    1957         was_reduced = p->can_reduce_by(*ir);
    1958         if (was_reduced)
    1959         {
    1960           time_reduction_search += time_from_last_call();
    1961           p->reduce_by(*ir);
    1962           time_reduction += time_from_last_call();
    1963           break;
    1964         }
    1965         if (ir == known_gvw_greater_p) break;
    1966         --ir;
    1967       }
    1968       if (!was_reduced && ir != R.begin())
    1969       {
    1970         --ir;
    1971         while(1)
    1972         {
    1973           if (!gvw_less(p, *ir))
    1974           {
    1975             ++ir;
    1976             break;
    1977           }
    1978           was_reduced = p->can_reduce_by(*ir);
    1979           if (was_reduced)
    1980           {
    1981             time_reduction_search += time_from_last_call();
    1982             p->reduce_by(*ir);
    1983             time_reduction += time_from_last_call();
    1984             break;
    1985           }
    1986           if (ir == R.begin()) break;
    1987           --ir;
    1988         }
    1989         known_gvw_greater_p = ir;
    1990       }
    1991       if (!was_reduced) break;
    1992       reduced_to_zero = p->p_ == NULL;
    1993       if (reduced_to_zero)
    1994       {
    1995         ++zero_reductions;
    1996         known_gvw_greater_p = R.begin();
    1997         break;
    1998       }
    1999     }
    2000     time_reduction_search += time_from_last_call();
    2001     const LPolysByGvw::iterator p_insert_pos =
    2002       R.insert(known_gvw_greater_p, p);
    2003     time_add_r += time_from_last_call();
    2004     SigMuledMinimumFinder b_min_finder(B);
    2005     for(int i=0;i<B.size();)
    2006     {
    2007       LabeledPolyMuled& b = B[i];
    2008       if (p->sig_divides(b) && gvw_less(p,b.not_muled_))
    2009       {
    2010         b.Release();
    2011         B.erase_and_move_from_back(i);
    2012       }else
    2013       {
    2014         b_min_finder.UpdateBy(i);
    2015         ++i;
    2016       }
    2017     }
    2018     time_filter_b += time_from_last_call();
    2019     if (!reduced_to_zero)
    2020     {
    2021       LabeledPolyMuled bnew;
    2022       bnew.Init();
    2023        /*
    2024         printf("\nR = \n");
    2025        for(LPolysByGvw::iterator ir = R.begin(); ir != R.end(); ++ir)
    2026        {
    2027        printf("p = ");pWrite((*ir)->p_);
    2028        printf("s = ");pWrite((*ir)->s_monom_);
    2029        }
    2030        */
    2031       for(LPolysByGvw::const_iterator ir = --R.end();ir != p_insert_pos;--ir)
    2032       {
    2033         //printf ("pNew = "); pWrite(p->p_);
    2034         bnew.FillBy((*ir)->p_, *p);
    2035         bool rejected = false;
    2036         for(LPolysByGvw::const_iterator ir2 = R.begin();ir2 != p_insert_pos;++ir2)
    2037         {
    2038           if ((*ir2)->sig_divides(bnew))
    2039           {
    2040             rejected = true;
    2041             break;
    2042           }
    2043         }
    2044         time_add_b1_testings += time_from_last_call();
    2045         if (!rejected)
    2046         {
    2047           B.push_back(bnew);
    2048           b_min_finder.UpdateBy(B.size() - 1);
    2049           bnew.Init();
    2050           time_add_b1_insertion += time_from_last_call();
    2051         }
    2052       }
    2053       for(LPolysByGvw::const_iterator ir = R.begin();ir != p_insert_pos;++ir)
    2054       {
    2055         if (!gvw_less(*ir, p)) break;
    2056         if ((*ir)->p_ == NULL) continue;
    2057         bool rejected = false;
    2058         bnew.FillBy(p->p_, *(*ir));
    2059         for(LPolysByGvw::const_iterator ir2 = R.begin();ir2 != ir;++ir2)
    2060         {
    2061           if ((*ir2)->sig_divides(bnew))
    2062           {
    2063             rejected = true;
    2064             break;
    2065           }
    2066         }
    2067         if (!rejected)
    2068         {
    2069           B.push_back(bnew);
    2070           b_min_finder.UpdateBy(B.size() - 1);
    2071           bnew.Init();
    2072         }
    2073       }
    2074       bnew.Release();
    2075       time_add_b2 += time_from_last_call();
    2076     }
    2077     /*
    2078        printf("B = \n");
    2079        for(LPolysMuledBySig::iterator ib = B.begin(); ib != B.end(); ++ib)
    2080        {
    2081        printf("smuled = ");pWrite((*ib).smuled_monom_);
    2082     //printf("s = ");pWrite((*ib).not_muled_.s_monom_);
    2083     }
    2084     */
    2085     if (b_min_finder.minimum_idx_ == SigMuledMinimumFinder::NO_ELEMENTS)
    2086     {
    2087       break;
    2088     }else{
    2089       p = LabeledPoly::ConvertFromAndRelease(B[b_min_finder.minimum_idx_]);
    2090       B.erase_and_move_from_back(b_min_finder.minimum_idx_);
    2091     }
    2092   }
    2093   idDelete(&I0);
    2094   I0 = idInit(R.size());
    2095   int i0_idx = 0;
    2096   for(LPolysByGvw::iterator ir = R.begin();ir != R.end();++ir,++i0_idx)
    2097   {
    2098     std::swap(I0->m[i0_idx], (*ir)->p_);
    2099     delete (*ir);
    2100 
    2101   }
    2102   R.clear();
    2103 
    2104   printf("time time_interred = %d\n", time_interred);
    2105   printf("time time_prepare = %d\n", time_prepare);
    2106   printf("time time_reduction_search = %d\n", time_reduction_search);
    2107   printf("time time_reduction = %d\n", time_reduction);
    2108   printf("time time_add_r = %d\n", time_add_r);
    2109   printf("time time_filter_b = %d\n", time_filter_b);
    2110   printf("time time_add_b1_testings = %d\n", time_add_b1_testings);
    2111   printf("time time_add_b1_insertion = %d\n", time_add_b1_insertion);
    2112   printf("time time_add_b2 = %d\n", time_add_b2);
    2113 
    2114   printf("ZERO REDUCTIONS: %d\n", zero_reductions);
    2115 
    2116   return I0;
    2117 }
    2118 ideal ssg (ideal F, ideal Q,intvec *w,intvec *hilb,kStrategy strat)
    2119 {
    2120         int
    2121                 time_interred = 0, time_prepare = 0, time_reduction_search = 0, time_reduction = 0,
    2122                 time_add_r = 0, time_filter_b = 0, time_add_b1_testings = 0, time_add_b1_insertion = 0,
    2123                 time_add_b2 = 0;
    2124 
    2125         time_from_last_call();
    2126         int current_input_idx = 0;
    2127         while (F->m[current_input_idx] == NULL && current_input_idx < IDELEMS(F))
    2128         {
    2129                 ++current_input_idx;
    2130         }
    2131         ideal I0 = idInit(1);
    2132         if (current_input_idx >= IDELEMS(F))
    2133         {
    2134                 return I0;
    2135         }
    2136         I0->m[0] = pCopy(F->m[current_input_idx]);
    2137         int zero_reductions = 0;
    2138         LabeledPoly::GvwLess gvw_less;
    2139         for (current_input_idx +=1; current_input_idx < IDELEMS(F); ++current_input_idx)
    2140         {
    2141                 if (!F->m[current_input_idx]) continue;
    2142                 idDelDiv(I0);
    2143                 idSkipZeroes(I0);
    2144 #ifndef SSG_NO_INTERRED
    2145                 std::sort(I0->m, I0->m+IDELEMS(I0), LmCompareForNonZeroPolys());
    2146                
    2147                 ideal I0_tail_reduced = idInit(IDELEMS(I0));
    2148                 //tail reducton
    2149                 for(int n0 = IDELEMS(I0) - 1; n0 > 0; --n0)
    2150                 {
    2151                         poly p_old = NULL;
    2152                         std::swap(p_old,I0->m[n0]);
    2153                         poly p_new = kNF(I0, Q, p_old);
    2154                         pDelete(&p_old);
    2155                         I0_tail_reduced->m[n0] = p_new;
    2156                 }
    2157                 std::swap(I0_tail_reduced->m[0], I0->m[0]);
    2158                 idDelete(&I0);
    2159                 I0 = I0_tail_reduced;
    2160 #endif
    2161                 time_interred += time_from_last_call();
    2162                 LPolysByGvw R;
    2163                 LPolysMuledBySig B;
    2164                 LabeledPoly* p = LabeledPoly::CreateOneSig(F->m[current_input_idx]);
    2165                 for(int n0 = IDELEMS(I0) - 1; n0 >=0; --n0)
    2166                 {
    2167                         R.push_back(LabeledPoly::CreateZeroSig(I0->m[n0]));
    2168                 }
    2169                 const LPolysByGvw::iterator first_zero_sig = R.begin();
    2170                 for(int n0 = IDELEMS(I0) - 1; n0 >=0; --n0)
    2171                 {
    2172                         R.push_front(LabeledPoly::CreateZeroPoly(I0->m[n0]));
    2173                 }
    2174     /*
    2175                                 printf("\nR-init = \n");
    2176                                 for(LPolysByGvw::iterator ir = R.begin(); ir != R.end(); ++ir)
    2177                                 {
    2178                                         printf("p = ");pWrite((*ir)->p_);
    2179                                         printf("s = ");pWrite((*ir)->s_monom_);
    2180                                 }
    2181     */
    2182                 time_prepare += time_from_last_call();
    2183                 while(1)
    2184                 {
    2185                         bool reduced_to_zero = false;
    2186                         LPolysByGvw::iterator known_gvw_greater_p = first_zero_sig;
    2187 #if 1
    2188       /*
    2189                         if (n ==  IDELEMS(F) - 1)
    2190                         {
    2191       */
    2192                                 /*
    2193         printf("\nR = \n");
    2194                                 for(LPolysByGvw::iterator ir = R.begin(); ir != R.end(); ++ir)
    2195                                 {
    2196                                         printf("p = ");pWrite((*ir)->p_);
    2197                                         printf("s = ");pWrite((*ir)->s_monom_);
    2198                                 }
    2199                                 printf("B = \n");
    2200                                 for(LPolysMuledBySig::iterator ib = B.begin(); ib != B.end(); ++ib)
    2201                                 {
    2202                                         printf("smuled = ");pWrite((*ib).smuled_monom_);
    2203           //printf("s = ");pWrite((*ib)->not_muled_.s_monom_);
    2204                                 }
    2205         */
    2206                         /*
    2207       }
    2208       */
    2209 #endif
    2210                         while(1)
    2211                         {
    2212                                 bool was_reduced = false;
    2213                                 LPolysByGvw::iterator ir = --R.end();
    2214         //printf("p to reduce = ");pWrite (p->p_);
    2215                                 while(1)
    2216                                 {
    2217                                         was_reduced = p->can_reduce_by(*ir);
    2218                                         if (was_reduced)
    2219                                         {
    2220                                                 time_reduction_search += time_from_last_call();
    2221                                                 p->reduce_by(*ir);
    2222                                                 time_reduction += time_from_last_call();
    2223                                                 break;
    2224                                         }
    2225                                         if (ir == known_gvw_greater_p) break;
    2226                                         --ir;
    2227                                 }
    2228                                 if (!was_reduced && ir != R.begin())
    2229                                 {
    2230                                         --ir;
    2231                                         while(1)
    2232                                         {
    2233                                                 if (!gvw_less(p, *ir))
    2234                                                 {
    2235                                                         ++ir;
    2236                                                         break;
    2237                                                 }
    2238                                                 was_reduced = p->can_reduce_by(*ir);
    2239                                                 if (was_reduced)
    2240                                                 {
    2241                                                         time_reduction_search += time_from_last_call();
    2242                                                         p->reduce_by(*ir);
    2243                                                         time_reduction += time_from_last_call();
    2244                                                         break;
    2245                                                 }
    2246                                                 if (ir == R.begin()) break;
    2247                                                 --ir;
    2248                                         }
    2249                                         known_gvw_greater_p = ir;
    2250                                 }
    2251                                 if (!was_reduced) break;
    2252                                 reduced_to_zero = p->p_ == NULL;
    2253                                 if (reduced_to_zero)
    2254                                 {
    2255                                         ++zero_reductions;
    2256                                         known_gvw_greater_p = R.begin();
    2257                                         break;
    2258                                 }
    2259                         }
    2260                         time_reduction_search += time_from_last_call();
    2261                         const LPolysByGvw::iterator p_insert_pos =
    2262                                 R.insert(known_gvw_greater_p, p);
    2263                         time_add_r += time_from_last_call();
    2264                         SigMuledMinimumFinder b_min_finder(B);
    2265                         for(int i=0;i<B.size();)
    2266                         {
    2267                                 LabeledPolyMuled& b = B[i];
    2268                                 if (p->sig_divides(b) && gvw_less(p,b.not_muled_))
    2269                                 {
    2270                                         b.Release();
    2271                                         B.erase_and_move_from_back(i);
    2272                                 }else
    2273                                 {
    2274                                         b_min_finder.UpdateBy(i);
    2275                                         ++i;
    2276                                 }
    2277                         }
    2278                         time_filter_b += time_from_last_call();
    2279                         if (!reduced_to_zero)
    2280                         {
    2281                                 LabeledPolyMuled bnew;
    2282                                 bnew.Init();
    2283                                 for(LPolysByGvw::const_iterator ir = --R.end();ir != p_insert_pos;--ir)
    2284                                 {
    2285                                         bnew.FillBy((*ir)->p_, *p);
    2286                                         bool rejected = false;
    2287                                         for(LPolysByGvw::const_iterator ir2 = R.begin();ir2 != p_insert_pos;++ir2)
    2288                                         {
    2289                                                 if ((*ir2)->sig_divides(bnew))
    2290                                                 {
    2291                                                         rejected = true;
    2292                                                         break;
    2293                                                 }
    2294                                         }
    2295                                         time_add_b1_testings += time_from_last_call();
    2296                                         if (!rejected)
    2297                                         {
    2298                                                 B.push_back(bnew);
    2299                                                 b_min_finder.UpdateBy(B.size() - 1);
    2300                                                 bnew.Init();
    2301                                                 time_add_b1_insertion += time_from_last_call();
    2302                                         }
    2303                                 }
    2304                                 for(LPolysByGvw::const_iterator ir = R.begin();ir != p_insert_pos;++ir)
    2305                                 {
    2306                                         if (!gvw_less(*ir, p)) break;
    2307                                         if ((*ir)->p_ == NULL) continue;
    2308                                         bool rejected = false;
    2309                                         bnew.FillBy(p->p_, *(*ir));
    2310                                         for(LPolysByGvw::const_iterator ir2 = R.begin();ir2 != ir;++ir2)
    2311                                         {
    2312                                                 if ((*ir2)->sig_divides(bnew))
    2313                                                 {
    2314                                                         rejected = true;
    2315                                                         break;
    2316                                                 }
    2317                                         }
    2318                                         if (!rejected)
    2319                                         {
    2320                                                 B.push_back(bnew);
    2321                                                 b_min_finder.UpdateBy(B.size() - 1);
    2322                                                 bnew.Init();
    2323                                         }
    2324                                 }
    2325                                 bnew.Release();
    2326                                 time_add_b2 += time_from_last_call();
    2327                         }
    2328                                 /*
    2329         printf("B = \n");
    2330                                 for(LPolysMuledBySig::iterator ib = B.begin(); ib != B.end(); ++ib)
    2331                                 {
    2332                                         printf("smuled = ");pWrite((*ib).smuled_monom_);
    2333           //printf("s = ");pWrite((*ib).not_muled_.s_monom_);
    2334                                 }
    2335         */
    2336                         if (b_min_finder.minimum_idx_ == SigMuledMinimumFinder::NO_ELEMENTS)
    2337                         {
    2338                                 break;
    2339                         }else{
    2340                                 p = LabeledPoly::ConvertFromAndRelease(B[b_min_finder.minimum_idx_]);
    2341                                 B.erase_and_move_from_back(b_min_finder.minimum_idx_);
    2342                         }
    2343      
    2344                 }
    2345                 idDelete(&I0);
    2346                 I0 = idInit(R.size());
    2347                 int i0_idx = 0;
    2348                 for(LPolysByGvw::iterator ir = R.begin();ir != R.end();++ir,++i0_idx)
    2349                 {
    2350                         std::swap(I0->m[i0_idx], (*ir)->p_);
    2351                         delete (*ir);
    2352                        
    2353                 }
    2354                 R.clear();
    2355         }
    2356 
    2357         printf("time time_interred = %d\n", time_interred);
    2358         printf("time time_prepare = %d\n", time_prepare);
    2359         printf("time time_reduction_search = %d\n", time_reduction_search);
    2360         printf("time time_reduction = %d\n", time_reduction);
    2361         printf("time time_add_r = %d\n", time_add_r);
    2362         printf("time time_filter_b = %d\n", time_filter_b);
    2363         printf("time time_add_b1_testings = %d\n", time_add_b1_testings);
    2364         printf("time time_add_b1_insertion = %d\n", time_add_b1_insertion);
    2365         printf("time time_add_b2 = %d\n", time_add_b2);
    2366 
    2367         printf("ZERO REDUCTIONS: %d\n", zero_reductions);
    2368 
    2369         return I0;
    23701480}
    23711481ideal sba (ideal F0, ideal Q,intvec *w,intvec *hilb,kStrategy strat)

  • kernel/kutil.h

    r83be980 r1bc7d4a  
    618618ideal bba (ideal F, ideal Q,intvec *w,intvec *hilb,kStrategy strat);
    619619ideal sba (ideal F, ideal Q,intvec *w,intvec *hilb,kStrategy strat);
    620 ideal ssg (ideal F, ideal Q,intvec *w,intvec *hilb,kStrategy strat);
    621 ideal ssgincschreyer (ideal F, ideal Q,intvec *w,intvec *hilb,kStrategy strat);
    622 ideal ssgnoninc (ideal F, ideal Q,intvec *w,intvec *hilb,kStrategy strat);
    623620poly kNF2 (ideal F, ideal Q, poly q, kStrategy strat, int lazyReduce);
    624621ideal kNF2 (ideal F,ideal Q,ideal q, kStrategy strat, int lazyReduce);
Note: See TracChangeset for help on using the changeset viewer.