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

## Application of Groebner Bases

### Problem

Let 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], Z)
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],Integer)))) ->
UnivariatePolynomial(x,DistributedMultivariatePolynomial([d,n,m],
Fraction(DistributedMultivariatePolynomial([a,b,c],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],Integer)))) ->
UnivariatePolynomial(x,DistributedMultivariatePolynomial([d,n,m],
Fraction(DistributedMultivariatePolynomial([a,b,c],Integer))))
has been added to workspace.
Type: Void
fricas
y:PX := m*x+n (1)
Type: UnivariatePolynomial(x,DistributedMultivariatePolynomial?([d,n,m],Fraction(DistributedMultivariatePolynomial?([a,b,c],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],Integer)))) ->
UnivariatePolynomial(x,DistributedMultivariatePolynomial([d,n,m],
Fraction(DistributedMultivariatePolynomial([a,b,c],Integer))))
fricas
Compiling function q with type UnivariatePolynomial(x,
DistributedMultivariatePolynomial([d,n,m],Fraction(
DistributedMultivariatePolynomial([a,b,c],Integer)))) ->
UnivariatePolynomial(x,DistributedMultivariatePolynomial([d,n,m],
Fraction(DistributedMultivariatePolynomial([a,b,c],Integer)))) (2)
Type: UnivariatePolynomial(x,DistributedMultivariatePolynomial?([d,n,m],Fraction(DistributedMultivariatePolynomial?([a,b,c],Integer))))

## Compute the solution

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

fricas
coeffs := coefficients r (3)
Type: List(DistributedMultivariatePolynomial?([d,n,m],Fraction(DistributedMultivariatePolynomial?([a,b,c],Integer))))

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

fricas
gb := groebner coeffs (4)
Type: List(DistributedMultivariatePolynomial?([d,n,m],Fraction(DistributedMultivariatePolynomial?([a,b,c],Integer))))
fricas
egb: List Equation Fraction Polynomial Z := [p=0 for p in gb] (5)
Type: List(Equation(Fraction(Polynomial(Integer))))
fricas
solve(egb, [d,m,n]) (6)
Type: List(List(Equation(Fraction(Polynomial(Integer)))))

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

fricas
ecoeffs: List Equation Fraction Polynomial Z := [p=0 for p in coeffs] (7)
Type: List(Equation(Fraction(Polynomial(Integer))))
fricas
solve(ecoeffs, [d,m,n]) (8)
Type: List(List(Equation(Fraction(Polynomial(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(Integer)))))

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

Example code --rrogers, Tue, 02 Dec 2014 23:49:41 +0000 reply
fricas
---- Ordered  variable lists.
Poly_to_Gauss:=[d,n,m] (9)
Type: List(OrderedVariableList([d,n,m]))
fricas
Gauss_to_Poly:=[x,y,a,b,c] (10)
Type: List(UnivariatePolynomial(x,DistributedMultivariatePolynomial?([d,n,m],Fraction(DistributedMultivariatePolynomial?([a,b,c],Integer)))))
fricas
----coefficient arrays.
corg :=  d* matrix [[c,b,a]] (11)
Type: Matrix(Polynomial(Integer))
fricas
---- Explicit target
cgauss := matrix [[0, 1, -1]] (12)
Type: Matrix(Integer)
fricas
---- Generalized target
ctar := matrix [[w,v,u]] (13)
Type: Matrix(Polynomial(Integer))
fricas
---- polynomial basis arrays.
xorg := matrix ([[1, x, x^2]]) (14)
Type: Matrix(Polynomial(Integer))
fricas
xgauss := matrix([[1,y,y^2]]) (15)
Type: Matrix(UnivariatePolynomial(x,DistributedMultivariatePolynomial?([d,n,m],Fraction(DistributedMultivariatePolynomial?([a,b,c],Integer)))))
fricas
---- Example
row(corg * transpose(xorg),1) (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)) (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

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 (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) (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)) (20)
Type: Matrix(Polynomial(Integer))

fricas
Z==>Integer; Q==>Fraction Z
Type: Void
fricas
CP==>DistributedMultivariatePolynomial([a,b,c,u,v,w], Z)
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,u,v,w],Integer)))) ->
UnivariatePolynomial(x,DistributedMultivariatePolynomial([d,n,m],
Fraction(DistributedMultivariatePolynomial([a,b,c,u,v,w],Integer)
))) has been added to workspace.
Type: Void
fricas
fp(x:PX):PX == u*x^2+v*x+w
Function declaration fp : UnivariatePolynomial(x,
DistributedMultivariatePolynomial([d,n,m],Fraction(
DistributedMultivariatePolynomial([a,b,c,u,v,w],Integer)))) ->
UnivariatePolynomial(x,DistributedMultivariatePolynomial([d,n,m],
Fraction(DistributedMultivariatePolynomial([a,b,c,u,v,w],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,u,v,w],Integer)))) ->
UnivariatePolynomial(x,DistributedMultivariatePolynomial([d,n,m],
Fraction(DistributedMultivariatePolynomial([a,b,c,u,v,w],Integer)
))) has been added to workspace.
Type: Void
fricas
y:PX := m*x+n (1)
Type: UnivariatePolynomial(x,DistributedMultivariatePolynomial?([d,n,m],Fraction(DistributedMultivariatePolynomial?([a,b,c,u,v,w],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,u,v,w],Integer)))) ->
UnivariatePolynomial(x,DistributedMultivariatePolynomial([d,n,m],
Fraction(DistributedMultivariatePolynomial([a,b,c,u,v,w],Integer)
)))
fricas
Compiling function q with type UnivariatePolynomial(x,
DistributedMultivariatePolynomial([d,n,m],Fraction(
DistributedMultivariatePolynomial([a,b,c,u,v,w],Integer)))) ->
UnivariatePolynomial(x,DistributedMultivariatePolynomial([d,n,m],
Fraction(DistributedMultivariatePolynomial([a,b,c,u,v,w],Integer)
))) (2)
Type: UnivariatePolynomial(x,DistributedMultivariatePolynomial?([d,n,m],Fraction(DistributedMultivariatePolynomial?([a,b,c,u,v,w],Integer))))
fricas
s:PX := fp(x) - d*q(y)
fricas
Compiling function fp with type UnivariatePolynomial(x,
DistributedMultivariatePolynomial([d,n,m],Fraction(
DistributedMultivariatePolynomial([a,b,c,u,v,w],Integer)))) ->
UnivariatePolynomial(x,DistributedMultivariatePolynomial([d,n,m],
Fraction(DistributedMultivariatePolynomial([a,b,c,u,v,w],Integer)
))) (3)
Type: UnivariatePolynomial(x,DistributedMultivariatePolynomial?([d,n,m],Fraction(DistributedMultivariatePolynomial?([a,b,c,u,v,w],Integer))))
fricas
coeffs := coefficients r (4)
Type: List(DistributedMultivariatePolynomial?([d,n,m],Fraction(DistributedMultivariatePolynomial?([a,b,c,u,v,w],Integer))))
fricas
fcoeffs := coefficients s (5)
Type: List(DistributedMultivariatePolynomial?([d,n,m],Fraction(DistributedMultivariatePolynomial?([a,b,c,u,v,w],Integer))))
fricas
gb := groebner coeffs (6)
Type: List(DistributedMultivariatePolynomial?([d,n,m],Fraction(DistributedMultivariatePolynomial?([a,b,c,u,v,w],Integer))))
fricas
fgb := groebner fcoeffs (7)
Type: List(DistributedMultivariatePolynomial?([d,n,m],Fraction(DistributedMultivariatePolynomial?([a,b,c,u,v,w],Integer))))
fricas
egb: List Equation Fraction Polynomial Z := [p=0 for p in gb] (8)
Type: List(Equation(Fraction(Polynomial(Integer))))
fricas
fegb:  List Equation Fraction Polynomial Z := [p=0 for p in fgb] (9)
Type: List(Equation(Fraction(Polynomial(Integer))))
fricas
ecoeffs: List Equation Fraction Polynomial Z := [p=0 for p in coeffs] (10)
Type: List(Equation(Fraction(Polynomial(Integer))))
fricas
fecoeffs: List Equation Fraction Polynomial Z := [p=0 for p in fcoeffs] (11)
Type: List(Equation(Fraction(Polynomial(Integer))))
fricas
cc:=solve(egb, [d,n,m]);
Type: List(List(Equation(Fraction(Polynomial(Integer)))))
fricas
cc.1 (12)
Type: List(Equation(Fraction(Polynomial(Integer))))
fricas
dd:=solve(ecoeffs, [d,n,m]);
Type: List(List(Equation(Fraction(Polynomial(Integer)))))
fricas
dd.1 (13)
Type: List(Equation(Fraction(Polynomial(Integer))))
fricas
fcc:=solve(fegb,[d,n,m]);
Type: List(List(Equation(Fraction(Polynomial(Integer)))))
fricas
fcc.1 (14)
Type: List(Equation(Fraction(Polynomial(Integer))))
fricas
fdd:=solve(fecoeffs, [d,n,m]);
Type: List(List(Equation(Fraction(Polynomial(Integer)))))
fricas
fdd.1 (15)
Type: List(Equation(Fraction(Polynomial(Integer))))

 Subject:   Be Bold !! ( 15 subscribers )