Triangular bases of integral closures

Abstract

En aquest treball, considerem el problema de computar bases triangulars de clausures enteres d'anells locals unidimensionals.

Es presenta "MaxMin", un algoritme eficient que empra representacions OM d'ideals primers per computar bases locals d'ideals fraccionaris de cossos de nombres i cossos de funcions. MaxMin garanteix que les bases generades són reduïdes i triangulars. D'aquesta manera, s'evita l'aplicació de rutines de triangularització, com ara el pas a la forma normal d'Hermite, que són lentes per a cossos de grau alt.

Mostrem que aquest algoritme té la mateixa complexitat computacional asimptòtica que els mètodes ja existents basats en representacions OM. MaxMin ha estat desenvolupat i inclòs en el paquet +Ideals, dissenyat per treballar qüestions aritmètiques en cossos grans. La implementació quasi sempre és més ràpida que la de les altres rutines basades en representacions OM. Respecte a les rutines que es troben actualment als sistemes d'àlgebra computacional estàndard, la nostra implementació de MaxMin és també considerablement més ràpida, exceptuant casos concrets d'extensions de cossos molt petites.

En este trabajo, consideramos el problema de computar bases triangulares de clausuras enteras de anillos locales unidimensionales.

Se presenta "MaxMin", un algoritmo eficiente que emplea representaciones OM de ideales primos para computar bases locales de ideales fraccionarios de cuerpos de números y cuerpos de funciones. MaxMin garantiza que las bases generadas son reducidas y triangulares. De este modo, se evita la aplicación de rutinas de triangularización, como el paso a la forma normal de Hermite, que son lentas para cuerpos de grado alto.

Mostramos que este algoritmo tiene la misma complejidad computacional asintótica que los métodos ya existentes basados en representaciones OM. MaxMin ha sido desarrollado e incluido en +Ideals, un paquete diseñado para trabajar cuestiones aritméticas en cuerpos grandes. La implementación casi siempre es más rápida que las otras rutinas basadas en representaciones OM. Respecto a las rutinas que se encuentran actualmente en los sistemas de álgebra computacional estándard, nuestra implementación de MaxMin es de nuevo considerablemente más rápida, exceptuando casos concretos de extensiones de cuerpos muy pequeñas.

In this work, we consider the problem of computing triangular bases of integral closures of one-dimensional local rings.

"MaxMin" is presented, an efficient algorithm which employs OM representations of prime ideals to compute local bases of fractional ideals of number fields and function fields. The proposed algorithm generates bases which are guaranteed to be reduced and triangular. In this way, it avoids the application of triangularisation routines, such as the Hermite Normal Form, which are slow for fields of large degree. We show that this algorithm has the same asymptotic computational complexity as existing methods based on OM representations. MaxMin has been developed and included as part of the +Ideals package for arithmetic in large fields. This implementation is almost always faster than existing OM-based routines. It is also considerably faster than the routines currently found in standard computer algebra systems, excepting some cases involving very small field extensions.