An algorithm for computing an integral basis in an algebraic function field
This paper contains a new method for computing an
integral basis for an algebraic function field using
Puiseux expansions. The algorithm is very efficient
because of the following two ingredients:
1) A good bound (in practice: sharp in most cases) for
the number of terms that one needs to compute for
the Puiseux expansions.
2) A precise bound for the denominators in the integral
basis. A consequence of this bound is that in the
intermediate computations the expressions can be
truncated at exactly the right spot, every term that
does not affect the final result can be skipped. This
way the expressions will be small during the computation
and hence the algorithm will be fast.
An integral basis is very useful for computations with
algebraic curves. It can be used for L(D) computations
(instead of using adjoint curves). It contains information
about the singularities in a form that is very suitable
for computer computations which leads to good
efficiency, for example, my parametrization algorithm in
Maple is often very efficient.
The algorithm is available in Maple V release 5. The
implementation contains some special purpose code for
the cases where the discriminant has a factor of multiplicity
2 or 3 (this is not explained in the paper). The Puiseux code,
on which the integral basis algorithm is based, also contains
improvements over the traditional method, such as a different
Newton polygon that can be computed more quickly, and
sharp bounds on which terms in the intermediate expressions
are necessary and which are not (and so avoiding computing
unnecessary terms, which greatly reduces expression swell).
These improvements can be found in my implementation
but they're not written down.
For the implementation see the files puiseux and
integral_basis in
the algcurves
package.
Download this paper