Issue 284, axiom crashes for a Groebner basis.
Waldek Hebisch
recursion on invalid data. Namely, computeBasis expects basis
(with respect to total degree, reverse lexicographic ordering)
of a _zero_ dimensional ideal. I did not check if given polynomials
are a basis, but definitly the ideal is _not_ zero dimensional.
It is known that zero dimensional ideal contains polynomial
which depends only on one variable. The intcompBasis function
in LinGroebnerPackage effectively tries all powers of variable
to find (bound on) degree of this polynomial. However, if
ideal is not zero dimensional no power will do and the procedure
will loop (recurse) exhausting all available resources.
What can we do? We can change recursion to iteration, which
would avoid stack overflow, but eventually will exhaust memory.
We can put hard limit on degree of polynomial that we try -- but
in most other places we just blindly perform computations without
checking if computation is feasible. We can press Lisp implementations
to reliably detect stack overflow -- in this case Clisp detects
overflow, but gcl crashes, in other cases gcl detected stack
overflow but Clisp crashed...
Comments?
--
Waldek Hebisch
heb...@math.uni.wroc.pl
Martin Rubey
I'd move the bug to Axiom Documentation and document computeBasis properly.
(DISCLAIMER: I do not know enough about Groebner bases, Ralf does...) Of
course, this should include a warning that axiom may die on wrong input.
In fact, if the "expected" output is a Groebner basis, then the user should
just have called groebner. Furthermore, the package is unexposed, so the user
should well know what he/she is doing.
Martin
Waldek Hebisch
> I'd move the bug to Axiom Documentation and document computeBasis properly.
> (DISCLAIMER: I do not know enough about Groebner bases, Ralf does...) Of
> course, this should include a warning that axiom may die on wrong input.
>
> In fact, if the "expected" output is a Groebner basis, then the user should
> just have called groebner. Furthermore, the package is unexposed, so the user
> should well know what he/she is doing.
>
Well, in LinGroebnerPackage we have:
++ Given a Groebner basis B with respect to the total degree ordering for
++ a zero-dimensional ideal I, compute
++ a Groebner basis with respect to the lexicographical ordering by using
++ linear algebra.
AFAICS LinGroebnerPackage is really an internal package, not intended
for end user. In particular computeBasis is a helper function which
does _not_ compute Groebner basis -- it computes basis of a linear
space which contains lexicographic Groebner basis.
I guess you want to add something like:
++ This is an internal package. It may give wrong answer or crash
++ on invalid input.
I would oppose to anything more verbose. In fact, this warning is really
redundant: the same applies to most unexposed packages.
--
Waldek Hebisch
heb...@math.uni.wroc.pl
Martin Rubey
> I guess you want to add something like:
++ Given a Groebner basis B with respect to the total degree ordering for a
++ zero-dimensional ideal I, compute a Groebner basis with respect to the
++ lexicographical ordering by using linear algebra. This is an internal
++ package.
and for computeBasis:
++ computeBasis is a helper function which computes a basis of a linear space
++ which contains a lexicographic Groebner basis. It may crash on invalid
++ input.
Please correct if this is misleading. wrong answer on invalid input should be
obvious, though. Would be nice to be more precise, in fact: what is the input,
what is the output.
> I would oppose to anything more verbose. In fact, this warning is really
> redundant: the same applies to most unexposed packages.
I agree partially. There may be some unexposed packages which are really safe
to use but are not exposed to help the interpreter. (but I don't know whether
this is a likely scenario)
However: if a function may crash axiom, this should be documented in any case.
Martin
Waldek Hebisch
> Waldek Hebisch <heb...@math.uni.wroc.pl> writes:
>
> > I guess you want to add something like:
>
> ++ Given a Groebner basis B with respect to the total degree ordering for a
> ++ zero-dimensional ideal I, compute a Groebner basis with respect to the
> ++ lexicographical ordering by using linear algebra. This is an internal
> ++ package.
>
> and for computeBasis:
>
> ++ computeBasis is a helper function which computes a basis of a linear space
> ++ which contains a lexicographic Groebner basis. It may crash on invalid
> ++ input.
>
OK for the first sentence. I am affraid that the second really applies to
the whole package.
> Please correct if this is misleading. wrong answer on invalid input should be
> obvious, though.
Well behaved routines signal error on invalid input -- this should be
our standard for user visible functionality.
> > I would oppose to anything more verbose. In fact, this warning is really
> > redundant: the same applies to most unexposed packages.
>
> I agree partially. There may be some unexposed packages which are really safe
> to use but are not exposed to help the interpreter. (but I don't know whether
> this is a likely scenario)
>
> However: if a function may crash axiom, this should be documented in any case.
Almost any function can crash FriCAS. Vladimir had an example:
integrate(z^3000, z=0..1)
This may run out of memory and crash (if machine has enough memory
it is just slow).
Almost all FriCAS functions use dynamnic memory allocation so may run
out of memory and crash. Significant fraction may require a lot of
memory on "small" inputs.
Do not get me wrong: I am worried by the crashes. But IMHO the real
problem is not in computBasis (or integrate) -- the problem is that
underlying Lisp crashes. In other words, the correct place to detect
that we use too much memory (or stack) is in Lisp implementation.
--
Waldek Hebisch
heb...@math.uni.wroc.pl
Martin Rubey
> Martin Rubey wrote:
> > Waldek Hebisch <heb...@math.uni.wroc.pl> writes:
> >
> > > I guess you want to add something like:
> >
> > ++ Given a Groebner basis B with respect to the total degree ordering for a
> > ++ zero-dimensional ideal I, compute a Groebner basis with respect to the
> > ++ lexicographical ordering by using linear algebra. This is an internal
> > ++ package.
> >
> > and for computeBasis:
> >
> > ++ computeBasis is a helper function which computes a basis of a linear space
> > ++ which contains a lexicographic Groebner basis. It may crash on invalid
> > ++ input.
> >
>
> OK for the first sentence. I am affraid that the second really applies to
> the whole package.
Aha. In fact, I just saw that you know more than I put into the docstring.
Thus, better:
++ computeBasis is a helper function which computes a basis of a linear space
++ which contains a lexicographic Groebner basis. It expects a basis (ordered
++ by total degree, reverse lexicographic) of a _zero_ dimensional ideal.
I hope its correct. I think that this docstring won't hurt and will make sure
that nobody believes computeBasis would compute a Groebner basis...
And
++ Given a Groebner basis B with respect to the total degree ordering for a
++ zero-dimensional ideal I, compute a Groebner basis with respect to the
++ lexicographical ordering by using linear algebra. This is an internal
++ package, operations in this package may crash on invalid input.
> Well behaved routines signal error on invalid input -- this should be our
> standard for user visible functionality.
Yes, I agree. Except the documentation states explicitely that no checking is
done.
> > > I would oppose to anything more verbose. In fact, this warning is really
> > > redundant: the same applies to most unexposed packages.
> >
> > I agree partially. There may be some unexposed packages which are really
> > safe to use but are not exposed to help the interpreter. (but I don't know
> > whether this is a likely scenario)
> >
> > However: if a function may crash axiom, this should be documented in any
> > case.
>
> Almost any function can crash FriCAS. Vladimir had an example:
>
> integrate(z^3000, z=0..1)
>
> This may run out of memory and crash (if machine has enough memory it is just
> slow).
Oh. I thought this issue is closed (in fact it is: #105). Why is this so
slow? integrate(z^3000, z) works just fine.
In any case, it's a bug.
Apart from that, yes, I know that I can crash axiom easily. I don't think it's
worse than with any other CAS, though. But there are things which I'd expect
to go wrong like
(a+b)^(10^10);
and others where I'd like to be warned. The more obscure a function is, the
more I will be grateful for a word of warning. Of course, too many warnings
make warnings pointless - there has to be a balance.
> Do not get me wrong: I am worried by the crashes. But IMHO the real
> problem is not in computBasis (or integrate) -- the problem is that
> underlying Lisp crashes. In other words, the correct place to detect
> that we use too much memory (or stack) is in Lisp implementation.
I wonder whether this wouldn't imply a significant performance hit?
Martin
Martin Rubey
> integrate(z^3000, z=0..1)
>
> This may run out of memory and crash (if machine has enough memory
> it is just slow).
Now I understand:
integrate(z^3000, z)
is OK, since it invokes integration of polynomials, while
integrate(z^3000, z=0..1)
is slow, since it invokes general integration of expressions...
But the strange bit is: there is a better integration function, only, it is not
used:
integrate((z^3000)::FRAC POLY INT, z=0..1)
Any idea why?
Martin
Waldek Hebisch
>
> Waldek Hebisch <heb...@math.uni.wroc.pl> writes:
>
> > integrate(z^3000, z=0..1)
> >
> > This may run out of memory and crash (if machine has enough memory
> > it is just slow).
>
> Now I understand:
>
> integrate(z^3000, z)
>
> is OK, since it invokes integration of polynomials, while
>
> integrate(z^3000, z=0..1)
>
> is slow, since it invokes general integration of expressions...
>
Not exactly, integration works reasonably well. But definite integration
uses limits. Limit (or maybe definite integral) transforms z^3001 into
exp(3001*log(z)). Then limit tries to expand this into power series.
This series starts with 3000 zero terms. I suspect that computing
those 3000 zeros produces quite a lot of bignums (notice that exp has
coefficients of order factorial(3000) and we have numbers like 3001^3000).
Looking at reports from 'top' I see that clisp uses about 48 Mb on this
problem, sbcl about 95 Mb, gcl-2.6.7 goes beyond 110 Mb and crashes.
gcl-2.6.8 uses about 105 Mb. I recall Camm writing that gcl had
problems allocating memory for bignums. So it seems that crash
on z^3000 is a bug in gcl-2.6.7 -- I recall now that using 2.6.8
I need bigger (and correctly chosen) exponent to cause crash.
> But the strange bit is: there is a better integration function, only, it is not
> used:
>
> integrate((z^3000)::FRAC POLY INT, z=0..1)
>
> Any idea why?
>
I do know why another version is not used. But the main version
has another problem (issue 292), which may be related: utility
routines does not recognize integral powers as regular function.
I have a patch for this issue, but in testing another problem
showed up, so I need some more time to investigate this.
--
Waldek Hebisch
heb...@math.uni.wroc.pl
Martin Rubey
> I do know why another version is not used. But the main version has another
> problem (issue 292), which may be related: utility routines does not
> recognize integral powers as regular function. I have a patch for this
> issue, but in testing another problem showed up, so I need some more time to
> investigate this.
OK. Meanwhile, I think I should reopen #105, but rename it appropriately, and
ask why the bad signature is chosen. Note that usually the interpreter prefers
FRAC POLY INT over EXPR INT, so there is hope!
Martin
Martin Rubey
> > But the strange bit is: there is a better integration function, only, it is not
> > used:
> >
> > integrate((z^3000)::FRAC POLY INT, z=0..1)
> >
> > Any idea why?
> >
>
> I do know why another version is not used.
I guess you meant: "I do not know"
> But the main version has another problem (issue 292), which may be related:
> utility routines does not recognize integral powers as regular function. I
> have a patch for this issue, but in testing another problem showed up, so I
> need some more time to investigate this.
Hm, I looked into this: the obvious fix is to check for isExpt in checkSMP.
Something (the types are wrong here, of course) like below. I'd like to see
your patch and know what's going wrong.
However: this is quite certainly unrelated to #105, since z^3000 passes OK.
Something else is going wrong there.
Martin
-- true if p has a pole between a and b
checkSMP(p, x, k, a, b) ==
(u := polyIfCan(p, k)) case UP => false
(z := isExpt p) case Record(var: ???, exponent: NonNegativeInteger) =>
((w := checkSMP(z.var, x, k, a, b)) case "failed") or (w::B) => return w
false
(v := isTimes p) case List(P) =>
for t in v::List(P) repeat
((w := checkSMP(t, x, k, a, b)) case "failed") or (w::B) => return w
false
(v := isPlus p) case List(P) =>
n := 0 -- number of summand having a pole
for t in v::List(P) repeat
(w := checkSMP(t, x, k, a, b)) case "failed" => return w
if w::B then n := n + 1
zero? n => false -- no summand has a pole
-- one? n => true -- only one summand has a pole
(n = 1) => true -- only one summand has a pole
"failed" -- at least 2 summands have a pole
(r := retractIfCan(p)@Union(K, "failed")) case "failed" => "failed"
kk := r::K
-- nullary operators have no poles
nullary? operator kk => false
f := first argument kk
-- functions which are defined over all the reals:
is?(kk, "exp"::SE) or is?(kk, "sin"::SE) or is?(kk, "cos"::SE)
or is?(kk, "sinh"::SE) or is?(kk, "cosh"::SE) or is?(kk, "tanh"::SE)
or is?(kk, "sech"::SE) or is?(kk, "atan"::SE) or is?(kk, "acot"::SE)
or is?(kk, "asinh"::SE) => checkForPole(f, x, k, a, b)
-- functions which are defined on (-1,+1):
is?(kk, "asin"::SE) or is?(kk, "acos"::SE) or is?(kk, "atanh"::SE) =>
((w := checkForPole(f, x, k, a, b)) case "failed") or (w::B) => w
((w := posit(f - 1, x, k, a, b)) case "failed") or (w::B) => w
negat(f + 1, x, k, a, b)
-- functions which are defined on (+1, +infty):
is?(kk, "acosh"::SE) =>
((w := checkForPole(f, x, k, a, b)) case "failed") or (w::B) => w
negat(f - 1, x, k, a, b)
-- functions which are defined on (0, +infty):
is?(kk, "log"::SE) =>
((w := checkForPole(f, x, k, a, b)) case "failed") or (w::B) => w
negat(f, x, k, a, b)
"failed"
Ralf Hemmecke
> I have looked at issue 284. The crash is caused by unlimited
> recursion on invalid data. Namely, computeBasis expects basis
> (with respect to total degree, reverse lexicographic ordering)
> of a _zero_ dimensional ideal. I did not check if given polynomials
> are a basis, but definitly the ideal is _not_ zero dimensional.
Well one could make such functions internal to the package (not
exporting them). There could be a wrapper function which checks its
input to be zero-dimensional.
But maybe this test is not appropriate for someone who knows in advance
that his ideal is zero-dimensional. So putting a note into the API would
seem reasonable.
If the input is supposed to be a GB, then one can compute an upper bound
on the number of terms that are below the stairs. (Simply take the for
each variable the maximum of its degree in any leading term, then
multily these maxima. (That maybe much too big, but it is not
infinite.)) The degree of the univariate polynomial cannot exceed that
number, since the number of terms below the stairs is given by the
Hilbert function and thus an invariant of the ideal (not of the GB).
If the input is not a GB, one can take the same procedure, but the
output is not supposed to be correct (this still matches the API).
Anyway, it should be possible to compute it in finite time.
> What can we do? We can change recursion to iteration, which
> would avoid stack overflow, but eventually will exhaust memory.
> We can put hard limit on degree of polynomial that we try -- but
> in most other places we just blindly perform computations without
> checking if computation is feasible.
> We can press Lisp implementations
> to reliably detect stack overflow -- in this case Clisp detects
> overflow, but gcl crashes, in other cases gcl detected stack
> overflow but Clisp crashed...
> Comments?
Yes. *Never* put LISP code inside the Algebra part. I have nothing
against detecting memory overflow somewhere else, but make it invisible
from the Algebra part.
Ralf
Martin Rubey
the bug, is this OK?
Martin Rubey <martin...@univie.ac.at> writes:
> ++ computeBasis is a helper function which computes a basis of a linear space
> ++ which contains a lexicographic Groebner basis. It expects a basis (ordered
> ++ by total degree, reverse lexicographic) of a zero dimensional ideal.
> ++ Given a Groebner basis B with respect to the total degree ordering for a
> ++ zero-dimensional ideal I, compute a Groebner basis with respect to the
> ++ lexicographical ordering by using linear algebra. This is an internal
> ++ package, operations in this package may crash on invalid input.
(Ralf's comments are visible from IssueTracker, so we won't loose them if we
are going to revisit the issue)
Martin
Waldek Hebisch
>
> Waldek, I'd like to commit the documentation update now, and fixed in FriCAS
> the bug, is this OK?
>
OK.
--
Waldek Hebisch
heb...@math.uni.wroc.pl