login  home  contents  what's new  discussion  bug reports     help  links  subscribe  changes  refresh  edit
IssueTracker
#17 algebra BOOTSTRAP fixed point  ← ↑ →  #171 Solve handles lists of expressions differently

#170 Axiom fails to solve "separable" system of equations
  
last edited 11 years ago by test1

Edit detail for #170 Axiom fails to solve "separable" system of equations revision 1 of 3
1 2 3
Editor:
Time: 2007/11/17 22:01:54 GMT-8
Note: 
changed:
-
Some examples:

\begin{axiom}
L := [ A = 2*X+Y, B = 2*Y+X, C = 2*U+V, D = 2*V+U];
solve(L, [X,Y])
\end{axiom}

However:

\begin{axiom}
solve(L,[X,Y,U,V])
\end{axiom}

Simpler:

\begin{axiom}
solve([a - b = 0, c - d = 0],[b])
linSolve([a - b, c - d],[b])
\end{axiom}

The operation 'solve' calls 'linSolve', which sets up the corresponding matrix
and vector and solves it using 'solve\$LinearSystemMatrixPackage'. This in turn
returns '"failed"', since the last columns of the matrix contain zeros, the
vector does not. In the example above, the matrix and vector are::

         +- 1+
   [mat= |   |,vec= [- a,d - c]]
         + 0 +


Note that 

\begin{axiom}
linSolve([a - b, 0],[b])
\end{axiom}

works.
The same happens, if the equation is not linear:

\begin{axiom}
L := [ A = 2*X^2+Y, B = 2*Y+X, C = 2*U+V, D = 2*V+U];
solve(L, [X, Y])
)set output algebra on
)set output tex off
solve(L, [X, Y, U, V])
)set output algebra off
)set output tex on
\end{axiom}

So, very probably, a fix would need to do two things:

- seperate the equations into those that do and those that don't contain the
  given variables.

- check whether those that don't contain the variables are contradicting.

- solve the others.

The second point is necessary, since

\begin{axiom}
L := [ A = P+Q, B = P-Q, C = 1, C = -1];
solve(L, [P,Q])
solve(L,[P,Q,C])
\end{axiom}

really has no solution. As far as I know, this would have to be done in the very last function defined in 'syssolp.spad', which is::

       -- general solver. Input in polynomial style  --
       solve(lr:L F,vl:L SE) ==
           empty? vl => empty()
           checkLinear(lr,vl) =>
                            -- linear system --
               soln := linSolve(lr, vl)
               soln case "failed" => []
               eqns: L EQ F := []
               for i in 1..#vl repeat
                   lhs := (vl.i::(P R))::F
                   rhs :=  rhs soln.i
                   eqns := append(eqns, [lhs = rhs])
               [eqns]

                         -- polynomial system --
           if R has GcdDomain then
             parRes:=triangularSystems(lr,vl)
             [[makeEq(map(makeR2F,f)\$PP2,vl) for f in pr]
                                                        for pr in parRes]
           else [[]]


The letter 'F' is a macro for 'FRAC POLY R' here. To check whether an equation contains a variable we have to check numerator and denominator of both sides of the equation with 'variables\$POLY R'. I do not know however, how to find out whether the equations independent of 'vl' are contradicting.

Submitted by : (unknown) at: 2007-11-17T22:01:54-08:00 (17 years ago)
Name :
Axiom Version :
Category : Severity : Status :
Optional subject :  
Optional comment : 

Some examples:


axiom
L := [ A = 2*X+Y, B = 2*Y+X, C = 2*U+V, D = 2*V+U];


Type: List(Equation(Polynomial(Integer)))


axiom
solve(L, [X,Y])

\begin{equation*}
\label{eq1}\left[ \right]?\end{equation*}

Type: List(List(Equation(Fraction(Polynomial(Integer)))))


However:


axiom
solve(L,[X,Y,U,V])

\begin{equation*}
\label{eq2}\begin{array}{@{}l}
\displaystyle
\left[ \left[{X ={{- B +{2 \  A}}\over 3}}, \:{Y ={{{2 \  B}- A}\over 3}}, \:{U ={{- D +{2 \  C}}\over 3}}, \: \right.
\
\
\displaystyle
\left.{V ={{{2 \  D}- C}\over 3}}\right] \right] 
\end{array}
\end{equation*}

Type: List(List(Equation(Fraction(Polynomial(Integer)))))


Simpler:


axiom
solve([a - b = 0, c - d = 0],[b])

\begin{equation*}
\label{eq3}\left[ \right]?\end{equation*}

Type: List(List(Equation(Fraction(Polynomial(Integer)))))


axiom
linSolve([a - b, c - d],[b])

\begin{equation*}
\label{eq4}\left[{particular = \mbox{\tt "failed"}}, \:{basis ={\left[ \right]?}}\right]\end{equation*}

Type: Record(particular: Union(Vector(Fraction(Polynomial(Integer))),"failed"),basis: List(Vector(Fraction(Polynomial(Integer)))))


The operation solve calls linSolve, which sets up the corresponding matrix
and vector and solves it using solve$LinearSystemMatrixPackage. This in turn
returns "failed", since the last columns of the matrix contain zeros, the
vector does not. In the example above, the matrix and vector are:

         +- 1+
   [mat= |   |,vec= [- a,d - c]]
         + 0 +





Note that 


axiom
linSolve([a - b, 0],[b])

\begin{equation*}
\label{eq5}\left[{particular ={\left[ a \right]?}}, \:{basis ={\left[ \right]?}}\right]\end{equation*}

Type: Record(particular: Union(Vector(Fraction(Polynomial(Integer))),"failed"),basis: List(Vector(Fraction(Polynomial(Integer)))))


works.
The same happens, if the equation is not linear:


axiom
L := [ A = 2*X^2+Y, B = 2*Y+X, C = 2*U+V, D = 2*V+U];


Type: List(Equation(Polynomial(Integer)))


axiom
solve(L, [X, Y])

\begin{equation*}
\label{eq6}\left[{\left[ \right]?}\right]\end{equation*}

Type: List(List(Equation(Fraction(Polynomial(Integer)))))


axiom
)set output algebra on
 


axiom
)set output tex off

solve(L, [X, Y, U, V])

                        2                   2           - D + 2C    2D - C
   (9)  [[X= - 2Y + B,8Y  + (- 8B + 1)Y + 2B  - A= 0,U= --------,V= ------]]
                                                            3          3


Type: List(List(Equation(Fraction(Polynomial(Integer)))))


axiom
)set output algebra off
 


axiom
)set output tex on


So, very probably, a fix would need to do two things:



    

  • seperate the equations into those that do and those that don't contain the
  given variables.
    • 

  • check whether those that don't contain the variables are contradicting.
    • 

  • solve the others.
    • 




The second point is necessary, since


axiom
L := [ A = P+Q, B = P-Q, C = 1, C = -1];


Type: List(Equation(Polynomial(Integer)))


axiom
solve(L, [P,Q])

\begin{equation*}
\label{eq7}\left[ \right]?\end{equation*}

Type: List(List(Equation(Fraction(Polynomial(Integer)))))


axiom
solve(L,[P,Q,C])

\begin{equation*}
\label{eq8}\left[ \right]?\end{equation*}

Type: List(List(Equation(Fraction(Polynomial(Integer)))))


really has no solution. As far as I know, this would have to be done in the very last function defined in syssolp.spad, which is:

       -- general solver. Input in polynomial style  --
       solve(lr:L F,vl:L SE) ==
           empty? vl => empty()
           checkLinear(lr,vl) =>
                            -- linear system --
               soln := linSolve(lr, vl)
               soln case "failed" => []
               eqns: L EQ F := []
               for i in 1..#vl repeat
                   lhs := (vl.i::(P R))::F
                   rhs :=  rhs soln.i
                   eqns := append(eqns, [lhs = rhs])
               [eqns]

                         -- polynomial system --
           if R has GcdDomain then
             parRes:=triangularSystems(lr,vl)
             [[makeEq(map(makeR2F,f)$PP2,vl) for f in pr]
                                                        for pr in parRes]
           else [[]]





The letter F is a macro for FRAC POLY R here. To check whether an equation contains a variable we have to check numerator and denominator of both sides of the equation with variables$POLY R. I do not know however, how to find out whether the equations independent of vl are contradicting.
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
(./4045461453203660388-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/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/generic/xypic/xyknot.tex
 Xy-pic option: Knots and Links feature v.3.4 knots and links, loaded))
(/usr/share/texmf-texlive/tex/generic/xypic/xyarc.tex
 Xy-pic option: Circle, Ellipse, Arc feature v.3.4 circles, ellipses,
elliptical arcs, loaded)
(/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: `setspace 6.7 <2000/12/01>
) (/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 4045461453203660388-16.0px.sage
(./4045461453203660388-16.0px.sout))
(/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))
(./4045461453203660388-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]


Package amsmath Warning: Foreign command \over;
(amsmath)                \frac or \genfrac should be used instead
(amsmath)                 on input line 127.
 Missing \right. inserted.
<inserted text> 
                \right .
l.128 \


 Extra \right.
l.131 ...V ={{{2 \  D}- C}\over 3}}\right] \right]




[2] [3] (/usr/share/texmf-texlive/tex/latex/base/t1cmtt.fd) [4] [5] [6]
[7] [8] (./4045461453203660388-16.0px.aux) )
(see the transcript file for additional information)
Output written on 4045461453203660388-16.0px.dvi (8 pages, 2456 bytes).
Transcript written on 4045461453203660388-16.0px.log.