| Home | Trees | Indices | Help |
|---|
|
|
object --+
|
structure.sage_object.SageObject --+
|
structure.element.Element --+
|
structure.element.ModuleElement --+
|
structure.element.RingElement --+
|
structure.element.CommutativeRingElement --+
|
structure.element.CommutativeAlgebraElement --+
|
Polynomial
File: sage/rings/polynomial/polynomial_element.pyx (starting at line 134)
A polynomial.
EXAMPLE:
sage: R.<y> = QQ['y']
sage: S.<x> = R['x']
sage: f = x*y; f
y*x
sage: type(f)
<type 'sage.rings.polynomial.polynomial_element.Polynomial_generic_dense'>
sage: p = (y+1)^10; p(1)
1024
|
|||
|
|||
|
|||
|
|||
|
|||
|
|||
|
|||
|
|||
|
|||
|
|||
|
|||
|
|||
|
|||
|
|||
|
|||
|
|||
|
|||
|
|||
|
|||
|
|||
|
|||
|
|||
|
|||
|
|||
|
|||
|
|||
|
|||
|
|||
|
|||
|
|||
|
|||
|
|||
|
|||
|
|||
|
|||
|
|||
|
|||
|
|||
|
|||
|
|||
|
|||
|
|||
|
|||
|
|||
|
|||
|
|||
|
|||
|
|||
|
|||
|
|||
|
|||
|
|||
|
|||
|
|||
|
|||
|
|||
|
|||
|
|||
|
|||
|
|||
|
|||
|
|||
|
|||
|
|||
|
|||
|
|||
|
|||
|
|||
|
|||
|
|||
|
|||
|
|||
|
|||
|
|||
|
|||
|
|||
|
|||
|
|||
|
|||
|
|||
|
|||
|
|||
|
|||
|
|||
|
|||
|
|||
|
|||
|
|||
|
|||
|
|||
|
|||
|
|||
|
|||
|
|||
|
|||
|
|||
|
|||
|
|||
|
|||
|
|||
|
|||
|
|||
|
|||
|
|||
|
|||
|
|||
|
|||
|
|||
|
|||
|
|||
|
|||
|
|||
|
|||
|
Inherited from Inherited from Inherited from Inherited from Inherited from Inherited from Inherited from Inherited from |
|||
|
|||
|
Inherited from |
|||
|
|||
File: sage/rings/polynomial/polynomial_element.pyx (starting at line 317)
Evaluate polynomial at x=a.
INPUT:
a -- ring element a; need not be in the coefficient
ring of the polynomial.
-- or --
a dictionary for kwds:value pairs. If the variable
name of the polynomial is a kwds it is substituted in;
otherwise this polynomial is returned unchanged.
OUTPUT:
the value of f at a.
EXAMPLES:
sage: R.<x> = QQ[]
sage: f = x/2 - 5
sage: f(3)
-7/2
sage: R.<x> = ZZ[]
sage: f = (x-1)^5
sage: f(2/3)
-1/243
We evaluate a polynomial over a quaternion algebra:
sage: A.<i,j,k> = QuaternionAlgebra(QQ, -1,-1)
sage: R.<w> = PolynomialRing(A,sparse=True)
sage: f = i*j*w^5 - 13*i*w^2 + (i+j)*w + i
sage: f(i+j+1)
24 + 26*i - 10*j - 25*k
sage: w = i+j+1; i*j*w^5 - 13*i*w^2 + (i+j)*w + i
24 + 26*i - 10*j - 25*k
The parent ring of the answer always "starts" with the parent
of the object at which we are evaluating. Thus, e.g., if
we input a matrix, we are guaranteed to get a matrix out,
though the base ring of that matrix may change depending on
the base of the polynomial ring.
sage: R.<x> = QQ[]
sage: f = R(2/3)
sage: a = matrix(ZZ,2)
sage: b = f(a); b
[2/3 0]
[ 0 2/3]
sage: b.parent()
Full MatrixSpace of 2 by 2 dense matrices over Rational Field
sage: f = R(1)
sage: b = f(a); b
[1 0]
[0 1]
sage: b.parent()
Full MatrixSpace of 2 by 2 dense matrices over Rational Field
sage: R.<w> = GF(17)[]
sage: f = w^3 + 3*w +2
sage: f(5)
6
sage: f(w=5)
6
sage: f(x=10) # x isn't mention
w^3 + 3*w + 2
Nested polynomial ring elements can be called like multi-variate polynomials.
sage: R.<x> = QQ[]; S.<y> = R[]
sage: f = x+y*x+y^2
sage: f.parent()
Univariate Polynomial Ring in y over Univariate Polynomial Ring in x over Rational Field
sage: f(2)
3*x + 4
sage: f(2,4)
16
sage: f(y=2,x=4)
16
sage: f(2,x=4)
16
sage: f(2,x=4,z=5)
16
sage: f(2,4, z=10)
16
sage: f(y=x)
2*x^2 + x
sage: f(x=y)
2*y^2 + y
The following results in an element of the symbolic ring.
sage: f(x=sqrt(2))
y*(y + sqrt(2)) + sqrt(2)
sage: R.<t> = PowerSeriesRing(QQ, 't'); S.<x> = R[]
sage: f = 1 + x*t^2 + 3*x*t^4
sage: f(2)
1 + 2*t^2 + 6*t^4
sage: f(2, 1/2)
15/8
AUTHORS:
-- David Joyner, 2005-04-10
-- William Stein, 2006-01-22; change so parent
is determined by the arithmetic
-- William Stein, 2007-03-24: fix parent being determined in the constant case!
-- Robert Bradshaw, 2007-04-09: add support for nested calling
-- Tom Boothby, 2007-05-01: evaluation done by CompiledPolynomialFunction
-- William Stein, 2007-06-03: add support for keyword arguments.
|
File: sage/rings/polynomial/polynomial_element.pyx (starting at line 1482)
Return a "copy" of self. This is just self, since in SAGE polynomials are
immutable this just returns self again.
EXAMPLES:
We create the polynomial $f=x+3$, then note that the copy is just
the same polynomial again, which is fine since polynomials are immutable.
sage: x = ZZ['x'].0
sage: f = x + 3
sage: g = copy(f)
sage: g is f
True
|
File: sage/rings/polynomial/polynomial_element.pyx (starting at line 934)
EXAMPLES:
sage: x = QQ['x'].0
sage: f = (x^3 + 5)/3; f
1/3*x^3 + 5/3
sage: f.parent()
Univariate Polynomial Ring in x over Rational Field
If we do the same over $\ZZ$ the result is in the polynomial
ring over $\QQ$.
sage: x = ZZ['x'].0
sage: f = (x^3 + 5)/3; f
1/3*x^3 + 5/3
sage: f.parent()
Univariate Polynomial Ring in x over Rational Field
Divides can make elements of the fraction field:
sage: R.<x> = QQ['x']
sage: f = x^3 + 5
sage: g = R(3)
sage: h = f/g; h
1/3*x^3 + 5/3
sage: h.parent()
Fraction Field of Univariate Polynomial Ring in x over Rational Field
This is another example over a non-prime finite field
(submited by a student of Jon Hanke). It illustrates
cancellation between the numerator and denominator
over a non-prime finite field.
sage: R.<x> = PolynomialRing(GF(5^2, 'a'), 'x')
sage: f = x^3 + 4*x
sage: f / (x - 1)
x^2 + x
Be careful about coercions (this used to be broken):
sage: R.<x> = ZZ['x']
sage: f = x / Mod(2,5); f
3*x
sage: f.parent()
Univariate Polynomial Ring in x over Ring of integers modulo 5
|
x==y
|
File: sage/rings/polynomial/polynomial_element.pyx (starting at line 1163)
Quotient of division of self by other. This is denoted //.
If self = quotient * right + remainder, this function returns
quotient.
EXAMPLES:
sage: R.<x> = ZZ[]
sage: f = x^3 + x + 1
sage: g = f*(x^2-2) + x
sage: g.__floordiv__(f)
x^2 - 2
sage: g//f
x^2 - 2
|
x>=y
|
x>y
|
hash(x)
|
x.__init__(...) initializes x; see x.__class__.__doc__ for signature
|
File: sage/rings/polynomial/polynomial_element.pyx (starting at line 711)
EXAMPLES:
sage: R.<x> = QQ[]
sage: f = x - 90283
sage: f.__invert__()
1/(x - 90283)
sage: ~f
1/(x - 90283)
|
x<=y
|
File: sage/rings/polynomial/polynomial_element.pyx (starting at line 829)
EXAMPLES:
sage: R.<x> = ZZ[]
sage: f = x - 902384
sage: long(f)
Traceback (most recent call last):
...
TypeError: cannot coerce nonconstant polynomial to long
sage: long(R(939392920202))
939392920202L
|
x<y
|
File: sage/rings/polynomial/polynomial_element.pyx (starting at line 1182)
Remainder of division of self by other.
EXAMPLES:
sage: R.<x> = ZZ[]
sage: x % (x+1)
-1
sage: (x^3 + x - 1) % (x^2 - 1)
2*x - 1
|
x!=y
|
|
x != 0
|
pow(x, y[, z])
|
y/x
|
pow(x, y[, z])
|
File: sage/rings/polynomial/polynomial_element.pyx (starting at line 1611)
Return the formal derivative of this polynomial with respect
to the variable var.
If var is the generator of this polynomial ring (or the default
value None), this is the usual formal derivative.
Otherwise, _derivative(var) is called recursively for each of the
coefficients of this polynomial.
SEE ALSO:
self.derivative()
EXAMPLES:
sage: R.<x> = ZZ[]
sage: R(0)._derivative()
0
sage: parent(R(0)._derivative())
Univariate Polynomial Ring in x over Integer Ring
sage: f = 7*x^5 + x^2 - 2*x - 3
sage: f._derivative()
35*x^4 + 2*x - 2
sage: f._derivative(None)
35*x^4 + 2*x - 2
sage: f._derivative(x)
35*x^4 + 2*x - 2
In the following example, it doesn't recognise 2*x as the generator, so it
tries to differentiate each of the coefficients with respect to 2*x, which
doesn't work because the integer coefficients don't have a _derivative() method:
sage: f._derivative(2*x)
Traceback (most recent call last):
...
AttributeError: 'sage.rings.integer.Integer' object has no attribute '_derivative'
Examples illustrating recursive behaviour:
sage: R.<x> = ZZ[]
sage: S.<y> = PolynomialRing(R)
sage: f = x^3 + y^3
sage: f._derivative()
3*y^2
sage: f._derivative(y)
3*y^2
sage: f._derivative(x)
3*x^2
sage: R = ZZ['x']
sage: S = R.fraction_field(); x = S.gen()
sage: R(1).derivative(R(x))
0
|
File: sage/rings/polynomial/polynomial_element.pyx (starting at line 502)
Returns a quickly-evaluating function on floats.
EXAMPLE:
sage: R.<t> = QQ[]
sage: f = t^3-t
sage: ff = f._fast_float_()
sage: ff(10)
990.0
Horner's method is used:
sage: f = (t+10)^3; f
t^3 + 30*t^2 + 300*t + 1000
sage: list(f._fast_float_())
['load 0', 'push 30.0', 'add', 'load 0', 'mul', 'push 300.0', 'add', 'load 0', 'mul', 'push 1000.0', 'add']
|
File: sage/rings/polynomial/polynomial_element.pyx (starting at line 2756)
EXAMPLES:
sage: R.<y> = ZZ[]
sage: f = y^3 - 17*y + 5
sage: g = gap(f); g
y^3-17*y+5
sage: f._gap_init_()
'y^3 - 17*y + 5'
sage: R.<z> = ZZ[]
sage: gap(R)
PolynomialRing( Integers, ["z"] )
sage: g
y^3-17*y+5
sage: gap(z^2 + z)
z^2+z
We coerce a polynomial with coefficients in a finite field:
sage: R.<y> = GF(7)[]
sage: f = y^3 - 17*y + 5
sage: g = gap(f); g
y^3+Z(7)^4*y+Z(7)^5
sage: g.Factors()
[ y+Z(7)^0, y+Z(7)^0, y+Z(7)^5 ]
sage: f.factor()
(y + 5) * (y + 1)^2
|
File: sage/rings/polynomial/polynomial_element.pyx (starting at line 2753)
|
File: sage/rings/polynomial/polynomial_element.pyx (starting at line 654)
EXAMPLES:
sage: R.<x> = ZZ[]
sage: H = Hom(R, QQ); H
Set of Homomorphisms from Univariate Polynomial Ring in x over Integer Ring to Rational Field
sage: f = H([5]); f
Ring morphism:
From: Univariate Polynomial Ring in x over Integer Ring
To: Rational Field
Defn: x |--> 5
sage: f(x)
5
sage: f(x^2 + 3)
28
|
File: sage/rings/polynomial/polynomial_element.pyx (starting at line 680)
EXAMPLES:
sage: k = GF(47)
sage: R.<x> = PolynomialRing(k)
sage: ZZ(R(45))
45
sage: ZZ(3*x + 45)
Traceback (most recent call last):
...
TypeError: cannot coerce nonconstant polynomial
|
File: sage/rings/polynomial/polynomial_element.pyx (starting at line 1195)
|
File: sage/rings/polynomial/polynomial_element.pyx (starting at line 1085)
Return the latex representation of this polynomial.
EXAMPLES:
A fairly simple example over $\QQ$.
sage: x = polygen(QQ)
sage: latex(x^3+2/3*x^2 - 5/3)
x^{3} + \frac{2}{3} x^{2} - \frac{5}{3}
A $p$-adic example where the coefficients are $0$ to some precision.
sage: K = Qp(3,20)
sage: R.<x> = K[]
sage: f = K(0,-2)*x + K(0,-1)
sage: f
(O(3^-2))*x + (O(3^-1))
sage: latex(f)
\left(O(3^{-2})\right) x + O(3^{-1})
The following illustrates the fix of trac \#2586:
sage: latex(ZZ['alpha']['b']([0, ZZ['alpha'].0]))
\alpha b
|
File: sage/rings/polynomial/polynomial_element.pyx (starting at line 2133) Let f and g be two polynomials. Then this function returns the monic least common multiple of f and g. |
File: sage/rings/polynomial/polynomial_element.pyx (starting at line 2723)
Return the Magma version of this polynomial.
EXAMPLES:
sage: R.<y> = ZZ[]
sage: f = y^3 - 17*y + 5
sage: g = magma(f); g # optional -- requires Magma
y^3 - 17*y + 5
Note that in Magma there is only one polynomial ring over each base,
so if we make the polynomial ring over ZZ with variable $z$, then
this changes the variable name of the polynomial we already defined:
sage: R.<z> = ZZ[]
sage: magma(R) # optional -- requires Magma
Univariate Polynomial Ring in z over Integer Ring
sage: g # optional -- requires Magma
z^3 - 17*z + 5
In SAGE the variable name does not change:
sage: f
y^3 - 17*y + 5
|
File: sage/rings/polynomial/polynomial_element.pyx (starting at line 2711)
Return a string that evaluates in Magma to this polynomial.
EXAMPLES:
sage: R.<y> = ZZ[]
sage: f = y^3 - 17*y + 5
sage: f._magma_init_()
'Polynomial(IntegerRing(), [5,-17,0,1])'
|
File: sage/rings/polynomial/polynomial_element.pyx (starting at line 1432)
Return a dict of coefficent entries suitable for construction of a MPolynomial_polydict
with the given variables.
EXAMPLES:
sage: R.<x> = ZZ[]
sage: R(0)._mpoly_dict_recursive()
{}
sage: f = 7*x^5 + x^2 - 2*x - 3
sage: f._mpoly_dict_recursive()
{(0,): -3, (1,): -2, (5,): 7, (2,): 1}
|
File: sage/rings/polynomial/polynomial_element.pyx (starting at line 1238)
Returns the product of two polynomials using Kronecker's trick
to do the multiplication. This could be used used over a
generic base ring.
NOTES:
\begin{itemize}
\item Since this is implemented in interpreted Python, it
could be hugely sped up by reimplementing it in Pyrex.
\item Over the reals there is precision loss, at least in
the current implementation.
\end{itemize}
INPUT:
self -- Polynomial
right -- Polynomial (over same base ring as self)
OUTPUT: Polynomial
The product self*right.
ALGORITHM:
Based on a paper by R. Fateman
{\tt http://www.cs.berkeley.edu/~fateman/papers/polysbyGMP.pdf}
The idea is to encode dense univariate polynomials as big
integers, instead of sequences of coefficients. The paper
argues that because integer multiplication is so cheap, that
encoding 2 polynomials to big numbers and then decoding the
result might be faster than popular multiplication algorithms.
This seems true when the degree is larger than 200.
EXAMPLES:
sage: S.<y> = PolynomialRing(RR)
sage: f = y^10 - 1.393493*y + 0.3
sage: f._mul_karatsuba(f)
1.00000000000000*y^20 - 2.78698600000000*y^11 + 0.600000000000000*y^10 + 1.11022302462516e-16*y^8 - 1.11022302462516e-16*y^6 - 1.11022302462516e-16*y^3 + 1.94182274104900*y^2 - 0.836095800000000*y + 0.0900000000000000
sage: f._mul_fateman(f)
1.00000000000000*y^20 - 2.78698600000000*y^11 + 0.600000000000000*y^10 + 1.94182274104900*y^2 - 0.836095800000000*y + 0.0900000000000000
Advantages:
\begin{itemize}
\item Faster than Karatsuba over $\Q$ and $\Z$
(but much slower still than calling NTL's
optimized C++ implementation, which is the
default over $\Z$)
\item Potentially less complicated.
\end{itemize}
Drawbacks:
\begin{itemize}
\item Slower over R when the degree of both of polynomials is less
than 250 (roughly).
\item Over R, results may not be as accurate as the Karatsuba
case. This is because we represent coefficients of
polynomials over R as fractions, then convert them back to
floating-point numbers.
\end{itemize}
AUTHOR:
-- Didier Deshommes (2006-05-25)
|
File: sage/rings/polynomial/polynomial_element.pyx (starting at line 1307)
Returns the product of two polynomials using the Karatsuba
divide and conquer multiplication algorithm. This is only
used over a generic base ring. (Special libraries like NTL
are used, e.g., for the integers and rationals, which are much
faster.)
INPUT:
self: Polynomial
right: Polynomial (over same base ring as self)
OUTPUT: Polynomial
The product self*right.
ALGORITHM:
The basic idea is to use that
$$
(aX + b) (cX + d) = acX^2 + ((a+b)(c+d)-ac-bd)X + bd
$$
where ac=a*c and bd=b*d, which requires three
multiplications instead of the naive four. (In my examples,
strangely just doing the above with four multiplications
does tend to speed things up noticeably.)
Given f and g of arbitrary degree bigger than one, let e
be min(deg(f),deg(g))/2. Write
$$
f = a X^e + b \text{ and } g = c X^e + d
$$
and use the identity
$$
(aX^e + b) (cX^e + d) = ac X^{2e} +((a+b)(c+d) - ac - bd)X^e + bd
$$
to recursively compute $fg$.
TIMINGS:
On a Pentium M 1.8Ghz laptop:
f=R.random(1000,bound=100)
g=R.random(1000,bound=100)
time h=f._mul_karatsuba(g)
Time: 0.42 seconds
The naive multiplication algorithm takes 14.58 seconds.
In contrast, MAGMA does this sort of product almost
instantly, and can easily deal with degree 5000. Basically
MAGMA is 100 times faster at polynomial multiplication.
Over Z using NTL, multiplying two polynomials constructed
using R.random(10000,bound=100) takes 0.10 seconds. Using
MAGMA V2.11-10 the same takes 0.14 seconds. So in this
case NTL is somewhat faster than MAGMA.
Over Q using PARI, multiplying two polynomials constructed
using R.random(10000,bound=100) takes 1.23 seconds. Not
good! TODO: use NTL polynomials over Z with a denominator
instead of PARI.
NOTES:
* Karatsuba multiplication of polynomials is also implemented in PARI in
src/basemath/polarit3.c
* The MAGMA documentation appears to give no information about how
polynomial multiplication is implemented.
|
File: sage/rings/polynomial/polynomial_element.pyx (starting at line 2629)
Return polynomial as a PARI object.
SAGE does not handle PARI's variable ordering requirements gracefully
at this time. In practice, this means that the variable \code{x}
needs to be the topmost variable, as in the example.
EXAMPLES:
sage: f = QQ['x']([0,1,2/3,3])
sage: pari(f)
3*x^3 + 2/3*x^2 + x
sage: S.<a> = QQ['a']
sage: R.<x> = S['x']
sage: f = R([0, a]) + R([0, 0, 2/3])
sage: pari(f)
2/3*x^2 + a*x
TESTS:
Unfortunately, variable names matter:
sage: R.<x, y> = QQ[]
sage: S.<a> = R[]
sage: f = x^2 + a; g = y^3 + a
sage: pari(f)
Traceback (most recent call last):
...
PariError: (8)
Stacked polynomial rings, first with a univariate ring on the bottom:
sage: S.<a> = QQ['a']
sage: R.<x> = S['x']
sage: pari(x^2 + 2*x)
x^2 + 2*x
sage: pari(a*x + 2*x^3)
2*x^3 + a*x
Stacked polynomial rings, second with a multivariate ring on the bottom:
sage: S.<a, b> = ZZ['a', 'b']
sage: R.<x> = S['x']
sage: pari(x^2 + 2*x)
x^2 + 2*x
sage: pari(a*x + 2*b*x^3)
2*b*x^3 + a*x
Stacked polynomial rings with exotic base rings:
sage: S.<a, b> = GF(7)['a', 'b']
sage: R.<x> = S['x']
sage: pari(x^2 + 9*x)
x^2 + 2*x
sage: pari(a*x + 9*b*x^3)
2*b*x^3 + a*x
sage: S.<a> = Integers(8)['a']
sage: R.<x> = S['x']
sage: pari(x^2 + 2*x)
Mod(1, 8)*x^2 + Mod(2, 8)*x
sage: pari(a*x + 10*x^3)
Mod(2, 8)*x^3 + (Mod(1, 8)*a)*x
|
File: sage/rings/polynomial/polynomial_element.pyx (starting at line 2708)
|
File: sage/rings/polynomial/polynomial_element.pyx (starting at line 2691)
Return polynomial as a PARI object with topmost variable \code{name}.
For internal use only.
|
File: sage/rings/polynomial/polynomial_element.pyx (starting at line 696)
EXAMPLES:
sage: R.<x> = PolynomialRing(QQ)
sage: QQ(R(45/4))
45/4
sage: QQ(3*x + 45)
Traceback (most recent call last):
...
TypeError: cannot coerce nonconstant polynomial
|
File: sage/rings/polynomial/polynomial_element.pyx (starting at line 1023)
Return the string representation of this polynomial.
INPUT:
name -- None or a string; used for printing the variable.
EXAMPLES:
sage: R.<x> = QQ[]
sage: f = x^3 + x + 1
sage: f._repr()
'x^3 + x + 1'
sage: f._repr('theta')
'theta^3 + theta + 1'
sage: f._repr('sage math')
'sage math^3 + sage math + 1'
|
File: sage/rings/polynomial/polynomial_element.pyx (starting at line 1070)
Return string representatin of this polynomial.
EXAMPLES:
sage: x = polygen(QQ)
sage: f = x^3+2/3*x^2 - 5/3
sage: f._repr_()
'x^3 + 2/3*x^2 - 5/3'
sage: f.rename('vaughn')
sage: f
vaughn
|
File: sage/rings/polynomial/polynomial_element.pyx (starting at line 3667)
Extended gcd of self and polynomial other.
Returns g, u, and v such that
\code{g = u*self + v*other.}
EXAMPLES:
sage: P.<x> = QQ[]
sage: F = (x^2 + 2)*x^3; G = (x^2+2)*(x-3)
sage: g, u, v = F.xgcd(G)
sage: g, u, v
(27*x^2 + 54, 1, -x^2 - 3*x - 9)
sage: u*F + v*G
27*x^2 + 54
sage: g, u, v = x.xgcd(P(0)); g, u, v
(x, 1, 0)
sage: g == u*x + v*P(0)
True
sage: g, u, v = P(0).xgcd(x); g, u, v
(x, 0, 1)
sage: g == u*P(0) + v*x
True
|
File: sage/rings/polynomial/polynomial_element.pyx (starting at line 3577)
Returns the generator of this polynomial ring, which is the (only)
argument used when calling self.
EXAMPLES:
sage: R.<x> = QQ[]
sage: x.args()
(x,)
A constant polynomial has no variables, but still takes a single argument.
sage: R(2).args()
(x,)
|
File: sage/rings/polynomial/polynomial_element.pyx (starting at line 1384)
Return a copy of this polynomial but with coefficients in R, if there
is a natural map from coefficient ring of self to R.
EXAMPLES:
sage: R.<x> = QQ[]
sage: f = x^3 - 17*x + 3
sage: f.base_extend(GF(7))
Traceback (most recent call last):
...
TypeError: no such base extension
sage: f.change_ring(GF(7))
x^3 + 4*x + 3
|
File: sage/rings/polynomial/polynomial_element.pyx (starting at line 1371)
Return the base ring of the parent of self.
EXAMPLES:
sage: R.<x> = ZZ[]
sage: x.base_ring()
Integer Ring
sage: (2*x+3).base_ring()
Integer Ring
|
File: sage/rings/polynomial/polynomial_element.pyx (starting at line 1418)
Return a copy of this polynomial but with coefficients in R, if at
all possible.
EXAMPLES:
sage: K.<z> = CyclotomicField(3)
sage: f = K.defining_polynomial()
sage: f.change_ring(GF(7))
x^2 + x + 1
|
File: sage/rings/polynomial/polynomial_element.pyx (starting at line 1402)
Return a new polynomial over the same base ring but in a different
variable.
EXAMPLES:
sage: x = polygen(QQ,'x')
sage: f = -2/7*x^3 + (2/3)*x - 19/993; f
-2/7*x^3 + 2/3*x - 19/993
sage: f.change_variable_name('theta')
-2/7*theta^3 + 2/3*theta - 19/993
|
File: sage/rings/polynomial/polynomial_element.pyx (starting at line 2410)
Return the coefficients of the monomials appearing in self.
EXAMPLES:
sage: _.<x> = PolynomialRing(ZZ)
sage: f = x^4+2*x^2+1
sage: f.coefficients()
[1, 2, 1]
|
File: sage/rings/polynomial/polynomial_element.pyx (starting at line 2526)
Returns \code{self.list()}.
(It potentially slightly faster better to use
\code{self.list()} directly.)
EXAMPLES:
sage: x = QQ['x'].0
sage: f = 10*x^3 + 5*x + 2/17
sage: f.coeffs()
[2/17, 5, 0, 10]
|
File: sage/rings/polynomial/polynomial_element.pyx (starting at line 3502)
Return the complex roots of this polynomial, without
multiplicities.
Calls self.roots(ring=CC), unless this is a polynomial
with floating-point coefficients, in which case it is uses
the appropriate precision from the input coefficients.
EXAMPLES:
sage: x = polygen(ZZ)
sage: (x^3 - 1).complex_roots() # note: low order bits slightly different on ppc.
[1.00000000000000, -0.500000000000000 + 0.86602540378443...*I, -0.500000000000000 - 0.86602540378443...*I]
TESTS:
sage: x = polygen(RR)
sage: (x^3 - 1).complex_roots()[0].parent()
Complex Field with 53 bits of precision
sage: x = polygen(RDF)
sage: (x^3 - 1).complex_roots()[0].parent()
Complex Double Field
sage: x = polygen(RealField(200))
sage: (x^3 - 1).complex_roots()[0].parent()
Complex Field with 200 bits of precision
sage: x = polygen(CDF)
sage: (x^3 - 1).complex_roots()[0].parent()
Complex Double Field
sage: x = polygen(ComplexField(200))
sage: (x^3 - 1).complex_roots()[0].parent()
Complex Field with 200 bits of precision
|
File: sage/rings/polynomial/polynomial_element.pyx (starting at line 2232)
Return the constant coefficient of this polynomial.
OUTPUT:
elemenet of base ring
EXAMPLES:
sage: R.<x> = QQ[]
sage: f = -2*x^3 + 2*x - 1/3
sage: f.constant_coefficient()
-1/3
|
File: sage/rings/polynomial/polynomial_element.pyx (starting at line 1499)
Return the degree of this polynomial. The zero polynomial
has degree -1.
EXAMPLES:
sage: x = ZZ['x'].0
sage: f = x^93 + 2*x + 1
sage: f.degree()
93
sage: x = PolynomialRing(QQ, 'x', sparse=True).0
sage: f = x^100000
sage: f.degree()
100000
sage: x = QQ['x'].0
sage: f = 2006*x^2006 - x^2 + 3
sage: f.degree()
2006
sage: f = 0*x
sage: f.degree()
-1
sage: f = x + 33
sage: f.degree()
1
AUTHORS:
-- Naqi Jaffery (2006-01-24): examples
|
File: sage/rings/polynomial/polynomial_element.pyx (starting at line 1530)
Return the least common multiple of the denominators of
the entries of self, when this makes sense, i.e., when the
coefficients have a denominator function.
WARNING: This is not the denominator of the rational function
defined by self, which would always be 1 since self is a polynomial.
EXAMPLES:
First we compute the denominator of a polynomial with integer
coefficients, which is of course 1.
sage: R.<x> = ZZ[]
sage: f = x^3 + 17*x + 1
sage: f.denominator()
1
Next we compute the denominator of a polynomial with rational coefficients.
sage: R.<x> = PolynomialRing(QQ)
sage: f = (1/17)*x^19 - (2/3)*x + 1/3; f
1/17*x^19 - 2/3*x + 1/3
sage: f.denominator()
51
Finally, we try to compute the denominator of a polynomial with
coefficients in the real numbers, which is a ring whose elements
do not have a denominator method.
sage: R.<x> = RR[]
sage: f = x + RR('0.3'); f
1.00000000000000*x + 0.300000000000000
sage: f.denominator()
Traceback (most recent call last):
...
AttributeError: 'sage.rings.real_mpfr.RealNumber' object has no attribute 'denominator'
|
File: sage/rings/polynomial/polynomial_element.pyx (starting at line 1575)
The formal derivative of this polynomial, with respect to
variables supplied in args.
Multiple variables and iteration counts may be supplied; see
documentation for the global derivative() function for more details.
SEE ALSO:
self._derivative()
EXAMPLES:
sage: R.<x> = PolynomialRing(QQ)
sage: g = -x^4 + x^2/2 - x
sage: g.derivative()
-4*x^3 + x - 1
sage: g.derivative(x)
-4*x^3 + x - 1
sage: g.derivative(x, x)
-12*x^2 + 1
sage: g.derivative(x, 2)
-12*x^2 + 1
sage: R.<t> = PolynomialRing(ZZ)
sage: S.<x> = PolynomialRing(R)
sage: f = t^3*x^2 + t^4*x^3
sage: f.derivative()
3*t^4*x^2 + 2*t^3*x
sage: f.derivative(x)
3*t^4*x^2 + 2*t^3*x
sage: f.derivative(t)
4*t^3*x^3 + 3*t^2*x^2
|
File: sage/rings/polynomial/polynomial_element.pyx (starting at line 1721)
Return a sparse dictionary representation of this univariate polynomial.
EXAMPLES:
sage: R.<x> = QQ[]
sage: f = x^3 + -1/7*x + 13
sage: f.dict()
{0: 13, 1: -1/7, 3: 1}
|
File: sage/rings/polynomial/polynomial_element.pyx (starting at line 2851)
Returns the discrimant of self.
The discriminant is $$R_n := a_n^{2 n-2} \prod_{1<i<j<n} (r_i-r_j)^2,$$
where $n$ is the degree of self, $a_n$ is the leading coefficient of
self and the roots of self are $r_1, \ldots, r_n$.
OUTPUT:
An element of the base ring of the polynomial ring.
NOTES:
Uses the identity $R_n(f) := (-1)^(n (n-1)/2) R(f, f') a_n^(n-k-2)$,
where $n$ is the degree of self, $a_n$ is the leading coefficient
of self, $f'$ is the derivative of $f$, and $k$ is the degree of $f'$.
Calls \code{self.resultant}.
EXAMPLES:
In the case of elliptic curves in special form, the discriminant is
easy to calculate:
sage: R.<x> = QQ[]
sage: f = x^3 + x + 1
sage: d = f.discriminant(); d
-31
sage: d.parent() is QQ
True
sage: EllipticCurve([1, 1]).discriminant()/16
-31
sage: R.<x> = QQ[]
sage: f = 2*x^3 + x + 1
sage: d = f.discriminant(); d
-116
We can also compute discriminants over univariate and
multivariate polynomial rings, provided that PARI's variable
ordering requirements are respected. Usually, your discriminants
will work if you always ask for them in the variable \code{x}:
sage: R.<a> = QQ[]
sage: S.<x> = R[]
sage: f = a*x + x + a + 1
sage: d = f.discriminant(); d
1
sage: d.parent() is R
True
sage: R.<a, b> = QQ[]
sage: S.<x> = R[]
sage: f = x^2 + a + b
sage: d = f.discriminant(); d
-4*a - 4*b
sage: d.parent() is R
True
Unfortunately SAGE does not handle PARI's variable ordering requirements
gracefully, so the following fails:
sage: R.<x, y> = QQ[]
sage: S.<a> = R[]
sage: f = x^2 + a
sage: f.discriminant()
Traceback (most recent call last):
...
PariError: (8)
|
File: sage/rings/polynomial/polynomial_element.pyx (starting at line 2424)
Return the exponents of the monomials appearing in self.
EXAMPLES:
sage: _.<x> = PolynomialRing(ZZ)
sage: f = x^4+2*x^2+1
sage: f.exponents()
[0, 2, 4]
|
File: sage/rings/polynomial/polynomial_element.pyx (starting at line 1739)
Return the factorization of self over the base ring of this polynomial.
Factoring polynomials over $\Z/n\Z$ for $n$ composite is at the moment
not implemented.
INPUT:
a polynomial
OUTPUT:
Factorization -- the factorization of self, which is
a product of a unit with a product of powers of irreducible
factors.
Over a field the irreducible factors are all monic.
EXAMPLES:
We factor some polynomials over $\Q$.
sage: x = QQ['x'].0
sage: f = (x^3 - 1)^2
sage: f.factor()
(x - 1)^2 * (x^2 + x + 1)^2
Notice that over the field $\Q$ the irreducible factors are monic.
sage: f = 10*x^5 - 1
sage: f.factor()
(10) * (x^5 - 1/10)
sage: f = 10*x^5 - 10
sage: f.factor()
(10) * (x - 1) * (x^4 + x^3 + x^2 + x + 1)
Over $\Z$ the irreducible factors need not be monic:
sage: x = ZZ['x'].0
sage: f = 10*x^5 - 1
sage: f.factor()
10*x^5 - 1
We factor a non-monic polynomial over the finite field $F_{25}$.
sage: k.<a> = GF(25)
sage: R.<x> = k[]
sage: f = 2*x^10 + 2*x + 2*a
sage: F = f.factor(); F
(2) * (x + a + 2) * (x^2 + 3*x + 4*a + 4) * (x^2 + (a + 1)*x + a + 2) * (x^5 + (3*a + 4)*x^4 + (3*a + 3)*x^3 + 2*a*x^2 + (3*a + 1)*x + 3*a + 1)
Notice that the unit factor is included when we multiply $F$ back out.
sage: expand(F)
2*x^10 + 2*x + 2*a
Factorization also works even if the variable of the finite field is nefariously
labeled "x".
sage: x = GF(3^2, 'a')['x'].0
sage: f = x^10 +7*x -13
sage: G = f.factor(); G
(x + a) * (x + 2*a + 1) * (x^4 + (a + 2)*x^3 + (2*a + 2)*x + 2) * (x^4 + 2*a*x^3 + (a + 1)*x + 2)
sage: prod(G) == f
True
sage: f.parent().base_ring()._assign_names(['a'])
sage: f.factor()
(x + a) * (x + 2*a + 1) * (x^4 + (a + 2)*x^3 + (2*a + 2)*x + 2) * (x^4 + 2*a*x^3 + (a + 1)*x + 2)
sage: k = GF(9,'x') # purposely calling it x to test robustness
sage: x = PolynomialRing(k,'x0').gen()
sage: f = x^3 + x + 1
sage: f.factor()
(x0 + 2) * (x0 + x) * (x0 + 2*x + 1)
sage: f = 0*x
sage: f.factor()
Traceback (most recent call last):
...
ValueError: factorization of 0 not defined
sage: f = x^0
sage: f.factor()
1
Arbitrary precision real and complex factorization:
sage: R.<x> = RealField(100)[]
sage: F = factor(x^2-3); F
(1.0000000000000000000000000000*x - 1.7320508075688772935274463415) * (1.0000000000000000000000000000*x + 1.7320508075688772935274463415)
sage: expand(F)
1.0000000000000000000000000000*x^2 - 3.0000000000000000000000000000
sage: factor(x^2 + 1)
1.0000000000000000000000000000*x^2 + 1.0000000000000000000000000000
sage: C = ComplexField(100)
sage: R.<x> = C[]
sage: F = factor(x^2+3); F
(1.0000000000000000000000000000*x - 1.7320508075688772935274463415*I) * (1.0000000000000000000000000000*x + 1.7320508075688772935274463415*I)
sage: expand(F)
1.0000000000000000000000000000*x^2 + 3.0000000000000000000000000000
sage: factor(x^2+1)
(1.0000000000000000000000000000*x - 1.0000000000000000000000000000*I) * (1.0000000000000000000000000000*x + 1.0000000000000000000000000000*I)
sage: f = C.0 * (x^2 + 1) ; f
1.0000000000000000000000000000*I*x^2 + 1.0000000000000000000000000000*I
sage: F = factor(f); F
(1.0000000000000000000000000000*I) * (1.0000000000000000000000000000*x - 1.0000000000000000000000000000*I) * (1.0000000000000000000000000000*x + 1.0000000000000000000000000000*I)
sage: expand(F)
1.0000000000000000000000000000*I*x^2 + 1.0000000000000000000000000000*I
Over a complicated number field:
sage: x = polygen(QQ, 'x')
sage: f = x^6 + 10/7*x^5 - 867/49*x^4 - 76/245*x^3 + 3148/35*x^2 - 25944/245*x + 48771/1225
sage: K.<a> = NumberField(f)
sage: S.<T> = K[]
sage: ff = S(f); ff
T^6 + 10/7*T^5 + (-867/49)*T^4 + (-76/245)*T^3 + 3148/35*T^2 + (-25944/245)*T + 48771/1225
sage: F = ff.factor()
sage: len(F)
4
sage: F[:2]
[(T - a, 1), (T - 40085763200/924556084127*a^5 - 145475769880/924556084127*a^4 + 527617096480/924556084127*a^3 + 1289745809920/924556084127*a^2 - 3227142391585/924556084127*a - 401502691578/924556084127, 1)]
sage: expand(F)
T^6 + 10/7*T^5 + (-867/49)*T^4 + (-76/245)*T^3 + 3148/35*T^2 + (-25944/245)*T + 48771/1225
sage: f = x^2 - 1/3 ; K.<a> = NumberField(f) ; A.<T> = K[] ; g = A(x^2-1)
sage: g.factor()
(T - 1) * (T + 1)
sage: h = A(3*x^2-1) ; h.factor()
(3) * (T - a) * (T + a)
sage: h = A(x^2-1/3) ; h.factor()
(T - a) * (T + a)
Over the real double field:
sage: x = polygen(RDF)
sage: f = (x-1)^3
sage: f.factor() # random output (unfortunately)
(1.0*x - 1.00000859959) * (1.0*x^2 - 1.99999140041*x + 0.999991400484)
sage: (-2*x^2 - 1).factor()
(-2.0) * (1.0*x^2 + 0.5)
sage: (-2*x^2 - 1).factor().expand()
-2.0*x^2 - 1.0
Note that this factorization suffers from the roots function:
sage: f.roots() # random output (unfortunately)
[1.00000859959, 0.999995700205 + 7.44736245561e-06*I, 0.999995700205 - 7.44736245561e-06*I]
Over the complex double field. Because this approximate, all factors will occur
with multiplicity 1.
sage: x = CDF['x'].0; i = CDF.0
sage: f = (x^2 + 2*i)^3
sage: f.factor() # random low order bits
(1.0*x + -0.999994409957 + 1.00001040378*I) * (1.0*x + -0.999993785062 + 0.999989956987*I) * (1.0*x + -1.00001180498 + 0.999999639235*I) * (1.0*x + 0.999995530902 - 0.999987780431*I) * (1.0*x + 1.00001281704 - 1.00000223945*I) * (1.0*x + 0.999991652054 - 1.00000998012*I)
sage: f(-f.factor()[0][0][0]) # random low order bits
-2.38358052913e-14 - 2.57571741713e-14*I
Over a relative number field:
sage: x = QQ['x'].0
sage: L.<a> = CyclotomicField(3).extension(x^3 - 2)
sage: x = L['x'].0
sage: f = (x^3 + x + a)*(x^5 + x + L.1); f
x^8 + x^6 + a*x^5 + x^4 + zeta3*x^3 + x^2 + (a + zeta3)*x + zeta3*a
sage: f.factor()
(x^3 + x + a) * (x^5 + x + zeta3)
Factoring polynomials over $\Z/n\Z$ for composite $n$ is not
implemented:
sage: R.<x> = PolynomialRing(Integers(35))
sage: f = (x^2+2*x+2)*(x^2+3*x+9)
sage: f.factor()
Traceback (most recent call last):
...
NotImplementedError: factorization of polynomials over rings with composite characteristic is not implemented
|
File: sage/rings/polynomial/polynomial_element.pyx (starting at line 1678)
Return the integral of this polynomial.
NOTE: The integral is always chosen so the constant term is 0.
EXAMPLES:
sage: R.<x> = ZZ[]
sage: R(0).integral()
0
sage: f = R(2).integral(); f
2*x
Note that since the integral is defined over the same base
ring the integral is actually in the base ring.
sage: f.parent()
Univariate Polynomial Ring in x over Integer Ring
If the integral isn't defined over the same base ring, then the
base ring is extended:
sage: f = x^3 + x - 2
sage: g = f.integral(); g
1/4*x^4 + 1/2*x^2 - 2*x
sage: g.parent()
Univariate Polynomial Ring in x over Rational Field
|
File: sage/rings/polynomial/polynomial_element.pyx (starting at line 744)
Inverts the polynomial a with respect to m, or throw a
ValueError if no such inverse exists.
EXAMMPLES:
sage: S.<t> = QQ[]
sage: f = inverse_mod(t^2 + 1, t^3 + 1); f
-1/2*t^2 - 1/2*t + 1/2
sage: f * (t^2 + 1) % (t^3 + 1)
1
sage: f = t.inverse_mod((t+1)^7); f
-t^6 - 7*t^5 - 21*t^4 - 35*t^3 - 35*t^2 - 21*t - 7
sage: (f * t) + (t+1)^7
1
It also works over in-exact rings, but note that due to rounding
error the product is only guerenteed to be withing epsilon of the
constant polynomial 1.
sage: R.<x> = RDF[]
sage: f = inverse_mod(x^2 + 1, x^5 + x + 1); f
0.4*x^4 - 0.2*x^3 - 0.4*x^2 + 0.2*x + 0.8
sage: f * (x^2 + 1) % (x^5 + x + 1)
5.55111512313e-17*x^3 + 1.66533453694e-16*x^2 + 5.55111512313e-17*x + 1.0
sage: f = inverse_mod(x^3 - x + 1, x - 2); f
0.142857142857
sage: f * (x^3 - x + 1) % (x - 2)
1.0
ALGORITHM:
Solve the system as + mt = 1, returning s as the inverse
of a mod m.
Uses the Euclidean algorithm for exact rings, and solves a
linear system for the coefficients of s and t for inexact rings
(as the Euclidean algorithm may not converge in that case).
AUTHOR:
-- Robert Bradshaw (2007-05-31)
|
File: sage/rings/polynomial/polynomial_element.pyx (starting at line 723)
EXAMPLES:
sage: R.<x> = QQ[]
sage: f = x - 90283
sage: f.inverse_of_unit()
Traceback (most recent call last):
...
ValueError: self is not a unit.
sage: f = R(-90283); g = f.inverse_of_unit(); g
-1/90283
sage: parent(g)
Univariate Polynomial Ring in x over Rational Field
|
File: sage/rings/polynomial/polynomial_element.pyx (starting at line 2143)
Return True if this is a constant polynomial.
OUTPUT:
bool -- True if and only if this polynomial is constant
EXAMPLES:
sage: R.<x> = ZZ[]
sage: x.is_constant()
False
sage: R(2).is_constant()
True
sage: R(0).is_constant()
True
|
File: sage/rings/polynomial/polynomial_element.pyx (starting at line 2325)
Return True if this polynomial is the distinguished generator
of the parent polynomial ring.
EXAMPLES:
sage: R.<x> = QQ[]
sage: R(1).is_gen()
False
sage: R(x).is_gen()
True
Important -- this function doesn't return True if self equals
the generator; it returs True if self \emph{is} the generator.
sage: f = R([0,1]); f
x
sage: f.is_gen()
False
sage: f is x
False
sage: f == x
True
|
File: sage/rings/polynomial/polynomial_element.pyx (starting at line 3713)
Return True precisely if this polynomial is irreducible over
its base ring. Testing irreducibility over $\Z/n\Z$ for
composite $n$ is not implemented.
EXAMPLES:
sage: R.<x> = ZZ[]
sage: (x^3 + 1).is_irreducible()
False
sage: (x^2 - 1).is_irreducible()
False
sage: (x^3 + 2).is_irreducible()
True
sage: R(0).is_irreducible()
Traceback (most recent call last):
...
ValueError: self must be nonzero
$4$ is irreducible as a polynomial, since as a polynomial
it doesn't factor:
sage: R(4).is_irreducible()
True
TESTS:
sage: F.<t> = NumberField(x^2-5)
sage: Fx.<xF> = PolynomialRing(F)
sage: f = Fx([2*t - 5, 5*t - 10, 3*t - 6, -t, -t + 2, 1])
sage: f.is_irreducible()
False
sage: f = Fx([2*t - 3, 5*t - 10, 3*t - 6, -t, -t + 2, 1])
sage: f.is_irreducible()
True
|
File: sage/rings/polynomial/polynomial_element.pyx (starting at line 2247)
Returns True if this polynomial is monic. The zero
polynomial is by definition not monic.
EXAMPLES:
sage: x = QQ['x'].0
sage: f = x + 33
sage: f.is_monic()
True
sage: f = 0*x
sage: f.is_monic()
False
sage: f = 3*x^3 + x^4 + x^2
sage: f.is_monic()
True
sage: f = 2*x^2 + x^3 + 56*x^5
sage: f.is_monic()
False
AUTHORS:
-- Naqi Jaffery (2006-01-24): examples
|
File: sage/rings/polynomial/polynomial_element.pyx (starting at line 2300)
Return True if this polynomial is nilpotent.
EXAMPLES:
sage: R = Integers(12)
sage: S.<x> = R[]
sage: f = 5 + 6*x
sage: f.is_nilpotent()
False
sage: f = 6 + 6*x^2
sage: f.is_nilpotent()
True
sage: f^2
0
EXERCISE (Atiyah-McDonald, Ch 1): Let $A[x]$ be a polynomial
ring in one variable. Then $f=\sum a_i x^i \in A[x]$ is
nilpotent if and only if every $a_i$ is nilpotent.
|
File: sage/rings/polynomial/polynomial_element.pyx (starting at line 3828)
Return True if this polynomial is square free.
EXAMPLES:
sage: x = polygen(QQ)
sage: f = (x-1)*(x-2)*(x^2-5)*(x^17-3); f
x^21 - 3*x^20 - 3*x^19 + 15*x^18 - 10*x^17 - 3*x^4 + 9*x^3 + 9*x^2 - 45*x + 30
sage: f.is_squarefree()
True
sage: (f*(x^2-5)).is_squarefree()
False
|
File: sage/rings/polynomial/polynomial_element.pyx (starting at line 2272)
Return True if this polynomial is a unit.
EXAMPLES:
sage: a = Integers(90384098234^3)
sage: b = a(2*191*236607587)
sage: b.is_nilpotent()
True
sage: R.<x> = a[]
sage: f = 3 + b*x + b^2*x^2
sage: f.is_unit()
True
sage: f = 3 + b*x + b^2*x^2 + 17*x^3
sage: f.is_unit()
False
EXERCISE (Atiyah-McDonald, Ch 1): Let $A[x]$ be a polynomial
ring in one variable. Then $f=\sum a_i x^i \in A[x]$ is a
unit if and only if $a_0$ is a unit and $a_1,\ldots, a_n$ are
nilpotent.
|
File: sage/rings/polynomial/polynomial_element.pyx (starting at line 2350)
Return the leading coefficient of this polynomial.
OUTPUT:
element of the base ring
EXAMPLES:
sage: R.<x> = QQ[]
sage: f = (-2/5)*x^3 + 2*x - 1/3
sage: f.leading_coefficient()
-2/5
|
File: sage/rings/polynomial/polynomial_element.pyx (starting at line 2438)
Return a new copy of the list of the underlying
elements of self.
EXAMPLES:
sage: R.<x> = QQ[]
sage: f = (-2/5)*x^3 + 2*x - 1/3
sage: v = f.list(); v
[-1/3, 2, 0, -2/5]
Note that v is a list, it is mutable, and each
call to the list method returns a new list:
sage: type(v)
<type 'list'>
sage: v[0] = 5
sage: f.list()
[-1/3, 2, 0, -2/5]
Here is an example with a generic polynomial ring:
sage: R.<x> = QQ[]
sage: S.<y> = R[]
sage: f = y^3 + x*y -3*x; f
y^3 + x*y - 3*x
sage: type(f)
<type 'sage.rings.polynomial.polynomial_element.Polynomial_generic_dense'>
sage: v = f.list(); v
[-3*x, x, 0, 1]
sage: v[0] = 10
sage: f.list()
[-3*x, x, 0, 1]
|
File: sage/rings/polynomial/polynomial_element.pyx (starting at line 2365)
Return this polynomial divided by its leading coefficient.
Does not change this polynomial.
EXAMPLES:
sage: x = QQ['x'].0
sage: f = 2*x^2 + x^3 + 56*x^5
sage: f.monic()
x^5 + 1/56*x^3 + 1/28*x^2
sage: f = (1/4)*x^2 + 3*x + 1
sage: f.monic()
x^2 + 12*x + 4
The following happens because $f = 0$ cannot be made into a monic polynomial
sage: f = 0*x
sage: f.monic()
Traceback (most recent call last):
...
ZeroDivisionError: rational division by zero
Notice that the monic version of a polynomial over the
integers is defined over the rationals.
sage: x = ZZ['x'].0
sage: f = 3*x^19 + x^2 - 37
sage: g = f.monic(); g
x^19 + 1/3*x^2 - 37/3
sage: g.parent()
Univariate Polynomial Ring in x over Rational Field
AUTHORS:
-- Naqi Jaffery (2006-01-24): examples
|
File: sage/rings/polynomial/polynomial_element.pyx (starting at line 3654)
Return the string variable name of the indeterminate of this polynomial.
EXAMPLES:
sage: R.<theta> = ZZ[];
sage: f = (2-theta)^3; f
-theta^3 + 6*theta^2 - 12*theta + 8
sage: f.name()
'theta'
|
File: sage/rings/polynomial/polynomial_element.pyx (starting at line 2541)
Return a list of n iterative approximations to a root of this
polynomial, computed using the Newton-Raphson method.
The Newton-Raphson method is an iterative root-finding algorithm.
For f(x) a polynomial, as is the case here, this is essentially
the same as Horner's method.
INPUT:
n -- an integer (=the number of iterations),
x0 -- an initial guess x0.
OUTPUT:
A list of numbers hopefully approximating a root of f(x)=0.
** If one of the iterates is a critical point of f then
a ZeroDivisionError exception is raised.
EXAMPLES:
sage: x = PolynomialRing(RealField(), 'x').gen()
sage: f = x^2 - 2
sage: f.newton_raphson(4, 1)
[1.50000000000000, 1.41666666666667, 1.41421568627451, 1.41421356237469]
AUTHORS: David Joyner and William Stein (2005-11-28)
|
File: sage/rings/polynomial/polynomial_element.pyx (starting at line 2605)
Return the $p$-adic slopes of the Newton polygon of self,
when this makes sense.
OUTPUT:
-- list of rational numbers
EXAMPLES:
sage: x = QQ['x'].0
sage: f = x^3 + 2
sage: f.newton_slopes(2)
[1/3, 1/3, 1/3]
ALGORITHM: Uses PARI.
|
File: sage/rings/polynomial/polynomial_element.pyx (starting at line 3858)
Return the $p$-norm of this polynomial.
DEFINITION: For integer $p$, the $p$-norm of a polynomial is
the $p$th root of the sum of the $p$th powers of the absolute
values of the coefficients of the polynomial.
INPUT:
p -- (positive integer or +infinity) the degree of
the norm
EXAMPLES:
sage: R.<x> =RR[]
sage: f = x^6 + x^2 + -x^4 - 2*x^3
sage: f.norm(2)
2.64575131106459
sage: (sqrt(1^2 + 1^2 + (-1)^2 + (-2)^2)).n()
2.64575131106459
sage: f.norm(1)
5.00000000000000
sage: f.norm(infinity)
2.00000000000000
sage: f.norm(-1)
Traceback (most recent call last):
...
ValueError: The degree of the norm must be positive
TESTS:
sage: R.<x> = RR[]
sage: f = x^6 + x^2 + -x^4 -x^3
sage: f.norm(int(2))
2.00000000000000
AUTHOR:
-- didier deshommes
-- William Stein: fix bugs, add definition, etc.
|
File: sage/rings/polynomial/polynomial_element.pyx (starting at line 3642)
This is the same as the valuation of self at p. See the documentation for
\code{self.valuation}.
EXAMPLES:
sage: P,x=PolynomialRing(ZZ,'x').objgen()
sage: (x^2+x).ord(x+1)
1
|
File: sage/rings/polynomial/polynomial_element.pyx (starting at line 2487)
Return list of coefficients of self up to (but not include $q^n$).
Includes 0's in the list on the right so that the list has
length $n$.
INPUT:
n -- (default: None); if given, an integer that is at least 0
EXAMPLES:
sage: x = polygen(QQ)
sage: f = 1 + x^3 + 23*x^5
sage: f.padded_list()
[1, 0, 0, 1, 0, 23]
sage: f.padded_list(10)
[1, 0, 0, 1, 0, 23, 0, 0, 0, 0]
sage: len(f.padded_list(10))
10
sage: f.padded_list(3)
[1, 0, 0]
sage: f.padded_list(0)
[]
sage: f.padded_list(-1)
Traceback (most recent call last):
...
ValueError: n must be at least 0
|
File: sage/rings/polynomial/polynomial_element.pyx (starting at line 212)
Return a plot of this polynomial.
INPUT:
xmin -- float
xmax -- float
*args, **kwds -- passed to either point or point
OUTPUT:
returns a graphic object.
EXAMPLES:
sage: x = polygen(GF(389))
sage: plot(x^2 + 1, rgbcolor=(0,0,1)).save()
sage: x = polygen(QQ)
sage: plot(x^2 + 1, rgbcolor=(1,0,0)).save()
|
File: sage/rings/polynomial/polynomial_element.pyx (starting at line 2578)
Return a new polynomial in the parent of self.
This function doesn't have much to do with self except that it
is a convenient shortcut to avoid having to write
\code{self.parent()(...)}.
INPUT:
*args, **kwds -- are passed on exactly as is to the parent
polynomial ring call method.
EXAMPLES:
sage: R.<x> = ZZ[]
sage: f = 2*x^2 - 3
sage: f.polynomial([12,5,7,3])
3*x^3 + 7*x^2 + 5*x + 12
The input list must of course define a polynomial in the parent:
sage: f.polynomial([12,5,7,3/2])
Traceback (most recent call last):
...
TypeError: no coercion of this rational to integer
|
File: sage/rings/polynomial/polynomial_element.pyx (starting at line 2472)
Return the precision of this polynomials. This is
always infinity, since polynomials are of infinite
precision by definition (there is no big-oh).
EXAMPLES:
sage: x = polygen(ZZ)
sage: (x^5 + x + 1).prec()
+Infinity
sage: x.prec()
+Infinity
|
File: sage/rings/polynomial/polynomial_element.pyx (starting at line 3843)
Returns the radical of self; over a field, this is the product of the
distinct irreducible factors of self. (This is also sometimes called the
"square-free part" of self, but that term is ambiguous; it is sometimes used
to mean the quotient of self by its maximal square factor.)
EXAMPLES:
sage: P.<x> = ZZ[]
sage: t = (x^2-x+1)^3 * (3*x-1)^2
sage: t.radical()
3*x^3 - 4*x^2 + 4*x - 1
|
File: sage/rings/polynomial/polynomial_element.pyx (starting at line 3475)
Return the real roots of this polynomial, without multiplicities.
Calls self.roots(ring=RR), unless this is a polynomial
with floating-point real coefficients, in which case it
calls self.roots().
EXAMPLES:
sage: x = polygen(ZZ)
sage: (x^2 - x - 1).real_roots()
[-0.618033988749895, 1.61803398874989]
TESTS:
sage: x = polygen(RealField(100))
sage: (x^2 - x - 1).real_roots()[0].parent()
Real Field with 100 bits of precision
sage: x = polygen(RDF)
sage: (x^2 - x - 1).real_roots()[0].parent()
Real Double Field
|
File: sage/rings/polynomial/polynomial_element.pyx (starting at line 2792)
Returns the resultant of self and other.
INPUT:
other -- a polynomial
OUTPUT:
an element of the base ring of the polynomial ring
NOTES:
Implemented using PARI's \code{polresultant} function.
EXAMPLES:
sage: R.<x> = QQ[]
sage: f = x^3 + x + 1; g = x^3 - x - 1
sage: r = f.resultant(g); r
-8
sage: r.parent() is QQ
True
We can also compute resultants over univariate and
multivariate polynomial rings, provided that PARI's variable
ordering requirements are respected. Usually, your resultants
will work if you always ask for them in the variable \code{x}:
sage: R.<a> = QQ[]
sage: S.<x> = R[]
sage: f = x^2 + a; g = x^3 + a
sage: r = f.resultant(g); r
a^3 + a^2
sage: r.parent() is R
True
sage: R.<a, b> = QQ[]
sage: S.<x> = R[]
sage: f = x^2 + a; g = x^3 + b
sage: r = f.resultant(g); r
a^3 + b^2
sage: r.parent() is R
True
Unfortunately SAGE does not handle PARI's variable ordering requirements
gracefully, so the following fails:
sage: R.<x, y> = QQ[]
sage: S.<a> = R[]
sage: f = x^2 + a; g = y^3 + a
sage: f.resultant(g)
Traceback (most recent call last):
...
PariError: (8)
|
File: sage/rings/polynomial/polynomial_element.pyx (starting at line 2930)
Return polynomial but with the coefficients reversed.
EXAMPLES:
sage: R.<x> = ZZ[]; S.<y> = R[]
sage: f = y^3 + x*y -3*x; f
y^3 + x*y - 3*x
sage: f.reverse()
(-3*x)*y^3 + x*y^2 + 1
|
File: sage/rings/polynomial/polynomial_element.pyx (starting at line 2161)
Return the field generated by the roots of the irreducible
polynomial self. The output is either a number field, relative
number field, a quotient of a polynomial ring over a field, or
the fraction field of the base ring.
EXAMPLES:
sage: R.<x> = QQ['x']
sage: f = x^3 + x + 17
sage: f.root_field('a')
Number Field in a with defining polynomial x^3 + x + 17
sage: R.<x> = QQ['x']
sage: f = x - 3
sage: f.root_field('b')
Rational Field
sage: R.<x> = ZZ['x']
sage: f = x^3 + x + 17
sage: f.root_field('b')
Number Field in b with defining polynomial x^3 + x + 17
sage: y = QQ['x'].0
sage: L.<a> = NumberField(y^3-2)
sage: R.<x> = L['x']
sage: f = x^3 + x + 17
sage: f.root_field('c')
Number Field in c with defining polynomial x^3 + x + 17 over its base field
sage: R.<x> = PolynomialRing(GF(9,'a'))
sage: f = x^3 + x^2 + 8
sage: K.<alpha> = f.root_field(); K
Univariate Quotient Polynomial Ring in alpha over Finite Field in a of size 3^2 with modulus x^3 + x^2 + 2
sage: alpha^2 + 1
alpha^2 + 1
sage: alpha^3 + alpha^2
1
sage: R.<x> = QQ[]
sage: f = x^2
sage: K.<alpha> = f.root_field()
Traceback (most recent call last):
...
ValueError: polynomial must be irreducible
TESTS:
sage: (PolynomialRing(Integers(31),name='x').0+5).root_field('a')
Ring of integers modulo 31
|
File: sage/rings/polynomial/polynomial_element.pyx (starting at line 2945)
Return the roots of this polynomial (by default, in the
base ring of this polynomial).
INPUT:
ring -- the ring to find roots in
multiplicities -- bool (default: True)
if True return list of pairs (r, n), where r is
the root and n is the multiplicity.
If False, just return the unique roots, with
no information about multiplicities.
algorithm -- the root-finding algorithm to use.
We attempt to select a reasonable algorithm by
default, but this lets the caller override our choice.
By default, this finds all the roots that lie in the base ring
of the polynomial. However, the ring parameter can be used
to specify a ring to look for roots in.
If the polynomial and the output ring are both exact (integers,
rationals, finite fields, etc.), then the output should always
be correct (or raise an exception, if that case is not yet
handled).
If the output ring is approximate (floating-point real or complex
numbers), then the answer will be estimated numerically, using
floating-point arithmetic of at least the precision of the output
ring. If the polynomial is ill-conditioned, meaning that a
small change in the coefficients of the polynomial will lead to a
relatively large change in the location of the roots, this may
give poor results. Distinct roots may be returned as multiple
roots, multiple roots may be returned as distinct roots, real
roots may be lost entirely (because the numerical estimate
thinks they are complex roots). Note that polynomials with
multiple roots are always ill-conditioned; there's a footnote
at the end of the docstring about this.
If the output ring is a RealIntervalField or
ComplexIntervalField of a given precision, then the answer
will always be correct (or an exception will be raised, if a
case is not implemented). Each root will be contained in one
of the returned intervals, and the intervals will be disjoint.
(The returned intervals may be of higher precision than the
specified output ring.)
At the end of this docstring (after the examples) is a description
of all the cases implemented in this function, and the algorithms
used. That section also describes the possibilities for
"algorithm=", for the cases where multiple algorithms exist.
EXAMPLES:
sage: x = QQ['x'].0
sage: f = x^3 - 1
sage: f.roots()
[(1, 1)]
sage: f.roots(ring=CC) # note -- low order bits slightly different on ppc.
[(1.00000000000000, 1), (-0.500000000000000 + 0.86602540378443...*I, 1), (-0.500000000000000 - 0.86602540378443...*I, 1)]
sage: f = (x^3 - 1)^2
sage: f.roots()
[(1, 2)]
sage: f = -19*x + 884736
sage: f.roots()
[(884736/19, 1)]
sage: (f^20).roots()
[(884736/19, 20)]
sage: K.<z> = CyclotomicField(3)
sage: f = K.defining_polynomial()
sage: f.roots(ring=GF(7))
[(4, 1), (2, 1)]
sage: g = f.change_ring(GF(7))
sage: g.roots()
[(4, 1), (2, 1)]
sage: g.roots(multiplicities=False)
[4, 2]
An example over RR, which illustrates that only the roots in RR
are returned:
sage: x = RR['x'].0
sage: f = x^3 -2
sage: f.roots()
[(1.25992104989487, 1)]
sage: f.factor()
(1.00000000000000*x - 1.25992104989487) * (1.00000000000000*x^2 + 1.25992104989487*x + 1.58740105196820)
sage: x = RealField(100)['x'].0
sage: f = x^3 -2
sage: f.roots()
[(1.2599210498948731647672106073, 1)]
sage: x = CC['x'].0
sage: f = x^3 -2
sage: f.roots()
[(1.25992104989487, 1), (-0.62996052494743... + 1.09112363597172*I, 1), (-0.62996052494743... - 1.09112363597172*I, 1)]
sage: f.roots(algorithm='pari')
[(1.25992104989487, 1), (-0.629960524947437 + 1.09112363597172*I, 1), (-0.629960524947437 - 1.09112363597172*I, 1)]
Another example showing that only roots in the base ring
are returned:
sage: x = polygen(ZZ)
sage: f = (2*x-3) * (x-1) * (x+1)
sage: f.roots()
[(1, 1), (-1, 1)]
sage: f.roots(ring=QQ)
[(3/2, 1), (1, 1), (-1, 1)]
An example involving large numbers:
sage: x = RR['x'].0
sage: f = x^2 - 1e100
sage: f.roots()
[(-1.00000000000000e50, 1), (1.00000000000000e50, 1)]
sage: f = x^10 - 2*(5*x-1)^2
sage: f.roots(multiplicities=False)
[-1.6772670339941..., 0.19995479628..., 0.20004530611..., 1.5763035161844...]
sage: x = CC['x'].0
sage: i = CC.0
sage: f = (x - 1)*(x - i)
sage: f.roots(multiplicities=False) #random - this example is numerically rather unstable
[2.22044604925031e-16 + 1.00000000000000*I, 1.00000000000000 + 8.32667268468867e-17*I]
sage: g=(x-1.33+1.33*i)*(x-2.66-2.66*i)
sage: g.roots(multiplicities=False)
[2.66000000000000 + 2.66000000000000*I, 1.33000000000000 - 1.33000000000000*I]
A purely symbolic roots example:
sage: X = var('X')
sage: f = expand((X-1)*(X-I)^3*(X^2 - sqrt(2))); f
X^6 - 3*I*X^5 - X^5 + 3*I*X^4 - sqrt(2)*X^4 - 3*X^4 + 3*sqrt(2)*I*X^3 + I*X^3 + sqrt(2)*X^3 + 3*X^3 - 3*sqrt(2)*I*X^2 - I*X^2 + 3*sqrt(2)*X^2 - sqrt(2)*I*X - 3*sqrt(2)*X + sqrt(2)*I
sage: print f.roots()
[(I, 3), (-2^(1/4), 1), (2^(1/4), 1), (1, 1)]
A couple of examples where the base ring doesn't have a
factorization algorithm (yet). Note that this is currently
done via naive enumeration, so could be very slow:
sage: R = Integers(6)
sage: S.<x> = R['x']
sage: p = x^2-1
sage: p.roots()
Traceback (most recent call last):
...
NotImplementedError: root finding with multiplicities for this polynomial not implemented (try the multiplicities=False option)
sage: p.roots(multiplicities=False)
[1, 5]
sage: R = Integers(9)
sage: A = PolynomialRing(R, 'y')
sage: y = A.gen()
sage: f = 10*y^2 - y^3 - 9
sage: f.roots(multiplicities=False)
[0, 1, 3, 6]
An example over the complex double field (where root finding
is fast, thanks to numpy):
sage: R.<x> = CDF[]
sage: f = R.cyclotomic_polynomial(5); f
1.0*x^4 + 1.0*x^3 + 1.0*x^2 + 1.0*x + 1.0
sage: f.roots(multiplicities=False) # slightly random
[0.309016994375 + 0.951056516295*I, 0.309016994375 - 0.951056516295*I, -0.809016994375 + 0.587785252292*I, -0.809016994375 - 0.587785252292*I]
sage: [z^5 for z in f.roots(multiplicities=False)] # slightly random
[1.0 - 2.44929359829e-16*I, 1.0 + 2.44929359829e-16*I, 1.0 - 4.89858719659e-16*I, 1.0 + 4.89858719659e-16*I]
sage: f = CDF['x']([1,2,3,4]); f
4.0*x^3 + 3.0*x^2 + 2.0*x + 1.0
sage: r = f.roots(multiplicities=False)
sage: [f(a) for a in r] # slightly random
[2.55351295664e-15, -4.4408920985e-16 - 2.08166817117e-16*I, -4.4408920985e-16 + 2.08166817117e-16*I]
Another example over RDF:
sage: x = RDF['x'].0
sage: ((x^3 -1)).roots()
[(1.0, 1)]
sage: ((x^3 -1)).roots(multiplicities=False)
[1.0]
Another examples involving the complex double field:
sage: x = CDF['x'].0
sage: i = CDF.0
sage: f = x^3 + 2*i; f
1.0*x^3 + 2.0*I
sage: f.roots() # random low-order bits
[(-1.09112363597 - 0.629960524947*I, 1), (6.66133814775e-16 + 1.25992104989*I, 1), (1.09112363597 - 0.629960524947*I, 1)]
sage: f.roots(multiplicities=False) # random low-order bits
[-1.09112363597 - 0.629960524947*I, 6.66133814775e-16 + 1.25992104989*I, 1.09112363597 - 0.629960524947*I]
sage: [f(z) for z in f.roots(multiplicities=False)] # random low-order bits
[-3.10862446895e-15 - 4.4408920985e-16*I, -3.17226455498e-15 + 3.99680288865e-15*I, -5.55111512313e-16 - 8.881784197e-16*I]
sage: f = i*x^3 + 2; f
1.0*I*x^3 + 2.0
sage: f.roots() # random low-order bits
[(-1.09112363597 + 0.629960524947*I, 1), (6.66133814775e-16 - 1.25992104989*I, 1), (1.09112363597 + 0.629960524947*I, 1)]
sage: f(f.roots()[0][0]) # random low-order bits
-4.4408920985e-16 - 3.10862446895e-15*I
Examples using real root isolation:
sage: x = polygen(ZZ)
sage: f = x^2 - x - 1
sage: f.roots()
[]
sage: f.roots(ring=RIF)
[([-0.618033988749894848204586834365642 .. -0.618033988749894848204586834365629], 1), ([1.61803398874989484820458683436561 .. 1.61803398874989484820458683436565], 1)]
sage: f.roots(ring=RIF, multiplicities=False)
[[-0.618033988749894848204586834365642 .. -0.618033988749894848204586834365629], [1.61803398874989484820458683436561 .. 1.61803398874989484820458683436565]]
sage: f.roots(ring=RealIntervalField(150))
[([-0.61803398874989484820458683436563811772030917980576286213544862277 .. -0.61803398874989484820458683436563811772030917980576286213544862260], 1), ([1.6180339887498948482045868343656381177203091798057628621354486226 .. 1.6180339887498948482045868343656381177203091798057628621354486230], 1)]
sage: f.roots(ring=AA)
[([-0.61803398874989491 .. -0.61803398874989479], 1), ([1.6180339887498946 .. 1.6180339887498950], 1)]
sage: f = f^2 * (x - 1)
sage: f.roots(ring=RIF)
[([-0.618033988749894848204586834365642 .. -0.618033988749894848204586834365629], 2), ([0.999999999999999999999999999999987 .. 1.00000000000000000000000000000003], 1), ([1.61803398874989484820458683436561 .. 1.61803398874989484820458683436565], 2)]
sage: f.roots(ring=RIF, multiplicities=False)
[[-0.618033988749894848204586834365642 .. -0.618033988749894848204586834365629], [0.999999999999999999999999999999987 .. 1.00000000000000000000000000000003], [1.61803398874989484820458683436561 .. 1.61803398874989484820458683436565]]
Examples using complex root isolation:
sage: x = polygen(ZZ)
sage: p = x^5 - x - 1
sage: p.roots()
[]
sage: p.roots(ring=CIF)
[([1.1673039782614185 .. 1.16730397826141...], 1), ([0.18123244446987518 .. 0.18123244446987558] + [1.0839541013177103 .. 1.0839541013177110]*I, 1), ([0.181232444469875... .. 0.1812324444698755...] - [1.083954101317710... .. 1.0839541013177110]*I, 1), ([-0.76488443360058489 .. -0.76488443360058455] + [0.35247154603172609 .. 0.3524715460317264...]*I, 1), ([-0.76488443360058489 .. -0.76488443360058455] - [0.35247154603172609 .. 0.35247154603172643]*I, 1)]
sage: p.roots(ring=ComplexIntervalField(200))
[([1.1673039782614186842560458998548421807205603715254890391400816 .. 1.1673039782614186842560458998548421807205603715254890391400829], 1), ([0.18123244446987538390180023778112063996871646618462304743773153 .. 0.18123244446987538390180023778112063996871646618462304743773341] + [1.0839541013177106684303444929807665742736402431551156543011306 .. 1.0839541013177106684303444929807665742736402431551156543011344]*I, 1), ([0.18123244446987538390180023778112063996871646618462304743773153 .. 0.18123244446987538390180023778112063996871646618462304743773341] - [1.0839541013177106684303444929807665742736402431551156543011306 .. 1.0839541013177106684303444929807665742736402431551156543011344]*I, 1), ([-0.76488443360058472602982318770854173032899665194736756700777... .. -0.76488443360058472602982318770854173032899665194736756700777...] + [0.35247154603172624931794709140258105439420648082424733283769... .. 0.35247154603172624931794709140258105439420648082424733283769...]*I, 1), ([-0.76488443360058472602982318770854173032899665194736756700777454 .. -0.764884433600584726029823187708541730328996651947367567007772...] - [0.35247154603172624931794709140258105439420648082424733283769... .. 0.352471546031726249317947091402581054394206480824247332837693...]*I, 1)]
sage: rts = p.roots(ring=QQbar); rts
[([1.1673039782614185 .. 1.1673039782614188], 1), ([0.18123244446987538 .. 0.18123244446987541] + [1.0839541013177105 .. 1.0839541013177108]*I, 1), ([0.18123244446987538 .. 0.18123244446987541] - [1.0839541013177105 .. 1.0839541013177108]*I, 1), ([-0.76488443360058478 .. -0.76488443360058466] + [0.35247154603172620 .. 0.35247154603172626]*I, 1), ([-0.76488443360058478 .. -0.76488443360058466] - [0.35247154603172620 .. 0.35247154603172626]*I, 1)]
sage: p.roots(ring=AA)
[([1.1673039782614185 .. 1.1673039782614188], 1)]
sage: p = (x - rts[1][0])^2 * (3*x^2 + x + 1)
sage: p.roots(ring=QQbar)
[([-0.16666666666666669 .. -0.16666666666666665] + [0.55277079839256659 .. 0.55277079839256671]*I, 1), ([-0.16666666666666669 .. -0.16666666666666665] - [0.55277079839256659 .. 0.55277079839256671]*I, 1), ([0.18123244446987538 .. 0.18123244446987541] + [1.0839541013177105 .. 1.0839541013177108]*I, 2)]
sage: p.roots(ring=CIF)
[([-0.16666666666666672 .. -0.16666666666666662] + [0.55277079839256648 .. 0.55277079839256671]*I, 1), ([-0.16666666666666672 .. -0.16666666666666662] - [0.55277079839256648 .. 0.55277079839256671]*I, 1), ([0.18123244446987538 .. 0.18123244446987541] + [1.0839541013177105 .. 1.0839541013177108]*I, 2)]
Note that coefficients in a number field with defining polynomial
$x^2 + 1$ are considered to be Gaussian rationals (with the generator
mapping to +I), if you ask for complex roots.
sage: K.<im> = NumberField(x^2 + 1)
sage: y = polygen(K)
sage: p = y^4 - 2 - im
sage: p.roots(ring=CC)
[(-1.2146389322441... - 0.14142505258239...*I, 1), (-0.14142505258239... + 1.2146389322441...*I, 1), (0.14142505258239... - 1.2146389322441...*I, 1), (1.2146389322441... + 0.14142505258239...*I, 1)]
sage: p = p^2 * (y^2 - 2)
sage: p.roots(ring=CIF)
[([-1.41421356237309... .. -1.41421356237309...], 1), ([1.41421356237309... .. 1.41421356237309...], 1), ([-1.214638932244182... .. -1.21463893224418...] - [0.1414250525823937... .. 0.1414250525823939...]*I, 2), ([-0.141425052582393... .. -0.1414250525823937...] + [1.21463893224418... .. 1.214638932244182...]*I, 2), ([0.141425052582393... .. 0.141425052582393...] - [1.21463893224418... .. 1.21463893224418...]*I, 2), ([1.21463893224418... .. 1.21463893224418...] + [0.141425052582393... .. 0.141425052582393...]*I, 2)]
There are many combinations of floating-point input and output
types that work. (Note that some of them are quite pointless...
there's no reason to use high-precision input and output, and still
use numpy to find the roots.)
sage: rflds = (RR, RDF, RealField(100))
sage: cflds = (CC, CDF, ComplexField(100))
sage: def cross(a, b):
... return list(cartesian_product_iterator([a, b]))
sage: flds = cross(rflds, rflds) + cross(rflds, cflds) + cross(cflds, cflds)
sage: for (fld_in, fld_out) in flds:
... x = polygen(fld_in)
... f = x^3 - fld_in(2)
... x2 = polygen(fld_out)
... f2 = x2^3 - fld_out(2)
... for algo in (None, 'pari', 'numpy'):
... rts = f.roots(ring=fld_out, multiplicities=False)
... if fld_in == fld_out and algo is None:
... print fld_in, rts
... for rt in rts:
... assert(abs(f2(rt)) <= 1e-10)
... assert(rt.parent() == fld_out)
Real Field with 53 bits of precision [1.25992104989487]
Real Double Field [1.25992104989]
Real Field with 100 bits of precision [1.2599210498948731647672106073]
Complex Field with 53 bits of precision [1.25992104989487, -0.62996052494743... + 1.09112363597172*I, -0.62996052494743... - 1.09112363597172*I]
Complex Double Field [1.25992104989, -0.62996052494... + 1.09112363597*I, -0.62996052494... - 1.09112363597*I]
Complex Field with 100 bits of precision [1.2599210498948731647672106073, -0.62996052494743658238360530364 + 1.0911236359717214035600726142*I, -0.62996052494743658238360530364 - 1.0911236359717214035600726142*I]
Note that we can find the roots of a polynomial with
algebraic coefficients:
sage: rt2 = sqrt(AA(2))
sage: rt3 = sqrt(AA(3))
sage: x = polygen(AA)
sage: f = (x - rt2) * (x - rt3); f
x^2 + [-3.1462643699419726 .. -3.1462643699419721]*x + [2.4494897427831778 .. 2.4494897427831784]
sage: rts = f.roots(); rts
[([1.4142135623730949 .. 1.4142135623730952], 1), ([1.7320508075688771 .. 1.7320508075688775], 1)]
sage: rts[0][0] == rt2
True
sage: f.roots(ring=RealIntervalField(150))
[([1.4142135623730950488016887242096980785696718753769480731766797377 .. 1.4142135623730950488016887242096980785696718753769480731766797381], 1), ([1.7320508075688772935274463415058723669428052538103806280558069793 .. 1.7320508075688772935274463415058723669428052538103806280558069797], 1)]
Algorithms used:
For brevity, we will use RR to mean any RealField of any
precision; similarly for RIF, CC, and CIF. Since Sage has no
specific implementation of Gaussian rationals (or of number
fields with embedding, at all), when we refer to Gaussian
rationals below we will accept any number field with defining
polynomial $x^2+1$, mapping the field generator to +I.
We call the base ring of the polynomial K, and the ring given
by the ring= argument L. (If ring= is not specified, then L
is the same as K.)
If K and L are floating-point (RDF, CDF, RR, or CC), then
a floating-point root-finder is used. If L has precision
53 bits or less (RDF and CDF both have precision exactly
53 bits, as do the default RR=RealField() and CC=ComplexField())
then we default to using numpy's roots(); otherwise, we use
Pari's polroots(). This choice can be overridden with
algorithm='pari' or algorithm='numpy'.
If L is AA or RIF, and K is ZZ, QQ, or AA, then the root isolation
algorithm sage.rings.polynomial.real_roots.real_roots() is used.
(You can call real_roots() directly to get more control than
this method gives.)
If L is QQbar or CIF, and K is ZZ, QQ, AA, QQbar, or the
Gaussian rationals, then the root isolation algorithm
sage.rings.polynomial.complex_roots.complex_roots() is used.
(You can call complex_roots() directly to get more control
than this method gives.)
If L is AA and K is QQbar or the Gaussian rationals, then
complex_roots() is used (as above) to find roots in QQbar,
then these roots are filtered to select only the real roots.
If L is floating-point and K is not, then we attempt to change
the polynomial ring to L (using .change_ring()) (or, if L is
complex and K is not, to the corresponding real field). Then
we use either Pari or numpy as specified above.
For all other cases where K is different than L, we just use
.change_ring(L) and proceed as below.
The next method, which is used if K is an integral domain, is
to attempt to factor the polynomial. If this succeeds, then
for every degree-one factor a*x+b, we add -b/a as a root (as
long as this quotient is actually in the desired ring).
If factoring over K is not implemented (or K is not an
integral domain), and K is finite, then we find the roots by
enumerating all elements of K and checking whether the
polynomial evaluates to zero at that value.
NOTE: We mentioned above that polynomials with multiple roots
are always ill-conditioned; if your input is given to n bits
of precision, you should not expect more than n/k good bits
for a k-fold root. (You can get solutions that make the
polynomial evaluate to a number very close to zero; basically
the problem is that with a multiple root, there are many such
numbers, and it's difficult to choose between them.)
To see why this is true, consider the naive floating-point
error analysis model where you just pretend that all
floating-point numbers are somewhat imprecise -- a little "fuzzy",
if you will. Then the graph of a floating-point polynomial
will be a fuzzy line. Consider the graph of $(x-1)^3$; this
will be a fuzzy line with a horizontal tangent at $x=1$,
$y=0$. If the fuzziness extends up and down by about j, then
it will extend left and right by about cube_root(j).
|
File: sage/rings/polynomial/polynomial_element.pyx (starting at line 3757)
Returns this polynomial multiplied by the power $x^n$. If $n$ is negative,
terms below $x^n$ will be discarded. Does not change this polynomial (since
polynomials are immutable).
EXAMPLES:
sage: R.<x> = PolynomialRing(PolynomialRing(QQ,'w'),'x')
sage: p = x^2 + 2*x + 4
sage: p.shift(0)
x^2 + 2*x + 4
sage: p.shift(-1)
x + 2
sage: p.shift(-5)
0
sage: p.shift(2)
x^4 + 2*x^3 + 4*x^2
One can also use the infix shift operator:
sage: f = x^3 + x
sage: f >> 2
x
sage: f << 2
x^5 + x^3
AUTHOR:
-- David Harvey (2006-08-06)
-- Robert Bradshaw (2007-04-18) Added support for infix operator.
|
File: sage/rings/polynomial/polynomial_element.pyx (starting at line 856)
Returns the square of this polynomial.
TODO:
-- This is just a placeholder; for now it just uses ordinary
multiplication. But generally speaking, squaring is faster than
ordinary multiplication, and it's frequently used, so subclasses
may choose to provide a specialised squaring routine.
-- Perhaps this even belongs at a lower level? ring_element
or something?
AUTHOR:
-- David Harvey (2006-09-09)
EXAMPLES:
sage: R.<x> = QQ[]
sage: f = x^3 + 1
sage: f.square()
x^6 + 2*x^3 + 1
sage: f*f
x^6 + 2*x^3 + 1
|
File: sage/rings/polynomial/polynomial_element.pyx (starting at line 882)
Return the square-free decomposition of self. This is
a partial factorization of self into square-free, relatively
prime polynomials.
This is the straightforward algorithm, using only polynomial
GCD and polynomial division. Faster algorithms exist. The
algorithm comes from the Wikipedia article,
"Square-free polynomial".
EXAMPLES:
sage: x = polygen(QQ)
sage: p = 37 * (x-1)^3 * (x-2)^3 * (x-1/3)^7 * (x-3/7)
sage: p.squarefree_decomposition()
(37*x - 111/7) * (x^2 - 3*x + 2)^3 * (x - 1/3)^7
sage: p = 37 * (x-2/3)^2
sage: p.squarefree_decomposition()
(37) * (x - 2/3)^2
|
File: sage/rings/polynomial/polynomial_element.pyx (starting at line 285)
Identical to self(*x).
See the docstring for \code{self.__call__}.
EXAMPLES:
sage: R.<x> = QQ[]
sage: f = x^3 + x - 3
sage: f.subs(x=5)
127
sage: f.subs(5)
127
sage: f.subs({x:2})
7
sage: f.subs({})
x^3 + x - 3
sage: f.subs({'x':2})
Traceback (most recent call last):
...
TypeError: keys do not match self's parent
|
File: sage/rings/polynomial/polynomial_element.pyx (starting at line 285)
Identical to self(*x).
See the docstring for \code{self.__call__}.
EXAMPLES:
sage: R.<x> = QQ[]
sage: f = x^3 + x - 3
sage: f.subs(x=5)
127
sage: f.subs(5)
127
sage: f.subs({x:2})
7
sage: f.subs({})
x^3 + x - 3
sage: f.subs({'x':2})
Traceback (most recent call last):
...
TypeError: keys do not match self's parent
|
File: sage/rings/polynomial/polynomial_element.pyx (starting at line 3804)
Returns the polynomial of degree $ < n$ which is equivalent to self
modulo $x^n$.
EXAMPLES:
sage: R.<x> = ZZ[]; S.<y> = R[]
sage: f = y^3 + x*y -3*x; f
y^3 + x*y - 3*x
sage: f.truncate(2)
x*y - 3*x
sage: f.truncate(1)
-3*x
sage: f.truncate(0)
0
|
File: sage/rings/polynomial/polynomial_element.pyx (starting at line 3593)
If $f = a_r x^r + a_{r+1}x^{r+1} + \cdots$, with $a_r$ nonzero,
then the valuation of $f$ is $r$. The valuation of the zero
polynomial is $\infty$.
If a prime (or non-prime) $p$ is given, then the valuation is
the largest power of $p$ which divides self.
The valuation at $\infty$ is -self.degree().
EXAMPLES:
sage: P,x=PolynomialRing(ZZ,'x').objgen()
sage: (x^2+x).valuation()
1
sage: (x^2+x).valuation(x+1)
1
sage: (x^2+1).valuation()
0
sage: (x^3+1).valuation(infinity)
-3
sage: P(0).valuation()
+Infinity
|
File: sage/rings/polynomial/polynomial_element.pyx (starting at line 3544)
Return name of variable used in this polynomial as a string.
OUTPUT:
string
EXAMPLES:
sage: R.<t> = QQ[]
sage: f = t^3 + 3/2*t + 5
sage: f.variable_name()
't'
|
File: sage/rings/polynomial/polynomial_element.pyx (starting at line 3559)
Returns the list of variables occuring in this polynomial.
EXAMPLES:
sage: R.<x> = QQ[]
sage: x.variables()
(x,)
A constant polynomial has no variables.
sage: R(2).variables()
()
|
| Home | Trees | Indices | Help |
|---|
| Generated by Epydoc 3.0beta1 on Thu Jul 17 04:23:57 2008 | http://epydoc.sourceforge.net |