I have implemented a number of
different approaches
for the g=1 code. The code is kind of a mess, but if you are interested I can
e-mail it to you. Bugs:
currently I do not know of any bugs in IntBasis, though I don't doubt there
will still be some bugs left at the moment.
I have implemented a number of
different approaches
for the g=1 code. The code is kind of a mess, but if you are interested I can
e-mail it to you.
Things to avoid:
It turns that out that divisions in an algebraic function field are very costly, example . So these have to be avoided whenever reasonably possible. (***)
As in most algorithms, large algebraic extensions have to be avoided in the implementation. However, we need algebraic extensions for the Puiseux expansions. To keep the tower of algebraic extensions as small as possible IntBasis will never split polynomials. If the roots of a polynomial are needed, the polynomial will be factored. Afterwards the algorithm treats all factors 1 by 1, by taking only 1 root of a factor at a time. This way extensions of exponential degree are avoided.
Things not to avoid:
Note that for problems where roots of a polynomial p are needed one can often try to avoid factorization of the polynomial by ignoring the fact that the polynomial p may be reducible and simply assuming that Q[x]/(p) is a field. If later in the algorithm an error occurs due the a failed division in the ring Q[x]/(p) then a factorization of p is automatically obtained. Though this approach is becoming more and more popular, we will not use it in IntBasis. The reason is the following: even though the theoretical complexity is is bad, factorization in Maple is usually cheap, and if a factorization of p is found then 1 larger problem (computing with a root of p) is split up in smaller subproblems (computing with a root of every factor of p). These smaller subproblems can usually be handled much quicker than the 1 larger problem, so this means that a factorization of p speeds up the algorithm. We do not want to avoid speedups, so we do not want to avoid factorization of polynomials in IntBasis.
(***) I found out recently (Nov 1995) that divisions aren't as bad as I thought. Even though the fact that the result of a division can be huge is still true, in the cases where the result is not too big it isn't that costly to compute it. This little procedure performs these divisions much faster than evala(Normal(a/b)) in Maple 5.3