6.3 operations with polynomials and rational expressions

6.3.1 var

var(rat)

:: Main variable (indeterminate) of rat.

return

indeterminate

rat

rational expression

• See Types in Asir for main variable.
• Indeterminates (variables) are ordered by default as follows.

  x, y, z, u, v, w, p, q, r, s, t, a, b, c, d, e, f, g, h, i, j, k, l, m, n, o. The other variables will be ordered after the above noted variables so that the first comer will be ordered prior to the followers.

[0] var(x^2+y^2+a^2);
x
[1] var(a*b*c*d*e);
a
[2] var(3/abc+2*xy/efg);
abc

References

ord, vars.

6.3.2 vars

vars(obj)

:: A list of variables (indeterminates) in an expression obj.

return

list

obj

arbitrary

• Returns a list of variables (indeterminates) contained in a given expression.
• Lists variables according to the variable ordering.

[0] vars(x^2+y^2+a^2);
[x,y,a]
[1] vars(3/abc+2*xy/efg);
[abc,xy,efg]
[2] vars([x,y,z]);
[x,y,z]

References

var, uc, ord.

6.3.3 uc

uc()

:: Create a new indeterminate for an undetermined coefficient.

return

indeterminate with its vtype 1.

• At every evaluation of command uc(), a new indeterminate in the sequence of indeterminates _0, _1, _2, … is created successively.
• Indeterminates created by uc() cannot be input on the keyboard. By this property, you are free, no matter how many indeterminates you will create dynamically by a program, from collision of created names with indeterminates input from the keyboard or from program files.
• Functions, rtostr() and strtov(), are used to create ordinary indeterminates (indeterminates having 0 for their vtype).
• Kernel sub-type of indeterminates created by uc() is 1. (vtype(uc())=1)

[0] A=uc();
_0
[1] B=uc();
_1
[2] (uc()+uc())^2;
_2^2+2*_3*_2+_3^2
[3] (A+B)^2;
_0^2+2*_1*_0+_1^2

References

vtype, rtostr, strtov.

6.3.4 coef

coef(poly,deg[,var])

:: The coefficient of a polynomial poly at degree deg with respect to the variable var (main variable if unspecified).

return

polynomial

poly

polynomial

var

indeterminate

deg

non-negative integer

• The coefficient of a polynomial poly at degree deg with respect to the variable var.
• The default value for var is the main variable, i.e., var(poly).
• For multi-variate polynomials, access to coefficients depends on the specified indeterminates. For example, taking coef for the main variable is much faster than for other variables.

[0] A = (x+y+z)^3;
x^3+(3*y+3*z)*x^2+(3*y^2+6*z*y+3*z^2)*x+y^3+3*z*y^2+3*z^2*y+z^3
[1] coef(A,1,y);
3*x^2+6*z*x+3*z^2
[2] coef(A,0);
y^3+3*z*y^2+3*z^2*y+z^3

References

var, deg, mindeg.

6.3.5 deg, mindeg

deg(poly,var)

:: The degree of a polynomial poly with respect to variable.

mindeg(poly,var)

:: The least exponent of the terms with non-zero coefficients in a polynomial poly with respect to the variable var. In this manual, this quantity is sometimes referred to the minimum degree of a polynomial for short.

return

non-negative integer

poly

polynomial

var

indeterminate

• The least exponent of the terms with non-zero coefficients in a polynomial poly with respect to the variable var. In this manual, this quantity is sometimes referred to the minimum degree of a polynomial for short.
• Variable var must be specified.

[0] deg((x+y+z)^10,x);
10
[1] deg((x+y+z)^10,w);
0
[75] mindeg(x^2+3*x*y,x);
1

6.3.6 nmono

nmono(rat)

:: Number of monomials in rational expression rat.

return

non-negative integer

rat

rational expression

• Number of monomials with non-zero number coefficients in the full expanded form of the given polynomial.
• For a rational expression, the sum of the numbers of monomials of the numerator and denominator.
• A function form is regarded as a single indeterminate no matter how complex arguments it has.

[0] nmono((x+y)^10);
11
[1] nmono((x+y)^10/(x+z)^10);
22
[2] nmono(sin((x+y)^10));
1

References

vtype.

6.3.7 ord

ord([varlist])

:: It sets the ordering of indeterminates (variables).

return

list of indeterminates

varlist

list of indeterminates

• When an argument is given, this function rearranges the ordering of variables (indeterminates) so that the indeterminates in the argument varlist precede and the other indeterminates follow in the system’s variable ordering. Regardless of the existence of an argument, it always returns the final variable ordering.
• Note that no change will be made to the variable ordering of internal forms of objects which already exists in the system, no matter what reordering you specify. Therefore, the reordering should be limited to the time just after starting Asir, or to the time when one has decided himself to start a totally new computation which has no relation with the previous results. Note that unexpected results may be obtained from operations between objects which are created under different variable ordering.

[0] ord();
[x,y,z,u,v,w,p,q,r,s,t,a,b,c,d,e,f,g,h,i,j,k,l,m,n,o,_x,_y,_z,_u,_v,
_w,_p,_q,_r,_s,_t,_a,_b,_c,_d,_e,_f,_g,_h,_i,_j,_k,_l,_m,_n,_o,
exp(_x),(_x)^(_y),log(_x),(_x)^(_y-1),cos(_x),sin(_x),tan(_x),
(-_x^2+1)^(-1/2),cosh(_x),sinh(_x),tanh(_x),
(_x^2+1)^(-1/2),(_x^2-1)^(-1/2)]
[1] ord([dx,dy,dz,a,b,c]);
[dx,dy,dz,a,b,c,x,y,z,u,v,w,p,q,r,s,t,d,e,f,g,h,i,j,k,l,m,n,o,_x,_y,
_z,_u,_v,_w,_p,_q,_r,_s,_t,_a,_b,_c,_d,_e,_f,_g,_h,_i,_j,_k,_l,_m,_n,
_o,exp(_x),(_x)^(_y),log(_x),(_x)^(_y-1),cos(_x),sin(_x),tan(_x),
(-_x^2+1)^(-1/2),cosh(_x),sinh(_x),tanh(_x),
(_x^2+1)^(-1/2),(_x^2-1)^(-1/2)]

6.3.8 sdiv, sdivm, srem, sremm, sqr, sqrm

sdiv(poly1,poly2[,v])

sdivm(poly1,poly2,mod[,v])

:: Quotient of poly1 divided by poly2 provided that the division can be performed within polynomial arithmetic over the rationals.

srem(poly1,poly2[,v])

sremm(poly1,poly2,mod[,v])

:: Remainder of poly1 divided by poly2 provided that the division can be performed within polynomial arithmetic over the rationals.

sqr(poly1,poly2[,v])

sqrm(poly1,poly2,mod[,v])

:: Quotient and remainder of poly1 divided by poly2 provided that the division can be performed within polynomial arithmetic over the rationals.

return

sdiv(), sdivm(), srem(), sremm() : polynomial sqr(), sqrm() : a list [quotient,remainder]

poly1 poly2

polynomial

v

indeterminate

mod

prime

• Regarding poly1 as an uni-variate polynomial in the main variable of poly2, i.e. var(poly2) (v if specified), sdiv() and srem() compute the polynomial quotient and remainder of poly1 divided by poly2.
• sdivm(), sremm(), sqrm() execute the same operation over GF(mod).
• Division operation of polynomials is performed by the following steps: (1) obtain the quotient of leading coefficients; let it be Q; (2) remove the leading term of poly1 by subtracting, from poly1, the product of Q with some powers of main variable and poly2; obtain a new poly1; (3) repeat the above step until the degree of poly1 become smaller than that of poly2. For fulfillment, by operating in polynomials, of this procedure, the divisions at step (1) in every repetition must be an exact division of polynomials. This is the true meaning of what we say “division can be performed within polynomial arithmetic over the rationals.”
• There are typical cases where the division is possible: leading coefficient of poly2 is a rational number; poly2 is a factor of poly1.
• Use sqr() to get both the quotient and remainder at once.
• Use idiv(), irem() for integer quotient.
• For remainder operation on all integer coefficients, use %.

[0] sdiv((x+y+z)^3,x^2+y+a);    
x+3*y+3*z
[1] srem((x+y+z)^2,x^2+y+a);
(2*y+2*z)*x+y^2+(2*z-1)*y+z^2-a
[2] X=(x+y+z)*(x-y-z)^2;
x^3+(-y-z)*x^2+(-y^2-2*z*y-z^2)*x+y^3+3*z*y^2+3*z^2*y+z^3
[3] Y=(x+y+z)^2*(x-y-z);  
x^3+(y+z)*x^2+(-y^2-2*z*y-z^2)*x-y^3-3*z*y^2-3*z^2*y-z^3
[4] G=gcd(X,Y);
x^2-y^2-2*z*y-z^2
[5] sqr(X,G);
[x-y-z,0]
[6] sqr(Y,G);
[x+y+z,0]
[7] sdiv(y*x^3+x+1,y*x+1);  
divsp: cannot happen
return to toplevel

References

idiv, irem, %.

6.3.9 tdiv

tdiv(poly1,poly2)

:: Tests whether poly2 divides poly1.

return

Quotient if poly2 divides poly1, 0 otherwise.

poly1 poly2

polynomial

• Tests whether poly2 divides poly1 in polynomial ring.
• One application of this function: Consider the case where a polynomial is certainly an irreducible factor of the other polynomial, but the multiplicity of the factor is unknown. Application of tdiv() to the polynomials repeatedly yields the multiplicity.

[11] Y=(x+y+z)^5*(x-y-z)^3;  
x^8+(2*y+2*z)*x^7+(-2*y^2-4*z*y-2*z^2)*x^6
+(-6*y^3-18*z*y^2-18*z^2*y-6*z^3)*x^5
+(6*y^5+30*z*y^4+60*z^2*y^3+60*z^3*y^2+30*z^4*y+6*z^5)*x^3
+(2*y^6+12*z*y^5+30*z^2*y^4+40*z^3*y^3+30*z^4*y^2+12*z^5*y+2*z^6)*x^2
+(-2*y^7-14*z*y^6-42*z^2*y^5-70*z^3*y^4-70*z^4*y^3-42*z^5*y^2
-14*z^6*y-2*z^7)*x-y^8-8*z*y^7-28*z^2*y^6-56*z^3*y^5-70*z^4*y^4
-56*z^5*y^3-28*z^6*y^2-8*z^7*y-z^8
[12] for(I=0,F=x+y+z,T=Y; T=tdiv(T,F); I++); 
[13] I;
5

References

sdiv, sdivm, srem, sremm, sqr, sqrm.

6.3.10 %

poly % m

:: integer remainder to all integer coefficients of the polynomial.

return

integer or polynomial

poly

integer or polynomial with integer coefficients

m

integer

• Returns a polynomial whose coefficients are remainders of the coefficients of the input polynomial divided by m.
• The resulting coefficients are all normalized to non-negative integers.
• An integer is allowed for poly. This can be used for an alternative for irem() except that the result is normalized to a non-negative integer.
• Coefficients of poly and m must all be integers, though the type checking is not done.

[0] (x+2)^5 % 3;
x^5+x^4+x^3+2*x^2+2*x+2
[1] (x-2)^5 % 3;
x^5+2*x^4+x^3+x^2+2*x+1
[2] (-5) % 4;
3
[3] irem(-5,4);
-1

References

idiv, irem.

6.3.11 subst, psubst

subst(rat[,varn,ratn]*)

psubst(rat[,var,rat]*)

:: Substitute ratn for varn in expression rat. (n=1,2,…. Substitution will be done successively from left to right if arguments are repeated.)

return

rational expression

rat ratn

rational expression

varn

indeterminate

• Substitutes rational expressions for specified kernels in a rational expression.
• subst(r,v1,r1,v2,r2,…) has the same effect as subst(subst(r,v1,r1),v2,r2,…).
• Note that repeated substitution is done from left to right successively. You may get different result by changing the specification order.
• Ordinary subst() performs substitution at all levels of a scalar algebraic expression creeping into arguments of function forms recursively. Function psubst() regards such a function form as an independent indeterminate, and does not attempt to apply substitution to its arguments. (The name comes after Partial SUBSTitution.)
• Since Asir does not reduce common divisors of a rational expression automatically, substitution of a rational expression to an expression may cause unexpected increase of computation time. Thus, it is often necessary to write a special function to meet the individual problem so that the denominator and the numerator do not become too large.
• The same applies to substitution by rational numbers.

[0] subst(x^3-3*y*x^2+3*y^2*x-y^3,y,2);
x^3-6*x^2+12*x-8
[1] subst(@@,x,-1);
-27
[2] subst(x^3-3*y*x^2+3*y^2*x-y^3,y,2,x,-1);
-27
[3] subst(x*y^3,x,y,y,x);  
x^4
[4] subst(x*y^3,y,x,x,y);    
y^4
[5] subst(x*y^3,x,t,y,x,t,y);
y*x^3
[6] subst(x*sin(x),x,t);
sint(t)*t
[7] psubst(x*sin(x),x,t);
sin(x)*t

6.3.12 diff

diff(rat[,varn]*)

diff(rat,varlist)

:: Differentiate rat successively by var’s for the first form, or by variables in varlist for the second form.

return

expression

rat

rational expression which contains elementary functions.

varn

indeterminate

varlist

list of indeterminates

• Differentiate rat successively by var’s for the first form, or by variables in varlist for the second form.
• differentiation is performed by the specified indeterminates (variables) from left to right. diff(rat,x,y) is the same as diff(diff(rat,x),y).

[0] diff((x+2*y)^2,x);  
2*x+4*y
[1] diff((x+2*y)^2,x,y);
4
[2] diff(x/sin(log(x)+1),x);
(sin(log(x)+1)-cos(log(x)+1))/(sin(log(x)+1)^2)
[3] diff(sin(x),[x,x,x,x]);
sin(x)

6.3.13 ediff

ediff(poly[,varn]*)

ediff(poly,varlist)

:: Differentiate poly successively by Euler operators of var’s for the first form, or by Euler operators of variables in varlist for the second form.

return

polynomial

poly

polynomial

varn

indeterminate

varlist

list of indeterminates

• differentiation is performed by the specified indeterminates (variables) from left to right. ediff(poly,x,y) is the same as ediff(ediff(poly,x),y).

[0] ediff((x+2*y)^2,x);  
2*x^2+4*y*x
[1] ediff((x+2*y)^2,x,y);
4*y*x

6.3.14 res

res(var,poly1,poly2[,mod])

:: Resultant of poly1 and poly2 with respect to var.

return

polynomial

var

indeterminate

poly1 poly2

polynomial

mod

prime

• Resultant of two polynomials poly1 and poly2 with respect to var.
• Sub-resultant algorithm is used to compute the resultant.
• The computation is done over GF(mod) if mod is specified.

[0] res(t,(t^3+1)*x+1,(t^3+1)*y+t);
-x^3-x^2-y^3

6.3.15 fctr, sqfr

fctr(poly)

:: Factorize polynomial poly over the rationals.

sqfr(poly)

:: Gets a square-free factorization of polynomial poly.

return

list

poly

polynomial with rational coefficients

• Factorizes polynomial poly over the rationals. fctr() for irreducible factorization; sqfr() for square-free factorization.
• The result is represented by a list, whose elements are a pair represented as

  [[num,1],[factor,multiplicity],...].

• Products of all factor^multiplicity and num is equal to poly.
• The number num is determined so that (poly/num) is an integral polynomial and its content (GCD of all coefficients) is 1. (See section ptozp.)

[0] fctr(x^10-1);
[[1,1],[x-1,1],[x+1,1],[x^4+x^3+x^2+x+1,1],[x^4-x^3+x^2-x+1,1]]
[1] fctr(x^3+y^3+(z/3)^3-x*y*z);
[[1/27,1],[9*x^2+(-9*y-3*z)*x+9*y^2-3*z*y+z^2,1],[3*x+3*y+z,1]]
[2] A=(a+b+c+d)^2;
a^2+(2*b+2*c+2*d)*a+b^2+(2*c+2*d)*b+c^2+2*d*c+d^2
[3] fctr(A);
[[1,1],[a+b+c+d,2]]
[4] A=(x+1)*(x^2-y^2)^2; 
x^5+x^4-2*y^2*x^3-2*y^2*x^2+y^4*x+y^4
[5] sqfr(A);
[[1,1],[x+1,1],[-x^2+y^2,2]]
[6] fctr(A);
[[1,1],[x+1,1],[-x-y,2],[x-y,2]]

References

ufctrhint.

6.3.16 ufctrhint

ufctrhint(poly,hint)

:: Factorizes uni-variate polynomial poly over the rational number field when the degrees of its factors are known to be some integer multiples of hint.

return

list

poly

uni-variate polynomial with rational coefficients

hint

non-negative integer

• By any reason, if the degree of all the irreducible factors of poly is known to be some multiples of hint, factors can be computed more efficiently by the knowledge than fctr().
• When hint is 1, ufctrhint() is the same as fctr() for uni-variate polynomials. An typical application where ufctrhint() is effective: Consider the case where poly is a norm (Algebraic numbers) of a certain polynomial over an extension field with its extension degree d, and it is square free; Then, every irreducible factor has a degree that is a multiple of d.

[10] A=t^9-15*t^6-87*t^3-125;               
t^9-15*t^6-87*t^3-125
0msec
[11] N=res(t,subst(A,t,x-2*t),A);           
-x^81+1215*x^78-567405*x^75+139519665*x^72-19360343142*x^69
+1720634125410*x^66-88249977024390*x^63-4856095669551930*x^60
+1999385245240571421*x^57-15579689952590251515*x^54
+15956967531741971462865*x^51
...
+140395588720353973535526123612661444550659875*x^6
+10122324287343155430042768923500799484375*x^3
+139262743444407310133459021182733314453125
980msec + gc : 250msec
[12] sqfr(N);
[[-1,1],[x^81-1215*x^78+567405*x^75-139519665*x^72+19360343142*x^69
-1720634125410*x^66+88249977024390*x^63+4856095669551930*x^60
-1999385245240571421*x^57+15579689952590251515*x^54
...
-10122324287343155430042768923500799484375*x^3
-139262743444407310133459021182733314453125,1]]
20msec
[13] fctr(N);                               
[[-1,1],[x^9-405*x^6-63423*x^3-2460375,1],
[x^18-486*x^15+98739*x^12-9316620*x^9+945468531*x^6-12368049246*x^3
+296607516309,1],[x^18-8667*x^12+19842651*x^6+19683,1],
[x^18-324*x^15+44469*x^12-1180980*x^9+427455711*x^6+2793253896*x^3
+31524548679,1],
[x^18+10773*x^12+2784051*x^6+307546875,1]]
167.050sec + gc : 1.890sec
[14] ufctrhint(N,9);
[[-1,1],[x^9-405*x^6-63423*x^3-2460375,1],
[x^18-486*x^15+98739*x^12-9316620*x^9+945468531*x^6-12368049246*x^3
+296607516309,1],[x^18-8667*x^12+19842651*x^6+19683,1],
[x^18-324*x^15+44469*x^12-1180980*x^9+427455711*x^6+2793253896*x^3
+31524548679,1],
[x^18+10773*x^12+2784051*x^6+307546875,1]]
119.340sec + gc : 1.300sec

References

fctr, sqfr.

6.3.17 modfctr

modfctr(poly,mod)

:: Factorizer over small finite fields

return

list

poly

Polynomial with integer coefficients

mod

non-negative integer

• This function factorizes a polynomial poly over the finite prime field of characteristic mod, where mod must be smaller than 2^29.
• The result is represented by a list, whose elements are a pair represented as

  [[num,1],[factor,multiplicity],...].

• Products of all factor^multiplicity and num is equal to poly.
• To factorize polynomials over large finite fields, use fctr_ff (see section Finite fields,fctr_ff).

[0] modfctr(x^10+x^2+1,2147483647);
[[1,1],[x+1513477736,1],[x+2055628767,1],[x+91854880,1],
[x+634005911,1],[x+1513477735,1],[x+634005912,1],
[x^4+1759639395*x^2+2045307031,1]]
[1] modfctr(2*x^6+(y^2+z*y)*x^4+2*z*y^3*x^2+(2*z^2*y^2+z^3*y)*x+z^4,3);
[[2,1],[2*x^3+z*y*x+z^2,1],[2*x^3+y^2*x+2*z^2,1]]

References

fctr, sqfr.

6.3.18 ptozp

ptozp(poly)

:: Converts a polynomial poly with rational coefficients into an integral polynomial such that GCD of all its coefficients is 1.

return

polynomial

poly

polynomial

• Converts the given polynomial by multiplying some rational number into an integral polynomial such that GCD of all its coefficients is 1.
• In general, operations on polynomials can be performed faster for integer coefficients than for rational number coefficients. Therefore, this function is conveniently used to improve efficiency.
• Function red does not convert rational coefficients of the numerator. You cannot obtain an integral polynomial by direct use of the function nm(). The function nm() returns the numerator of its argument, and a polynomial with rational coefficients is the numerator of itself and will be returned as it is.
• When the option factor is set, the return value is a list [g,c]. Here, c is a rational number, g is an integral polynomial and poly = c*g holds.

[0] ptozp(2*x+5/3);
6*x+5
[1] nm(2*x+5/3);   
2*x+5/3

References

nm, dn.

6.3.19 prim, cont

prim(poly[,v])

:: Primitive part of poly.

cont(poly[,v])

:: Content of poly.

return poly

polynomial over the rationals

v

indeterminate

• The primitive part and the content of a polynomial poly with respect to its main variable (v if specified).

[0] E=(y-z)*(x+y)*(x-z)*(2*x-y);
(2*y-2*z)*x^3+(y^2-3*z*y+2*z^2)*x^2+(-y^3+z^2*y)*x+z*y^3-z^2*y^2
[1] prim(E);
2*x^3+(y-2*z)*x^2+(-y^2-z*y)*x+z*y^2
[2] cont(E);
y-z
[3] prim(E,z);
(y-z)*x-z*y+z^2

References

var, ord.

6.3.20 gcd, gcdz

gcd(poly1,poly2[,mod])

gcdz(poly1,poly2)

:: The polynomial greatest common divisor of poly1 and poly2.

return

polynomial

poly1 poly2

polynomial

mod

prime

• Functions gcd() and gcdz() return the greatest common divisor (GCD) of the given two polynomials.
• Function gcd() returns an integral polynomial GCD over the rational number field. The coefficients are normalized such that their GCD is 1. It returns 1 in case that the given polynomials are mutually prime.
• Function gcdz() works for arguments of integral polynomials, and returns a polynomial GCD over the integer ring, that is, it returns gcd() multiplied by the contents of all coefficients of the two input polynomials.
• gcd() computes the GCD over GF(mod) if mod is specified.
• Polynomial GCD is computed by an improved algorithm based on Extended Zassenhaus algorithm.
• GCD over a finite field is computed by PRS algorithm and it may not be efficient for large inputs and co-prime inputs.

[0] gcd(12*(x^2+2*x+1)^2,18*(x^2+(y+1)*x+y)^3);
x^3+3*x^2+3*x+1
[1] gcdz(12*(x^2+2*x+1)^2,18*(x^2+(y+1)*x+y)^3);
6*x^3+18*x^2+18*x+6
[2] gcd((x+y)*(x-y)^2,(x+y)^2*(x-y));
x^2-y^2
[3] gcd((x+y)*(x-y)^2,(x+y)^2*(x-y),2);
x^3+y*x^2+y^2*x+y^3

References

igcd,igcdcntl.

6.3.21 red

red(rat)

:: Reduced form of rat by canceling common divisors.

return

rational expression

rat

rational expression

• Asir automatically performs cancellation of common divisors of rational numb ers. But, without an explicit command, it does not cancel common polynomial divisors of rational expressions. (Reduction of rational expressions to a common denominator will be always done.) Use command red() to perform this cancellation.
• Cancel the common divisors of the numerator and the denominator of a rational expression rat by computing their GCD.
• The denominator polynomial of the result is an integral polynomial which has no common divisors in its coefficients, while the numerator may have rational coefficients.
• Since GCD computation is a very hard operation, it is desirable to detect and remove by any means common divisors as far as possible. Furthermore, a call to this function after swelling of the denominator and the numerator shall usually take a very long time. Therefore, often, to some extent, reduction of common divisors is inevitable for operations of rational expressions.

[0] (x^3-1)/(x-1);
(x^3-1)/(x-1)
[1] red((x^3-1)/(x-1));
x^2+x+1
[2] red((x^3+y^3+z^3-3*x*y*z)/(x+y+z));
x^2+(-y-z)*x+y^2-z*y+z^2
[3] red((3*x*y)/(12*x^2+21*y^3*x));
(y)/(4*x+7*y^3)
[4] red((3/4*x^2+5/6*x)/(2*y*x+4/3*x));
(9/8*x+5/4)/(3*y+2)

References

nm, dn, gcd, gcdz, ptozp.

This document was generated on December 22, 2024 using texi2html 5.0.