11 views

Skip to first unread message

Jan 19, 2008, 9:15:22 AM1/19/08

to fricas...@googlegroups.com

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.

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.

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

Jan 19, 2008, 9:27:13 AM1/19/08

to fricas...@googlegroups.com

Waldek Hebisch <heb...@math.uni.wroc.pl> writes:

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

Jan 19, 2008, 10:11:36 AM1/19/08

to fricas...@googlegroups.com

Martin Rubey wrote:

> 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.

>

> 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

Jan 19, 2008, 10:29:29 AM1/19/08

to fricas...@googlegroups.com

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.

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

Jan 19, 2008, 11:46:49 AM1/19/08

to fricas...@googlegroups.com

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.

>

> 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

Jan 19, 2008, 12:19:56 PM1/19/08

to fricas...@googlegroups.com

Waldek Hebisch <heb...@math.uni.wroc.pl> writes:

> 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

Jan 19, 2008, 12:53:40 PM1/19/08

to fricas...@googlegroups.com

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...

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

Jan 19, 2008, 1:49:23 PM1/19/08

to fricas...@googlegroups.com

Martin Rubey wrote:

>

> 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...

>

>

> 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

Jan 19, 2008, 1:51:12 PM1/19/08

to fricas...@googlegroups.com

Waldek Hebisch <heb...@math.uni.wroc.pl> writes:

> 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

Jan 20, 2008, 1:17:53 PM1/20/08

to fricas...@googlegroups.com

Waldek Hebisch <heb...@math.uni.wroc.pl> writes:

> > 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"

Jan 21, 2008, 4:29:07 AM1/21/08

to fricas...@googlegroups.com

On 01/19/2008 03:15 PM, Waldek Hebisch wrote:

> 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.

> 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

Jan 21, 2008, 11:17:11 AM1/21/08

to fricas...@googlegroups.com

Waldek, I'd like to commit the documentation update now, and fixed in FriCAS

the bug, is this OK?

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

Jan 21, 2008, 2:50:46 PM1/21/08

to fricas...@googlegroups.com

Martin Rubey wrote:

>

> Waldek, I'd like to commit the documentation update now, and fixed in FriCAS

> the bug, is this OK?

>

>

> 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

Reply all

Reply to author

Forward

0 new messages

Search

Clear search

Close search

Google apps

Main menu