help links subscribe changes refresh edit

	FrontPage
ExampleFreeAbelianGroup ←	↑	→ ExampleIntegration

ExampleGroebner

Edit detail for ExampleGroebner revision 4 of 8

	1 2 3 4 5 6 7 8
Editor: hemmecke Time: 2014/12/03 11:59:06 GMT+0
Note:

changed:
-    Find a m and n (depending on the coefficients of p and q
    Find a m and n (depending on the coefficients of p and q)

Application of Groebner Bases

Problem

Let

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

Find a m and n (depending on the coefficients of p and q) such that for the transformaton

it holds

Setup of the problem

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

fricas

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

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

(1)

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

fricas

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

$\label{eq2}\left[ x , \: y , \: a , \: b , \: c \right]$

(2)

Type: List(OrderedVariableList?([x,y,a,b,c]))

fricas

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

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

(3)

Type: Matrix(Polynomial(Integer))

fricas

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

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

(4)

Type: Matrix(Integer)

fricas

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

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

(5)

Type: Matrix(Polynomial(Integer))

fricas

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

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

(6)

Type: Matrix(Polynomial(Integer))

fricas

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

$\label{eq7}\left[ \begin{array}{ccc} 1 & y &{{y}^{2}}$

(7)

Type: Matrix(Polynomial(Integer))

fricas

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

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

(8)

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{eq9}\left[ \begin{array}{ccc} {{{n}^{2}}- n +{c \ d}}&{{2 \ m \ n}- m +{b \ d}}&{{{m}^{2}}+{a \ d}}$

(9)

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{eq10}\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]$

(10)

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{eq11}\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]$

(11)

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{eq12}\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}}$

(12)

Type: Matrix(Polynomial(Integer))