login  home  contents  what's new  discussion  bug reports     help  links  subscribe  changes  refresh  edit

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
y = m x + n 
it holds
p(x) = d q(m x + n). 

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))