Martin Rubey wrote:
>
> Waldek Hebisch <[email protected]> writes:
>
> > I have now code which mostly avoids this problem: it moves
> > all algebraics into numerator and then normal GCD is enough
> > to remove common factors. But approach has its own problems:
> > many expression get bigger after moving algebraics into
> > numerator and moving algebraics into numerator may be quite
> > time consuming too. The effect is that with new code FriCAS
> > can do in few seconds the nasty examples that would otherwise
> > take weeks or months or run out of memory. But on average
> > FriCAS got slower (probably about two times slower) and there
> > is an example which works well with old code but did not finish
> > in few hours with new one.
>
> do you happen to know how others (eg sympy) deal with the problem?
>
Did not look at sympy. In paper from 2002 Monagan and van Hoej
give very bad timing for algebraic GCD in Maple -- much worse
than apropriately rescaled FriCAS times. So, my conclusion is
that in 2002 Maple did not handle the problem. Now Maple uses
modular algorithm for algebraic GCD. Beside GCD we would need
resultant and determinant (it would be nice to have a few more
operations working in modular way, but such operations currently
are done via GCDs, resultants and determinants, so the three are
really crucial).
To put it differently: I believe that the code I mentioned would
signifcantly speed up FFFG on algebraic problems. OTOH modular
solver handling algebraics should be faster.
Magma also uses modular algorithm for algebraic GCD. Additionally,
they use combination of triangular systems and modular computations
to implement algebraic closure -- in principle simplified version
of this may speed up what we do.
Maxima and Reduce have a lot of switches on all the time turn
them on or off. I do not think either does anything really smart
with algebraics.
--
Waldek Hebisch
[email protected]
--
You received this message because you are subscribed to the Google Groups
"FriCAS - computer algebra system" group.
To post to this group, send email to [email protected].
To unsubscribe from this group, send email to
[email protected].
For more options, visit this group at
http://groups.google.com/group/fricas-devel?hl=en.
