help links subscribe changes refresh edit

	FrontPage
ExampleFreeAbelianGroup ←	↑	→ ExampleIntegration

ExampleGroebner

Edit detail for ExampleGroebner revision 6 of 8

	1 2 3 4 5 6 7 8
Editor: hemmecke Time: 2014/12/03 16:49:21 GMT+0
Note:

added:
    ((Unfortunately, the axiom-wiki does not properly show the result,
    so we have added a semicolon to suppress the output.))


changed:
-solve(ecoeffs, [d,n,m])
solve(ecoeffs, [d,n,m]);

Application of Groebner Bases

Problem

Let

$p(x) = - x^2 + x, \qquad q(y) = a y^2 + b y + c.$

Find d, m, n (depending on the coefficients a,b,c of q) such that for the transformaton

it holds

Setup of the problem

fricas

Z==>Integer; Q==>Fraction Z

Type: Void

fricas

CP==>DistributedMultivariatePolynomial([a,b,c], Q)

Type: Void

fricas

CF==>Fraction CP

Type: Void

fricas

P==>DistributedMultivariatePolynomial([d,n,m], CF)

Type: Void

fricas

PX==>UnivariatePolynomial('x, P)

Type: Void

fricas

p(x:PX):PX == x*(1-x)

   Function declaration p : UnivariatePolynomial(x,
      DistributedMultivariatePolynomial([d,n,m],Fraction(
      DistributedMultivariatePolynomial([a,b,c],Fraction(Integer)))))
       -> UnivariatePolynomial(x,DistributedMultivariatePolynomial([d,n
      ,m],Fraction(DistributedMultivariatePolynomial([a,b,c],Fraction(
      Integer))))) has been added to workspace.

Type: Void

fricas

q(y:PX):PX == a*y^2+b*y+c

   Function declaration q : UnivariatePolynomial(x,
      DistributedMultivariatePolynomial([d,n,m],Fraction(
      DistributedMultivariatePolynomial([a,b,c],Fraction(Integer)))))
       -> UnivariatePolynomial(x,DistributedMultivariatePolynomial([d,n
      ,m],Fraction(DistributedMultivariatePolynomial([a,b,c],Fraction(
      Integer))))) has been added to workspace.

Type: Void

fricas

y:PX := m*x+n

$\label{eq1}{m \ x}+ n$

(1)

Type: UnivariatePolynomial?(x,DistributedMultivariatePolynomial?([d,n,m],Fraction(DistributedMultivariatePolynomial?([a,b,c],Fraction(Integer)))))

fricas

r:PX := p(x) - d*q(y)

fricas

Compiling function p with type UnivariatePolynomial(x,
      DistributedMultivariatePolynomial([d,n,m],Fraction(
      DistributedMultivariatePolynomial([a,b,c],Fraction(Integer)))))
       -> UnivariatePolynomial(x,DistributedMultivariatePolynomial([d,n
      ,m],Fraction(DistributedMultivariatePolynomial([a,b,c],Fraction(
      Integer)))))

fricas

Compiling function q with type UnivariatePolynomial(x,
      DistributedMultivariatePolynomial([d,n,m],Fraction(
      DistributedMultivariatePolynomial([a,b,c],Fraction(Integer)))))
       -> UnivariatePolynomial(x,DistributedMultivariatePolynomial([d,n
      ,m],Fraction(DistributedMultivariatePolynomial([a,b,c],Fraction(
      Integer)))))

$\label{eq2}\begin{array}{@{}l} \displaystyle {{\left(-{a \ d \ {{m}^{2}}}- 1 \right)}\ {{x}^{2}}}+{{\left(-{2 \ a \ d \ n \ m}-{b \ d \ m}+ 1 \right)}\ x}-{a \ d \ {{n}^{2}}}- \ \ \displaystyle {b \ d \ n}-{c \ d}$

(2)

Type: UnivariatePolynomial?(x,DistributedMultivariatePolynomial?([d,n,m],Fraction(DistributedMultivariatePolynomial?([a,b,c],Fraction(Integer)))))

Compute the solution

We must first extract the coefficients, since each coefficient of any power of a must vanish if the polynomial r is identically 0.

fricas

coeffs := coefficients r

$\label{eq3}\begin{array}{@{}l} \displaystyle \left[{-{a \ d \ {{m}^{2}}}- 1}, \:{-{2 \ a \ d \ n \ m}-{b \ d \ m}+ 1}, \: \right. \ \ \displaystyle \left.{-{a \ d \ {{n}^{2}}}-{b \ d \ n}-{c \ d}}\right]$

(3)

Type: List(DistributedMultivariatePolynomial?([d,n,m],Fraction(DistributedMultivariatePolynomial?([a,b,c],Fraction(Integer)))))

Now we compute a Groebner basis and then solve for the respective variables.

fricas

gb := groebner coeffs

$\label{eq4}\left[{d -{{{1 \over 4}\ a}\over{{a \ c}-{{1 \over 4}\ {{b}^{2}}}}}}, \:{n +{{1 \over 2}\ m}+{{{1 \over 2}\ b}\over a}}, \:{{{m}^{2}}+{{{4 \ a \ c}-{{b}^{2}}}\over{{a}^{2}}}}\right]$

(4)

Type: List(DistributedMultivariatePolynomial?([d,n,m],Fraction(DistributedMultivariatePolynomial?([a,b,c],Fraction(Integer)))))

fricas

egb: List Equation Fraction Polynomial Q := [p=0 for p in gb]

$\label{eq5}\begin{array}{@{}l} \displaystyle \left[{{{{{\left({a \ c}-{{1 \over 4}\ {{b}^{2}}}\right)}\ d}-{{1 \over 4}\ a}}\over{{a \ c}-{{1 \over 4}\ {{b}^{2}}}}}= 0}, \:{{{{a \ n}+{{1 \over 2}\ a \ m}+{{1 \over 2}\ b}}\over a}= 0}, \: \right. \ \ \displaystyle \left.{{{{{{a}^{2}}\ {{m}^{2}}}+{4 \ a \ c}-{{b}^{2}}}\over{{a}^{2}}}= 0}\right]$

(5)

Type: List(Equation(Fraction(Polynomial(Fraction(Integer)))))

fricas

solve(egb, [d,m,n])

$\label{eq6}\left[{\left[{d ={{{1 \over 4}\ a}\over{{a \ c}-{{1 \over 4}\ {{b}^{2}}}}}}, \:{m ={{-{2 \ a \ n}- b}\over a}}, \:{{{a \ {{n}^{2}}}+{b \ n}+ c}= 0}\right]}\right]$

(6)

Type: List(List(Equation(Fraction(Polynomial(Fraction(Integer))))))

In fact, solve is powerful enough so that it is unnecessary to call the Buchberger algorithm explicitly.

fricas

ecoeffs: List Equation Fraction Polynomial Q := [p=0 for p in coeffs]

$\label{eq7}\begin{array}{@{}l} \displaystyle \left[{{-{a \ d \ {{m}^{2}}}- 1}= 0}, \:{{-{2 \ a \ d \ m \ n}-{b \ d \ m}+ 1}= 0}, \: \right. \ \ \displaystyle \left.{{-{a \ d \ {{n}^{2}}}-{b \ d \ n}-{c \ d}}= 0}\right]$

(7)

Type: List(Equation(Fraction(Polynomial(Fraction(Integer)))))

fricas

solve(ecoeffs, [d,m,n])

$\label{eq8}\left[{\left[{d ={{{1 \over 4}\ a}\over{{a \ c}-{{1 \over 4}\ {{b}^{2}}}}}}, \:{m ={{-{2 \ a \ n}- b}\over a}}, \:{{{a \ {{n}^{2}}}+{b \ n}+ c}= 0}\right]}\right]$

(8)

Type: List(List(Equation(Fraction(Polynomial(Fraction(Integer))))))

Of course, the result depends on the order of the variables given to the solve command.

((Unfortunately, the axiom-wiki does not properly show the result, so we have added a semicolon to suppress the output.))

fricas

solve(ecoeffs, [d,n,m]);

Type: List(List(Equation(Fraction(Polynomial(Fraction(Integer))))))

===============================================================

Example code --rrogers, Tue, 02 Dec 2014 23:49:41 +0000 reply

fricas

---- Ordered  variable lists.
Poly_to_Gauss:=[d,n,m]

$\label{eq9}\left[ d , \: n , \: m \right]$

(9)

Type: List(OrderedVariableList?([d,n,m]))

fricas

Gauss_to_Poly:=[x,y,a,b,c]

$\label{eq10}\left[ x , \:{{m \ x}+ n}, \: a , \: b , \: c \right]$

(10)

Type: List(UnivariatePolynomial?(x,DistributedMultivariatePolynomial?([d,n,m],Fraction(DistributedMultivariatePolynomial?([a,b,c],Fraction(Integer))))))

fricas

----coefficient arrays.
corg :=  d* matrix [[c,b,a]]

$\label{eq11}\left[ \begin{array}{ccc} {c \ d}&{b \ d}&{a \ d}$

(11)

Type: Matrix(Polynomial(Integer))

fricas

---- Explicit target
cgauss := matrix [[0, 1, -1]]

$\label{eq12}\left[ \begin{array}{ccc} 0 & 1 & - 1$

(12)

Type: Matrix(Integer)

fricas

---- Generalized target
ctar := matrix [[w,v,u]]

$\label{eq13}\left[ \begin{array}{ccc} w & v & u$

(13)

Type: Matrix(Polynomial(Integer))

fricas

---- polynomial basis arrays.
xorg := matrix ([[1, x, x^2]])

$\label{eq14}\left[ \begin{array}{ccc} 1 & x &{{x}^{2}}$

(14)

Type: Matrix(Polynomial(Integer))

fricas

xgauss := matrix([[1,y,y^2]])

$\label{eq15}\left[ \begin{array}{ccc} 1 &{{m \ x}+ n}&{{{{m}^{2}}\ {{x}^{2}}}+{2 \ n \ m \ x}+{{n}^{2}}}$

(15)

Type: Matrix(UnivariatePolynomial?(x,DistributedMultivariatePolynomial?([d,n,m],Fraction(DistributedMultivariatePolynomial?([a,b,c],Fraction(Integer))))))

fricas

---- Example
row(corg * transpose(xorg),1)

$\label{eq16}\left[{{a \ d \ {{x}^{2}}}+{b \ d \ x}+{c \ d}}\right]$

(16)

Type: Vector(Polynomial(Integer))

fricas

----  Translation matrix Pascal Pa(n) for 3x3 case
----  see Aceto below for references.
Pa(n) == matrix [[1,0,0],[n,1,0],[n^2, 2*n,1]]

Type: Void

fricas

---- Scalar matrix
Sc(m) == diagonalMatrix [1,m,m^2]

Type: Void

fricas

---- Now define transform in matrix form
D := corg -(cgauss * Pa(n) * Sc(m))

fricas

Compiling function Pa with type Variable(n) -> Matrix(Polynomial(
      Integer))

fricas

Compiling function Sc with type Variable(m) -> Matrix(Polynomial(
      Integer))

$\label{eq17}\left[ \begin{array}{ccc} {{{n}^{2}}- n +{c \ d}}&{{2 \ m \ n}- m +{b \ d}}&{{{m}^{2}}+{a \ d}}$

(17)

Type: Matrix(Polynomial(Integer))

fricas

---- Now we do a more realistic solve in two steps
---- Step one disallow silly answers
E:=groebnerFactorize(row(D,1),[b*d,m,a,b^2-3*a*c],true)

   we found a groebner basis and check whether it
   contains reducible polynomials
   [1]
   factorGroebnerBasis: no reducible polynomials in this basis
   we found a groebner basis and check whether it
   contains reducible polynomials
     2
   [n  - n + c d, 2m n - m + b d, 2b d n + (- 4c d + 1)m - b d, 2a n - b m - a,
     2                 2
    m  + a d, (4a c - b )d - a]
   factorGroebnerBasis: no reducible polynomials in this basis

$\label{eq18}\begin{array}{@{}l} \displaystyle \left[{ \begin{array}{@{}l} \displaystyle \left[{{{n}^{2}}- n +{c \ d}}, \:{{2 \ m \ n}- m +{b \ d}}, \: \right. \ \ \displaystyle \left.{{2 \ b \ d \ n}+{{\left(-{4 \ c \ d}+ 1 \right)}\ m}-{b \ d}}, \:{{2 \ a \ n}-{b \ m}- a}, \:{{{m}^{2}}+{a \ d}}, \: \right. \ \ \displaystyle \left.{{{\left({4 \ a \ c}-{{b}^{2}}\right)}\ d}- a}\right]$

(18)

Type: List(List(Polynomial(Integer)))

fricas

----  and clean it up (a lot).  I wish these two steps could be one!
solve(E.1,Poly_to_Gauss)

$\label{eq19}\left[{\left[{d ={a \over{{4 \ a \ c}-{{b}^{2}}}}}, \:{n ={{{b \ m}+ a}\over{2 \ a}}}, \:{{{{\left({4 \ a \ c}-{{b}^{2}}\right)}\ {{m}^{2}}}+{{a}^{2}}}= 0}\right]}\right]$

(19)

Type: List(List(Equation(Fraction(Polynomial(Integer)))))

fricas

---- Now lets test the reasonableness the width to start with is
---- 2*sqrt(b^2-4*a*c)/(2*a)  which the left hand term yields.  There is a sign ambiguity
---- corresponding to whether the source quadratic is to the left or right.
---- I could swap n,m in solve() but then the n term (left hand one) is more obscure
---- Knowing the width m we can compute moving the center to 1/2 (for x*(1-x))
---- It should amount to -b/(2*a)+1/2 
---- and in fact that is the answer n= m(scale factor)*(b/2a)+1/2
---- d is required and in English is a "normalizing factor"

----General formulation
Dorg := corg -(ctar * Pa(n) * Sc(m))

$\label{eq20}\left[ \begin{array}{ccc} {- w -{n \ v}-{{{n}^{2}}\ u}+{c \ d}}&{-{m \ v}-{2 \ m \ n \ u}+{b \ d}}&{-{{{m}^{2}}\ u}+{a \ d}}$

(20)

Type: Matrix(Polynomial(Integer))