|
|
|
last edited 9 years ago by rrogers |
Edit detail for ExampleGroebner revision 5 of 8
| 1 2 3 4 5 6 7 8 | ||
|
Editor: hemmecke
Time: 2014/12/03 16:47:12 GMT+0 |
||
| Note: | ||
changed: - 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) 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) changed: - $$p(x) = q(m x + n).$$ $$p(x) = d q(m x + n).$$ changed: - \begin{axiom} Z==>Integer; Q==>Fraction Z CP==>DistributedMultivariatePolynomial([a,b,c], Q) CF==>Fraction CP P==>DistributedMultivariatePolynomial([d,n,m], CF) PX==>UnivariatePolynomial('x, P) p(x:PX):PX == x*(1-x) q(y:PX):PX == a*y^2+b*y+c y:PX := m*x+n r:PX := p(x) - d*q(y) \end{axiom} 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. \begin{axiom} coeffs := coefficients r \end{axiom} Now we compute a Groebner basis and then solve for the respective variables. \begin{axiom} gb := groebner coeffs egb: List Equation Fraction Polynomial Q := [p=0 for p in gb] solve(egb, [d,m,n]) \end{axiom} In fact, solve is powerful enough so that it is unnecessary to call the Buchberger algorithm explicitly. \begin{axiom} ecoeffs: List Equation Fraction Polynomial Q := [p=0 for p in coeffs] solve(ecoeffs, [d,m,n]) \end{axiom} Of course, the result depends on the order of the variables given to the solve command. \begin{axiom} solve(ecoeffs, [d,n,m]) \end{axiom} ===============================================================
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
Z==>Integer; Q==>Fraction Z
CP==>DistributedMultivariatePolynomial([a,b, c], Q)
CF==>Fraction CP
P==>DistributedMultivariatePolynomial([d,n, m], CF)
PX==>UnivariatePolynomial('x,
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.
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.
y:PX := m*x+n\begin{equation} \label{eq1}{m \ x}+ n\end{equation}
r:PX := p(x) - d*q(y)
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)))))
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)))))
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.
coeffs := coefficients r\begin{equation*} \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] \end{array} \end{equation*}
Now we compute a Groebner basis and then solve for the respective variables.
gb := groebner coeffs\begin{equation*} \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]?\end{equation*}
egb: List Equation Fraction Polynomial Q := [p=0 for p in gb]\begin{equation*} \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] \end{array} \end{equation*}
solve(egb,\begin{equation*} \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]\end{equation*}[d, m, n])
In fact, solve is powerful enough so that it is unnecessary to call the Buchberger algorithm explicitly.
ecoeffs: List Equation Fraction Polynomial Q := [p=0 for p in coeffs]\begin{equation*} \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] \end{array} \end{equation*}
solve(ecoeffs,\begin{equation*} \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]\end{equation*}[d, m, n])
Of course, the result depends on the order of the variables given to the solve command.
solve(ecoeffs,\begin{equation*} \label{eq9}\begin{array}{@{}l} \displaystyle \left[ \left[{d ={{{1 \over 4}\ a}\over{{a \ c}-{{1 \over 4}\ {{b}^{2}}}}}}, \:{n ={{-{{1 \over 2}\ a \ m}-{{1 \over 2}\ b}}\over a}}, \: \right. \ \ \displaystyle \left.{{{{{a}^{2}}\ {{m}^{2}}}+{4 \ a \ c}-{{b}^{2}}}= 0}\right] \right] \end{array} \end{equation*}[d, n, m])
===============================================================
---- Ordered variable lists. Poly_to_Gauss:=[d,\begin{equation*} \label{eq10}\left[ d , \: n , \: m \right]?\end{equation*}n, m]
Gauss_to_Poly:=[x,\begin{equation*} \label{eq11}\left[ x , \:{{m \ x}+ n}, \: a , \: b , \: c \right]?\end{equation*}y, a, b, c]
----coefficient arrays. corg := d* matrix [[c,\begin{equation*} \label{eq12}\left[ \begin{array}{ccc} {c \ d}&{b \ d}&{a \ d} \end{array} \right]\end{equation*}b, a]]
---- Explicit target cgauss := matrix [[0,\begin{equation*} \label{eq13}\left[ \begin{array}{ccc} 0 & 1 & - 1 \end{array} \right]\end{equation*}1, -1]]
---- Generalized target ctar := matrix [[w,\begin{equation*} \label{eq14}\left[ \begin{array}{ccc} w & v & u \end{array} \right]\end{equation*}v, u]]
---- polynomial basis arrays. xorg := matrix ([[1,\begin{equation*} \label{eq15}\left[ \begin{array}{ccc} 1 & x &{{x}^{2}} \end{array} \right]\end{equation*}x, x^2]])
xgauss := matrix([[1,\begin{equation*} \label{eq16}\left[ \begin{array}{ccc} 1 &{{m \ x}+ n}&{{{{m}^{2}}\ {{x}^{2}}}+{2 \ n \ m \ x}+{{n}^{2}}} \end{array} \right]\end{equation*}y, y^2]])
---- Example row(corg * transpose(xorg),\begin{equation*} \label{eq17}\left[{{a \ d \ {{x}^{2}}}+{b \ d \ x}+{c \ d}}\right]?\end{equation*}1)
---- 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]]
---- Scalar matrix Sc(m) == diagonalMatrix [1,m, m^2]
---- Now define transform in matrix form D := corg -(cgauss * Pa(n) * Sc(m))
Compiling function Pa with type Variable(n) -> Matrix(Polynomial(
Integer))Compiling function Sc with type Variable(m) -> Matrix(Polynomial(
Integer))---- Now we do a more realistic solve in two steps ---- Step one disallow silly answers E:=groebnerFactorize(row(D,\begin{equation*} \label{eq19}\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] \end{array} }, \right. \ \ \displaystyle \left.\:{\left[ 1 \right]?}\right] \end{array} \end{equation*}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
---- and clean it up (a lot). I wish these two steps could be one! solve(E.1,\begin{equation*} \label{eq20}\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]\end{equation*}Poly_to_Gauss)
---- 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,\begin{equation*} \label{eq21}\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}} \end{array} \right]\end{equation*}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))
Some or all expressions may not have rendered properly, because Latex returned the following error:
This is pdfTeXk, Version 3.141592-1.40.3 (Web2C 7.5.6) \write18 enabled. %&-line parsing enabled. entering extended mode (./4214857621687599592-16.0px.tex LaTeX2e <2005/12/01> Babel <v3.8h> and hyphenation patterns for english, usenglishmax, dumylang, noh yphenation, arabic, farsi, croatian, ukrainian, russian, bulgarian, czech, slov ak, danish, dutch, finnish, basque, french, german, ngerman, ibycus, greek, mon ogreek, ancientgreek, hungarian, italian, latin, mongolian, norsk, icelandic, i nterlingua, turkish, coptic, romanian, welsh, serbian, slovenian, estonian, esp eranto, uppersorbian, indonesian, polish, portuguese, spanish, catalan, galicia n, swedish, ukenglish, pinyin, loaded. (/usr/share/texmf-texlive/tex/latex/base/article.cls Document Class: article 2005/09/16 v1.4f Standard LaTeX document class (/usr/share/texmf-texlive/tex/latex/base/size12.clo)) (/usr/share/texmf-texlive/tex/latex/ucs/ucs.sty (/usr/share/texmf-texlive/tex/latex/ucs/data/uni-global.def)) (/usr/share/texmf-texlive/tex/latex/base/inputenc.sty (/usr/share/texmf-texlive/tex/latex/ucs/utf8x.def)) (/usr/share/texmf-texlive/tex/latex/bbm/bbm.sty) (/usr/share/texmf-texlive/tex/latex/jknapltx/mathrsfs.sty) (/usr/share/texmf-texlive/tex/latex/base/fontenc.sty (/usr/share/texmf-texlive/tex/latex/base/t1enc.def)) (/usr/share/texmf-texlive/tex/latex/pstricks/pstricks.sty (/usr/share/texmf-texlive/tex/generic/pstricks/pstricks.tex `PSTricks' v1.15 <2006/12/22> (tvz) (/usr/share/texmf-texlive/tex/generic/pstricks/pstricks.con)) (/usr/share/texmf/tex/latex/xcolor/xcolor.sty (/etc/texmf/tex/latex/config/color.cfg) (/usr/share/texmf-texlive/tex/latex/graphics/dvips.def) (/usr/share/texmf-texlive/tex/latex/graphics/dvipsnam.def))) (/usr/share/texmf-texlive/tex/latex/graphics/epsfig.sty (/usr/share/texmf-texlive/tex/latex/graphics/graphicx.sty (/usr/share/texmf-texlive/tex/latex/graphics/keyval.sty) (/usr/share/texmf-texlive/tex/latex/graphics/graphics.sty (/usr/share/texmf-texlive/tex/latex/graphics/trig.sty) (/etc/texmf/tex/latex/config/graphics.cfg)))) (/usr/share/texmf-texlive/tex/latex/pst-grad/pst-grad.sty (/usr/share/texmf-texlive/tex/generic/pst-grad/pst-grad.tex (/usr/share/texmf-texlive/tex/latex/xkeyval/pst-xkey.tex (/usr/share/texmf-texlive/tex/latex/xkeyval/xkeyval.sty (/usr/share/texmf-texlive/tex/latex/xkeyval/xkeyval.tex))) `pst-plot' v1.05, 2006/11/04 (tvz,dg,hv))) (/usr/share/texmf-texlive/tex/latex/pstricks/pst-plot.sty (/usr/share/texmf-texlive/tex/generic/pstricks/pst-plot.tex v97 patch 2, 1999/12/12 (/usr/share/texmf-texlive/tex/generic/multido/multido.tex v1.41, 2004/05/18 <tvz>))) (/usr/share/texmf-texlive/tex/latex/geometry/geometry.sty (/usr/share/texmf-texlive/tex/xelatex/xetexconfig/geometry.cfg)Package geometry Warning: `lmargin' and `rmargin' result in NEGATIVE (-108.405p t). `width' should be shortened in length.
) (/usr/share/texmf-texlive/tex/latex/amsmath/amsmath.sty For additional information on amsmath, use the `?
option. (/usr/share/texmf-texlive/tex/latex/amsmath/amstext.sty (/usr/share/texmf-texlive/tex/latex/amsmath/amsgen.sty)) (/usr/share/texmf-texlive/tex/latex/amsmath/amsbsy.sty) (/usr/share/texmf-texlive/tex/latex/amsmath/amsopn.sty)) (/usr/share/texmf-texlive/tex/latex/amsfonts/amsfonts.sty) (/usr/share/texmf-texlive/tex/latex/amsfonts/amssymb.sty) (/usr/share/texmf-texlive/tex/latex/amscls/amsthm.sty) (/usr/share/texmf-texlive/tex/latex/setspace/setspace.sty Package: `setspace6.7 <2000/12/01> ) (/usr/share/texmf-texlive/tex/generic/xypic/xy.sty (/usr/share/texmf-texlive/tex/generic/xypic/xy.tex Bootstrap'ing: catcodes, docmode, (/usr/share/texmf-texlive/tex/generic/xypic/xyrecat.tex) (/usr/share/texmf-texlive/tex/generic/xypic/xyidioms.tex)Xy-pic version 3.7 <1999/02/16> Copyright (c) 1991-1998 by Kristoffer H. Rose <krisrose@ens-lyon.fr> Xy-pic is free software: see the User's Guide for details.
Loading kernel: messages; fonts; allocations: state, direction, utility macros; pictures: \xy, positions, objects, decorations; kernel objects: directionals, circles, text; options; algorithms: directions, edges, connections; Xy-pic loaded)) (/usr/share/texmf-texlive/tex/generic/xypic/xyall.tex Xy-pic option: All features v.3.3 (/usr/share/texmf-texlive/tex/generic/xypic/xycurve.tex Xy-pic option: Curve and Spline extension v.3.7 curve, circles, loaded) (/usr/share/texmf-texlive/tex/generic/xypic/xyframe.tex Xy-pic option: Frame and Bracket extension v.3.7 loaded) (/usr/share/texmf-texlive/tex/generic/xypic/xycmtip.tex Xy-pic option: Computer Modern tip extension v.3.3 (/usr/share/texmf-texlive/tex/generic/xypic/xytips.tex Xy-pic option: More Tips extension v.3.3 loaded) loaded) (/usr/share/texmf-texlive/tex/generic/xypic/xyline.tex Xy-pic option: Line styles extension v.3.6 loaded) (/usr/share/texmf-texlive/tex/generic/xypic/xyrotate.tex Xy-pic option: Rotate and Scale extension v.3.3 loaded) (/usr/share/texmf-texlive/tex/generic/xypic/xycolor.tex Xy-pic option: Colour extension v.3.3 loaded) (/usr/share/texmf-texlive/tex/generic/xypic/xymatrix.tex Xy-pic option: Matrix feature v.3.4 loaded) (/usr/share/texmf-texlive/tex/generic/xypic/xyarrow.tex Xy-pic option: Arrow and Path feature v.3.5 path, \ar, loaded) (/usr/share/texmf-texlive/tex/generic/xypic/xygraph.tex Xy-pic option: Graph feature v.3.7 loaded) loaded) (/usr/share/texmf-texlive/tex/latex/tools/verbatim.sty) (/usr/share/texmf/tex/latex/graphviz/graphviz.sty (/usr/share/texmf-texlive/tex/latex/psfrag/psfrag.sty)) (/usr/share/texmf/tex/latex/sagetex.sty Writing sage input file 4214857621687599592-16.0px.sage ) (/usr/share/texmf-texlive/tex/latex/gnuplottex/gnuplottex.sty (/usr/share/texmf-texlive/tex/latex/base/latexsym.sty) (/usr/share/texmf-texlive/tex/latex/moreverb/moreverb.sty) (/usr/share/texmf-texlive/tex/latex/base/ifthen.sty)) (./4214857621687599592-16.0px.aux) (/usr/share/texmf-texlive/tex/latex/ucs/ucsencs.def) (/usr/share/texmf-texlive/tex/latex/jknapltx/ursfs.fd) (/usr/share/texmf-texlive/tex/latex/amsfonts/umsa.fd) (/usr/share/texmf-texlive/tex/latex/amsfonts/umsb.fd) (/usr/share/texmf-texlive/tex/latex/base/ulasy.fd) [1] [2] [3] [4] [5] [6]
Package amsmath Warning: Foreign command \over; (amsmath) \frac or \genfrac should be used instead (amsmath) on input line 147.
[7] [8] [9] [10] [11] Missing \right. inserted. <inserted text> \right . l.175 \
Extra \right. l.178 ... \ a \ c}-{{b}^{2}}}= 0}\right] \right]
[12] [13] [14] [15] [16] [17] [18] [19] [20] [21] [22] [23] [24] (./4214857621687599592-16.0px.aux) ) (see the transcript file for additional information) Output written on 4214857621687599592-16.0px.dvi (24 pages, 9692 bytes). Transcript written on 4214857621687599592-16.0px.log.