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

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 (19 years ago)
Name :
Axiom Version :
Category : Severity : Status :
Optional subject :  
Optional comment :

Some examples:

fricas
(1) -> L := [ A = 2*X+Y, B = 2*Y+X, C = 2*U+V, D = 2*V+U];
Type: List(Equation(Polynomial(Integer)))
fricas
solve(L, [X,Y])
\begin{equation*} \label{eq1}\left[ \right]?\end{equation*}
Type: List(List(Equation(Fraction(Polynomial(Integer)))))

However:

fricas
solve(L,[X,Y,U,V])
\begin{equation*} \label{eq2}\begin{array}{@{}l} \displaystyle \left[ \left[{X ={\frac{- B +{2 \ A}}{3}}}, \:{Y ={\frac{{2 \ B}- A}{3}}}, \: \right. \ \ \displaystyle \left.{U ={\frac{- D +{2 \ C}}{3}}}, \:{V ={\frac{{2 \ D}- C}{3}}}\right] \right] \end{array} \end{equation*}
Type: List(List(Equation(Fraction(Polynomial(Integer)))))

Simpler:

fricas
solve([a - b = 0, c - d = 0],[b])
\begin{equation*} \label{eq3}\left[ \right]?\end{equation*}
Type: List(List(Equation(Fraction(Polynomial(Integer)))))
fricas
linSolve([a - b, c - d],[b])
\begin{equation*} \label{eq4}\left[{particular = \verb#"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

fricas
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:

fricas
L := [ A = 2*X^2+Y, B = 2*Y+X, C = 2*U+V, D = 2*V+U];
Type: List(Equation(Polynomial(Integer)))
fricas
solve(L, [X, Y])
\begin{equation*} \label{eq6}\left[ \right]?\end{equation*}
Type: List(List(Equation(Fraction(Polynomial(Integer)))))
fricas
)set output algebra on
 
fricas
)set output tex off
solve(L, [X, Y, U, V])
(9) [ 2 2 - D + 2 C [X = - 2 Y + B, 8 Y + (- 8 B + 1)Y + 2 B - A = 0, U = ---------, 3 2 D - C V = -------] 3 ]
Type: List(List(Equation(Fraction(Polynomial(Integer)))))
fricas
)set output algebra off
 
fricas
)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

fricas
L := [ A = P+Q, B = P-Q, C = 1, C = -1];
Type: List(Equation(Polynomial(Integer)))
fricas
solve(L, [P,Q])
\begin{equation*} \label{eq7}\left[ \right]?\end{equation*}
Type: List(List(Equation(Fraction(Polynomial(Integer)))))
fricas
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 pdfTeX, Version 3.141592653-2.6-1.40.24 (TeX Live 2022/Debian) (preloaded format=latex)
 restricted \write18 enabled.
entering extended mode
(./6903459085527494319-16.0px.tex
LaTeX2e <2022-11-01> patch level 1
L3 programming layer <2023-01-16>
(/usr/share/texlive/texmf-dist/tex/latex/base/article.cls
Document Class: article 2022/07/02 v1.4n Standard LaTeX document class
(/usr/share/texlive/texmf-dist/tex/latex/base/size12.clo))
(/usr/share/texlive/texmf-dist/tex/latex/ucs/ucs.sty
(/usr/share/texlive/texmf-dist/tex/latex/ucs/data/uni-global.def))
(/usr/share/texlive/texmf-dist/tex/latex/base/inputenc.sty
(/usr/share/texlive/texmf-dist/tex/latex/ucs/utf8x.def))
(/usr/share/texlive/texmf-dist/tex/latex/bbm-macros/bbm.sty)
(/usr/share/texlive/texmf-dist/tex/latex/jknapltx/mathrsfs.sty)
(/usr/share/texlive/texmf-dist/tex/latex/base/fontenc.sty)
(/usr/share/texlive/texmf-dist/tex/latex/pstricks/pstricks.sty
(/usr/share/texlive/texmf-dist/tex/generic/iftex/iftex.sty)
(/usr/share/texlive/texmf-dist/tex/latex/xcolor/xcolor.sty
(/usr/share/texlive/texmf-dist/tex/latex/graphics-cfg/color.cfg)
(/usr/share/texlive/texmf-dist/tex/latex/graphics-def/dvips.def)
(/usr/share/texlive/texmf-dist/tex/latex/graphics/mathcolor.ltx)
(/usr/share/texlive/texmf-dist/tex/latex/graphics/dvipsnam.def))
(/usr/share/texlive/texmf-dist/tex/generic/xkeyval/pst-xkey.tex
(/usr/share/texlive/texmf-dist/tex/latex/xkeyval/xkeyval.sty
(/usr/share/texlive/texmf-dist/tex/generic/xkeyval/xkeyval.tex
(/usr/share/texlive/texmf-dist/tex/generic/xkeyval/xkvutils.tex
(/usr/share/texlive/texmf-dist/tex/generic/xkeyval/keyval.tex)))))
(/usr/share/texlive/texmf-dist/tex/generic/pstricks/pstricks.tex
(/usr/share/texlive/texmf-dist/tex/generic/pstricks/pst-fp.tex
`pst-fp' v0.06, 2020/11/20 (hv))
(/usr/share/texlive/texmf-dist/tex/latex/pgf/utilities/pgffor.sty
(/usr/share/texlive/texmf-dist/tex/latex/pgf/utilities/pgfrcs.sty
(/usr/share/texlive/texmf-dist/tex/generic/pgf/utilities/pgfutil-common.tex)
(/usr/share/texlive/texmf-dist/tex/generic/pgf/utilities/pgfutil-latex.def)
(/usr/share/texlive/texmf-dist/tex/generic/pgf/utilities/pgfrcs.code.tex
(/usr/share/texlive/texmf-dist/tex/generic/pgf/pgf.revision.tex)))
(/usr/share/texlive/texmf-dist/tex/latex/pgf/utilities/pgfkeys.sty
(/usr/share/texlive/texmf-dist/tex/generic/pgf/utilities/pgfkeys.code.tex
(/usr/share/texlive/texmf-dist/tex/generic/pgf/utilities/pgfkeyslibraryfiltered
.code.tex))) (/usr/share/texlive/texmf-dist/tex/latex/pgf/math/pgfmath.sty
(/usr/share/texlive/texmf-dist/tex/generic/pgf/math/pgfmath.code.tex
(/usr/share/texlive/texmf-dist/tex/generic/pgf/math/pgfmathutil.code.tex)
(/usr/share/texlive/texmf-dist/tex/generic/pgf/math/pgfmathparser.code.tex)
(/usr/share/texlive/texmf-dist/tex/generic/pgf/math/pgfmathfunctions.code.tex)
(/usr/share/texlive/texmf-dist/tex/generic/pgf/math/pgfmathfunctions.basic.code
.tex)
(/usr/share/texlive/texmf-dist/tex/generic/pgf/math/pgfmathfunctions.trigonomet
ric.code.tex)
(/usr/share/texlive/texmf-dist/tex/generic/pgf/math/pgfmathfunctions.random.cod
e.tex)
(/usr/share/texlive/texmf-dist/tex/generic/pgf/math/pgfmathfunctions.comparison
.code.tex)
(/usr/share/texlive/texmf-dist/tex/generic/pgf/math/pgfmathfunctions.base.code.
tex)
(/usr/share/texlive/texmf-dist/tex/generic/pgf/math/pgfmathfunctions.round.code
.tex)
(/usr/share/texlive/texmf-dist/tex/generic/pgf/math/pgfmathfunctions.misc.code.
tex)
(/usr/share/texlive/texmf-dist/tex/generic/pgf/math/pgfmathfunctions.integerari
thmetics.code.tex)
(/usr/share/texlive/texmf-dist/tex/generic/pgf/math/pgfmathcalc.code.tex)
(/usr/share/texlive/texmf-dist/tex/generic/pgf/math/pgfmathfloat.code.tex)))
(/usr/share/texlive/texmf-dist/tex/generic/pgf/utilities/pgffor.code.tex))
`PSTricks' v3.18  <2022/11/28> (tvz,hv)
--- We are running latex or xelatex ---
(/usr/share/texlive/texmf-dist/tex/generic/pstricks/pstricks.con)
(/usr/share/texlive/texmf-dist/tex/generic/pstricks/pstricks-color.tex)
(/usr/share/texlive/texmf-dist/tex/generic/pstricks/pstricks-arrows.tex)
(/usr/share/texlive/texmf-dist/tex/generic/pstricks/pstricks-dots.tex)
(/usr/share/texlive/texmf-dist/tex/generic/pstricks/pstricks.con))
(/usr/share/texlive/texmf-dist/tex/generic/pstricks/pst-fp.tex
`pst-fp' v0.06, 2020/11/20 (hv)))
(/usr/share/texlive/texmf-dist/tex/latex/graphics/epsfig.sty
(/usr/share/texlive/texmf-dist/tex/latex/graphics/graphicx.sty
(/usr/share/texlive/texmf-dist/tex/latex/graphics/graphics.sty
(/usr/share/texlive/texmf-dist/tex/latex/graphics/trig.sty)
(/usr/share/texlive/texmf-dist/tex/latex/graphics-cfg/graphics.cfg))))
(/usr/share/texlive/texmf-dist/tex/latex/pst-grad/pst-grad.sty
(/usr/share/texlive/texmf-dist/tex/generic/pst-grad/pst-grad.tex
`pst-grad' v1.06, 2006/11/27 (tvz,dg,hv)))
(/usr/share/texlive/texmf-dist/tex/latex/pst-plot/pst-plot.sty
(/usr/share/texlive/texmf-dist/tex/latex/xkeyval/pst-xkey.sty)
(/usr/share/texlive/texmf-dist/tex/latex/multido/multido.sty
(/usr/share/texlive/texmf-dist/tex/generic/multido/multido.tex
 v1.42, 2010/05/14 <tvz>))
(/usr/share/texlive/texmf-dist/tex/generic/pst-plot/pst-plot.tex
(/usr/share/texlive/texmf-dist/tex/generic/pst-tools/pst-tools.tex
`PST-tools' v0.12, 2021/09/23 (hv))
(/usr/share/texlive/texmf-dist/tex/generic/pstricks-add/pstricks-add.tex
(/usr/share/texlive/texmf-dist/tex/generic/pst-node/pst-node.tex
 v1.43, 2022/01/31)
(/usr/share/texlive/texmf-dist/tex/generic/pst-arrow/pst-arrow.tex
`pst-arrow' v0.05, 2021/11/16 (dr,hv))
(/usr/share/texlive/texmf-dist/tex/generic/pst-3d/pst-3d.tex
`PST-3d' v1.11, 2010/02/14 (tvz))
(/usr/share/texlive/texmf-dist/tex/generic/pst-math/pst-math.tex
`pst-math' v0.66 , (CJ,hv)) `pstricks-add' v3.93, 2022/11/21 (dr,hv))
 v1.94, 2022/11/21 (tvz,hv)))
(/usr/share/texlive/texmf-dist/tex/latex/geometry/geometry.sty
(/usr/share/texlive/texmf-dist/tex/generic/iftex/ifvtex.sty)

Package geometry Warning: `lmargin' and `rmargin' result in NEGATIVE (-108.405p t). `width' should be shortened in length.

) (/usr/share/texlive/texmf-dist/tex/latex/amsmath/amsmath.sty For additional information on amsmath, use the `?' option. (/usr/share/texlive/texmf-dist/tex/latex/amsmath/amstext.sty (/usr/share/texlive/texmf-dist/tex/latex/amsmath/amsgen.sty)) (/usr/share/texlive/texmf-dist/tex/latex/amsmath/amsbsy.sty) (/usr/share/texlive/texmf-dist/tex/latex/amsmath/amsopn.sty)) (/usr/share/texlive/texmf-dist/tex/latex/amsfonts/amsfonts.sty) (/usr/share/texlive/texmf-dist/tex/latex/amsfonts/amssymb.sty) (/usr/share/texlive/texmf-dist/tex/latex/amscls/amsthm.sty) (/usr/share/texlive/texmf-dist/tex/latex/setspace/setspace.sty) (/usr/share/texlive/texmf-dist/tex/generic/xypic/xy.sty (/usr/share/texlive/texmf-dist/tex/generic/xypic/xy.tex Bootstrap'ing: catcodes, docmode, (/usr/share/texlive/texmf-dist/tex/generic/xypic/xyrecat.tex ) (/usr/share/texlive/texmf-dist/tex/generic/xypic/xyidioms.tex)

Xy-pic version 3.8.9 <2013/10/06> Copyright (c) 1991-2013 by Kristoffer H. Rose <krisrose@tug.org> and others 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/texlive/texmf-dist/tex/generic/iftex/ifpdf.sty)) (/usr/share/texlive/texmf-dist/tex/generic/xypic/xyall.tex Xy-pic option: All features v.3.8 (/usr/share/texlive/texmf-dist/tex/generic/xypic/xycurve.tex Xy-pic option: Curve and Spline extension v.3.12 curve, circles, loaded) (/usr/share/texlive/texmf-dist/tex/generic/xypic/xyframe.tex Xy-pic option: Frame and Bracket extension v.3.14 loaded) (/usr/share/texlive/texmf-dist/tex/generic/xypic/xycmtip.tex Xy-pic option: Computer Modern tip extension v.3.7 (/usr/share/texlive/texmf-dist/tex/generic/xypic/xytips.tex Xy-pic option: More Tips extension v.3.11 loaded) loaded) (/usr/share/texlive/texmf-dist/tex/generic/xypic/xyline.tex Xy-pic option: Line styles extension v.3.10 loaded) (/usr/share/texlive/texmf-dist/tex/generic/xypic/xyrotate.tex Xy-pic option: Rotate and Scale extension v.3.8 loaded) (/usr/share/texlive/texmf-dist/tex/generic/xypic/xycolor.tex Xy-pic option: Colour extension v.3.11 loaded) (/usr/share/texlive/texmf-dist/tex/generic/xypic/xymatrix.tex Xy-pic option: Matrix feature v.3.14 loaded) (/usr/share/texlive/texmf-dist/tex/generic/xypic/xyarrow.tex Xy-pic option: Arrow and Path feature v.3.9 path, \ar, loaded) (/usr/share/texlive/texmf-dist/tex/generic/xypic/xygraph.tex Xy-pic option: Graph feature v.3.11 loaded) loaded) (/usr/share/texlive/texmf-dist/tex/latex/tools/verbatim.sty) (/usr/share/texlive/texmf-dist/tex/latex/graphviz/graphviz.sty (/usr/share/texlive/texmf-dist/tex/latex/psfrag/psfrag.sty)) (/usr/share/texmf/tex/latex/sagetex.sty Writing sage input file 6903459085527494319-16.0px.sage ) (/usr/share/texlive/texmf-dist/tex/latex/gnuplottex/gnuplottex.sty (/usr/share/texlive/texmf-dist/tex/latex/moreverb/moreverb.sty) (/usr/share/texlive/texmf-dist/tex/latex/base/ifthen.sty) (/usr/share/texlive/texmf-dist/tex/generic/catchfile/catchfile.sty (/usr/share/texlive/texmf-dist/tex/generic/infwarerr/infwarerr.sty) (/usr/share/texlive/texmf-dist/tex/generic/ltxcmds/ltxcmds.sty) (/usr/share/texlive/texmf-dist/tex/generic/etexcmds/etexcmds.sty))

Package gnuplottex Warning: Shell escape not enabled. (gnuplottex) You'll need to convert the graphs yourself.

) (/usr/share/texlive/texmf-dist/tex/latex/l3backend/l3backend-dvips.def) No file 6903459085527494319-16.0px.aux. (/usr/share/texlive/texmf-dist/tex/latex/ucs/ucsencs.def) geometry driver: auto-detecting geometry detected driver: dvips (/usr/share/texlive/texmf-dist/tex/latex/jknapltx/ursfs.fd) (/usr/share/texlive/texmf-dist/tex/latex/amsfonts/umsa.fd) (/usr/share/texlive/texmf-dist/tex/latex/amsfonts/umsb.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 ... ={\frac{{2 \ D}- C}{3}}}\right] \right]

[2] [3] (/usr/share/texlive/texmf-dist/tex/latex/base/t1cmtt.fd) [4] [5] [6] [7] [8] (./6903459085527494319-16.0px.aux)

LaTeX Warning: Label(s) may have changed. Rerun to get cross-references right.

) (see the transcript file for additional information) Output written on 6903459085527494319-16.0px.dvi (8 pages, 3040 bytes). Transcript written on 6903459085527494319-16.0px.log.