Context Navigation

source: sage/rings/multi_polynomial_libsingular.pyx @ 4366:32bd4665bebf

Visit:

Revision 4366:32bd4665bebf, 86.6 KB checked in by William Stein <wstein@…>, 6 years ago (diff)
merge

Line
1	"""
2	Multivariate polynomials over QQ and GF(p) implemented using SINGULAR as backend.
3
4	AUTHORS:
5	Martin Albrecht <malb@informatik.uni-bremen.de>
6
7
8
9	TODO:
10	* implement every method from multi_polynomial_ring and multi_polynomial_element
11	* check SINGULAR code base for 'interesting' methods to add
12	* add required methods for F4, Buchberger etc.
13	* implement GF(p^n)
14	* implement block orderings
15	* implement Real, Complex
16	* test under CYGWIN (link error)
17
18	"""
19	# We do this as we get a link error for init_csage(). However, on
20	# obscure plattforms (Windows) we might need to link to csage anyway.
21
22	cdef extern from "stdsage.h":
23	ctypedef void PyObject
24	object PY_NEW(object t)
25	int PY_TYPE_CHECK(object o, object t)
26	PyObject** FAST_SEQ_UNSAFE(object o)
27	void init_csage()
28
29	void sage_free(void *p)
30	void* sage_realloc(void *p, size_t n)
31	void* sage_malloc(size_t)
32
33	import os
34	import sage.rings.memory
35
36	from sage.libs.singular.singular import Conversion
37	from sage.libs.singular.singular cimport Conversion
38
39	cdef Conversion co
40	co = Conversion()
41
42	from sage.rings.multi_polynomial_ring import singular_name_mapping, TermOrder
43	from sage.rings.multi_polynomial_ideal import MPolynomialIdeal
44	from sage.rings.polydict import ETuple
45
46	from sage.rings.rational_field import RationalField
47	from sage.rings.finite_field import FiniteField_prime_modn
48
49	from sage.rings.rational cimport Rational
50
51	from sage.interfaces.singular import singular as singular_default, is_SingularElement, SingularElement
52	from sage.interfaces.macaulay2 import macaulay2 as macaulay2_default, is_Macaulay2Element
53	from sage.structure.factorization import Factorization
54
55	from complex_field import is_ComplexField
56	from real_mpfr import is_RealField
57
58
59	from sage.rings.integer_ring import IntegerRing
60	from sage.structure.element cimport EuclideanDomainElement, \
61	RingElement, \
62	ModuleElement, \
63	Element, \
64	CommutativeRingElement
65
66	from sage.rings.integer cimport Integer
67
68	from sage.structure.parent cimport Parent
69	from sage.structure.parent_base cimport ParentWithBase
70	from sage.structure.parent_gens cimport ParentWithGens
71
72	from sage.misc.sage_eval import sage_eval
73	from sage.misc.latex import latex
74
75
76	# shared library loading
77	cdef extern from "dlfcn.h":
78	void dlopen(char , long)
79	char *dlerror()
80
81	cdef extern from "string.h":
82	char strdup(char s)
83
84
85	cdef init_singular():
86	"""
87	This initializes the Singular library. Right now, this is a hack.
88
89	SINGULAR has a concept of compiled extension modules similar to
90	SAGE. For this, the compiled modules need to see the symbols from
91	the main programm. However, SINGULAR is a shared library in this
92	context these symbols are not known globally. The work around so
93	far is to load the library again and to specifiy RTLD_GLOBAL.
94	"""
95
96	cdef void *handle
97
98
99	for extension in ["so", "dylib", "dll"]:
100	lib = os.environ['SAGE_LOCAL']+"/lib/libsingular."+extension
101	if os.path.exists(lib):
102	handle = dlopen(lib, 256+1)
103	break
104
105	if handle == NULL:
106	print dlerror()
107	raise ImportError, "cannot load libSINGULAR library"
108
109	# Load Singular
110	siInit(lib)
111
112	# Steal Memory Manager back or weird things may happen
113	sage.rings.memory.pmem_malloc()
114
115	# call it
116	init_singular()
117
118	cdef class MPolynomialRing_libsingular(MPolynomialRing_generic):
119	"""
120	A multivariate polynomial ring over QQ or GF(p) implemented using SINGULAR.
121
122	"""
123	def __init__(self, base_ring, n, names, order='degrevlex'):
124	"""
125
126	Construct a multivariate polynomial ring subject to the following conditions:
127
128	INPUT:
129	base_ring -- base ring (must be either GF(p) (p prime) or QQ)
130	n -- number of variables (must be at least 1)
131	names -- names of ring variables, may be string of list/tuple
132	order -- term order (default: degrevlex)
133
134	EXAMPLES:
135	sage: from sage.rings.multi_polynomial_libsingular import MPolynomialRing_libsingular
136	sage: P.<x,y,z> = MPolynomialRing_libsingular(QQ,3)
137	sage: P
138	Polynomial Ring in x, y, z over Rational Field
139
140	sage: f = 27/113 * x^2 + y*z + 1/2; f
141	27/113x^2 + yz + 1/2
142
143	sage: P.term_order()
144	Degree reverse lexicographic term order
145
146	sage: P = MPolynomialRing_libsingular(GF(127),3,names='abc', order='lex')
147	sage: P
148	Polynomial Ring in a, b, c over Finite Field of size 127
149
150	sage: a,b,c = P.gens()
151	sage: f = 57 * a^2b + 43 c + 1; f
152	57a^2b + 43*c + 1
153
154	sage: P.term_order()
155	Lexicographic term order
156
157	"""
158	cdef char **_names
159	cdef char *_name
160	cdef int i
161	cdef int characteristic
162
163	n = int(n)
164	if n<1:
165	raise ArithmeticError, "number of variables must be at least 1"
166
167	self.__ngens = n
168
169	MPolynomialRing_generic.__init__(self, base_ring, n, names, TermOrder(order))
170
171	self._has_singular = True
172
173	_names = <char*>sage_malloc(sizeof(char)*len(self._names))
174
175	for i from 0 <= i < n:
176	_name = self._names[i]
177	_names[i] = strdup(_name)
178
179	if PY_TYPE_CHECK(base_ring, FiniteField_prime_modn):
180	characteristic = base_ring.characteristic()
181
182	elif PY_TYPE_CHECK(base_ring, RationalField):
183	characteristic = 0
184
185	else:
186	raise NotImplementedError, "Only GF(p) and QQ are supported right now, sorry"
187
188	try:
189	order = singular_name_mapping[order]
190	except KeyError:
191	pass
192
193	self._ring = rDefault(characteristic, n, _names)
194	if(self._ring != currRing): rChangeCurrRing(self._ring)
195
196	rUnComplete(self._ring)
197
198	omFree(self._ring.wvhdl)
199	omFree(self._ring.order)
200	omFree(self._ring.block0)
201	omFree(self._ring.block1)
202
203	self._ring.wvhdl = <int *>omAlloc0(3 sizeof(int*))
204	self._ring.order = <int >omAlloc0(3 sizeof(int *))
205	self._ring.block0 = <int >omAlloc0(3 sizeof(int *))
206	self._ring.block1 = <int >omAlloc0(3 sizeof(int *))
207
208	if order == "dp":
209	self._ring.order[0] = ringorder_dp
210	elif order == "Dp":
211	self._ring.order[0] = ringorder_Dp
212	elif order == "lp":
213	self._ring.order[0] = ringorder_lp
214	elif order == "rp":
215	self._ring.order[0] = ringorder_rp
216	else:
217	self._ring.order[0] = ringorder_lp
218
219	self._ring.order[1] = ringorder_C
220
221	self._ring.block0[0] = 1
222	self._ring.block1[0] = n
223
224	rComplete(self._ring, 1)
225	self._ring.ShortOut = 0
226
227	self._zero = <MPolynomial_libsingular>new_MP(self,NULL)
228
229	for i from 0 <= i < n:
230	free(_names[i]) # strdup() --> free()
231	sage_free(_names)
232
233	def __dealloc__(self):
234	"""
235	"""
236	rDelete(self._ring)
237
238	cdef _coerce_c_impl(self, element):
239	"""
240
241	Coerces elements to self.
242
243	EXAMPLES:
244	sage: from sage.rings.multi_polynomial_libsingular import MPolynomialRing_libsingular
245	sage: P.<x,y,z> = MPolynomialRing_libsingular(QQ,3)
246
247	We can coerce elements of self to self
248
249	sage: P._coerce_(x*y + 1/2)
250	x*y + 1/2
251
252	We can coerce elements for a ring with the same algebraic properties
253
254	sage: R.<x,y,z> = MPolynomialRing_libsingular(QQ,3)
255	sage: P == R
256	True
257
258	sage: P is R
259	False
260
261	sage: P._coerce_(x*y + 1)
262	x*y + 1
263
264	We can coerce base ring elements
265
266	sage: P._coerce_(3/2)
267	3/2
268
269	sage: P._coerce_(ZZ(1))
270	1
271
272	sage: P._coerce_(int(1))
273	1
274
275	"""
276	cdef poly *_p
277	cdef ring *_ring
278	cdef number *_n
279	cdef poly *rm
280	cdef int ok
281	cdef int i
282	cdef ideal from_id, to_id, *res_id
283
284	_ring = self._ring
285
286	if(_ring != currRing): rChangeCurrRing(_ring)
287
288	if PY_TYPE_CHECK(element, MPolynomial_libsingular):
289	if element.parent() is <object>self:
290	return element
291	elif element.parent() == self:
292	# is this safe?
293	_p = p_Copy((<MPolynomial_libsingular>element)._poly, _ring)
294	else:
295	raise TypeError, "parents do not match"
296
297	elif PY_TYPE_CHECK(element, CommutativeRingElement):
298	# Accepting ZZ
299	if element.parent() is IntegerRing():
300	_p = p_ISet(int(element), _ring)
301
302	elif <Parent>element.parent() is self._base:
303	# Accepting GF(p)
304	if PY_TYPE_CHECK(self._base, FiniteField_prime_modn):
305	_p = p_ISet(int(element), _ring)
306
307	# Accepting QQ
308	elif PY_TYPE_CHECK(self._base, RationalField):
309	_n = co.sa2si_QQ(element,_ring)
310	_p = p_NSet(_n, _ring)
311	else:
312	raise NotImplementedError
313	else:
314	raise TypeError, "base rings must be identical"
315
316	# Accepting int
317	elif PY_TYPE_CHECK(element, int):
318	_p = p_ISet(int(element), _ring)
319	else:
320	raise TypeError, "Cannot coerce element"
321
322	return new_MP(self,_p)
323
324	def __call__(self, element):
325	"""
326	Construct a new element in self.
327
328	INPUT:
329	element -- several types are supported, see below
330
331	EXAMPLE:
332	Call supports all conversions _coerce_ supports, plus:
333
334	sage: from sage.rings.multi_polynomial_libsingular import MPolynomialRing_libsingular
335	sage: P.<x,y,z> = MPolynomialRing_libsingular(QQ,3)
336	sage: P('x+y + 1/4')
337	x + y + 1/4
338
339	sage: P._singular_()
340	// characteristic : 0
341	// number of vars : 3
342	// block 1 : ordering dp
343	// : names x y z
344	// block 2 : ordering C
345
346	sage: P(singular('x + 3/4'))
347	x + 3/4
348	"""
349	cdef poly _m, _p, *_tmp
350	cdef ring *_r
351
352	if PY_TYPE_CHECK(element, SingularElement):
353	element = str(element)
354
355	if PY_TYPE_CHECK(element,str):
356	# let python do the the parsing
357	return sage_eval(element,self.gens_dict())
358
359	# this almost does what I want, besides variables with 0-9 in their names
360	## _r = self._ring
361	## if(_r != currRing): rChangeCurrRing(_r)
362	## # improve this
363	## element = element.replace('^','').replace('**','').replace(' ','').strip()
364	## monomials = element.split('+')
365	## _p = p_ISet(0, _r)
366	## # wrong for e.g. x0,..,x7
367	## for m in monomials:
368	## _m = p_ISet(1,_r)
369	## for var in m.split('*'):
370	## p_Read(var, _tmp, _r)
371	## _m = p_Mult_q(_m,_tmp, _r)
372
373	## _p = p_Add_q(_p,_m,_r)
374
375	## return new_MP(self,_p)
376
377	return self._coerce_c_impl(element)
378
379	def _repr_(self):
380	"""
381	EXAMPLE:
382	sage: from sage.rings.multi_polynomial_libsingular import MPolynomialRing_libsingular
383	sage: P.<x,y> = MPolynomialRing_libsingular(QQ, 2)
384	sage: P
385	Polynomial Ring in x, y over Rational Field
386
387	"""
388	varstr = ", ".join([ rRingVar(i,self._ring) for i in range(self.__ngens) ])
389	return "Polynomial Ring in %s over %s"%(varstr,self._base)
390
391	def ngens(self):
392	"""
393	Returns the number of variables in self.
394
395	EXAMPLES:
396	sage: from sage.rings.multi_polynomial_libsingular import MPolynomialRing_libsingular
397	sage: P.<x,y> = MPolynomialRing_libsingular(QQ, 2)
398	sage: P.ngens()
399	2
400
401	sage: P = MPolynomialRing_libsingular(GF(127),1000,'x')
402	sage: P.ngens()
403	1000
404
405	"""
406	return int(self.__ngens)
407
408	def gens(self):
409	"""
410	Return the tuple of variables in self.
411
412	EXAMPLES:
413	sage: from sage.rings.multi_polynomial_libsingular import MPolynomialRing_libsingular
414	sage: P.<x,y,z> = MPolynomialRing_libsingular(QQ,3)
415	sage: P.gens()
416	(x, y, z)
417
418	sage: P = MPolynomialRing_libsingular(QQ,10,'x')
419	sage: P.gens()
420	(x0, x1, x2, x3, x4, x5, x6, x7, x8, x9)
421
422	sage: P.<SAGE,SINGULAR> = MPolynomialRing_libsingular(QQ,2) # weird names
423	sage: P.gens()
424	(SAGE, SINGULAR)
425
426	"""
427	return tuple([self.gen(i) for i in range(self.__ngens) ])
428
429	def gen(self, int n=0):
430	"""
431	Returns the n-th generator of self.
432
433	EXAMPLES:
434	sage: from sage.rings.multi_polynomial_libsingular import MPolynomialRing_libsingular
435	sage: P.<x,y,z> = MPolynomialRing_libsingular(QQ,3)
436	sage: P.gen(),P.gen(1)
437	(x, y)
438
439	sage: P = MPolynomialRing_libsingular(GF(127),1000,'x')
440	sage: P.gen(500)
441	x500
442
443	sage: P.<SAGE,SINGULAR> = MPolynomialRing_libsingular(QQ,2) # weird names
444	sage: P.gen(1)
445	SINGULAR
446
447	"""
448	cdef poly *_p
449	cdef ring *_ring
450
451	if n < 0 or n >= self.__ngens:
452	raise ValueError, "Generator not defined."
453
454	_ring = self._ring
455	_p = p_ISet(1,_ring)
456
457	# oddly enough, Singular starts counting a 1!!!
458	p_SetExp(_p, n+1, 1, _ring)
459	p_Setm(_p, _ring);
460
461	return new_MP(self,_p)
462
463	def ideal(self, gens, coerce=True):
464	"""
465	Create an ideal in this polynomial ring.
466
467	INPUT:
468	gens -- generators of the ideal
469	coerce -- shall the generators be coerced first (default:True)
470
471	EXAMPLE:
472	sage: from sage.rings.multi_polynomial_libsingular import MPolynomialRing_libsingular
473	sage: P.<x,y,z> = MPolynomialRing_libsingular(QQ,3)
474	sage: sage.rings.ideal.Katsura(P)
475	Ideal (x + 2y + 2z - 1, x^2 + 2y^2 + 2z^2 - x, 2xy + 2yz - y) of Polynomial Ring in x, y, z over Rational Field
476
477	sage: P.ideal([x + 2y + 2z-1, 2xy + 2yz-y, x^2 + 2y^2 + 2z^2-x])
478	Ideal (x + 2y + 2z - 1, 2xy + 2yz - y, x^2 + 2y^2 + 2z^2 - x) of Polynomial Ring in x, y, z over Rational Field
479
480	"""
481	if is_SingularElement(gens):
482	gens = list(gens)
483	coerce = True
484	if is_Macaulay2Element(gens):
485	gens = list(gens)
486	coerce = True
487	elif not isinstance(gens, (list, tuple)):
488	gens = [gens]
489	if coerce:
490	gens = [self(x) for x in gens] # this will even coerce from singular ideals correctly!
491	return MPolynomialIdeal(self, gens, coerce=False)
492
493	def _macaulay2_(self, macaulay2=macaulay2_default):
494	"""
495	Create a M2 representation of self if Macaulay2 is installed.
496
497	INPUT:
498	macaulay2 -- M2 interpreter (default: macaulay2_default)
499	"""
500	try:
501	R = self.__macaulay2
502	if R is None or not (R.parent() is macaulay2):
503	raise ValueError
504	R._check_valid()
505	return R
506	except (AttributeError, ValueError):
507	if self.base_ring().is_prime_field():
508	if self.characteristic() == 0:
509	base_str = "QQ"
510	else:
511	base_str = "ZZ/" + str(self.characteristic())
512	elif is_IntegerRing(self.base_ring()):
513	base_str = "ZZ"
514	else:
515	raise TypeError, "no conversion of to a Macaulay2 ring defined"
516	self.__macaulay2 = macaulay2.ring(base_str, str(self.gens()), \
517	self.term_order().macaulay2_str())
518	return self.__macaulay2
519
520	def _singular_(self, singular=singular_default):
521	"""
522	Create a SINGULAR (as in the CAS) representation of self. The
523	result is cached.
524
525	INPUT:
526	singular -- SINGULAR interpreter (default: singular_default)
527
528	EXAMPLES:
529	sage: from sage.rings.multi_polynomial_libsingular import MPolynomialRing_libsingular
530	sage: P.<x,y,z> = MPolynomialRing_libsingular(QQ,3)
531	sage: P._singular_()
532	// characteristic : 0
533	// number of vars : 3
534	// block 1 : ordering dp
535	// : names x y z
536	// block 2 : ordering C
537
538	sage: P._singular_() is P._singular_()
539	True
540
541	sage: P._singular_().name() == P._singular_().name()
542	True
543
544	TESTS:
545	sage: from sage.rings.multi_polynomial_libsingular import MPolynomialRing_libsingular
546	sage: P.<x> = MPolynomialRing_libsingular(QQ,1)
547	sage: P._singular_()
548	// characteristic : 0
549	// number of vars : 1
550	// block 1 : ordering lp
551	// : names x
552	// block 2 : ordering C
553
554	"""
555	try:
556	R = self.__singular
557	if R is None or not (R.parent() is singular):
558	raise ValueError
559	R._check_valid()
560	if self.base_ring().is_prime_field():
561	return R
562	if self.base_ring().is_finite():
563	R.set_ring() #sorry for that, but needed for minpoly
564	if singular.eval('minpoly') != self.__minpoly:
565	singular.eval("minpoly=%s"%(self.__minpoly))
566	return R
567	except (AttributeError, ValueError):
568	return self._singular_init_(singular)
569
570	def _singular_init_(self, singular=singular_default):
571	"""
572	Create a SINGULAR (as in the CAS) representation of self. The
573	result is NOT cached.
574
575	INPUT:
576	singular -- SINGULAR interpreter (default: singular_default)
577
578	EXAMPLES:
579	sage: from sage.rings.multi_polynomial_libsingular import MPolynomialRing_libsingular
580	sage: P.<x,y,z> = MPolynomialRing_libsingular(QQ,3)
581	sage: P._singular_init_()
582	// characteristic : 0
583	// number of vars : 3
584	// block 1 : ordering dp
585	// : names x y z
586	// block 2 : ordering C
587	sage: P._singular_init_() is P._singular_init_()
588	False
589
590	sage: P._singular_init_().name() == P._singular_init_().name()
591	False
592
593	TESTS:
594	sage: from sage.rings.multi_polynomial_libsingular import MPolynomialRing_libsingular
595	sage: P.<x> = MPolynomialRing_libsingular(QQ,1)
596	sage: P._singular_init_()
597	// characteristic : 0
598	// number of vars : 1
599	// block 1 : ordering lp
600	// : names x
601	// block 2 : ordering C
602
603	"""
604	if self.ngens()==1:
605	_vars = str(self.gen())
606	if "" in _vars: # 1.000...000x
607	_vars = _vars.split("*")[1]
608	order = 'lp'
609	else:
610	_vars = str(self.gens())
611	order = self.term_order().singular_str()
612
613	if is_RealField(self.base_ring()):
614	# singular converts to bits from base_10 in mpr_complex.cc by:
615	# size_t bits = 1 + (size_t) ((float)digits * 3.5);
616	precision = self.base_ring().precision()
617	digits = sage.rings.arith.ceil((2*precision - 2)/7.0)
618	self.__singular = singular.ring("(real,%d,0)"%digits, _vars, order=order)
619
620	elif is_ComplexField(self.base_ring()):
621	# singular converts to bits from base_10 in mpr_complex.cc by:
622	# size_t bits = 1 + (size_t) ((float)digits * 3.5);
623	precision = self.base_ring().precision()
624	digits = sage.rings.arith.ceil((2*precision - 2)/7.0)
625	self.__singular = singular.ring("(complex,%d,0,I)"%digits, _vars, order=order)
626
627	elif self.base_ring().is_prime_field():
628	self.__singular = singular.ring(self.characteristic(), _vars, order=order)
629
630	elif self.base_ring().is_finite(): #must be extension field
631	gen = str(self.base_ring().gen())
632	r = singular.ring( "(%s,%s)"%(self.characteristic(),gen), _vars, order=order)
633	self.__minpoly = "("+(str(self.base_ring().modulus()).replace("x",gen)).replace(" ","")+")"
634	singular.eval("minpoly=%s"%(self.__minpoly) )
635
636	self.__singular = r
637	else:
638	raise TypeError, "no conversion to a Singular ring defined"
639
640	return self.__singular
641
642	def __hash__(self):
643	"""
644	Return a hash for self, that is, a hash of the string representation of self
645
646	EXAMPLE:
647	sage: from sage.rings.multi_polynomial_libsingular import MPolynomialRing_libsingular
648	sage: P.<x,y,z> = MPolynomialRing_libsingular(QQ,3)
649	sage: hash(P)
650	-6257278808099690586 # 64-bit
651	-1767675994 # 32-bit
652	"""
653	return hash(self.__repr__())
654
655	def __richcmp__(left, right, int op):
656	return (<Parent>left)._richcmp(right, op)
657
658	cdef int _cmp_c_impl(left, Parent right) except -2:
659	"""
660	Multivariate polynomial rings are said to be equal if:
661	* their base rings match
662	* their generator names match
663	* their term orderings match
664
665	EXAMPLES:
666	sage: from sage.rings.multi_polynomial_libsingular import MPolynomialRing_libsingular
667	sage: P.<x,y,z> = MPolynomialRing_libsingular(QQ,3)
668	sage: R.<x,y,z> = MPolynomialRing_libsingular(QQ,3)
669	sage: P == R
670	True
671
672	sage: R.<x,y,z> = MPolynomialRing_libsingular(GF(127),3)
673	sage: P == R
674	False
675
676	sage: R.<x,y> = MPolynomialRing_libsingular(QQ,2)
677	sage: P == R
678	False
679
680	sage: R.<x,y,z> = MPolynomialRing_libsingular(QQ,3,order='revlex')
681	sage: P == R
682	False
683
684
685	"""
686	if PY_TYPE_CHECK(right, MPolynomialRing_libsingular):
687	return cmp( (left.base_ring(), map(str, left.gens()), left.term_order()),
688	(right.base_ring(), map(str, right.gens()), right.term_order())
689	)
690	else:
691	return cmp(type(left),type(right))
692
693	def __reduce__(self):
694	"""
695	Serializes self.
696
697	EXAMPLES:
698	sage: from sage.rings.multi_polynomial_libsingular import MPolynomialRing_libsingular
699	sage: P.<x,y,z> = MPolynomialRing_libsingular(QQ,3, order='degrevlex')
700	sage: P == loads(dumps(P))
701	True
702
703	sage: P = MPolynomialRing_libsingular(GF(127),3,names='abc')
704	sage: P == loads(dumps(P))
705	True
706
707	"""
708	return sage.rings.multi_polynomial_libsingular.unpickle_MPolynomialRing_libsingular, ( self.base_ring(),
709	map(str, self.gens()),
710	self.term_order() )
711
712	### The following methods are handy for implementing e.g. F4. They
713	### do only superficial type/sanity checks and should be called
714	### carefully.
715
716	def monomial_m_div_n(self, MPolynomial_libsingular f, MPolynomial_libsingular g, coeff=False):
717	"""
718	Return f/g, where both f and g are treated as
719	monomials. Coefficients are ignored by default.
720
721	INPUT:
722	f -- monomial
723	g -- monomial
724	coeff -- divide coefficents as well (default: False)
725
726	EXAMPLE:
727	sage: from sage.rings.multi_polynomial_libsingular import MPolynomialRing_libsingular
728	sage: P.<x,y,z>=MPolynomialRing_libsingular(QQ,3)
729	sage: P.monomial_m_div_n(3/2xy,x)
730	y
731
732	sage: P.monomial_m_div_n(3/2xy,x,coeff=True)
733	3/2*y
734
735	TESTS:
736	sage: from sage.rings.multi_polynomial_libsingular import MPolynomialRing_libsingular
737	sage: R.<x,y,z>=MPolynomialRing_libsingular(QQ,3)
738	sage: P.<x,y,z>=MPolynomialRing_libsingular(QQ,3)
739	sage: P.monomial_m_div_n(x*y,x)
740	y
741
742	sage: P.monomial_m_div_n(x*y,R.gen())
743	y
744
745	sage: P.monomial_m_div_n(P(0),P(1))
746	0
747
748	sage: P.monomial_m_div_n(P(1),P(0))
749	Traceback (most recent call last):
750	...
751	ZeroDivisionError
752
753	sage: P.monomial_m_div_n(P(3/2),P(2/3), coeff=True)
754	9/4
755
756	sage: P.monomial_m_div_n(x,y) # Note the wrong result
757	xy^1048575z^1048575 # 64-bit
758	xy^65535z^65535 # 32-bit
759
760	sage: P.monomial_m_div_n(x,P(1))
761	x
762
763	NOTE: Assumes that the head term of f is a multiple of the
764	head term of g and return the multiplicant m. If this rule is
765	violated, funny things may happen.
766
767
768
769	"""
770	cdef poly *res
771	cdef ring *r = self._ring
772
773	if not <ParentWithBase>self is f._parent:
774	f = self._coerce_c(f)
775	if not <ParentWithBase>self is g._parent:
776	g = self._coerce_c(g)
777
778	if(r != currRing): rChangeCurrRing(r)
779
780	if not f._poly:
781	return self._zero
782	if not g._poly:
783	raise ZeroDivisionError
784
785	res = pDivide(f._poly,g._poly)
786	if coeff:
787	p_SetCoeff(res, n_Div( p_GetCoeff(f._poly, r) , p_GetCoeff(g._poly, r), r), r)
788	else:
789	p_SetCoeff(res, n_Init(1, r), r)
790	return new_MP(self, res)
791
792	def monomial_lcm(self, MPolynomial_libsingular f, MPolynomial_libsingular g):
793	"""
794	LCM for monomials. Coefficients are ignored.
795
796	INPUT:
797	f -- monomial
798	g -- monomial
799
800	EXAMPLE:
801	sage: from sage.rings.multi_polynomial_libsingular import MPolynomialRing_libsingular
802	sage: P.<x,y,z>=MPolynomialRing_libsingular(QQ,3)
803	sage: P.monomial_lcm(3/2xy,x)
804	x*y
805
806	TESTS:
807	sage: from sage.rings.multi_polynomial_libsingular import MPolynomialRing_libsingular
808	sage: R.<x,y,z>=MPolynomialRing_libsingular(QQ,3)
809	sage: P.<x,y,z>=MPolynomialRing_libsingular(QQ,3)
810	sage: P.monomial_lcm(x*y,R.gen())
811	x*y
812
813	sage: P.monomial_lcm(P(3/2),P(2/3))
814	1
815
816	sage: P.monomial_lcm(x,P(1))
817	x
818
819	"""
820	cdef poly *m = p_ISet(1,self._ring)
821
822	if not <ParentWithBase>self is f._parent:
823	f = self._coerce_c(f)
824	if not <ParentWithBase>self is g._parent:
825	g = self._coerce_c(g)
826
827	if f._poly == NULL:
828	if g._poly == NULL:
829	return self._zero
830	else:
831	raise ArithmeticError, "cannot compute lcm of zero and nonzero element"
832	if g._poly == NULL:
833	raise ArithmeticError, "cannot compute lcm of zero and nonzero element"
834
835	if(self._ring != currRing): rChangeCurrRing(self._ring)
836
837	pLcm(f._poly, g._poly, m)
838	return new_MP(self,m)
839
840	def monomial_reduce(self, MPolynomial_libsingular f, G):
841	"""
842	Try to find a g in G where g.lm() divides f. If found (g,flt)
843	is returned, (0,0) otherwise, where flt is f/g.lm().
844
845	It is assumed that G is iterable and contains ONLY elements in
846	self.
847
848	INPUT:
849	f -- monomial
850	G -- list/set of mpolynomials
851
852	EXAMPLES:
853	sage: from sage.rings.multi_polynomial_libsingular import MPolynomialRing_libsingular
854	sage: P.<x,y,z>=MPolynomialRing_libsingular(QQ,3)
855	sage: f = x*y^2
856	sage: G = [ 3/2x^3 + y^2 + 1/2, 1/4x*y + 2/7, 1/2 ]
857	sage: P.monomial_reduce(f,G)
858	(1/4xy + 2/7, y)
859
860	TESTS:
861	sage: from sage.rings.multi_polynomial_libsingular import MPolynomialRing_libsingular
862	sage: P.<x,y,z>=MPolynomialRing_libsingular(QQ,3)
863	sage: f = x*y^2
864	sage: G = [ 3/2x^3 + y^2 + 1/2, 1/4x*y + 2/7, 1/2 ]
865
866	sage: P.monomial_reduce(P(0),G)
867	(0, 0)
868
869	sage: P.monomial_reduce(f,[P(0)])
870	(0, 0)
871
872	"""
873	cdef poly *m = f._poly
874	cdef ring *r = self._ring
875	cdef poly *flt
876
877	if not m:
878	return f,f
879
880	for g in G:
881	if PY_TYPE_CHECK(g, MPolynomial_libsingular) \
882	and (<MPolynomial_libsingular>g) \
883	and p_LmDivisibleBy((<MPolynomial_libsingular>g)._poly, m, r):
884	flt = pDivide(f._poly, (<MPolynomial_libsingular>g)._poly)
885	#p_SetCoeff(flt, n_Div( p_GetCoeff(f._poly, r) , p_GetCoeff((<MPolynomial_libsingular>g)._poly, r), r), r)
886	p_SetCoeff(flt, n_Init(1, r), r)
887	return g, new_MP(self,flt)
888	return self._zero,self._zero
889
890	def monomial_pairwise_prime(self, MPolynomial_libsingular g, MPolynomial_libsingular h):
891	"""
892	Return True if h and g are pairwise prime. Both are treated as monomials.
893
894	INPUT:
895	h -- monomial
896	g -- monomial
897
898	EXAMPLES:
899	sage: from sage.rings.multi_polynomial_libsingular import MPolynomialRing_libsingular
900	sage: P.<x,y,z> = MPolynomialRing_libsingular(QQ,3)
901	sage: P.monomial_pairwise_prime(x^2*z^3, y^4)
902	True
903
904	sage: P.monomial_pairwise_prime(1/2x^3y^2, 3/4*y^3)
905	False
906
907	TESTS:
908	sage: from sage.rings.multi_polynomial_libsingular import MPolynomialRing_libsingular
909	sage: Q.<x,y,z> = MPolynomialRing_libsingular(QQ,3)
910	sage: P.<x,y,z> = MPolynomialRing_libsingular(QQ,3)
911	sage: P.monomial_pairwise_prime(x^2*z^3, Q('y^4'))
912	True
913
914	sage: P.monomial_pairwise_prime(1/2x^3y^2, Q(0))
915	True
916
917	sage: P.monomial_pairwise_prime(P(1/2),x)
918	False
919
920
921	"""
922	cdef int i
923	cdef ring *r
924	cdef poly p, q
925
926	if h._parent is not g._parent:
927	g = (<MPolynomialRing_libsingular>h._parent)._coerce_c(g)
928
929	r = (<MPolynomialRing_libsingular>h._parent)._ring
930	p = g._poly
931	q = h._poly
932
933	if p == NULL:
934	if q == NULL:
935	return False #GCD(0,0) = 0
936	else:
937	return True #GCD(x,0) = 1
938
939	elif q == NULL:
940	return True # GCD(0,x) = 1
941
942	elif p_IsConstant(p,r) or p_IsConstant(q,r): # assuming a base field
943	return False
944
945	for i from 1 <= i <= r.N:
946	if p_GetExp(p,i,r) and p_GetExp(q,i,r):
947	return False
948	return True
949
950	def monomial_is_divisible_by(self, MPolynomial_libsingular a, MPolynomial_libsingular b):
951	"""
952	Return 0 if b does not divide a and the factor
953	otherwise. Coefficients are ignored.
954
955	INPUT:
956	a -- monomial
957	b -- monomial
958
959	EXAMPLES:
960	sage: from sage.rings.multi_polynomial_libsingular import MPolynomialRing_libsingular
961	sage: P.<x,y,z>=MPolynomialRing_libsingular(QQ,3)
962	sage: P.monomial_is_divisible_by(x^3y^2z^4, xyz)
963	x^2yz^3
964	sage: P.monomial_is_divisible_by(xyz, x^3y^2z^4)
965	0
966
967	TESTS:
968	sage: from sage.rings.multi_polynomial_libsingular import MPolynomialRing_libsingular
969	sage: P.<x,y,z>=MPolynomialRing_libsingular(QQ,3)
970	sage: P.monomial_is_divisible_by(P(0),P(1))
971	0
972	sage: P.monomial_is_divisible_by(x,P(1))
973	x
974
975	"""
976	cdef poly *_a
977	cdef poly *_b
978	cdef ring *_r
979	cdef poly *ret
980	if a._parent is not b._parent:
981	b = (<MPolynomialRing_libsingular>a._parent)._coerce_c(b)
982
983	_a = a._poly
984	_b = b._poly
985	_r = (<MPolynomialRing_libsingular>a._parent)._ring
986	if(_r != currRing): rChangeCurrRing(_r)
987
988	if _b == NULL:
989	raise ZeroDivisionError
990	if _a == NULL:
991	return self._zero
992
993	if not p_DivisibleBy(_b, _a, _r):
994	return self._zero
995	else:
996	ret = pDivide(_a,_b)
997	p_SetCoeff(ret, n_Init(1, _r), _r)
998	return new_MP(self,ret)
999
1000	def unpickle_MPolynomialRing_libsingular(base_ring, names, term_order):
1001	"""
1002	inverse function for MPolynomialRing_libsingular.__reduce__
1003
1004	"""
1005	return MPolynomialRing_libsingular(base_ring, len(names), names, term_order)
1006
1007	cdef MPolynomial_libsingular new_MP(MPolynomialRing_libsingular parent, poly *juice):
1008	"""
1009	Construct a new MPolynomial_libsingular element
1010	"""
1011	cdef MPolynomial_libsingular p
1012	p = PY_NEW(MPolynomial_libsingular)
1013	p._parent = <ParentWithBase>parent
1014	p._poly = juice
1015	return p
1016
1017	cdef class MPolynomial_libsingular(sage.rings.multi_polynomial.MPolynomial):
1018	"""
1019	A multivariate polynomial implemented using libSINGULAR.
1020	"""
1021	def __init__(self, MPolynomialRing_libsingular parent):
1022	"""
1023	Construct a zero element in parent.
1024	"""
1025	self._parent = <ParentWithBase>parent
1026
1027	def __dealloc__(self):
1028	if self._poly:
1029	p_Delete(&self._poly, (<MPolynomialRing_libsingular>self._parent)._ring)
1030
1031	def __call__(self, *x):
1032	"""
1033	Evaluate a polynomial at the given point x
1034
1035	INPUT:
1036	x -- a list of elements in self.parent()
1037
1038	EXAMPLES:
1039	sage: from sage.rings.multi_polynomial_libsingular import MPolynomialRing_libsingular
1040	sage: P.<x,y,z>=MPolynomialRing_libsingular(QQ,3)
1041	sage: f = 3/2x^2y + 1/7 * y^2 + 13/27
1042	sage: f(0,0,0)
1043	13/27
1044
1045	sage: f(1,1,1)
1046	803/378
1047	sage: 3/2 + 1/7 + 13/27
1048	803/378
1049
1050	sage: f(45/2,19/3,1)
1051	7281167/1512
1052
1053	TESTS:
1054	sage: from sage.rings.multi_polynomial_libsingular import MPolynomialRing_libsingular
1055	sage: P.<x,y,z>=MPolynomialRing_libsingular(QQ,3)
1056	sage: P(0)(1,2,3)
1057	0
1058	sage: P(3/2)(1,2,3)
1059	3/2
1060	"""
1061	cdef int l = len(x)
1062	cdef MPolynomialRing_libsingular parent = (<MPolynomialRing_libsingular>self._parent)
1063	cdef ring *_ring = parent._ring
1064
1065	cdef poly *_p
1066
1067	if l != parent._ring.N:
1068	raise TypeError, "number of arguments does not match number of variables in parent"
1069
1070	return self.fix(dict(zip(parent.gens(), x)))
1071
1072	### the following is going to be faster at some size, but slower in general
1073	### TODO: find the crossover point
1074	## cdef ideal *to_id = idInit(l,1)
1075
1076	## try:
1077	## for i from 0 <= i < l:
1078	## e = x[i] # TODO: optimize this line
1079	## to_id.m[i]= p_Copy( (<MPolynomial_libsingular>(<MPolynomialRing_libsingular>parent._coerce_c(x[i])))._poly, _ring)
1080
1081	## except TypeError:
1082	## id_Delete(&to_id, _ring)
1083	## raise TypeError, "cannot coerce in arguments"
1084
1085	## cdef ideal *from_id=idInit(1,1)
1086	## from_id.m[0] = p_Copy(self._poly, _ring)
1087
1088	## cdef ideal *res_id = fast_map(from_id, _ring, to_id, _ring)
1089	## cdef poly *res = p_Copy(res_id.m[0], _ring)
1090
1091	## id_Delete(&to_id, _ring)
1092	## id_Delete(&from_id, _ring)
1093	## id_Delete(&res_id, _ring)
1094	## return new_MP(parent, res)
1095
1096	def __richcmp__(left, right, int op):
1097	return (<Element>left)._richcmp(right, op)
1098
1099	cdef int _cmp_c_impl(left, Element right) except -2:
1100	"""
1101	Compare left and right and return -1, 0, and 1 for <,==, and > respectively.
1102
1103	EXAMPLES:
1104	sage: from sage.rings.multi_polynomial_libsingular import MPolynomialRing_libsingular
1105	sage: P.<x,y,z> = MPolynomialRing_libsingular(QQ,3, order='degrevlex')
1106	sage: x == x
1107	True
1108
1109	sage: x > y
1110	True
1111	sage: y^2 > x
1112	True
1113
1114	sage: (2/3x^2 + 1/2y + 3) > (2/3x^2 + 1/4y + 10)
1115	True
1116
1117	TESTS:
1118	sage: from sage.rings.multi_polynomial_libsingular import MPolynomialRing_libsingular
1119	sage: P.<x,y,z> = MPolynomialRing_libsingular(QQ,3, order='degrevlex')
1120	sage: x > P(0)
1121	True
1122
1123	sage: P(0) == P(0)
1124	True
1125
1126	sage: P(0) < P(1)
1127	True
1128
1129	sage: x > P(1)
1130	True
1131
1132	sage: 1/2x < 3/4x
1133	True
1134
1135	sage: (x+1) > x
1136	True
1137
1138	sage: f = 3/4x^2y + 1/2*x + 2/7
1139	sage: f > f
1140	False
1141	sage: f < f
1142	False
1143	sage: f == f
1144	True
1145
1146	sage: from sage.rings.multi_polynomial_libsingular import MPolynomialRing_libsingular
1147	sage: P.<x,y,z> = MPolynomialRing_libsingular(GF(127),3, order='degrevlex')
1148	sage: (66x^2 + 23) > (66x^2 + 2)
1149	True
1150
1151
1152	"""
1153	cdef ring *r
1154	cdef poly p, q
1155	cdef number *h
1156	cdef int ret = 0
1157
1158	r = (<MPolynomialRing_libsingular>left._parent)._ring
1159	if(r != currRing): rChangeCurrRing(r)
1160	p = (<MPolynomial_libsingular>left)._poly
1161	q = (<MPolynomial_libsingular>right)._poly
1162
1163	# handle special cases first (slight slowdown, as special
1164	# cases are - well - special
1165	if p==NULL:
1166	if q==NULL:
1167	# compare 0, 0
1168	return 0
1169	elif p_IsConstant(q,r):
1170	# compare 0, const
1171	return 1-2*n_GreaterZero(p_GetCoeff(q,r), r) # -1: <, 1: > #
1172	elif q==NULL:
1173	if p_IsConstant(p,r):
1174	# compare const, 0
1175	return -1+2*n_GreaterZero(p_GetCoeff(p,r), r) # -1: <, 1: >
1176	#else
1177
1178	while ret==0 and p!=NULL and q!=NULL:
1179	ret = p_Cmp( p, q, r)
1180
1181	if ret==0:
1182	h = n_Sub(p_GetCoeff(p, r),p_GetCoeff(q, r), r)
1183	# compare coeffs
1184	ret = -1+n_IsZero(h, r)+2*n_GreaterZero(h, r) # -1: <, 0:==, 1: >
1185	n_Delete(&h, r)
1186	p = pNext(p)
1187	q = pNext(q)
1188
1189	if ret==0:
1190	if p==NULL and q != NULL:
1191	ret = -1
1192	elif p!=NULL and q==NULL:
1193	ret = 1
1194
1195	return ret
1196
1197	cdef ModuleElement _add_c_impl( left, ModuleElement right):
1198	"""
1199	Add left and right.
1200
1201	EXAMPLE:
1202	sage: from sage.rings.multi_polynomial_libsingular import MPolynomialRing_libsingular
1203	sage: P.<x,y,z>=MPolynomialRing_libsingular(QQ,3)
1204	sage: 3/2x + 1/2y + 1
1205	3/2x + 1/2y + 1
1206
1207	"""
1208	cdef MPolynomial_libsingular res
1209
1210	cdef poly _l, _r, *_p
1211	cdef ring *_ring
1212
1213	_ring = (<MPolynomialRing_libsingular>left._parent)._ring
1214
1215	_l = p_Copy(left._poly, _ring)
1216	_r = p_Copy((<MPolynomial_libsingular>right)._poly, _ring)
1217
1218	if(_ring != currRing): rChangeCurrRing(_ring)
1219	_p= p_Add_q(_l, _r, _ring)
1220
1221	return new_MP((<MPolynomialRing_libsingular>left._parent),_p)
1222
1223	cdef ModuleElement _sub_c_impl( left, ModuleElement right):
1224	"""
1225	Subtract left and right.
1226
1227	EXAMPLE:
1228	sage: from sage.rings.multi_polynomial_libsingular import MPolynomialRing_libsingular
1229	sage: P.<x,y,z>=MPolynomialRing_libsingular(QQ,3)
1230	sage: 3/2x - 1/2y - 1
1231	3/2x - 1/2y - 1
1232
1233	"""
1234	cdef MPolynomial_libsingular res
1235
1236	cdef poly _l, _r, *_p
1237	cdef ring *_ring
1238
1239	_ring = (<MPolynomialRing_libsingular>left._parent)._ring
1240
1241	_l = p_Copy(left._poly, _ring)
1242	_r = p_Copy((<MPolynomial_libsingular>right)._poly, _ring)
1243
1244	if(_ring != currRing): rChangeCurrRing(_ring)
1245	_p= p_Add_q(_l, p_Neg(_r, _ring), _ring)
1246
1247	return new_MP((<MPolynomialRing_libsingular>left._parent),_p)
1248
1249
1250	cdef ModuleElement _rmul_c_impl(self, RingElement left):
1251	"""
1252	Multiply self with a base ring element.
1253
1254	EXAMPLE:
1255	sage: from sage.rings.multi_polynomial_libsingular import MPolynomialRing_libsingular
1256	sage: P.<x,y,z>=MPolynomialRing_libsingular(QQ,3)
1257	sage: 3/2*x
1258	3/2*x
1259	"""
1260
1261	cdef number *_n
1262	cdef ring *_ring
1263	cdef poly *_p
1264
1265	_ring = (<MPolynomialRing_libsingular>self._parent)._ring
1266
1267	if(_ring != currRing): rChangeCurrRing(_ring)
1268
1269	if PY_TYPE_CHECK((<MPolynomialRing_libsingular>self._parent)._base, FiniteField_prime_modn):
1270	_n = n_Init(int(left),_ring)
1271
1272	elif PY_TYPE_CHECK((<MPolynomialRing_libsingular>self._parent)._base, RationalField):
1273	_n = co.sa2si_QQ(left,_ring)
1274
1275	_p = pp_Mult_nn(self._poly,_n,_ring)
1276	n_Delete(&_n, _ring)
1277	return new_MP((<MPolynomialRing_libsingular>self._parent),_p)
1278
1279	cdef RingElement _mul_c_impl(left, RingElement right):
1280	"""
1281	Multiply left and right.
1282
1283	EXAMPLE:
1284	sage: from sage.rings.multi_polynomial_libsingular import MPolynomialRing_libsingular
1285	sage: P.<x,y,z>=MPolynomialRing_libsingular(QQ,3)
1286	sage: (3/2x - 1/2y - 1) * (3/2x + 1/2y + 1)
1287	9/4x^2 - 1/4y^2 - y - 1
1288	"""
1289	cdef poly _l, _r, *_p
1290	cdef ring *_ring
1291
1292	_ring = (<MPolynomialRing_libsingular>left._parent)._ring
1293
1294	if(_ring != currRing): rChangeCurrRing(_ring)
1295	_p = pp_Mult_qq(left._poly, (<MPolynomial_libsingular>right)._poly, _ring)
1296
1297	return new_MP(left._parent,_p)
1298
1299	cdef RingElement _div_c_impl(left, RingElement right):
1300	"""
1301	Divide left by right
1302
1303	EXAMPLES:
1304	sage: from sage.rings.multi_polynomial_libsingular import MPolynomialRing_libsingular
1305	sage: R.<x,y>=MPolynomialRing_libsingular(QQ,2)
1306	sage: f = (x + y)/3
1307	sage: f.parent()
1308	Polynomial Ring in x, y over Rational Field
1309
1310	Note that / is still a constructor for elements of the
1311	fraction field in all cases as long as both arguments have the
1312	same parent.
1313
1314	sage: from sage.rings.multi_polynomial_libsingular import MPolynomialRing_libsingular
1315	sage: R.<x,y>=MPolynomialRing_libsingular(QQ,2)
1316	sage: f = x^3 + y
1317	sage: g = x
1318	sage: h = f/g; h
1319	(x^3 + y)/x
1320	sage: h.parent()
1321	Fraction Field of Polynomial Ring in x, y over Rational Field
1322
1323	TESTS:
1324	sage: from sage.rings.multi_polynomial_libsingular import MPolynomialRing_libsingular
1325	sage: R.<x,y>=MPolynomialRing_libsingular(QQ,2)
1326	sage: x/0
1327	Traceback (most recent call last):
1328	...
1329	ZeroDivisionError
1330
1331	"""
1332	cdef poly *p
1333	cdef ring *r
1334	cdef number *n
1335	if (<MPolynomial_libsingular>right).is_constant_c():
1336
1337	p = (<MPolynomial_libsingular>right)._poly
1338	if p == NULL:
1339	raise ZeroDivisionError
1340	r = (<MPolynomialRing_libsingular>(<MPolynomial_libsingular>left)._parent)._ring
1341	n = p_GetCoeff(p, r)
1342	n = nInvers(n)
1343	p = pp_Mult_nn(left._poly, n, r)
1344	n_Delete(&n,r)
1345	return new_MP(left._parent, p)
1346	else:
1347	return (<MPolynomialRing_libsingular>left._parent).fraction_field()(left,right)
1348
1349	def __pow__(MPolynomial_libsingular self,int exp,ignored):
1350	"""
1351	Return self^(exp).
1352
1353	EXAMPLE:
1354	sage: from sage.rings.multi_polynomial_libsingular import MPolynomialRing_libsingular
1355	sage: R.<x,y>=MPolynomialRing_libsingular(QQ,2)
1356	sage: f = x^3 + y
1357	sage: f^2
1358	x^6 + 2x^3y + y^2
1359
1360	"""
1361	cdef ring *_ring
1362	_ring = (<MPolynomialRing_libsingular>self._parent)._ring
1363
1364	cdef poly *_p
1365
1366
1367	if exp < 0:
1368	raise ArithmeticError, "Cannot comput negative powers of polynomials"
1369
1370	if(_ring != currRing): rChangeCurrRing(_ring)
1371	_p = pPower( p_Copy(self._poly,(<MPolynomialRing_libsingular>self._parent)._ring),exp)
1372	return new_MP((<MPolynomialRing_libsingular>self._parent),_p)
1373
1374
1375	def __neg__(self):
1376	"""
1377	Return -self.
1378
1379	EXAMPLE:
1380	sage: from sage.rings.multi_polynomial_libsingular import MPolynomialRing_libsingular
1381	sage: R.<x,y>=MPolynomialRing_libsingular(QQ,2)
1382	sage: f = x^3 + y
1383	sage: -f
1384	-x^3 - y
1385	"""
1386	cdef ring *_ring
1387	_ring = (<MPolynomialRing_libsingular>self._parent)._ring
1388	if(_ring != currRing): rChangeCurrRing(_ring)
1389
1390	return new_MP((<MPolynomialRing_libsingular>self._parent),\
1391	p_Neg(p_Copy(self._poly,_ring),_ring))
1392
1393	def _repr_(self):
1394	s = self._repr_short_c()
1395	s = s.replace("+"," + ").replace("-"," - ")
1396	if s.startswith(" - "):
1397	return "-" + s[3:]
1398	else:
1399	return s
1400
1401	def _repr_short(self):
1402	"""
1403	This is a faster but less pretty way to print polynomials. If available
1404	it uses the short SINGULAR notation.
1405	"""
1406	cdef ring *_ring = (<MPolynomialRing_libsingular>self._parent)._ring
1407	if _ring.CanShortOut:
1408	_ring.ShortOut = 1
1409	s = self._repr_short_c()
1410	_ring.ShortOut = 0
1411	else:
1412	s = self._repr_short_c()
1413	return s
1414
1415	cdef _repr_short_c(self):
1416	"""
1417	Raw SINGULAR printing.
1418	"""
1419	s = p_String(self._poly, (<MPolynomialRing_libsingular>self._parent)._ring, (<MPolynomialRing_libsingular>self._parent)._ring)
1420	return s
1421
1422	def _latex_(self):
1423	"""
1424	Return a polynomial latex representation of self.
1425
1426	EXAMPLE:
1427	sage: from sage.rings.multi_polynomial_libsingular import MPolynomialRing_libsingular
1428	sage: P.<x,y,z> = MPolynomialRing_libsingular(QQ,3)
1429	sage: f = - 1x^2y - 25/27 * y^3 - z^2
1430	sage: latex(f)
1431	- x^{2}y - \frac{25}{27} y^{3} - z^{2}
1432
1433	"""
1434	cdef ring *_ring = (<MPolynomialRing_libsingular>self._parent)._ring
1435	cdef int n = _ring.N
1436	cdef int j, e
1437	cdef poly *p = self._poly
1438	poly = ""
1439	gens = self.parent().gens()
1440	base = self.parent().base()
1441
1442	while p:
1443	sign_switch = False
1444
1445	# First determine the multinomial:
1446	multi = ""
1447	for j from 1 <= j <= n:
1448	e = p_GetExp(p, j, _ring)
1449	if e > 0:
1450	multi += str(gens[j-1])
1451	if e > 1:
1452	multi += "^{%d}"%e
1453
1454	# Next determine coefficient of multinomial
1455	c = co.si2sa( p_GetCoeff(p, _ring), _ring, base)
1456	if len(multi) == 0:
1457	multi = latex(c)
1458	elif c != 1:
1459	if c == -1:
1460	if len(poly) > 0:
1461	sign_switch = True
1462	else:
1463	multi = "- %s"%(multi)
1464	else:
1465	multi = "%s %s"%(latex(c),multi)
1466
1467	# Now add on coefficiented multinomials
1468	if len(poly) > 0:
1469	if sign_switch:
1470	poly = poly + " - "
1471	else:
1472	poly = poly + " + "
1473	poly = poly + multi
1474
1475	p = pNext(p)
1476
1477	poly = poly.lstrip().rstrip()
1478	poly = poly.replace("+ -","- ")
1479
1480	if len(poly) == 0:
1481	return "0"
1482	return poly
1483
1484	def _repr_with_changed_varnames(self, varnames):
1485	"""
1486	Return string representing self but change the variable names
1487	to varnames.
1488
1489	EXAMPLE:
1490	sage: from sage.rings.multi_polynomial_libsingular import MPolynomialRing_libsingular
1491	sage: P.<x,y,z> = MPolynomialRing_libsingular(QQ,3)
1492	sage: f = - 1x^2y - 25/27 * y^3 - z^2
1493	sage: print f._repr_with_changed_varnames(['FOO', 'BAR', 'FOOBAR'])
1494	-FOO^2BAR - 25/27BAR^3 - FOOBAR^2
1495
1496	"""
1497	cdef ring *_ring = (<MPolynomialRing_libsingular>self._parent)._ring
1498	cdef char **_names
1499	cdef char **_orig_names
1500	cdef char *_name
1501	cdef int i
1502
1503	if len(varnames) != _ring.N:
1504	raise TypeError, "len(varnames) doesn't equal self.parent().ngens()"
1505
1506
1507	_names = <char*>sage_malloc(sizeof(char)*_ring.N)
1508	for i from 0 <= i < _ring.N:
1509	_name = varnames[i]
1510	_names[i] = strdup(_name)
1511
1512	_orig_names = _ring.names
1513	_ring.names = _names
1514	s = str(self)
1515	_ring.names = _orig_names
1516
1517	for i from 0 <= i < _ring.N:
1518	free(_names[i]) # strdup() --> free()
1519	sage_free(_names)
1520
1521	return s
1522
1523	def degree(self, MPolynomial_libsingular x=None):
1524	"""
1525	Return the maximal degree of self in x, where x must be one of the
1526	generators for the parent of self.
1527
1528	INPUT:
1529	x -- multivariate polynmial (a generator of the parent of self)
1530	If x is not specified (or is None), return the total degree,
1531	which is the maximum degree of any monomial.
1532
1533	OUTPUT:
1534	integer
1535
1536	EXAMPLE:
1537	sage: from sage.rings.multi_polynomial_libsingular import MPolynomialRing_libsingular
1538	sage: R.<x, y> = MPolynomialRing_libsingular(QQ, 2)
1539	sage: f = y^2 - x^9 - x
1540	sage: f.degree(x)
1541	9
1542	sage: f.degree(y)
1543	2
1544	sage: (y^10x - 7x^2y^5 + 5x^3).degree(x)
1545	3
1546	sage: (y^10x - 7x^2y^5 + 5x^3).degree(y)
1547	10
1548
1549	TESTS:
1550	sage: from sage.rings.multi_polynomial_libsingular import MPolynomialRing_libsingular
1551	sage: P.<x, y> = MPolynomialRing_libsingular(QQ, 2)
1552	sage: P(0).degree(x)
1553	0
1554	sage: P(1).degree(x)
1555	0
1556
1557	"""
1558	cdef ring *r = (<MPolynomialRing_libsingular>self._parent)._ring
1559	cdef poly *p = self._poly
1560	cdef int deg, _deg
1561
1562	deg = 0
1563
1564	if not x:
1565	return self.total_degree()
1566
1567	# TODO: we can do this faster
1568	if not x in self._parent.gens():
1569	raise TypeError, "x must be one of the generators of the parent."
1570	for i from 1 <= i <= r.N:
1571	if p_GetExp(x._poly, i, r):
1572	break
1573	while p:
1574	_deg = p_GetExp(p,i,r)
1575	if _deg > deg:
1576	deg = _deg
1577	p = pNext(p)
1578
1579	return deg
1580
1581	def newton_polytope(self):
1582	"""
1583	Return the Newton polytope of this polynomial.
1584
1585	You should have the optional polymake package installed.
1586
1587	EXAMPLES:
1588	sage: from sage.rings.multi_polynomial_libsingular import MPolynomialRing_libsingular
1589	sage: R.<x,y> = MPolynomialRing_libsingular(QQ,2)
1590	sage: f = 1 + x*y + x^3 + y^3
1591	sage: P = f.newton_polytope()
1592	sage: P
1593	Convex hull of points [[1, 0, 0], [1, 0, 3], [1, 1, 1], [1, 3, 0]]
1594	sage: P.facets()
1595	[(0, 1, 0), (3, -1, -1), (0, 0, 1)]
1596	sage: P.is_simple()
1597	True
1598
1599	TESTS:
1600	sage: from sage.rings.multi_polynomial_libsingular import MPolynomialRing_libsingular
1601	sage: R.<x,y> = MPolynomialRing_libsingular(QQ,2)
1602	sage: R(0).newton_polytope()
1603	Convex hull of points []
1604	sage: R(1).newton_polytope()
1605	Convex hull of points [[1, 0, 0]]
1606
1607	"""
1608	from sage.geometry.all import polymake
1609	e = self.exponents()
1610	a = [[1] + list(v) for v in e]
1611	P = polymake.convex_hull(a)
1612	return P
1613
1614	def total_degree(self):
1615	"""
1616	Return the total degree of self, which is the maximum degree
1617	of all monomials in self.
1618
1619	EXAMPLES:
1620	sage: from sage.rings.multi_polynomial_libsingular import MPolynomialRing_libsingular
1621	sage: R.<x,y,z> = MPolynomialRing_libsingular(QQ, 3)
1622	sage: f=2xy^3*z^2
1623	sage: f.total_degree()
1624	6
1625	sage: f=4x^2y^2*z^3
1626	sage: f.total_degree()
1627	7
1628	sage: f=99x^6y^3*z^9
1629	sage: f.total_degree()
1630	18
1631	sage: f=xy^3z^6+3*x^2
1632	sage: f.total_degree()
1633	10
1634	sage: f=z^3+8x^4y^5*z
1635	sage: f.total_degree()
1636	10
1637	sage: f=z^9+10x^4+y^8x^2
1638	sage: f.total_degree()
1639	10
1640
1641	TESTS:
1642	sage: from sage.rings.multi_polynomial_libsingular import MPolynomialRing_libsingular
1643	sage: R.<x,y,z> = MPolynomialRing_libsingular(QQ, 3)
1644	sage: R(0).total_degree()
1645	0
1646	sage: R(1).total_degree()
1647	0
1648	"""
1649	cdef poly *p = self._poly
1650	cdef ring *r = (<MPolynomialRing_libsingular>self._parent)._ring
1651	cdef int l
1652	if self._poly == NULL:
1653	return 0
1654	if(r != currRing): rChangeCurrRing(r)
1655	return pLDeg(p,&l,r)
1656
1657	def monomial_coefficient(self, MPolynomial_libsingular mon):
1658	"""
1659	Return the coefficient of the monomial mon in self, where mon
1660	must have the same parent as self.
1661
1662	INPUT:
1663	mon -- a monomial
1664
1665	OUTPUT:
1666	ring element
1667
1668	EXAMPLE:
1669	sage: from sage.rings.multi_polynomial_libsingular import MPolynomialRing_libsingular
1670	sage: P.<x,y> = MPolynomialRing_libsingular(QQ, 2)
1671
1672	The coefficient returned is an element of the base ring of self; in
1673	this case, QQ.
1674
1675	sage: f = 2 * x * y
1676	sage: c = f.monomial_coefficient(x*y); c
1677	2
1678	sage: c in QQ
1679	True
1680
1681	sage: f = y^2 - x^9 - 7x + 5x*y
1682	sage: f.monomial_coefficient(y^2)
1683	1
1684	sage: f.monomial_coefficient(x*y)
1685	5
1686	sage: f.monomial_coefficient(x^9)
1687	-1
1688	sage: f.monomial_coefficient(x^10)
1689	0
1690	"""
1691	cdef poly *p = self._poly
1692	cdef poly *m = mon._poly
1693	cdef ring *r = (<MPolynomialRing_libsingular>self._parent)._ring
1694
1695	if not mon._parent is self._parent:
1696	raise TypeError, "mon must have same parent as self"
1697
1698	while(p):
1699	if p_ExpVectorEqual(p, m, r) == 1:
1700	return co.si2sa(p_GetCoeff(p, r), r, (<MPolynomialRing_libsingular>self._parent)._base)
1701	p = pNext(p)
1702
1703	return (<MPolynomialRing_libsingular>self._parent)._base(0)
1704
1705	def dict(self):
1706	"""
1707	Return a dictionary representing self. This dictionary is in
1708	the same format as the generic MPolynomial: The dictionary
1709	consists of ETuple:coefficient pairs.
1710
1711	EXAMPLE:
1712	sage: from sage.rings.multi_polynomial_libsingular import MPolynomialRing_libsingular
1713	sage: R.<x,y,z> = MPolynomialRing_libsingular(QQ, 3)
1714	sage: f=2xy^3z^2 + 1/7x^2 + 2/3
1715	sage: f.dict()
1716	{(2, 0, 0): 1/7, (0, 0, 0): 2/3, (1, 3, 2): 2}
1717	"""
1718	cdef poly *p
1719	cdef ring *r
1720	cdef int n
1721	cdef int v
1722	r = (<MPolynomialRing_libsingular>self._parent)._ring
1723	base = (<MPolynomialRing_libsingular>self._parent)._base
1724	p = self._poly
1725	pd = dict()
1726	while p:
1727	d = dict()
1728	for v from 1 <= v <= r.N:
1729	n = p_GetExp(p,v,r)
1730	if n!=0:
1731	d[v-1] = n
1732
1733	pd[ETuple(d,r.N)] = co.si2sa(p_GetCoeff(p, r), r, base)
1734
1735	p = pNext(p)
1736	return pd
1737
1738	def __getitem__(self,x):
1739	"""
1740	same as self.monomial_coefficent but for exponent vectors.
1741
1742	INPUT:
1743	x -- a tuple or, in case of a single-variable MPolynomial
1744	ring x can also be an integer.
1745
1746	EXAMPLES:
1747	sage: R.<x, y> = PolynomialRing(QQ, 2)
1748	sage: f = -10x^3y + 17xy
1749	sage: f[3,1]
1750	-10
1751	sage: f[1,1]
1752	17
1753	sage: f[0,1]
1754	0
1755
1756	sage: R.<x> = PolynomialRing(GF(7),1); R
1757	Polynomial Ring in x over Finite Field of size 7
1758	sage: f = 5*x^2 + 3; f
1759	3 + 5*x^2
1760	sage: f[2]
1761	5
1762	"""
1763
1764	cdef poly *m
1765	cdef poly *p = self._poly
1766	cdef ring *r = (<MPolynomialRing_libsingular>self._parent)._ring
1767	cdef int i
1768
1769	if PY_TYPE_CHECK(x, MPolynomial_libsingular):
1770	return self.monomial_coefficient(x)
1771	if not PY_TYPE_CHECK(x, tuple):
1772	try:
1773	x = tuple(x)
1774	except TypeError:
1775	x = (x,)
1776
1777	if len(x) != (<MPolynomialRing_libsingular>self._parent).__ngens:
1778	raise TypeError, "x must have length self.ngens()"
1779
1780	m = p_ISet(1,r)
1781	i = 1
1782	for e in x:
1783	p_SetExp(m, i, int(e), r)
1784	i += 1
1785	p_Setm(m, r)
1786
1787	while(p):
1788	if p_ExpVectorEqual(p, m, r) == 1:
1789	p_Delete(&m,r)
1790	return co.si2sa(p_GetCoeff(p, r), r, (<MPolynomialRing_libsingular>self._parent)._base)
1791	p = pNext(p)
1792
1793	p_Delete(&m,r)
1794	return (<MPolynomialRing_libsingular>self._parent)._base(0)
1795
1796	def coefficient(self, mon):
1797	raise NotImplementedError
1798
1799	def exponents(self):
1800	"""
1801	Return the exponents of the monomials appearing in self.
1802
1803	EXAMPLES:
1804	sage: from sage.rings.multi_polynomial_libsingular import MPolynomialRing_libsingular
1805	sage: R.<a,b,c> = MPolynomialRing_libsingular(QQ, 3)
1806	sage: f = a^3 + b + 2*b^2
1807	sage: f.exponents()
1808	[(3, 0, 0), (0, 2, 0), (0, 1, 0)]
1809	"""
1810	cdef poly *p
1811	cdef ring *r
1812	cdef int v
1813	r = (<MPolynomialRing_libsingular>self._parent)._ring
1814
1815	p = self._poly
1816
1817	pl = list()
1818	while p:
1819	ml = list()
1820	for v from 1 <= v <= r.N:
1821	ml.append(p_GetExp(p,v,r))
1822	pl.append(tuple(ml))
1823
1824	p = pNext(p)
1825	return pl
1826
1827	def is_unit(self):
1828	"""
1829	Return True if self is a unit.
1830
1831	EXAMPLES:
1832	sage: from sage.rings.multi_polynomial_libsingular import MPolynomialRing_libsingular
1833	sage: R.<x,y> = MPolynomialRing_libsingular(QQ, 2)
1834	sage: (x+y).is_unit()
1835	False
1836	sage: R(0).is_unit()
1837	False
1838	sage: R(-1).is_unit()
1839	True
1840	sage: R(-1 + x).is_unit()
1841	False
1842	sage: R(2).is_unit()
1843	True
1844	"""
1845	return bool(p_IsUnit(self._poly, (<MPolynomialRing_libsingular>self._parent)._ring))
1846
1847	def inverse_of_unit(self):
1848	"""
1849	Return the inverse of self if self is a unit.
1850
1851	EXAMPLES:
1852	sage: from sage.rings.multi_polynomial_libsingular import MPolynomialRing_libsingular
1853	sage: R.<x,y> = MPolynomialRing_libsingular(QQ, 2)
1854	"""
1855	cdef ring *_ring = (<MPolynomialRing_libsingular>self._parent)._ring
1856	if(_ring != currRing): rChangeCurrRing(_ring)
1857
1858	if not p_IsUnit(self._poly, _ring):
1859	raise ArithmeticError, "is not a unit"
1860	else:
1861	return new_MP(self._parent,pInvers(0,self._poly,NULL))
1862
1863	def is_homogeneous(self):
1864	"""
1865	Return True if self is a homogeneous polynomial.
1866
1867	EXAMPLES:
1868	sage: from sage.rings.multi_polynomial_libsingular import MPolynomialRing_libsingular
1869	sage: P.<x,y> = MPolynomialRing_libsingular(RationalField(), 2)
1870	sage: (x+y).is_homogeneous()
1871	True
1872	sage: (x.parent()(0)).is_homogeneous()
1873	True
1874	sage: (x+y^2).is_homogeneous()
1875	False
1876	sage: (x^2 + y^2).is_homogeneous()
1877	True
1878	sage: (x^2 + y^2*x).is_homogeneous()
1879	False
1880	sage: (x^2y + y^2x).is_homogeneous()
1881	True
1882
1883	"""
1884	cdef ring *_ring = (<MPolynomialRing_libsingular>self._parent)._ring
1885	if(_ring != currRing): rChangeCurrRing(_ring)
1886	return bool(pIsHomogeneous(self._poly))
1887
1888	def homogenize(self, var='h'):
1889	"""
1890	Return self is self is homogeneous. Otherwise return a
1891	homogeneous polynomial. If a string is given, return a
1892	polynomial in one more variable such that setting that
1893	variable equal to 1 yields self. This variable is added to the
1894	end of the variables. If either a variable in self.parent() or
1895	an index is given, this variable is used to homogenize the
1896	polynomial.
1897
1898	INPUT:
1899	var -- either a string (default: 'h'); a variable name for the new variable
1900	to be added in when homogenizing or a variable/index to specify the existing
1901	variable to be used.
1902
1903	OUTPUT:
1904	a multivariate polynomial
1905
1906	EXAMPLES:
1907	sage: from sage.rings.multi_polynomial_libsingular import MPolynomialRing_libsingular
1908	sage: P.<x,y> = MPolynomialRing_libsingular(QQ,2)
1909	sage: f = x^2 + y + 1 + 5xy^10
1910	sage: g = f.homogenize('z'); g
1911	5xy^10 + x^2z^9 + yz^10 + z^11
1912	sage: g.parent()
1913	Polynomial Ring in x, y, z over Rational Field
1914	sage: f.homogenize(x)
1915	2x^11 + x^10y + 5xy^10
1916
1917	"""
1918	cdef MPolynomialRing_libsingular parent = <MPolynomialRing_libsingular>self._parent
1919	cdef MPolynomial_libsingular f
1920
1921	if self.is_homogeneous():
1922	return self
1923
1924	if PY_TYPE_CHECK(var, MPolynomial_libsingular):
1925	if (<MPolynomial_libsingular>var)._parent is self._parent:
1926	var = var._variable_indices_()
1927	if len(var) == 1:
1928	var = var[0]
1929	else:
1930	raise TypeError, "parameter var must be single variable"
1931
1932	if PY_TYPE_CHECK(var,str):
1933	names = [str(e) for e in parent.gens()] + [var]
1934	P = MPolynomialRing_libsingular(parent.base(),parent.ngens()+1, names, order=parent.term_order())
1935	f = P(str(self))
1936	return new_MP(P, pHomogen(f._poly,len(names)))
1937	elif PY_TYPE_CHECK(var,int) or PY_TYPE_CHECK(var,Integer):
1938	if var < parent._ring.N:
1939	return new_MP(parent, pHomogen(p_Copy(self._poly, parent._ring), var+1))
1940	else:
1941	raise TypeError, "var must be < self.parent().ngens()"
1942	else:
1943	raise TypeError, "parameter var not understood"
1944
1945	def is_monomial(self):
1946	return not self._poly.next
1947
1948	def fix(self, fixed):
1949	"""
1950	Fixes some given variables in a given multivariate polynomial and
1951	returns the changed multivariate polynomials. The polynomial
1952	itself is not affected. The variable,value pairs for fixing are
1953	to be provided as dictionary of the form {variable:value}.
1954
1955	This is a special case of evaluating the polynomial with some of
1956	the variables constants and the others the original variables, but
1957	should be much faster if only few variables are to be fixed.
1958
1959	INPUT:
1960	fixed -- dict with variable:value pairs
1961
1962	OUTPUT:
1963	new MPolynomial
1964
1965	EXAMPLES:
1966	sage: from sage.rings.multi_polynomial_libsingular import MPolynomialRing_libsingular
1967	sage: x, y = MPolynomialRing_libsingular(QQ,2,'xy').gens()
1968	sage: f = x^2 + y + x^2*y^2 + 5
1969	sage: f(5,y)
1970	25*y^2 + y + 30
1971	sage: f.fix({x:5})
1972	25*y^2 + y + 30
1973
1974	TESTS:
1975	sage: from sage.rings.multi_polynomial_libsingular import MPolynomialRing_libsingular
1976	sage: P.<x,y,z> = MPolynomialRing_libsingular(QQ,3)
1977	sage: f = y
1978	sage: f.fix({y:x}).fix({x:z})
1979	z
1980
1981	"""
1982	cdef int mi, i
1983
1984	cdef MPolynomialRing_libsingular parent = <MPolynomialRing_libsingular>self._parent
1985	cdef ring *_ring = parent._ring
1986
1987	if(_ring != currRing): rChangeCurrRing(_ring)
1988
1989	cdef poly *_p = p_Copy(self._poly, _ring)
1990
1991	for m,v in fixed.iteritems():
1992	if PY_TYPE_CHECK(m,int) or PY_TYPE_CHECK(m,Integer):
1993	mi = m+1
1994	elif PY_TYPE_CHECK(m,MPolynomial_libsingular) and <MPolynomialRing_libsingular>m.parent() is parent:
1995	for i from 0 < i <= _ring.N:
1996	if p_GetExp((<MPolynomial_libsingular>m)._poly, i, _ring) != 0:
1997	mi = i
1998	break
1999	if i > _ring.N:
2000	raise TypeError, "key does not match"
2001	else:
2002	raise TypeError, "keys do not match self's parent"
2003	_p = pSubst(_p, mi, (<MPolynomial_libsingular>parent._coerce_c(v))._poly)
2004
2005	return new_MP(parent,_p)
2006
2007	def monomials(self):
2008	"""
2009	Return the list of monomials in self. The returned list is
2010	ordered by the term ordering of self.parent().
2011
2012	EXAMPLE:
2013	sage: from sage.rings.multi_polynomial_libsingular import MPolynomialRing_libsingular
2014	sage: P.<x,y,z> = MPolynomialRing_libsingular(QQ,3)
2015	sage: f = x + 3/2yz^2 + 2/3
2016	sage: f.monomials()
2017	[y*z^2, x, 1]
2018	sage: f = P(3/2)
2019	sage: f.monomials()
2020	[1]
2021
2022	TESTS:
2023	sage: from sage.rings.multi_polynomial_libsingular import MPolynomialRing_libsingular
2024	sage: P.<x,y,z> = MPolynomialRing_libsingular(QQ,3)
2025	sage: f = x
2026	sage: f.monomials()
2027	[x]
2028	sage: f = P(0)
2029	sage: f.monomials()
2030	[0]
2031
2032
2033	"""
2034	l = list()
2035	cdef MPolynomialRing_libsingular parent = <MPolynomialRing_libsingular>self._parent
2036	cdef ring *_ring = parent._ring
2037	cdef poly *p = p_Copy(self._poly, _ring)
2038	cdef poly *t
2039
2040	if p == NULL:
2041	return [parent._zero]
2042
2043	while p:
2044	t = pNext(p)
2045	p.next = NULL
2046	p_SetCoeff(p, n_Init(int(1),_ring), _ring)
2047	p_Setm(p, _ring)
2048	l.append( new_MP(parent,p) )
2049	p = t
2050
2051	return l
2052
2053	def constant_coefficent(self):
2054	raise NotImplementedError
2055
2056	def is_univariate(self):
2057	"""
2058	Return True if self is a univariate polynomial, that is if
2059	self contains only one variable.
2060
2061	EXAMPLE:
2062	sage: from sage.rings.multi_polynomial_libsingular import MPolynomialRing_libsingular
2063	sage: P.<x,y,z> = MPolynomialRing_libsingular(GF(2),3)
2064	sage: f = x^2 + 1
2065	sage: f.is_univariate()
2066	True
2067	sage: f = y*x^2 + 1
2068	sage: f.is_univariate()
2069	False
2070	sage: f = P(0)
2071	sage: f.is_univariate()
2072	True
2073	"""
2074	return bool(len(self._variable_indices_(sort=False))<2)
2075
2076	def univariate_polynomial(self, R=None):
2077	raise NotImplementedError
2078
2079	def _variable_indices_(self, sort=True):
2080	"""
2081	Return the indices of all variables occuring in self.
2082	This index is the index as SAGE uses them (starting at zero), not
2083	as SINGULAR uses them (starting at one).
2084
2085	INPUT:
2086	sort -- specifies whether the indices shall be sorted
2087
2088	EXAMPLE:
2089	sage: from sage.rings.multi_polynomial_libsingular import MPolynomialRing_libsingular
2090	sage: P.<x,y,z> = MPolynomialRing_libsingular(GF(2),3)
2091	sage: f = x*z^2 + z + 1
2092	sage: f._variable_indices_()
2093	[0, 2]
2094
2095	"""
2096	cdef poly *p
2097	cdef ring *r = (<MPolynomialRing_libsingular>self._parent)._ring
2098	cdef int i
2099	s = set()
2100	p = self._poly
2101	while p:
2102	for i from 1 <= i <= r.N:
2103	if p_GetExp(p,i,r):
2104	s.add(i-1)
2105	p = pNext(p)
2106	if sort:
2107	return sorted(s)
2108	else:
2109	return list(s)
2110
2111	def variables(self, sort=True):
2112	"""
2113	Return a list of all variables occuring in self.
2114
2115	INPUT:
2116	sort -- specifies whether the indices shall be sorted
2117
2118	EXAMPLE:
2119	sage: from sage.rings.multi_polynomial_libsingular import MPolynomialRing_libsingular
2120	sage: P.<x,y,z> = MPolynomialRing_libsingular(GF(2),3)
2121	sage: f = x*z^2 + z + 1
2122	sage: f.variables()
2123	[z, x]
2124	sage: f.variables(sort=False)
2125	[x, z]
2126
2127	"""
2128	cdef poly p, v
2129	cdef ring *r = (<MPolynomialRing_libsingular>self._parent)._ring
2130	cdef int i
2131	l = list()
2132	si = set()
2133	p = self._poly
2134	while p:
2135	for i from 1 <= i <= r.N:
2136	if i not in si and p_GetExp(p,i,r):
2137	v = p_ISet(1,r)
2138	p_SetExp(v, i, 1, r)
2139	p_Setm(v, r)
2140	l.append(new_MP(self._parent, v))
2141	si.add(i)
2142	p = pNext(p)
2143	if sort:
2144	return sorted(l)
2145	else:
2146	return l
2147
2148	def variable(self, i=0):
2149	"""
2150	Return the i-th variable occuring in self. The index i is the
2151	index in self.variables().
2152
2153	EXAMPLE:
2154	sage: from sage.rings.multi_polynomial_libsingular import MPolynomialRing_libsingular
2155	sage: P.<x,y,z> = MPolynomialRing_libsingular(GF(2),3)
2156	sage: f = x*z^2 + z + 1
2157	sage: f.variables()
2158	[z, x]
2159	sage: f.variable(1)
2160	x
2161	"""
2162	return self.variables()[i]
2163
2164	def nvariables(self):
2165	"""
2166	"""
2167	return self._variable_indices_(sort=False)
2168
2169	def is_constant(self):
2170	"""
2171	"""
2172	return bool(p_IsConstant(self._poly, (<MPolynomialRing_libsingular>self._parent)._ring))
2173
2174	cdef int is_constant_c(self):
2175	return p_IsConstant(self._poly, (<MPolynomialRing_libsingular>self._parent)._ring)
2176
2177	def __hash__(self):
2178	"""
2179	"""
2180	s = p_String(self._poly, (<MPolynomialRing_libsingular>self._parent)._ring, (<MPolynomialRing_libsingular>self._parent)._ring)
2181	return hash(s)
2182
2183	def lm(MPolynomial_libsingular self):
2184	"""
2185	Returns the lead monomial of self with respect to the term
2186	order of self.parent(). In SAGE a monomial is a product of
2187	variables in some power without a coefficient.
2188
2189	EXAMPLES:
2190	sage: from sage.rings.multi_polynomial_libsingular import MPolynomialRing_libsingular
2191
2192	sage: R.<x,y,z>=MPolynomialRing_libsingular(GF(7),3,order='lex')
2193	sage: f = x^1y^2 + y^3z^4
2194	sage: f.lm()
2195	x*y^2
2196	sage: f = x^3y^2z^4 + x^3y^2z^1
2197	sage: f.lm()
2198	x^3y^2z^4
2199
2200	sage: R.<x,y,z>=MPolynomialRing_libsingular(QQ,3,order='deglex')
2201	sage: f = x^1y^2z^3 + x^3y^2z^0
2202	sage: f.lm()
2203	xy^2z^3
2204	sage: f = x^1y^2z^4 + x^1y^1z^5
2205	sage: f.lm()
2206	xy^2z^4
2207
2208	sage: R.<x,y,z>=PolynomialRing(GF(127),3,order='degrevlex')
2209	sage: f = x^1y^5z^2 + x^4y^1z^3
2210	sage: f.lm()
2211	xy^5z^2
2212	sage: f = x^4y^7z^1 + x^4y^2z^3
2213	sage: f.lm()
2214	x^4y^7z
2215
2216	"""
2217	cdef poly *_p
2218	cdef ring *_ring
2219	_ring = (<MPolynomialRing_libsingular>self._parent)._ring
2220	_p = p_Head(self._poly, _ring)
2221	p_SetCoeff(_p, n_Init(int(1),_ring), _ring)
2222	p_Setm(_p,_ring)
2223	return new_MP((<MPolynomialRing_libsingular>self._parent), _p)
2224
2225
2226	def lc(MPolynomial_libsingular self):
2227	"""
2228	Leading coefficient of self. See self.lm() for details.
2229	"""
2230
2231	cdef poly *_p
2232	cdef ring *_ring
2233	cdef number *_n
2234	_ring = (<MPolynomialRing_libsingular>self._parent)._ring
2235
2236	if(_ring != currRing): rChangeCurrRing(_ring)
2237
2238	_p = p_Head(self._poly, _ring)
2239	_n = p_GetCoeff(_p, _ring)
2240
2241	return co.si2sa(_n, _ring, (<MPolynomialRing_libsingular>self._parent)._base)
2242
2243	def lt(MPolynomial_libsingular self):
2244	"""
2245	Leading term of self. In SAGE a term is a product of variables
2246	in some power AND a coefficient.
2247
2248	See self.lm() for details
2249	"""
2250	return new_MP((<MPolynomialRing_libsingular>self._parent),
2251	p_Head(self._poly,(<MPolynomialRing_libsingular>self._parent)._ring))
2252
2253	def is_zero(self):
2254	if self._poly is NULL:
2255	return True
2256	else:
2257	return False
2258
2259	def __nonzero__(self):
2260	if self._poly:
2261	return True
2262	else:
2263	return False
2264
2265	def __floordiv__(self,right):
2266	raise NotImplementedError
2267
2268	def factor(self, param=0):
2269	"""
2270
2271	Return the factorization of self.
2272
2273	INPUT:
2274	param -- 0: returns factors and multiplicities, first factor is a constant.
2275	1: returns non-constant factors (no multiplicities).
2276	2: returns non-constant factors and multiplicities.
2277	EXAMPLE:
2278	sage: from sage.rings.multi_polynomial_libsingular import MPolynomialRing_libsingular
2279	sage: R.<x,y,z> = MPolynomialRing_libsingular(GF(32003),3)
2280	sage: f = 9(x-1)^2(y+z)
2281	sage: f.factor(0)
2282	9 * (y + z) * (x - 1)^2
2283	sage: f.factor(1)
2284	(y + z) * (x - 1)
2285	sage: f.factor(2)
2286	(y + z) * (x - 1)^2
2287
2288	"""
2289	cdef ring *_ring
2290	cdef intvec *iv
2291	cdef int *ivv
2292	cdef ideal *I
2293	cdef MPolynomialRing_libsingular parent
2294	cdef int i
2295
2296	parent = self._parent
2297	_ring = parent._ring
2298
2299	if(_ring != currRing): rChangeCurrRing(_ring)
2300
2301	iv = NULL
2302	I = singclap_factorize ( self._poly, &iv , int(param)) #delete iv at some point
2303
2304	if param!=1:
2305	ivv = iv.ivGetVec()
2306	v = [(new_MP(parent, p_Copy(I.m[i],_ring)) , ivv[i]) for i in range(I.ncols)]
2307	else:
2308	v = [(new_MP(parent, p_Copy(I.m[i],_ring)) , 1) for i in range(I.ncols)]
2309
2310	# TODO: peel of 1
2311
2312	F = Factorization(v)
2313	F.sort()
2314
2315	omFree(iv)
2316	id_Delete(&I,_ring)
2317
2318	return F
2319
2320	def lift(self, I):
2321	#m = idLift(Ideal(self), I, NULL, FALSE, TRUE );
2322	#matrix_to_list(m)
2323	raise NotImplementedError
2324
2325	def reduce(self,I):
2326	"""
2327	Return the normal form of self w.r.t. I, i.e. return the
2328	remainder of self with respect to the polynomials in I. If the
2329	polynomial set/list I is not a Groebner basis the result is
2330	not canonical.
2331
2332	INPUT:
2333	I -- a list/set of polynomials in self.parent(). If I is an ideal,
2334	the generators are used.
2335
2336	EXAMPLE:
2337	sage: from sage.rings.multi_polynomial_libsingular import MPolynomialRing_libsingular
2338	sage: P.<x,y,z> = MPolynomialRing_libsingular(QQ,3)
2339	sage: f1 = -2 * x^2 + x^3
2340	sage: f2 = -2 * y + x* y
2341	sage: f3 = -x^2 + y^2
2342	sage: F = Ideal([f1,f2,f3])
2343	sage: g = xy - 3x*y^2
2344	sage: g.reduce(F)
2345	-6y^2 + 2y
2346	sage: g.reduce(F.gens())
2347	-6y^2 + 2y
2348
2349	"""
2350	cdef ideal *_I
2351	cdef MPolynomialRing_libsingular parent = <MPolynomialRing_libsingular>self._parent
2352	cdef int i = 0
2353	cdef ring *r = (<MPolynomialRing_libsingular>self._parent)._ring
2354	cdef poly *res
2355
2356	if(r != currRing): rChangeCurrRing(r)
2357
2358	if PY_TYPE_CHECK(I, MPolynomialIdeal):
2359	I = I.gens()
2360
2361	_I = idInit(len(I),1)
2362	for f in I:
2363	if not (PY_TYPE_CHECK(f,MPolynomial_libsingular) \
2364	and <MPolynomialRing_libsingular>(<MPolynomial_libsingular>f)._parent is parent):
2365	try:
2366	f = parent._coerce_c(f)
2367	except TypeError, msg:
2368	id_Delete(&_I,r)
2369	raise TypeError, msg
2370
2371	_I.m[i] = p_Copy((<MPolynomial_libsingular>f)._poly, r)
2372	i+=1
2373
2374	#the second parameter would be qring!
2375	res = kNF(_I, NULL, p_Copy(self._poly, r))
2376	return new_MP(parent,res)
2377
2378	def gcd(self, right):
2379	"""
2380	Return the greates common divisor of self and right.
2381
2382	INPUT:
2383	right -- polynomial
2384
2385	EXAMPLES:
2386	sage: from sage.rings.multi_polynomial_libsingular import MPolynomialRing_libsingular
2387	sage: P.<x,y,z> = MPolynomialRing_libsingular(QQ,3)
2388	sage: f = (xyz)^6 - 1
2389	sage: g = (xyz)^4 - 1
2390	sage: f.gcd(g)
2391	x^2y^2z^2 - 1
2392	sage: GCD([x^3 - 3*x + 2, x^4 - 1, x^6 -1])
2393	x - 1
2394
2395	TESTS:
2396	sage: from sage.rings.multi_polynomial_libsingular import MPolynomialRing_libsingular
2397	sage: Q.<x,y,z> = MPolynomialRing_libsingular(QQ,3)
2398	sage: P.<x,y,z> = MPolynomialRing_libsingular(QQ,3)
2399	sage: P(0).gcd(Q(0))
2400	0
2401	sage: x.gcd(1)
2402	1
2403
2404	"""
2405	cdef MPolynomial_libsingular _right
2406	cdef poly *_res
2407	cdef ring *_ring
2408
2409	_ring = (<MPolynomialRing_libsingular>self._parent)._ring
2410
2411	if(_ring != currRing): rChangeCurrRing(_ring)
2412
2413	if not PY_TYPE_CHECK(right, MPolynomial_libsingular):
2414	_right = (<MPolynomialRing_libsingular>self._parent)._coerce_c(right)
2415	else:
2416	_right = (<MPolynomial_libsingular>right)
2417
2418	_res = singclap_gcd(p_Copy(self._poly, _ring), p_Copy(_right._poly, _ring))
2419
2420	return new_MP((<MPolynomialRing_libsingular>self._parent), _res)
2421
2422	## def lcm(self, MPolynomial_libsingular g):
2423	## cdef ring *_ring = (<MPolynomialRing_libsingular>self._parent)._ring
2424	## cdef poly *ret
2425	## if(_ring != currRing): rChangeCurrRing(_ring)
2426
2427	## if self._parent is not g._parent:
2428	## g = (<MPolynomialRing_libsingular>self._parent)._coerce_c(g)
2429
2430	## # This guy calculates on napoly not poly
2431	## ret = singclap_alglcm(self._poly, (<MPolynomial_libsingular>g)._poly)
2432	## return new_MP(self._parent, ret)
2433
2434	def is_square_free(self):
2435	"""
2436	"""
2437	cdef ring *_ring = (<MPolynomialRing_libsingular>self._parent)._ring
2438	if(_ring != currRing): rChangeCurrRing(_ring)
2439	return bool(singclap_isSqrFree(self._poly))
2440
2441	def quo_rem(self, MPolynomial_libsingular right):
2442	"""
2443	"""
2444	if self._parent is not right._parent:
2445	right = self._parent._coerce_c(right)
2446	raise NotImplementedError
2447
2448	def _magma_(self, magma=None):
2449	"""
2450	Returns the MAGMA representation of self.
2451
2452	EXAMPLES:
2453	sage: from sage.rings.multi_polynomial_libsingular import MPolynomialRing_libsingular
2454	sage: R.<x,y> = MPolynomialRing_libsingular(GF(2),2)
2455	sage: f = y*x^2 + x +1
2456	sage: f._magma_() #optional
2457	x^2*y + x + 1
2458	"""
2459	if magma is None:
2460	# TODO: import this globally
2461	import sage.interfaces.magma
2462	magma = sage.interfaces.magma.magma
2463
2464	magma_gens = [e.name() for e in self.parent()._magma_().gens()]
2465	f = self._repr_with_changed_varnames(magma_gens)
2466	return magma(f)
2467
2468	def _singular_(self, singular=singular_default, have_ring=False):
2469	"""
2470	Return a SINGULAR (as in the CAS) element for this
2471	element. The result is cached.
2472
2473	INPUT:
2474	singular -- interpreter (default: singular_default)
2475	have_ring -- should the correct ring not be set in SINGULAR first (default:False)
2476
2477	EXAMPLES:
2478	sage: from sage.rings.multi_polynomial_libsingular import MPolynomialRing_libsingular
2479	sage: P.<x,y,z> = MPolynomialRing_libsingular(GF(127),3)
2480	sage: x._singular_()
2481	x
2482	sage: f =(x^2 + 35*y + 128); f
2483	x^2 + 35*y + 1
2484	sage: x._singular_().name() == x._singular_().name()
2485	True
2486
2487
2488	TESTS:
2489	sage: from sage.rings.multi_polynomial_libsingular import MPolynomialRing_libsingular
2490	sage: P.<x,y,z> = MPolynomialRing_libsingular(GF(127),3)
2491	sage: P(0)._singular_()
2492	0
2493
2494	"""
2495	if not have_ring:
2496	self.parent()._singular_(singular).set_ring() #this is expensive
2497
2498	try:
2499	if self.__singular is None:
2500	return self._singular_init_c(singular, True)
2501
2502	self.__singular._check_valid()
2503
2504	if self.__singular.parent() is singular:
2505	return self.__singular
2506
2507	except (AttributeError, ValueError):
2508	pass
2509
2510	return self._singular_init_c(singular, True)
2511
2512	def _singular_init_(self,singular=singular_default, have_ring=False):
2513	"""
2514	Return a new SINGULAR (as in the CAS) element for this element.
2515
2516	INPUT:
2517	singular -- interpreter (default: singular_default)
2518	have_ring -- should the correct ring not be set in SINGULAR first (default:False)
2519
2520	EXAMPLES:
2521	sage: from sage.rings.multi_polynomial_libsingular import MPolynomialRing_libsingular
2522	sage: P.<x,y,z> = MPolynomialRing_libsingular(GF(127),3)
2523	sage: x._singular_init_()
2524	x
2525	sage: (x^2+37*y+128)._singular_init_()
2526	x^2+37*y+1
2527	sage: x._singular_init_().name() == x._singular_init_().name()
2528	False
2529
2530	TESTS:
2531	sage: from sage.rings.multi_polynomial_libsingular import MPolynomialRing_libsingular
2532	sage: P(0)._singular_init_()
2533	0
2534	"""
2535	return self._singular_init_c(singular, have_ring)
2536
2537	cdef _singular_init_c(self,singular, have_ring):
2538	"""
2539	See MPolynomial_libsingular._singular_init_
2540
2541	"""
2542	if not have_ring:
2543	self.parent()._singular_(singular).set_ring() #this is expensive
2544
2545	self.__singular = singular(str(self))
2546	return self.__singular
2547
2548	def sub_m_mul_q(self, MPolynomial_libsingular m, MPolynomial_libsingular q):
2549	"""
2550	Return self - m*q, where m must be a monomial and q a
2551	polynomial.
2552
2553	INPUT:
2554	m -- a monomial
2555	q -- a polynomial
2556
2557	EXAMPLE:
2558	sage: from sage.rings.multi_polynomial_libsingular import MPolynomialRing_libsingular
2559	sage: P.<x,y,z>=MPolynomialRing_libsingular(QQ,3)
2560	sage: x.sub_m_mul_q(y,z)
2561	-y*z + x
2562
2563	TESTS:
2564	sage: from sage.rings.multi_polynomial_libsingular import MPolynomialRing_libsingular
2565	sage: Q.<x,y,z>=MPolynomialRing_libsingular(QQ,3)
2566	sage: P.<x,y,z>=MPolynomialRing_libsingular(QQ,3)
2567	sage: P(0).sub_m_mul_q(P(0),P(1))
2568	0
2569	sage: x.sub_m_mul_q(Q.gen(1),Q.gen(2))
2570	-y*z + x
2571
2572	"""
2573	cdef ring *r = (<MPolynomialRing_libsingular>self._parent)._ring
2574
2575	if not self._parent is m._parent:
2576	m = self._parent._coerce_c(m)
2577	if not self._parent is q._parent:
2578	q = self._parent._coerce_c(q)
2579
2580	if m._poly and m._poly.next:
2581	raise ArithmeticError, "m must be a monomial"
2582	elif not m._poly:
2583	return self
2584
2585	return new_MP(self._parent, p_Minus_mm_Mult_qq(p_Copy(self._poly, r), m._poly, q._poly, r))
2586
2587	def add_m_mul_q(self, MPolynomial_libsingular m, MPolynomial_libsingular q):
2588	"""
2589	Return self + m*q, where m must be a monomial and q a
2590	polynomial.
2591
2592	INPUT:
2593	m -- a monomial
2594	q -- a polynomial
2595
2596	EXAMPLE:
2597	sage: from sage.rings.multi_polynomial_libsingular import MPolynomialRing_libsingular
2598	sage: P.<x,y,z>=MPolynomialRing_libsingular(QQ,3)
2599	sage: x.add_m_mul_q(y,z)
2600	y*z + x
2601
2602	TESTS:
2603	sage: from sage.rings.multi_polynomial_libsingular import MPolynomialRing_libsingular
2604	sage: R.<x,y,z>=MPolynomialRing_libsingular(QQ,3)
2605	sage: P.<x,y,z>=MPolynomialRing_libsingular(QQ,3)
2606	sage: P(0).add_m_mul_q(P(0),P(1))
2607	0
2608	sage: x.add_m_mul_q(R.gen(),R.gen(1))
2609	x*y + x
2610	"""
2611
2612	cdef ring *r = (<MPolynomialRing_libsingular>self._parent)._ring
2613
2614	if not self._parent is m._parent:
2615	m = self._parent._coerce_c(m)
2616	if not self._parent is q._parent:
2617	q = self._parent._coerce_c(q)
2618
2619	if m._poly and m._poly.next:
2620	raise ArithmeticError, "m must be a monomial"
2621	elif not m._poly:
2622	return self
2623
2624	return new_MP(self._parent, p_Plus_mm_Mult_qq(p_Copy(self._poly, r), m._poly, q._poly, r))
2625
2626
2627	def __reduce__(self):
2628	"""
2629
2630	Serialize self.
2631
2632	EXAMPLES:
2633	sage: from sage.rings.multi_polynomial_libsingular import MPolynomialRing_libsingular
2634	sage: P.<x,y,z> = MPolynomialRing_libsingular(QQ,3, order='degrevlex')
2635	sage: f = 27/113 * x^2 + y*z + 1/2
2636	sage: f == loads(dumps(f))
2637	True
2638
2639	sage: P = MPolynomialRing_libsingular(GF(127),3,names='abc')
2640	sage: a,b,c = P.gens()
2641	sage: f = 57 * a^2b + 43 c + 1
2642	sage: f == loads(dumps(f))
2643	True
2644
2645	"""
2646	return sage.rings.multi_polynomial_libsingular.unpickle_MPolynomial_libsingular, ( self._parent, self.dict() )
2647
2648	def unpickle_MPolynomial_libsingular(MPolynomialRing_libsingular R, d):
2649	"""
2650	Deserialize a MPolynomial_libsingular object
2651
2652	INPUT:
2653	R -- the base ring
2654	d -- a Python dictionary as returned by MPolynomial_libsingular.dict
2655
2656	"""
2657	cdef ring *r = R._ring
2658	cdef poly m, p
2659	cdef int _i, _e
2660	p = p_ISet(0,r)
2661	for mon,c in d.iteritems():
2662	m = p_Init(r)
2663	for i,e in mon.sparse_iter():
2664	_i = i
2665	if _i >= r.N:
2666	p_Delete(&p,r)
2667	p_Delete(&m,r)
2668	raise TypeError, "variable index too big"
2669	_e = e
2670	if _e <= 0:
2671	p_Delete(&p,r)
2672	p_Delete(&m,r)
2673	raise TypeError, "exponent too small"
2674	p_SetExp(m, _i+1,_e, r)
2675	p_SetCoeff(m, co.sa2si(c, r), r)
2676	p_Setm(m,r)
2677	p = p_Add_q(p,m,r)
2678	return new_MP(R,p)

Note: See TracBrowser for help on using the repository browser.

Download in other formats: