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
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))))
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
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
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]
Type: List(Equation(Fraction(Polynomial(Integer))))
fricas
solve(egb, [d,m,n])
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]
Type: List(Equation(Fraction(Polynomial(Integer))))
fricas
solve(ecoeffs, [d,m,n])
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)))))
===============================================================
fricas
---- Ordered variable lists.
Poly_to_Gauss:=[d,n,m]
fricas
Gauss_to_Poly:=[x,y,a,b,c]
Type: List(
UnivariatePolynomial(x,
DistributedMultivariatePolynomial
?([d,
n,
m],
Fraction(DistributedMultivariatePolynomial
?([a,
b,
c],
Integer)))))
fricas
----coefficient arrays.
corg := d* matrix [[c,b,a]]
Type: Matrix(Polynomial(Integer))
fricas
---- Explicit target
cgauss := matrix [[0, 1, -1]]
Type: Matrix(Integer)
fricas
---- Generalized target
ctar := matrix [[w,v,u]]
Type: Matrix(Polynomial(Integer))
fricas
---- polynomial basis arrays.
xorg := matrix ([[1, x, x^2]])
Type: Matrix(Polynomial(Integer))
fricas
xgauss := matrix([[1,y,y^2]])
Type: Matrix(
UnivariatePolynomial(x,
DistributedMultivariatePolynomial
?([d,
n,
m],
Fraction(DistributedMultivariatePolynomial
?([a,
b,
c],
Integer)))))
fricas
---- Example
row(corg * transpose(xorg),1)
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))
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
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)
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))
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
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)
)))
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)
)))
Type: UnivariatePolynomial(x,
DistributedMultivariatePolynomial
?([d,
n,
m],
Fraction(DistributedMultivariatePolynomial
?([a,
b,
c,
u,
v,
w],
Integer))))
fricas
coeffs := coefficients r
Type: List(DistributedMultivariatePolynomial
?([d,
n,
m],
Fraction(DistributedMultivariatePolynomial
?([a,
b,
c,
u,
v,
w],
Integer))))
fricas
fcoeffs := coefficients s
Type: List(DistributedMultivariatePolynomial
?([d,
n,
m],
Fraction(DistributedMultivariatePolynomial
?([a,
b,
c,
u,
v,
w],
Integer))))
fricas
gb := groebner coeffs
Type: List(DistributedMultivariatePolynomial
?([d,
n,
m],
Fraction(DistributedMultivariatePolynomial
?([a,
b,
c,
u,
v,
w],
Integer))))
fricas
fgb := groebner fcoeffs
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]
Type: List(Equation(Fraction(Polynomial(Integer))))
fricas
fegb: List Equation Fraction Polynomial Z := [p=0 for p in fgb]
Type: List(Equation(Fraction(Polynomial(Integer))))
fricas
ecoeffs: List Equation Fraction Polynomial Z := [p=0 for p in coeffs]
Type: List(Equation(Fraction(Polynomial(Integer))))
fricas
fecoeffs: List Equation Fraction Polynomial Z := [p=0 for p in fcoeffs]
Type: List(Equation(Fraction(Polynomial(Integer))))
fricas
cc:=solve(egb, [d,n,m]);
Type: List(List(Equation(Fraction(Polynomial(Integer)))))
fricas
cc.1
Type: List(Equation(Fraction(Polynomial(Integer))))
fricas
dd:=solve(ecoeffs, [d,n,m]);
Type: List(List(Equation(Fraction(Polynomial(Integer)))))
fricas
dd.1
Type: List(Equation(Fraction(Polynomial(Integer))))
fricas
fcc:=solve(fegb,[d,n,m]);
Type: List(List(Equation(Fraction(Polynomial(Integer)))))
fricas
fcc.1
Type: List(Equation(Fraction(Polynomial(Integer))))
fricas
fdd:=solve(fecoeffs, [d,n,m]);
Type: List(List(Equation(Fraction(Polynomial(Integer)))))
fricas
fdd.1
Type: List(Equation(Fraction(Polynomial(Integer))))