On Aug 26, 1:19 am, "Ondrej Certik" <[EMAIL PROTECTED]> wrote:
> On Tue, Aug 26, 2008 at 10:16 AM, Burcin Erocal <[EMAIL PROTECTED]> wrote:
>
> > On Tue, 26 Aug 2008 00:40:22 -0700 (PDT)
> > Michel <[EMAIL PROTECTED]> wrote:
>
> >> An assumption framework is non-trivial as it is basically
> >> computational
> >> real algebraic geometry.
>
> >> Recenty there was a post about QEPCAD (http://www.cs.usna.edu/~qepcad/
> >> B/QEPCAD.html).
> >> Perhaps this might fit the bill?
I'm not sure what sort of assumptions are really useful/used in
practice, but I can certainly imagine assumptions that QEPCAD couldn't
handle. For example, it can't handle "x is an integer", or "x^2 + x +
e^x > 2", or anything that involves a mixture of x and sin(x).
> > AFAIK, MMA indeed uses cylindrical algebraic decomposition (CAD) for
> > this, and it would be great to have an efficient CAD implementation in
> > Sage. I am not an expert on this issue, but from what I have heard,
> > qepcad has its advantages (more flexible?) and disadvantages (slow?)
> > compared to the CAD implementation in MMA.
>
> > qepcad relies on an aging library saclib for the algebraic data
> > structures. It would be a worthwhile project to implement CAD/port
> > qepcad so that it is modular, and can work with more recent/better
> > libraries. Maybe someone (Carl Witty?) will take this on (or already
> > has?). :)
I am indeed working on a CAD implementation for Sage, but I can't
commit to any sort of schedule... it might be months, years, or never,
before I get anything useful. (I do have "something" now, but it's
100x slower than QEPCAD on trivial examples.) If people want CAD-
based assumptions in the near term, it would probably be better to
start with QEPCAD. I do think that this would be feasible, although
it would be take some work on QEPCAD (for instance, it doesn't yet
build on OSX).
I won't be working on a port of QEPCAD to not use saclib; I'm not
willing to spend that much time working with its ported-from-Fortran
code. It's unclear how much work such a port would be; I can't tell
to what extent QEPCAD depends on "internals" of saclib.
> Yes, but this is not necessary to get the infrustructure in and get
> the easy cases working and working fast.
>
> qepcad or other things will come handy when doing the general cases,
> where simple heuristics will fail. E.g. it's like with limits, the
> gruntz algorithm is nice and working, but all easy cases can be done
> (and are done) with heuristics, because it is simpler and way faster.
Yes; if you can handle some particular class of assumptions without
CAD, it will likely be faster. CAD is particularly horrible with
mutliple variables; constructing a CAD of a polynomial with k
variables and maximal degree d in each variable ends up constructing a
univariate polynomial of degree d^(2^(k-1)) in the generic case, if
I'm remembering right. (So a polynomial with 6 variables, that is
degree 2 in each variable, would end up with a base case of a
polynomial of degree 2^32.) ("Interesting" cases are likely to be
better, because intermediate polynomials are not irreducible; this
helps a lot.)
Similarly, you can do linear programming with CAD; but it will take
time exponential in the number of variables.
On the other hand, for one or two variables, CAD should be able to
handle fairly large problems.
Carl
--~--~---------~--~----~------------~-------~--~----~
To post to this group, send email to sage-devel@googlegroups.com
To unsubscribe from this group, send email to [EMAIL PROTECTED]
For more options, visit this group at http://groups.google.com/group/sage-devel
URLs: http://www.sagemath.org
-~----------~----~----~----~------~----~------~--~---
