My Project  debian-1:4.1.1-p2+ds-4build2
Data Structures | Macros | Typedefs | Functions | Variables
sparsmat.cc File Reference
#include "misc/auxiliary.h"
#include "omalloc/omalloc.h"
#include "misc/mylimits.h"
#include "misc/options.h"
#include "reporter/reporter.h"
#include "misc/intvec.h"
#include "coeffs/numbers.h"
#include "monomials/ring.h"
#include "monomials/p_polys.h"
#include "simpleideals.h"
#include "sparsmat.h"
#include "prCopy.h"
#include "templates/p_Procs.h"
#include "kbuckets.h"
#include "operations/p_Mult_q.h"

Go to the source code of this file.

Data Structures

struct  sm_prec
 
class  sparse_mat
 
struct  sm_nrec
 
class  sparse_number_mat
 

Macros

#define SM_MIN_LENGTH_BUCKET   MIN_LENGTH_BUCKET - 5
 

Typedefs

typedef sm_prec * smpoly
 
typedef sm_nrec * smnumber
 

Functions

static void sm_ExactPolyDiv (poly, poly, const ring)
 
static BOOLEAN sm_IsNegQuot (poly, const poly, const poly, const ring)
 
static void sm_ExpMultDiv (poly, const poly, const poly, const ring)
 
static void sm_PolyDivN (poly, const number, const ring)
 
static BOOLEAN smSmaller (poly, poly)
 
static void sm_CombineChain (poly *, poly, const ring)
 
static void sm_FindRef (poly *, poly *, poly, const ring)
 
static void sm_ElemDelete (smpoly *, const ring)
 
static smpoly smElemCopy (smpoly)
 
static float sm_PolyWeight (smpoly, const ring)
 
static smpoly sm_Poly2Smpoly (poly, const ring)
 
static poly sm_Smpoly2Poly (smpoly, const ring)
 
static BOOLEAN sm_HaveDenom (poly, const ring)
 
static number sm_Cleardenom (ideal, const ring)
 
static poly pp_Mult_Coeff_mm_DivSelect_MultDiv (poly p, int &lp, poly m, poly a, poly b, const ring currRing)
 
static poly sm_SelectCopy_ExpMultDiv (poly p, poly m, poly a, poly b, const ring currRing)
 
static void smMinSelect (long *, int, int)
 
long sm_ExpBound (ideal m, int di, int ra, int t, const ring currRing)
 
ring sm_RingChange (const ring origR, long bound)
 
void sm_KillModifiedRing (ring r)
 
BOOLEAN sm_CheckDet (ideal I, int d, BOOLEAN sw, const ring r)
 
poly sm_CallDet (ideal I, const ring R)
 
void sm_CallBareiss (ideal I, int x, int y, ideal &M, intvec **iv, const ring R)
 
poly sm_MultDiv (poly a, poly b, const poly c, const ring R)
 
void sm_SpecialPolyDiv (poly a, poly b, const ring R)
 
static void sm_NumberDelete (smnumber *, const ring R)
 
static smnumber smNumberCopy (smnumber)
 
static smnumber sm_Poly2Smnumber (poly, const ring)
 
static poly sm_Smnumber2Poly (number, const ring)
 
static BOOLEAN smCheckSolv (ideal)
 
ideal sm_CallSolv (ideal I, const ring R)
 

Variables

omBin smprec_bin = omGetSpecBin(sizeof(smprec))
 
static omBin smnrec_bin = omGetSpecBin(sizeof(smnrec))
 

Data Structure Documentation

◆ smprec

struct smprec

Definition at line 48 of file sparsmat.cc.

Data Fields
int e
float f
poly m
smpoly n
int pos

◆ smnrec

struct smnrec

Definition at line 2313 of file sparsmat.cc.

Data Fields
number m
smnumber n
int pos

Macro Definition Documentation

◆ SM_MIN_LENGTH_BUCKET

#define SM_MIN_LENGTH_BUCKET   MIN_LENGTH_BUCKET - 5

Definition at line 41 of file sparsmat.cc.

Typedef Documentation

◆ smnumber

typedef sm_nrec* smnumber

Definition at line 2312 of file sparsmat.cc.

◆ smpoly

typedef sm_prec* smpoly

Definition at line 47 of file sparsmat.cc.

Function Documentation

◆ pp_Mult_Coeff_mm_DivSelect_MultDiv()

static poly pp_Mult_Coeff_mm_DivSelect_MultDiv ( poly  p,
int &  lp,
poly  m,
poly  a,
poly  b,
const ring  currRing 
)
static

Definition at line 77 of file sparsmat.cc.

79 {
80  if (rOrd_is_Comp_dp(currRing) && currRing->ExpL_Size > 2)
81  {
82  // pp_Mult_Coeff_mm_DivSelectMult only works for (c/C,dp) and
83  // ExpL_Size > 2
84  // should be generalized, at least to dp with ExpL_Size == 2
85  // (is the case for 1 variable)
86  int shorter;
87  p = currRing->p_Procs->pp_Mult_Coeff_mm_DivSelectMult(p, m, a, b,
88  shorter, currRing);
89  lp -= shorter;
90  }
91  else
92  {
94  sm_ExpMultDiv(p, a, b, currRing);
95  }
96  return p;
97 }

◆ sm_CallBareiss()

void sm_CallBareiss ( ideal  I,
int  x,
int  y,
ideal &  M,
intvec **  iv,
const ring  R 
)

Definition at line 402 of file sparsmat.cc.

403 {
404  int r=id_RankFreeModule(I,R),t=r;
405  int c=IDELEMS(I),s=c;
406  long bound;
407  ring tmpR;
408  sparse_mat *bareiss;
409 
410  if ((x>0) && (x<t))
411  t-=x;
412  if ((y>1) && (y<s))
413  s-=y;
414  if (t>s) t=s;
415  bound=sm_ExpBound(I,c,r,t,R);
416  tmpR=sm_RingChange(R,bound);
417  ideal II = idrCopyR(I, R, tmpR);
418  bareiss = new sparse_mat(II,tmpR);
419  if (bareiss->smGetAct() == NULL)
420  {
421  delete bareiss;
422  *iv=new intvec(1,rVar(tmpR));
423  }
424  else
425  {
426  id_Delete(&II,tmpR);
427  bareiss->smNewBareiss(x, y);
428  II = bareiss->smRes2Mod();
429  *iv = new intvec(bareiss->smGetRed());
430  bareiss->smToIntvec(*iv);
431  delete bareiss;
432  II = idrMoveR(II,tmpR,R);
433  }
434  sm_KillModifiedRing(tmpR);
435  M=II;
436 }

◆ sm_CallDet()

poly sm_CallDet ( ideal  I,
const ring  R 
)

Definition at line 357 of file sparsmat.cc.

358 {
359  if (I->ncols != I->rank)
360  {
361  Werror("det of %ld x %d module (matrix)",I->rank,I->ncols);
362  return NULL;
363  }
364  int r=id_RankFreeModule(I,R);
365  if (I->ncols != r) // some 0-lines at the end
366  {
367  return NULL;
368  }
369  long bound=sm_ExpBound(I,r,r,r,R);
370  number diag,h=n_Init(1,R->cf);
371  poly res;
372  ring tmpR;
373  sparse_mat *det;
374  ideal II;
375 
376  tmpR=sm_RingChange(R,bound);
377  II = idrCopyR(I, R, tmpR);
378  diag = sm_Cleardenom(II,tmpR);
379  det = new sparse_mat(II,tmpR);
380  id_Delete(&II,tmpR);
381  if (det->smGetAct() == NULL)
382  {
383  delete det;
384  sm_KillModifiedRing(tmpR);
385  return NULL;
386  }
387  res=det->smDet();
388  if(det->smGetSign()<0) res=p_Neg(res,tmpR);
389  delete det;
390  res = prMoveR(res, tmpR, R);
391  sm_KillModifiedRing(tmpR);
392  if (!n_Equal(diag,h,R->cf))
393  {
394  p_Mult_nn(res,diag,R);
395  p_Normalize(res,R);
396  }
397  n_Delete(&diag,R->cf);
398  n_Delete(&h,R->cf);
399  return res;
400 }

◆ sm_CallSolv()

ideal sm_CallSolv ( ideal  I,
const ring  R 
)

Definition at line 2371 of file sparsmat.cc.

2372 {
2373  sparse_number_mat *linsolv;
2374  ring tmpR;
2375  ideal rr;
2376 
2377  if (id_IsConstant(I,R)==FALSE)
2378  {
2379  WerrorS("symbol in equation");
2380  return NULL;
2381  }
2382  I->rank = id_RankFreeModule(I,R);
2383  if (smCheckSolv(I)) return NULL;
2384  tmpR=sm_RingChange(R,1);
2385  rr=idrCopyR(I,R, tmpR);
2386  linsolv = new sparse_number_mat(rr,tmpR);
2387  rr=NULL;
2388  linsolv->smTriangular();
2389  if (linsolv->smIsSing() == 0)
2390  {
2391  linsolv->smSolv();
2392  rr = linsolv->smRes2Ideal();
2393  }
2394  else
2395  WerrorS("singular problem for linsolv");
2396  delete linsolv;
2397  if (rr!=NULL)
2398  rr = idrMoveR(rr,tmpR,R);
2399  sm_KillModifiedRing(tmpR);
2400  return rr;
2401 }

◆ sm_CheckDet()

BOOLEAN sm_CheckDet ( ideal  I,
int  d,
BOOLEAN  sw,
const ring  r 
)

Definition at line 306 of file sparsmat.cc.

307 {
308  int s,t,i;
309  poly p;
310 
311  if (d>100)
312  return sw;
313  if (!rField_is_Q(r))
314  return sw;
315  s = t = 0;
316  if (sw)
317  {
318  for(i=IDELEMS(I)-1;i>=0;i--)
319  {
320  p=I->m[i];
321  if (p!=NULL)
322  {
323  if(!p_IsConstant(p,r))
324  return sw;
325  s++;
326  t+=n_Size(pGetCoeff(p),r->cf);
327  }
328  }
329  }
330  else
331  {
332  for(i=IDELEMS(I)-1;i>=0;i--)
333  {
334  p=I->m[i];
335  if (!p_IsConstantPoly(p,r))
336  return sw;
337  while (p!=NULL)
338  {
339  s++;
340  t+=n_Size(pGetCoeff(p),r->cf);
341  pIter(p);
342  }
343  }
344  }
345  s*=15;
346  if (t>s)
347  return !sw;
348  else
349  return sw;
350 }

◆ sm_Cleardenom()

static number sm_Cleardenom ( ideal  id,
const ring  R 
)
static

Definition at line 2278 of file sparsmat.cc.

2279 {
2280  poly a;
2281  number x,y,res=n_Init(1,R->cf);
2282  BOOLEAN sw=FALSE;
2283 
2284  for (int i=0; i<IDELEMS(id); i++)
2285  {
2286  a = id->m[i];
2287  sw = sm_HaveDenom(a,R);
2288  if (sw) break;
2289  }
2290  if (!sw) return res;
2291  for (int i=0; i<IDELEMS(id); i++)
2292  {
2293  a = id->m[i];
2294  if (a!=NULL)
2295  {
2296  x = n_Copy(pGetCoeff(a),R->cf);
2297  p_Cleardenom(a, R);
2298  y = n_Div(x,pGetCoeff(a),R->cf);
2299  n_Delete(&x,R->cf);
2300  x = n_Mult(res,y,R->cf);
2301  n_Normalize(x,R->cf);
2302  n_Delete(&res,R->cf);
2303  res = x;
2304  }
2305  }
2306  return res;
2307 }

◆ sm_CombineChain()

static void sm_CombineChain ( poly *  px,
poly  r,
const ring  R 
)
static

Definition at line 2028 of file sparsmat.cc.

2029 {
2030  poly pa = *px, pb;
2031  number x;
2032  int i;
2033 
2034  loop
2035  {
2036  pb = pNext(pa);
2037  if (pb == NULL)
2038  {
2039  pa = pNext(pa) = r;
2040  break;
2041  }
2042  i = p_LmCmp(pb, r,R);
2043  if (i > 0)
2044  pa = pb;
2045  else
2046  {
2047  if (i == 0)
2048  {
2049  x = n_Add(pGetCoeff(pb), pGetCoeff(r),R->cf);
2050  p_LmDelete(&r,R);
2051  if (n_IsZero(x,R->cf))
2052  {
2053  p_LmDelete(&pb,R);
2054  pNext(pa) = p_Add_q(pb,r,R);
2055  }
2056  else
2057  {
2058  pa = pb;
2059  p_SetCoeff(pa,x,R);
2060  pNext(pa) = p_Add_q(pNext(pa), r, R);
2061  }
2062  }
2063  else
2064  {
2065  pa = pNext(pa) = r;
2066  pNext(pa) = p_Add_q(pb, pNext(pa),R);
2067  }
2068  break;
2069  }
2070  }
2071  *px = pa;
2072 }

◆ sm_ElemDelete()

static void sm_ElemDelete ( smpoly r,
const ring  R 
)
static

Definition at line 2131 of file sparsmat.cc.

2132 {
2133  smpoly a = *r, b = a->n;
2134 
2135  p_Delete(&a->m, R);
2136  omFreeBin((void *)a, smprec_bin);
2137  *r = b;
2138 }

◆ sm_ExactPolyDiv()

static void sm_ExactPolyDiv ( poly  a,
poly  b,
const ring  R 
)
static

Definition at line 1906 of file sparsmat.cc.

1907 {
1908  const number x = pGetCoeff(b);
1909  poly tail = pNext(b), e = p_Init(R);
1910  poly h;
1911  number y, yn;
1912  int lt = pLength(tail);
1913 
1914  if (lt + 1 >= SM_MIN_LENGTH_BUCKET && !TEST_OPT_NOT_BUCKETS)
1915  {
1916  kBucket_pt bucket = kBucketCreate(R);
1917  kBucketInit(bucket, pNext(a), 0);
1918  int lh = 0;
1919  do
1920  {
1921  y = n_Div(pGetCoeff(a), x, R->cf);
1922  n_Normalize(y, R->cf);
1923  p_SetCoeff(a,y, R);
1924  yn = n_InpNeg(n_Copy(y, R->cf), R->cf);
1925  pSetCoeff0(e,yn);
1926  lh = lt;
1927  if (sm_IsNegQuot(e, a, b, R))
1928  {
1929  h = pp_Mult_Coeff_mm_DivSelect_MultDiv(tail, lh, e, a, b, R);
1930  }
1931  else
1932  h = pp_Mult_mm(tail, e, R);
1933  n_Delete(&yn, R->cf);
1934  kBucket_Add_q(bucket, h, &lh);
1935 
1936  a = pNext(a) = kBucketExtractLm(bucket);
1937  } while (a!=NULL);
1938  kBucketDestroy(&bucket);
1939  }
1940  else
1941  {
1942  do
1943  {
1944  y = n_Div(pGetCoeff(a), x, R->cf);
1945  n_Normalize(y, R->cf);
1946  p_SetCoeff(a,y, R);
1947  yn = n_InpNeg(n_Copy(y, R->cf), R->cf);
1948  pSetCoeff0(e,yn);
1949  if (sm_IsNegQuot(e, a, b, R))
1950  h = sm_SelectCopy_ExpMultDiv(tail, e, a, b, R);
1951  else
1952  h = pp_Mult_mm(tail, e, R);
1953  n_Delete(&yn, R->cf);
1954  a = pNext(a) = p_Add_q(pNext(a), h, R);
1955  } while (a!=NULL);
1956  }
1957  p_LmFree(e, R);
1958 }

◆ sm_ExpBound()

long sm_ExpBound ( ideal  m,
int  di,
int  ra,
int  t,
const ring  currRing 
)

Definition at line 189 of file sparsmat.cc.

190 {
191  poly p;
192  long kr, kc;
193  long *r, *c;
194  int al, bl, i, j, k;
195 
196  if (ra==0) ra=1;
197  al = di*sizeof(long);
198  c = (long *)omAlloc(al);
199  bl = ra*sizeof(long);
200  r = (long *)omAlloc0(bl);
201  for (i=di-1;i>=0;i--)
202  {
203  kc = 0;
204  p = m->m[i];
205  while(p!=NULL)
206  {
207  k = p_GetComp(p, currRing)-1;
208  kr = r[k];
209  for (j=currRing->N;j>0;j--)
210  {
211  long t=p_GetExp(p,j, currRing);
212  if(t /*p_GetExp(p,j, currRing)*/ >kc)
213  kc=t; /*p_GetExp(p,j, currRing);*/
214  if(t /*p_GetExp(p,j, currRing)s*/ >kr)
215  kr=t; /*p_GetExp(p,j, currRing);*/
216  }
217  r[k] = kr;
218  pIter(p);
219  }
220  c[i] = kc;
221  }
222  if (t<di) smMinSelect(c, t, di);
223  if (t<ra) smMinSelect(r, t, ra);
224  kr = kc = 0;
225  for (j=t-1;j>=0;j--)
226  {
227  kr += r[j];
228  kc += c[j];
229  }
230  omFreeSize((ADDRESS)c, al);
231  omFreeSize((ADDRESS)r, bl);
232  if (kr<kc) kc = kr;
233  if (kr<1) kr = 1;
234  return kr;
235 }

◆ sm_ExpMultDiv()

static void sm_ExpMultDiv ( poly  t,
const poly  b,
const poly  c,
const ring  R 
)
static

Definition at line 1986 of file sparsmat.cc.

1987 {
1988  p_Test(t,R);
1989  p_LmTest(b,R);
1990  p_LmTest(c,R);
1991  poly bc = p_New(R);
1992 
1993  p_ExpVectorDiff(bc, b, c, R);
1994 
1995  while(t!=NULL)
1996  {
1997  p_ExpVectorAdd(t, bc, R);
1998  pIter(t);
1999  }
2000  p_LmFree(bc, R);
2001 }

◆ sm_FindRef()

static void sm_FindRef ( poly *  ref,
poly *  px,
poly  r,
const ring  R 
)
static

Definition at line 2075 of file sparsmat.cc.

2076 {
2077  number x;
2078  int i;
2079  poly pa = *px, pp = NULL;
2080 
2081  loop
2082  {
2083  i = p_LmCmp(pa, r,R);
2084  if (i > 0)
2085  {
2086  pp = pa;
2087  pIter(pa);
2088  if (pa==NULL)
2089  {
2090  pNext(pp) = r;
2091  break;
2092  }
2093  }
2094  else
2095  {
2096  if (i == 0)
2097  {
2098  x = n_Add(pGetCoeff(pa), pGetCoeff(r),R->cf);
2099  p_LmDelete(&r,R);
2100  if (n_IsZero(x,R->cf))
2101  {
2102  p_LmDelete(&pa,R);
2103  if (pp!=NULL)
2104  pNext(pp) = p_Add_q(pa,r,R);
2105  else
2106  *px = p_Add_q(pa,r,R);
2107  }
2108  else
2109  {
2110  pp = pa;
2111  p_SetCoeff(pp,x,R);
2112  pNext(pp) = p_Add_q(pNext(pp), r, R);
2113  }
2114  }
2115  else
2116  {
2117  if (pp!=NULL)
2118  pp = pNext(pp) = r;
2119  else
2120  *px = pp = r;
2121  pNext(pp) = p_Add_q(pa, pNext(r),R);
2122  }
2123  break;
2124  }
2125  }
2126  *ref = pp;
2127 }

◆ sm_HaveDenom()

static BOOLEAN sm_HaveDenom ( poly  a,
const ring  R 
)
static

Definition at line 2259 of file sparsmat.cc.

2260 {
2261  BOOLEAN sw;
2262  number x;
2263 
2264  while (a != NULL)
2265  {
2266  x = n_GetDenom(pGetCoeff(a),R->cf);
2267  sw = n_IsOne(x,R->cf);
2268  n_Delete(&x,R->cf);
2269  if (!sw)
2270  {
2271  return TRUE;
2272  }
2273  pIter(a);
2274  }
2275  return FALSE;
2276 }

◆ sm_IsNegQuot()

static BOOLEAN sm_IsNegQuot ( poly  a,
const poly  b,
const poly  c,
const ring  R 
)
static

Definition at line 1961 of file sparsmat.cc.

1962 {
1963  if (p_LmDivisibleByNoComp(c, b,R))
1964  {
1965  p_ExpVectorDiff(a, b, c,R);
1966  // Hmm: here used to be a p_Setm(a): but it is unnecessary,
1967  // if b and c are correct
1968  return FALSE;
1969  }
1970  else
1971  {
1972  int i;
1973  for (i=rVar(R); i>0; i--)
1974  {
1975  if(p_GetExp(c,i,R) > p_GetExp(b,i,R))
1976  p_SetExp(a,i,p_GetExp(c,i,R)-p_GetExp(b,i,R),R);
1977  else
1978  p_SetExp(a,i,0,R);
1979  }
1980  // here we actually might need a p_Setm, if a is to be used in
1981  // comparisons
1982  return TRUE;
1983  }
1984 }

◆ sm_KillModifiedRing()

void sm_KillModifiedRing ( ring  r)

Definition at line 290 of file sparsmat.cc.

291 {
292  if (r->qideal!=NULL) id_Delete(&(r->qideal),r);
293  for(int i=r->N-1;i>=0;i--) omFree(r->names[i]);
294  omFreeSize(r->names,r->N*sizeof(char*));
296 }

◆ sm_MultDiv()

poly sm_MultDiv ( poly  a,
poly  b,
const poly  c,
const ring  R 
)

Definition at line 1814 of file sparsmat.cc.

1815 {
1816  poly pa, e, res, r;
1817  BOOLEAN lead;
1818 
1819  if ((c == NULL) || p_LmIsConstantComp(c,R))
1820  {
1821  return pp_Mult_qq(a, b, R);
1822  }
1823  if (smSmaller(a, b))
1824  {
1825  r = a;
1826  a = b;
1827  b = r;
1828  }
1829  res = NULL;
1830  e = p_Init(R);
1831  lead = FALSE;
1832  while (!lead)
1833  {
1834  pSetCoeff0(e,pGetCoeff(b));
1835  if (sm_IsNegQuot(e, b, c, R))
1836  {
1837  lead = p_LmDivisibleByNoComp(e, a, R);
1838  r = sm_SelectCopy_ExpMultDiv(a, e, b, c, R);
1839  }
1840  else
1841  {
1842  lead = TRUE;
1843  r = pp_Mult_mm(a, e,R);
1844  }
1845  if (lead)
1846  {
1847  if (res != NULL)
1848  {
1849  sm_FindRef(&pa, &res, r, R);
1850  if (pa == NULL)
1851  lead = FALSE;
1852  }
1853  else
1854  {
1855  pa = res = r;
1856  }
1857  }
1858  else
1859  res = p_Add_q(res, r, R);
1860  pIter(b);
1861  if (b == NULL)
1862  {
1863  p_LmFree(e, R);
1864  return res;
1865  }
1866  }
1867  do
1868  {
1869  pSetCoeff0(e,pGetCoeff(b));
1870  if (sm_IsNegQuot(e, b, c, R))
1871  {
1872  r = sm_SelectCopy_ExpMultDiv(a, e, b, c, R);
1873  if (p_LmDivisibleByNoComp(e, a,R))
1874  sm_CombineChain(&pa, r, R);
1875  else
1876  pa = p_Add_q(pa,r,R);
1877  }
1878  else
1879  {
1880  r = pp_Mult_mm(a, e, R);
1881  sm_CombineChain(&pa, r, R);
1882  }
1883  pIter(b);
1884  } while (b != NULL);
1885  p_LmFree(e, R);
1886  return res;
1887 }

◆ sm_NumberDelete()

static void sm_NumberDelete ( smnumber r,
const ring  R 
)
static

Definition at line 2880 of file sparsmat.cc.

2881 {
2882  smnumber a = *r, b = a->n;
2883 
2884  n_Delete(&a->m,R->cf);
2886  *r = b;
2887 }

◆ sm_Poly2Smnumber()

static smnumber sm_Poly2Smnumber ( poly  q,
const ring  R 
)
static

Definition at line 2900 of file sparsmat.cc.

2901 {
2902  smnumber a, res;
2903  poly p = q;
2904 
2905  if (p == NULL)
2906  return NULL;
2908  a->pos = p_GetComp(p,R);
2909  a->m = pGetCoeff(p);
2910  n_New(&pGetCoeff(p),R->cf);
2911  loop
2912  {
2913  pIter(p);
2914  if (p == NULL)
2915  {
2916  p_Delete(&q,R);
2917  a->n = NULL;
2918  return res;
2919  }
2920  a = a->n = (smnumber)omAllocBin(smnrec_bin);
2921  a->pos = p_GetComp(p,R);
2922  a->m = pGetCoeff(p);
2923  n_New(&pGetCoeff(p),R->cf);
2924  }
2925 }

◆ sm_Poly2Smpoly()

static smpoly sm_Poly2Smpoly ( poly  q,
const ring  R 
)
static

Definition at line 2152 of file sparsmat.cc.

2153 {
2154  poly pp;
2155  smpoly res, a;
2156  long x;
2157 
2158  if (q == NULL)
2159  return NULL;
2160  a = res = (smpoly)omAllocBin(smprec_bin);
2161  a->pos = x = p_GetComp(q,R);
2162  a->m = q;
2163  a->e = 0;
2164  loop
2165  {
2166  p_SetComp(q,0,R);
2167  pp = q;
2168  pIter(q);
2169  if (q == NULL)
2170  {
2171  a->n = NULL;
2172  return res;
2173  }
2174  if (p_GetComp(q,R) != x)
2175  {
2176  a = a->n = (smpoly)omAllocBin(smprec_bin);
2177  pNext(pp) = NULL;
2178  a->pos = x = p_GetComp(q,R);
2179  a->m = q;
2180  a->e = 0;
2181  }
2182  }
2183 }

◆ sm_PolyDivN()

static void sm_PolyDivN ( poly  a,
const number  x,
const ring  R 
)
static

Definition at line 2004 of file sparsmat.cc.

2005 {
2006  number y;
2007 
2008  do
2009  {
2010  y = n_Div(pGetCoeff(a),x, R->cf);
2011  n_Normalize(y, R->cf);
2012  p_SetCoeff(a,y, R);
2013  pIter(a);
2014  } while (a != NULL);
2015 }

◆ sm_PolyWeight()

static float sm_PolyWeight ( smpoly  a,
const ring  R 
)
static

Definition at line 2230 of file sparsmat.cc.

2231 {
2232  poly p = a->m;
2233  int i;
2234  float res = (float)n_Size(pGetCoeff(p),R->cf);
2235 
2236  if (pNext(p) == NULL)
2237  {
2238  for(i=rVar(R); i>0; i--)
2239  {
2240  if (p_GetExp(p,i,R) != 0) return res+1.0;
2241  }
2242  return res;
2243  }
2244  else
2245  {
2246  i = 0;
2247  res = 0.0;
2248  do
2249  {
2250  i++;
2251  res += (float)n_Size(pGetCoeff(p),R->cf);
2252  pIter(p);
2253  }
2254  while (p);
2255  return res+(float)i;
2256  }
2257 }

◆ sm_RingChange()

ring sm_RingChange ( const ring  origR,
long  bound 
)

Definition at line 259 of file sparsmat.cc.

260 {
261 // *origR =currRing;
262  ring tmpR=rCopy0(origR,FALSE,FALSE);
264  int *block0=(int*)omAlloc0(3*sizeof(int));
265  int *block1=(int*)omAlloc0(3*sizeof(int));
266  ord[0]=ringorder_c;
267  ord[1]=ringorder_dp;
268  tmpR->order=ord;
269  tmpR->OrdSgn=1;
270  block0[1]=1;
271  tmpR->block0=block0;
272  block1[1]=tmpR->N;
273  tmpR->block1=block1;
274  tmpR->bitmask = 2*bound;
275  tmpR->wvhdl = (int **)omAlloc0((3) * sizeof(int*));
276 
277 // ???
278 // if (tmpR->bitmask > currRing->bitmask) tmpR->bitmask = currRing->bitmask;
279 
280  rComplete(tmpR,1);
281  if (origR->qideal!=NULL)
282  {
283  tmpR->qideal= idrCopyR_NoSort(origR->qideal, origR, tmpR);
284  }
285  if (TEST_OPT_PROT)
286  Print("[%ld:%d]", (long) tmpR->bitmask, tmpR->ExpL_Size);
287  return tmpR;
288 }

◆ sm_SelectCopy_ExpMultDiv()

static poly sm_SelectCopy_ExpMultDiv ( poly  p,
poly  m,
poly  a,
poly  b,
const ring  currRing 
)
static

Definition at line 99 of file sparsmat.cc.

100 {
101  int lp = 0;
102  return pp_Mult_Coeff_mm_DivSelect_MultDiv(p, lp, m, a, b, currRing);
103 }

◆ sm_Smnumber2Poly()

static poly sm_Smnumber2Poly ( number  a,
const ring  R 
)
static

Definition at line 2931 of file sparsmat.cc.

2932 {
2933  poly res;
2934 
2935  if (a == NULL) return NULL;
2936  res = p_Init(R);
2937  pSetCoeff0(res, a);
2938  return res;
2939 }

◆ sm_Smpoly2Poly()

static poly sm_Smpoly2Poly ( smpoly  a,
const ring  R 
)
static

Definition at line 2189 of file sparsmat.cc.

2190 {
2191  smpoly b;
2192  poly res, pp, q;
2193  long x;
2194 
2195  if (a == NULL)
2196  return NULL;
2197  x = a->pos;
2198  q = res = a->m;
2199  loop
2200  {
2201  p_SetComp(q,x,R);
2202  pp = q;
2203  pIter(q);
2204  if (q == NULL)
2205  break;
2206  }
2207  loop
2208  {
2209  b = a;
2210  a = a->n;
2211  omFreeBin((void *)b, smprec_bin);
2212  if (a == NULL)
2213  return res;
2214  x = a->pos;
2215  q = pNext(pp) = a->m;
2216  loop
2217  {
2218  p_SetComp(q,x,R);
2219  pp = q;
2220  pIter(q);
2221  if (q == NULL)
2222  break;
2223  }
2224  }
2225 }

◆ sm_SpecialPolyDiv()

void sm_SpecialPolyDiv ( poly  a,
poly  b,
const ring  R 
)

Definition at line 1895 of file sparsmat.cc.

1896 {
1897  if (pNext(b) == NULL)
1898  {
1899  sm_PolyDivN(a, pGetCoeff(b),R);
1900  return;
1901  }
1902  sm_ExactPolyDiv(a, b, R);
1903 }

◆ smCheckSolv()

static BOOLEAN smCheckSolv ( ideal  I)
static

Definition at line 2944 of file sparsmat.cc.

2945 { int i = I->ncols;
2946  if ((i == 0) || (i != I->rank-1))
2947  {
2948  WerrorS("wrong dimensions for linsolv");
2949  return TRUE;
2950  }
2951  for(;i;i--)
2952  {
2953  if(I->m[i-1] == NULL)
2954  {
2955  WerrorS("singular input for linsolv");
2956  return TRUE;
2957  }
2958  }
2959  return FALSE;
2960 }

◆ smElemCopy()

static smpoly smElemCopy ( smpoly  a)
static

Definition at line 2140 of file sparsmat.cc.

2141 {
2143  memcpy(r, a, sizeof(smprec));
2144 /* r->m = pCopy(r->m); */
2145  return r;
2146 }

◆ smMinSelect()

static void smMinSelect ( long *  c,
int  t,
int  d 
)
static

Definition at line 237 of file sparsmat.cc.

238 {
239  long m;
240  int pos, i;
241  do
242  {
243  d--;
244  pos = d;
245  m = c[pos];
246  for (i=d-1;i>=0;i--)
247  {
248  if(c[i]<m)
249  {
250  pos = i;
251  m = c[i];
252  }
253  }
254  for (i=pos;i<d;i++) c[i] = c[i+1];
255  } while (d>t);
256 }

◆ smNumberCopy()

static smnumber smNumberCopy ( smnumber  a)
static

Definition at line 2889 of file sparsmat.cc.

2890 {
2892  memcpy(r, a, sizeof(smnrec));
2893  return r;
2894 }

◆ smSmaller()

static BOOLEAN smSmaller ( poly  a,
poly  b 
)
static

Definition at line 2017 of file sparsmat.cc.

2018 {
2019  loop
2020  {
2021  pIter(b);
2022  if (b == NULL) return TRUE;
2023  pIter(a);
2024  if (a == NULL) return FALSE;
2025  }
2026 }

Variable Documentation

◆ smnrec_bin

omBin smnrec_bin = omGetSpecBin(sizeof(smnrec))
static

Definition at line 2319 of file sparsmat.cc.

◆ smprec_bin

omBin smprec_bin = omGetSpecBin(sizeof(smprec))

Definition at line 75 of file sparsmat.cc.

sm_IsNegQuot
static BOOLEAN sm_IsNegQuot(poly, const poly, const poly, const ring)
Definition: sparsmat.cc:1961
FALSE
#define FALSE
Definition: auxiliary.h:94
p_GetComp
#define p_GetComp(p, r)
Definition: monomials.h:71
p_LmIsConstantComp
static BOOLEAN p_LmIsConstantComp(const poly p, const ring r)
Definition: p_polys.h:962
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:469
j
int j
Definition: facHensel.cc:105
smprec
Definition: sparsmat.cc:48
omFree
#define omFree(addr)
Definition: omAllocDecl.h:261
p_Normalize
void p_Normalize(poly p, const ring r)
Definition: p_polys.cc:3709
TEST_OPT_PROT
#define TEST_OPT_PROT
Definition: options.h:102
k
int k
Definition: cfEzgcd.cc:92
idrCopyR_NoSort
ideal idrCopyR_NoSort(ideal id, ring src_r, ring dest_r)
Definition: prCopy.cc:205
sparse_mat::smToIntvec
void smToIntvec(intvec *)
Definition: sparsmat.cc:519
x
Variable x
Definition: cfModGcd.cc:4023
p_ExpVectorDiff
static void p_ExpVectorDiff(poly pr, poly p1, poly p2, const ring r)
Definition: p_polys.h:1420
y
const CanonicalForm int const CFList const Variable & y
Definition: facAbsFact.cc:57
n_New
#define n_New(n, r)
Definition: coeffs.h:441
smprec_bin
omBin smprec_bin
Definition: sparsmat.cc:75
ADDRESS
void * ADDRESS
Definition: auxiliary.h:133
smnrec_bin
static omBin smnrec_bin
Definition: sparsmat.cc:2319
sparse_number_mat::smRes2Ideal
ideal smRes2Ideal()
Definition: sparsmat.cc:2561
p_Neg
static poly p_Neg(poly p, const ring r)
Definition: p_polys.h:1043
sparse_mat::smGetRed
int smGetRed()
Definition: sparsmat.cc:174
rKillModifiedRing
void rKillModifiedRing(ring r)
Definition: ring.cc:2958
id_IsConstant
BOOLEAN id_IsConstant(ideal id, const ring r)
test if the ideal has only constant polynomials NOTE: zero ideal/module is also constant
Definition: simpleideals.cc:391
sparse_mat::smGetSign
int smGetSign()
Definition: sparsmat.cc:172
smMinSelect
static void smMinSelect(long *, int, int)
Definition: sparsmat.cc:237
n_Delete
static FORCE_INLINE void n_Delete(number *p, const coeffs r)
delete 'p'
Definition: coeffs.h:456
p_Test
#define p_Test(p, r)
Definition: p_polys.h:163
omAllocBin
#define omAllocBin(bin)
Definition: omAllocDecl.h:205
pp_Mult_mm
static poly pp_Mult_mm(poly p, poly m, const ring r)
Definition: p_polys.h:987
n_IsZero
static FORCE_INLINE BOOLEAN n_IsZero(number n, const coeffs r)
TRUE iff 'n' represents the zero element.
Definition: coeffs.h:465
sm_RingChange
ring sm_RingChange(const ring origR, long bound)
Definition: sparsmat.cc:259
n_IsOne
static FORCE_INLINE BOOLEAN n_IsOne(number n, const coeffs r)
TRUE iff 'n' represents the one element.
Definition: coeffs.h:469
loop
#define loop
Definition: structs.h:78
smCheckSolv
static BOOLEAN smCheckSolv(ideal)
Definition: sparsmat.cc:2944
b
CanonicalForm b
Definition: cfModGcd.cc:4044
n_Normalize
static FORCE_INLINE void n_Normalize(number &n, const coeffs r)
inplace-normalization of n; produces some canonical representation of n;
Definition: coeffs.h:579
pp_Mult_Coeff_mm_DivSelect
static poly pp_Mult_Coeff_mm_DivSelect(poly p, const poly m, const ring r)
Definition: p_polys.h:1026
p_SetExp
static unsigned long p_SetExp(poly p, const unsigned long e, const unsigned long iBitmask, const int VarOffset)
set a single variable exponent @Note: VarOffset encodes the position in p->exp
Definition: p_polys.h:488
rCopy0
ring rCopy0(const ring r, BOOLEAN copy_qideal, BOOLEAN copy_ordering)
Definition: ring.cc:1325
prMoveR
poly prMoveR(poly &p, ring src_r, ring dest_r)
Definition: prCopy.cc:90
pLength
static unsigned pLength(poly a)
Definition: p_polys.h:192
currRing
ring currRing
Widely used global variable which specifies the current polynomial ring for Singular interpreter and ...
Definition: polys.cc:13
n_Add
static FORCE_INLINE number n_Add(number a, number b, const coeffs r)
return the sum of 'a' and 'b', i.e., a+b
Definition: coeffs.h:657
rVar
static short rVar(const ring r)
#define rVar(r) (r->N)
Definition: ring.h:583
kBucketExtractLm
poly kBucketExtractLm(kBucket_pt bucket)
Definition: kbuckets.cc:493
p_ExpVectorAdd
static void p_ExpVectorAdd(poly p1, poly p2, const ring r)
Definition: p_polys.h:1357
TRUE
#define TRUE
Definition: auxiliary.h:98
i
int i
Definition: cfEzgcd.cc:125
id_Delete
void id_Delete(ideal *h, ring r)
deletes an ideal/module/matrix
Definition: simpleideals.cc:114
res
CanonicalForm res
Definition: facAbsFact.cc:64
kBucket_Add_q
void kBucket_Add_q(kBucket_pt bucket, poly q, int *l)
Add to Bucket a poly ,i.e. Bpoly == q+Bpoly.
Definition: kbuckets.cc:636
idrMoveR
ideal idrMoveR(ideal &id, ring src_r, ring dest_r)
Definition: prCopy.cc:248
kBucketDestroy
void kBucketDestroy(kBucket_pt *bucket_pt)
Definition: kbuckets.cc:213
id_RankFreeModule
long id_RankFreeModule(ideal s, ring lmRing, ring tailRing)
return the maximal component number found in any polynomial in s
Definition: simpleideals.cc:782
M
#define M
Definition: sirandom.c:24
smnumber
sm_nrec * smnumber
Definition: sparsmat.cc:2312
TEST_OPT_NOT_BUCKETS
#define TEST_OPT_NOT_BUCKETS
Definition: options.h:104
omFreeSize
#define omFreeSize(addr, size)
Definition: omAllocDecl.h:260
BOOLEAN
int BOOLEAN
Definition: auxiliary.h:85
kBucketInit
void kBucketInit(kBucket_pt bucket, poly lm, int length)
Definition: kbuckets.cc:475
sm_FindRef
static void sm_FindRef(poly *, poly *, poly, const ring)
Definition: sparsmat.cc:2075
smpoly
sm_prec * smpoly
Definition: sparsmat.cc:47
smSmaller
static BOOLEAN smSmaller(poly, poly)
Definition: sparsmat.cc:2017
sparse_mat::smNewBareiss
void smNewBareiss(int, int)
Definition: sparsmat.cc:604
h
static Poly * h
Definition: janet.cc:972
p_LmDelete
static void p_LmDelete(poly p, const ring r)
Definition: p_polys.h:711
p_New
static poly p_New(const ring, omBin bin)
Definition: p_polys.h:664
sparse_number_mat::smIsSing
int smIsSing()
Definition: sparsmat.cc:2358
pp_Mult_qq
static poly pp_Mult_qq(poly p, poly q, const ring r)
Definition: p_polys.h:1093
intvec
Definition: intvec.h:17
pIter
#define pIter(p)
Definition: monomials.h:44
p_Cleardenom
poly p_Cleardenom(poly p, const ring r)
Definition: p_polys.cc:2782
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:637
omAlloc
#define omAlloc(size)
Definition: omAllocDecl.h:210
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:539
sm_CombineChain
static void sm_CombineChain(poly *, poly, const ring)
Definition: sparsmat.cc:2028
p_Init
static poly p_Init(const ring r, omBin bin)
Definition: p_polys.h:1266
p_LmCmp
static int p_LmCmp(poly p, poly q, const ring r)
Definition: p_polys.h:1507
sparse_mat::smRes2Mod
ideal smRes2Mod()
Definition: sparsmat.cc:503
pp
CanonicalForm pp(const CanonicalForm &)
CanonicalForm pp ( const CanonicalForm & f )
Definition: cf_gcd.cc:253
sm_KillModifiedRing
void sm_KillModifiedRing(ring r)
Definition: sparsmat.cc:290
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:558
sm_PolyDivN
static void sm_PolyDivN(poly, const number, const ring)
Definition: sparsmat.cc:2004
ringorder_c
@ ringorder_c
Definition: ring.h:79
ringorder_dp
@ ringorder_dp
Definition: ring.h:85
p_LmTest
#define p_LmTest(p, r)
Definition: p_polys.h:164
smnrec
Definition: sparsmat.cc:2313
sm_Cleardenom
static number sm_Cleardenom(ideal, const ring)
Definition: sparsmat.cc:2278
p_LmFree
static void p_LmFree(poly p, ring)
Definition: p_polys.h:683
p_Delete
static void p_Delete(poly *p, const ring r)
Definition: p_polys.h:857
p_Add_q
static poly p_Add_q(poly p, poly q, const ring r)
Definition: p_polys.h:892
pp_Mult_Coeff_mm_DivSelect_MultDiv
static poly pp_Mult_Coeff_mm_DivSelect_MultDiv(poly p, int &lp, poly m, poly a, poly b, const ring currRing)
Definition: sparsmat.cc:77
sm_SelectCopy_ExpMultDiv
static poly sm_SelectCopy_ExpMultDiv(poly p, poly m, poly a, poly b, const ring currRing)
Definition: sparsmat.cc:99
bound
static CanonicalForm bound(const CFMatrix &M)
Definition: cf_linsys.cc:460
sm_ExpMultDiv
static void sm_ExpMultDiv(poly, const poly, const poly, const ring)
Definition: sparsmat.cc:1986
Print
#define Print
Definition: emacs.cc:80
sparse_mat
Definition: sparsmat.cc:125
Werror
void Werror(const char *fmt,...)
Definition: reporter.cc:189
rOrd_is_Comp_dp
static BOOLEAN rOrd_is_Comp_dp(const ring r)
Definition: ring.h:767
p_SetCoeff
static number p_SetCoeff(poly p, number n, ring r)
Definition: p_polys.h:412
pSetCoeff0
#define pSetCoeff0(p, n)
Definition: monomials.h:66
SM_MIN_LENGTH_BUCKET
#define SM_MIN_LENGTH_BUCKET
Definition: sparsmat.cc:41
n_Copy
static FORCE_INLINE number n_Copy(number n, const coeffs r)
return a copy of 'n'
Definition: coeffs.h:452
WerrorS
void WerrorS(const char *s)
Definition: feFopen.cc:24
m
int m
Definition: cfEzgcd.cc:121
NULL
#define NULL
Definition: omList.c:10
sparse_number_mat
Definition: sparsmat.cc:2330
sparse_number_mat::smSolv
void smSolv()
Definition: sparsmat.cc:2484
p_SetComp
static unsigned long p_SetComp(poly p, unsigned long c, ring r)
Definition: p_polys.h:247
kBucket
Definition: kbuckets.h:175
R
#define R
Definition: sirandom.c:26
sparse_mat::smGetAct
smpoly * smGetAct()
Definition: sparsmat.cc:173
sparse_number_mat::smTriangular
void smTriangular()
Definition: sparsmat.cc:2453
sm_ExactPolyDiv
static void sm_ExactPolyDiv(poly, poly, const ring)
Definition: sparsmat.cc:1906
n_Equal
static FORCE_INLINE BOOLEAN n_Equal(number a, number b, const coeffs r)
TRUE iff 'a' and 'b' represent the same number; they may have different representations.
Definition: coeffs.h:461
p
int p
Definition: cfModGcd.cc:4019
p_IsConstantPoly
static BOOLEAN p_IsConstantPoly(const poly p, const ring r)
Definition: p_polys.h:1937
p_IsConstant
static BOOLEAN p_IsConstant(const poly p, const ring r)
Definition: p_polys.h:1923
kBucketCreate
kBucket_pt kBucketCreate(const ring bucket_ring)
Creation/Destruction of buckets.
Definition: kbuckets.cc:206
s
const CanonicalForm int s
Definition: facAbsFact.cc:55
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:616
sm_ExpBound
long sm_ExpBound(ideal m, int di, int ra, int t, const ring currRing)
Definition: sparsmat.cc:189
IDELEMS
#define IDELEMS(i)
Definition: simpleideals.h:26
sm_HaveDenom
static BOOLEAN sm_HaveDenom(poly, const ring)
Definition: sparsmat.cc:2259
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:51
n_Size
static FORCE_INLINE int n_Size(number n, const coeffs r)
return a non-negative measure for the complexity of n; return 0 only when n represents zero; (used fo...
Definition: coeffs.h:571
omFreeBin
#define omFreeBin(addr, bin)
Definition: omAllocDecl.h:259
p_LmDivisibleByNoComp
static BOOLEAN p_LmDivisibleByNoComp(poly a, poly b, const ring r)
Definition: p_polys.h:1801
n_GetDenom
static FORCE_INLINE number n_GetDenom(number &n, const coeffs r)
return the denominator of n (if elements of r are by nature not fractional, result is 1)
Definition: coeffs.h:604
rRingOrder_t
rRingOrder_t
order stuff
Definition: ring.h:74
pNext
#define pNext(p)
Definition: monomials.h:43
sparse_mat::smDet
poly smDet()
Definition: sparsmat.cc:530
omAlloc0
#define omAlloc0(size)
Definition: omAllocDecl.h:211
p_Mult_nn
static poly p_Mult_nn(poly p, number n, const ring r)
Definition: p_polys.h:914
idrCopyR
ideal idrCopyR(ideal id, ring src_r, ring dest_r)
Definition: prCopy.cc:192
rField_is_Q
static BOOLEAN rField_is_Q(const ring r)
Definition: ring.h:501
rComplete
BOOLEAN rComplete(ring r, int force)
this needs to be called whenever a new ring is created: new fields in ring are created (like VarOffse...
Definition: ring.cc:3351