Using Semicontinuity for Standard Bases Computations

  • We present new results on standard basis computations of a 0-dimensional ideal I in a power series ring or in the localization of a polynomial ring over a computable field K. We prove the semicontinuity of the “highest corner” in a family of ideals, parametrized by the spectrum of a Noetherian domain A. This semicontinuity is used to design a new modular algorithm for computing a standard basis of I if K is the quotient field of A. It uses the computation over the residue field of a “good” prime ideal of A to truncate high order terms in the subsequent computation over K. We prove that almost all prime ideals are good, so a random choice is very likely to be good, and whether it is good is detected a posteriori by the algorithm. The algorithm yields a significant speed advantage over the non-modular version and works for arbitrary Noetherian domains. The most important special cases are perhaps A = ℤ and A = k[t], k any field and t a set of parameters. Besides its generality, the method differs substantially from previously known modular algorithms for A = ℤ, since it does not manipulate the coefficients. It is also usually faster and can be combined with other modular methods for computations in local rings. The algorithm is implemented in the computer algebra system SINGULAR and we present several examples illustrating its power.

Download full text files

Export metadata

Additional Services

Search Google Scholar
Author:Gert-Martin Greuel, Gerhard Pfister, Hans Schönemann
Parent Title (English):Mathematics in Computer Science
Publisher:Springer Nature - Springer
Document Type:Article
Language of publication:English
Date of Publication (online):2024/03/28
Year of first Publication:2022
Publishing Institution:Rheinland-Pfälzische Technische Universität Kaiserslautern-Landau
Date of the Publication (Server):2024/03/28
Article Number:21
Page Number:11
Faculties / Organisational entities:Kaiserslautern - Fachbereich Mathematik
DDC-Cassification:5 Naturwissenschaften und Mathematik / 510 Mathematik
Licence (German):Zweitveröffentlichung