My Project  debian-1:4.1.1-p2+ds-4
Public Types | Public Member Functions | Private Types | Private Member Functions | Private Attributes | Friends
CReducerFinder Class Reference

#include <syzextra.h>

Public Types

typedef long TComponentKey
 
typedef std::vector< const CLeadingTerm * > TReducers
 

Public Member Functions

 CReducerFinder (const ideal L, const SchreyerSyzygyComputationFlags &flags)
 goes over all leading terms More...
 
void Initialize (const ideal L)
 
 ~CReducerFinder ()
 
poly FindReducer (const poly multiplier, const poly monom, const poly syzterm, const CReducerFinder &checker) const
 
poly FindReducer (const poly product, const poly syzterm, const CReducerFinder &checker) const
 
bool IsDivisible (const poly q) const
 
bool IsNonempty () const
 
int PreProcessTerm (const poly t, CReducerFinder &syzChecker) const
 is the term to be "preprocessed" as lower order term or lead to only reducible syzygies... More...
 
- Public Member Functions inherited from SchreyerSyzygyComputationFlags
 SchreyerSyzygyComputationFlags (idhdl rootRingHdl)
 
 SchreyerSyzygyComputationFlags (const SchreyerSyzygyComputationFlags &attr)
 
void nextSyzygyLayer () const
 

Private Types

typedef std::map< TComponentKey, TReducersCReducersHash
 

Private Member Functions

 CReducerFinder (const CReducerFinder &)
 
void operator= (const CReducerFinder &)
 

Private Attributes

ideal m_L
 only for debug More...
 
CReducersHash m_hash
 

Friends

class CDivisorEnumerator2
 
class CDivisorEnumerator
 

Additional Inherited Members

- Data Fields inherited from SchreyerSyzygyComputationFlags
const int OPT__DEBUG
 output all the intermediate states More...
 
const int OPT__LEAD2SYZ
 ? More...
 
const int OPT__TAILREDSYZ
 Reduce syzygy tails wrt the leading syzygy terms. More...
 
const int OPT__HYBRIDNF
 Use the usual NF's S-poly reduction while dropping lower order terms 2 means - smart selection! More...
 
const int OPT__IGNORETAILS
 ignore tails and compute the pure Schreyer frame More...
 
int OPT__SYZNUMBER
 Syzygy level (within a resolution) More...
 
const int OPT__TREEOUTPUT
 output lifting tree More...
 
const int OPT__SYZCHECK
 CheckSyzygyProperty: TODO. More...
 
const bool OPT__PROT
 TEST_OPT_PROT. More...
 
const int OPT__NOCACHING
 no caching/stores/lookups More...
 
const ring m_rBaseRing
 global base ring More...
 

Detailed Description

Definition at line 264 of file syzextra.h.

Member Typedef Documentation

◆ CReducersHash

Definition at line 276 of file syzextra.h.

◆ TComponentKey

Definition at line 272 of file syzextra.h.

◆ TReducers

Definition at line 273 of file syzextra.h.

Constructor & Destructor Documentation

◆ CReducerFinder() [1/2]

CReducerFinder::CReducerFinder ( const ideal  L,
const SchreyerSyzygyComputationFlags flags 
)

goes over all leading terms

Definition at line 1505 of file syzextra.cc.

1505  :
1507  m_L(const_cast<ideal>(L)), // for debug anyway
1508  m_hash()
1509 {
1510  assume( flags.m_rBaseRing == m_rBaseRing );
1511  if( L != NULL )
1512  Initialize(L);
1513 }

◆ ~CReducerFinder()

CReducerFinder::~CReducerFinder ( )

Definition at line 1470 of file syzextra.cc.

1471 {
1472  for( CReducersHash::const_iterator it = m_hash.begin(); it != m_hash.end(); it++ )
1473  {
1474  const TReducers& v = it->second;
1475  for(TReducers::const_iterator vit = v.begin(); vit != v.end(); vit++ )
1476  delete const_cast<CLeadingTerm*>(*vit);
1477  }
1478 }

◆ CReducerFinder() [2/2]

CReducerFinder::CReducerFinder ( const CReducerFinder )
private

Member Function Documentation

◆ FindReducer() [1/2]

poly CReducerFinder::FindReducer ( const poly  multiplier,
const poly  monom,
const poly  syzterm,
const CReducerFinder checker 
) const

Definition at line 1823 of file syzextra.cc.

1826 {
1827  const ring& r = m_rBaseRing;
1828 
1829  p_Test(multiplier, r);
1830 
1831  CDivisorEnumerator2 itr(*this, multiplier, t);
1832  if( !itr.Reset() )
1833  return NULL;
1834 
1835  // don't care about the module component of multiplier (as it may be the syzygy term)
1836  // product = multiplier * t?
1837 
1838  assume( multiplier != NULL ); assume( t != NULL );
1839 
1840  const ideal& L = m_L; assume( L != NULL ); // for debug/testing only!
1841 
1842  long c = 0;
1843 
1844  if (syzterm != NULL)
1845  c = p_GetComp(syzterm, r) - 1;
1846 
1847  assume( c >= 0 && c < IDELEMS(L) );
1848 
1849  p_Test(multiplier, r);
1850 
1851  const BOOLEAN to_check = (syz_checker.IsNonempty()); // OPT__TAILREDSYZ &&
1852 
1853 // const poly q = p_One(r);
1854  const poly q = p_New(r); pNext(q) = NULL;
1855 
1856  assume( pNext(q) == NULL );
1857 
1858  p_Test(multiplier, r);
1859  while( itr.MoveNext() )
1860  {
1861  assume( itr.Current().CheckLT( L ) ); // ???
1862 
1863  const poly p = itr.Current().lt(); // ???
1864  const int k = itr.Current().label();
1865 
1866  p_ExpVectorSum(q, multiplier, t, r); // q == product == multiplier * t // TODO: do it once?
1867  p_ExpVectorDiff(q, q, p, r); // (LM(product) / LM(L[k]))
1868 
1869  p_SetComp(q, k + 1, r);
1870  p_Setm(q, r);
1871 
1872  p_Test(multiplier, r);
1873 
1874  // cannot allow something like: a*gen(i) - a*gen(i)
1875  if (syzterm != NULL && (k == c))
1876  if (p_ExpVectorEqual(syzterm, q, r))
1877  {
1878  assume( itr.Current().CheckLT( L ) ); // ???
1879  continue;
1880  }
1881 
1882  // while the complement (the fraction) is not reducible by leading syzygies
1883  if( to_check && syz_checker.IsDivisible(q) )
1884  {
1885  assume( itr.Current().CheckLT( L ) ); // ???
1886  continue;
1887  }
1888 
1889  number n = n_Mult( pGetCoeff(multiplier), pGetCoeff(t), r->cf);
1890 
1891 #if NODIVISION
1892  // we assume all leading coeffs to be 1!
1893  assume( n_IsOne(pGetCoeff(p), r->cf) );
1894 #else
1895  if( !n_IsOne( pGetCoeff(p), r ) )
1896  n = n_Div(n, pGetCoeff(p), r->cf);
1897 #endif
1898 
1899  p_SetCoeff0(q, n_InpNeg(n, r->cf), r);
1900 // n_Delete(&n, r);
1901 
1902  p_Test(multiplier, r);
1903  p_Test(q, r);
1904 
1905  assume( itr.Current().CheckLT( L ) ); // ???
1906  return q;
1907  }
1908 
1909  p_LmFree(q, r);
1910 
1911  p_Test(multiplier, r);
1912 
1913  return NULL;
1914 
1915 }

◆ FindReducer() [2/2]

poly CReducerFinder::FindReducer ( const poly  product,
const poly  syzterm,
const CReducerFinder checker 
) const

Definition at line 1919 of file syzextra.cc.

1920 {
1921  CDivisorEnumerator itr(*this, product);
1922  if( !itr.Reset() )
1923  return NULL;
1924 
1925 
1926 
1927  const ring& r = m_rBaseRing;
1928 
1929  assume( product != NULL );
1930 
1931  const ideal& L = m_L; assume( L != NULL ); // for debug/testing only!
1932 
1933  long c = 0;
1934 
1935  if (syzterm != NULL)
1936  c = p_GetComp(syzterm, r) - 1;
1937 
1938  assume( c >= 0 && c < IDELEMS(L) );
1939 
1940  const BOOLEAN to_check = (syz_checker.IsNonempty()); // OPT__TAILREDSYZ &&
1941 
1942  const poly q = p_New(r); pNext(q) = NULL;
1943 
1944  while( itr.MoveNext() )
1945  {
1946  assume( itr.Current().CheckLT( L ) ); // ???
1947 
1948  const poly p = itr.Current().lt(); // ??
1949  const int k = itr.Current().label();
1950 
1951  p_ExpVectorDiff(q, product, p, r); // (LM(product) / LM(L[k]))
1952  p_SetComp(q, k + 1, r);
1953  p_Setm(q, r);
1954 
1955  // cannot allow something like: a*gen(i) - a*gen(i)
1956  if (syzterm != NULL && (k == c))
1957  if (p_ExpVectorEqual(syzterm, q, r))
1958  {
1959  assume( itr.Current().CheckLT( L ) ); // ???
1960  continue;
1961  }
1962 
1963  // while the complement (the fraction) is not reducible by leading syzygies
1964  if( to_check && syz_checker.IsDivisible(q) ) // ?????
1965  {
1966  assume( itr.Current().CheckLT( L ) ); // ???
1967  continue;
1968  }
1969 
1970 
1971 #if NODIVISION
1972  assume( n_IsOne(p_GetCoeff(p, r), r->cf) );
1973  p_SetCoeff0(q, n_InpNeg( n_Copy(pGetCoeff(product), r->cf), r->cf), r);
1974 #else
1975  p_SetCoeff0(q, n_InpNeg( n_Div( pGetCoeff(product), p_GetCoeff(p), r->cf), r->cf), r);
1976 #endif
1977 
1978  assume( itr.Current().CheckLT( L ) ); // ???
1979  return q;
1980  }
1981 
1982 
1983 
1984 /*
1985  const long comp = p_GetComp(product, r);
1986  const unsigned long not_sev = ~p_GetShortExpVector(product, r);
1987 
1988  assume( comp >= 0 );
1989 
1990 // for( int k = IDELEMS(L)-1; k>= 0; k-- )
1991 // {
1992 // const poly p = L->m[k];
1993 //
1994 // if ( p_GetComp(p, r) != comp )
1995 // continue;
1996 //
1997 // const unsigned long p_sev = p_GetShortExpVector(p, r); // to be stored in m_hash!!!
1998 
1999  // looking for an appropriate diviser p = L[k]...
2000  CReducersHash::const_iterator it = m_hash.find(comp); // same module component
2001 
2002  if( it == m_hash.end() )
2003  return NULL;
2004 
2005  assume( m_L != NULL );
2006 
2007  const TReducers& reducers = it->second;
2008 
2009  const BOOLEAN to_check = (syz_checker.IsNonempty()); // OPT__TAILREDSYZ &&
2010 
2011  const poly q = p_New(r); pNext(q) = NULL;
2012 
2013  for(TReducers::const_iterator vit = reducers.begin(); vit != reducers.end(); vit++ )
2014  {
2015  const poly p = (*vit)->lt(); // ???
2016 
2017  assume( p_GetComp(p, r) == comp );
2018 
2019  const int k = (*vit)->label();
2020 
2021  assume( L->m[k] == p ); // CheckLT
2022 
2023  const unsigned long p_sev = (*vit)->sev();
2024 
2025  assume( p_sev == p_GetShortExpVector(p, r) );
2026 
2027  if( !p_LmShortDivisibleByNoComp(p, p_sev, product, not_sev, r) )
2028  continue;
2029 
2030 // // ... which divides the product, looking for the _1st_ appropriate one!
2031 // if( !p_LmDivisibleByNoComp(p, product, r) ) // included inside p_LmShortDivisibleBy!
2032 // continue;
2033 
2034  p_ExpVectorDiff(q, product, p, r); // (LM(product) / LM(L[k]))
2035  p_SetComp(q, k + 1, r);
2036  p_Setm(q, r);
2037 
2038  // cannot allow something like: a*gen(i) - a*gen(i)
2039  if (syzterm != NULL && (k == c))
2040  if (p_ExpVectorEqual(syzterm, q, r))
2041  {
2042  continue;
2043  }
2044 
2045  // while the complement (the fraction) is not reducible by leading syzygies
2046  if( to_check && syz_checker.IsDivisible(q) )
2047  {
2048  continue;
2049  }
2050 
2051  p_SetCoeff0(q, n_InpNeg( n_Div( p_GetCoeff(product, r), p_GetCoeff(p, r), r), r), r);
2052  return q;
2053  }
2054 */
2055 
2056  p_LmFree(q, r);
2057  return NULL;
2058 }

◆ Initialize()

void CReducerFinder::Initialize ( const ideal  L)

Definition at line 1481 of file syzextra.cc.

1482 {
1483  assume( m_L == NULL || m_L == L );
1484  if( m_L == NULL )
1485  m_L = L;
1486 
1487  assume( m_L == L );
1488 
1489  if( L != NULL )
1490  {
1491  const ring& R = m_rBaseRing;
1492  assume( R != NULL );
1493 
1494  for( int k = IDELEMS(L) - 1; k >= 0; k-- )
1495  {
1496  const poly a = L->m[k]; // assume( a != NULL );
1497 
1498  // NOTE: label is k \in 0 ... |L|-1!!!
1499  if( a != NULL )
1500  m_hash[p_GetComp(a, R)].push_back( new CLeadingTerm(k, a, R) );
1501  }
1502  }
1503 }

◆ IsDivisible()

bool CReducerFinder::IsDivisible ( const poly  q) const

Definition at line 1708 of file syzextra.cc.

1709 {
1710  assume( product != NULL );
1711 
1712  // NOTE: q may have no coeff!!!
1713 
1714  CDivisorEnumerator itr(*this, product);
1715  if( !itr.Reset() )
1716  return false;
1717 
1718  return itr.MoveNext();
1719 
1720 }

◆ IsNonempty()

bool CReducerFinder::IsNonempty ( ) const
inline

Definition at line 299 of file syzextra.h.

299 { return !m_hash.empty(); }

◆ operator=()

void CReducerFinder::operator= ( const CReducerFinder )
private

◆ PreProcessTerm()

int CReducerFinder::PreProcessTerm ( const poly  t,
CReducerFinder syzChecker 
) const

is the term to be "preprocessed" as lower order term or lead to only reducible syzygies...

Definition at line 402 of file syzextra.cc.

403 {
404  assume( t != NULL );
405 
406  const ring r = m_rBaseRing;
407 
408 
409  if( LIKELY(OPT__TAILREDSYZ) )
410  if( p_LmIsConstant(t, r) ) // most basic case of baing coprime with L, whatever that is...
411  return 1; // TODO: prove this...?
412 
413  // return false; // appears to be fine
414 
415  const long comp = p_GetComp(t, r);
416 
417  CReducersHash::const_iterator itr = m_hash.find(comp);
418 
419  if ( itr == m_hash.end() )
420  return 2; // no such leading component!!!
421 
422  assume( itr->first == comp );
423 
424  const bool bIdealCase = (comp == 0);
425  const bool bSyzCheck = syzChecker.IsNonempty(); // need to check even in ideal case????? proof? "&& !bIdealCase"
426 
427  if( LIKELY(OPT__TAILREDSYZ && (bIdealCase || bSyzCheck)) )
428  {
429  const TReducers& v = itr->second;
430  const int N = rVar(r);
431  // TODO: extract exps of t beforehand?!
432  bool coprime = true;
433  for(TReducers::const_iterator vit = v.begin(); (vit != v.end()) && coprime; ++vit )
434  {
435  assume( (*vit)->CheckLT( m_L ) );
436 
437  const poly p = (*vit)->lt();
438 
439  assume( p_GetComp(p, r) == comp );
440 
441  // TODO: check if coprime with Leads... if OPT__TAILREDSYZ !
442  for( int var = N; var > 0; --var )
443  if( (p_GetExp(p, var, r) != 0) && (p_GetExp(t, var, r) != 0) )
444  {
445  coprime = false; // t not coprime with p!
446  break;
447  }
448 
449  if( bSyzCheck && coprime )
450  {
451  poly ss = p_LmInit(t, r);
452  p_SetCoeff0(ss, n_Init(1, r->cf), r); // for delete & printout only!...
453  p_SetComp(ss, (*vit)->label() + 1, r); // coeff?
454  p_Setm(ss, r);
455 
456  coprime = ( syzChecker.IsDivisible(ss) );
457 
458  p_LmDelete(&ss, r); // deletes coeff as well???
459  }
460 
461  assume( p == (*vit)->lt() );
462  assume( (*vit)->CheckLT( m_L ) );
463  }
464 
465  return coprime? 3: 0; // t was coprime with all of leading terms!!!
466 
467  }
468  // return true; // delete the term
469 
470  return 0;
471 }

Friends And Related Function Documentation

◆ CDivisorEnumerator

friend class CDivisorEnumerator
friend

Definition at line 269 of file syzextra.h.

◆ CDivisorEnumerator2

friend class CDivisorEnumerator2
friend

Definition at line 267 of file syzextra.h.

Field Documentation

◆ m_hash

CReducersHash CReducerFinder::m_hash
private

Definition at line 307 of file syzextra.h.

◆ m_L

ideal CReducerFinder::m_L
private

only for debug

Definition at line 305 of file syzextra.h.


The documentation for this class was generated from the following files:
SchreyerSyzygyComputationFlags::m_rBaseRing
const ring m_rBaseRing
global base ring
Definition: syzextra.h:214
p_GetCoeff
#define p_GetCoeff(p, r)
Definition: monomials.h:54
p_GetComp
#define p_GetComp(p, r)
Definition: monomials.h:68
p_GetExp
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:457
CDivisorEnumerator2
TODO:
Definition: syzextra.cc:1725
p_SetCoeff0
#define p_SetCoeff0(p, n, r)
Definition: monomials.h:64
k
int k
Definition: cfEzgcd.cc:92
p_ExpVectorDiff
static void p_ExpVectorDiff(poly pr, poly p1, poly p2, const ring r)
Definition: p_polys.h:1402
SchreyerSyzygyComputationFlags::SchreyerSyzygyComputationFlags
SchreyerSyzygyComputationFlags(idhdl rootRingHdl)
Definition: syzextra.cc:1442
p_LmInit
static poly p_LmInit(poly p, const ring r)
Definition: p_polys.h:1264
LIKELY
#define LIKELY
Definition: auxiliary.h:420
p_Test
#define p_Test(p, r)
Definition: p_polys.h:155
flags
int status int void size_t count int const void size_t count const char int flags
Definition: si_signals.h:72
N
const CanonicalForm CFMap CFMap & N
Definition: cfEzgcd.cc:48
n_IsOne
static FORCE_INLINE BOOLEAN n_IsOne(number n, const coeffs r)
TRUE iff 'n' represents the one element.
Definition: coeffs.h:468
rVar
static short rVar(const ring r)
#define rVar(r) (r->N)
Definition: ring.h:582
SchreyerSyzygyComputationFlags::OPT__TAILREDSYZ
const int OPT__TAILREDSYZ
Reduce syzygy tails wrt the leading syzygy terms.
Definition: syzextra.h:183
CReducerFinder::m_hash
CReducersHash m_hash
Definition: syzextra.h:307
BOOLEAN
int BOOLEAN
Definition: auxiliary.h:85
CReducerFinder::m_L
ideal m_L
only for debug
Definition: syzextra.h:305
p_LmDelete
static void p_LmDelete(poly p, const ring r)
Definition: p_polys.h:698
p_New
static poly p_New(const ring, omBin bin)
Definition: p_polys.h:651
CReducerFinder::IsDivisible
bool IsDivisible(const poly q) const
Definition: syzextra.cc:1708
n_Mult
static FORCE_INLINE number n_Mult(number a, number b, const coeffs r)
return the product of 'a' and 'b', i.e., a*b
Definition: coeffs.h:636
n_Init
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:538
p_ExpVectorSum
static void p_ExpVectorSum(poly pr, poly p1, poly p2, const ring r)
Definition: p_polys.h:1353
n_InpNeg
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:557
CDivisorEnumerator
TODO:
Definition: syzextra.cc:1617
p_LmFree
static void p_LmFree(poly p, ring)
Definition: p_polys.h:670
CLeadingTerm
Definition: syzextra.h:233
n_Copy
static FORCE_INLINE number n_Copy(number n, const coeffs r)
return a copy of 'n'
Definition: coeffs.h:451
assume
#define assume(x)
Definition: mod2.h:384
NULL
#define NULL
Definition: omList.c:9
CReducerFinder::IsNonempty
bool IsNonempty() const
Definition: syzextra.h:299
p_SetComp
static unsigned long p_SetComp(poly p, unsigned long c, ring r)
Definition: p_polys.h:238
R
#define R
Definition: sirandom.c:26
CReducerFinder::Initialize
void Initialize(const ideal L)
Definition: syzextra.cc:1481
p_Setm
static void p_Setm(poly p, const ring r)
Definition: p_polys.h:224
v
const Variable & v
< [in] a sqrfree bivariate poly
Definition: facBivar.h:37
p
int p
Definition: cfModGcd.cc:4019
p_ExpVectorEqual
static BOOLEAN p_ExpVectorEqual(poly p1, poly p2, const ring r1, const ring r2)
Definition: p_polys.cc:4406
n_Div
static FORCE_INLINE number n_Div(number a, number b, const coeffs r)
return the quotient of 'a' and 'b', i.e., a/b; raises an error if 'b' is not invertible in r exceptio...
Definition: coeffs.h:615
IDELEMS
#define IDELEMS(i)
Definition: simpleideals.h:24
comp
int comp(const CanonicalForm &A, const CanonicalForm &B)
compare polynomials
Definition: facSparseHensel.h:25
pGetCoeff
static number & pGetCoeff(poly p)
return an alias to the leading coefficient of p assumes that p != NULL NOTE: not copy
Definition: monomials.h:48
CReducerFinder::TReducers
std::vector< const CLeadingTerm * > TReducers
Definition: syzextra.h:273
pNext
#define pNext(p)
Definition: monomials.h:40
p_LmIsConstant
static BOOLEAN p_LmIsConstant(const poly p, const ring r)
Definition: p_polys.h:964