Lower-level Singular interface / turn off unneeded PARI calculations

asked 2021-07-30 10:12:42 +0200

FabianG gravatar image

updated 2021-08-04 23:10:24 +0200

I am trying to implement an efficient elimination and substitution procedure for calculating the solution set of a zero-dimensional ideal $I \subseteq \mathbb{Q}[x_1, \ldots, x_n]$ over $\bar{\mathbb{Q}}$. (I know there is ideal.variety(QQbar) but would also like to compute directly the smallest number field over which each solution point is defined - number_field_elements_from_algebraics(..., minimal=True) can be very slow.)

The algorithm finds the irreducible factors $f_i$ of a generator of $I \cap \mathbb{Q}[x_n]$. These determine algebraic solutions for $x_n$ which can be plugged in to the remaining polynomials to inductively extend them to solutions of $I$.

The base field is thus extended from $\mathbb{Q}$ to the number field $\mathbb{Q}[x]/(f_i(x))$ (and iteratively to further extensions.)

When running the code, I observed that the construction of the field extensions is actually one of the main performance bottlenecks, in particular _pari_integral_basis. I assume that PARI's additional number field structure like the ring of integers is not necessary for Singular's Groebner algorithms and therefore wonder if these calculations can be turned off?

Working over Sage's quotient rings

QQ['x'].quotient(f)

does not seem to work together with Singular:

TypeError: Cannot call Singular function 'eliminate' with ring parameter of type '<class 'sage.rings.polynomial.multi_polynomial_ring.MPolynomialRing_polydict_domain_with_category'>'

TL;DR It currently seems impossible to call Singular's Groebner methods on an ideal in a polynomial ring defined over a number field without calling PARI's nfinit (which may spend a lot of time calculating an integral basis for the number field).

edit retag flag offensive close merge delete

Comments

If you're interested in groebner bases over number fields, you should probably just add a generator to your polynomial ring, and add the minimal polynomial to the ideal you're computing with:

Q(i)[x,y]/(x^2+2y^2-1,x^2+y^2+1) = Q[x,y,i]/(x^2+y^2-1,x^2+y^2+1,i^2+1)

It will fold the number-theoretical coefficient reductions in with the polynomial reductions required for groebner basis computations anyway. I expect it will be much more efficient than forcing Singular to work with generic coefficients.

nbruin gravatar imagenbruin ( 2021-08-05 05:52:57 +0200 )edit

Thanks, that is mostly what I resolved to do. In the process, I also need to factorize univariate polynomials over said number field, so I will still use Singular's minpoly it seems. (I will post an update once my algorithm works.)

FabianG gravatar imageFabianG ( 2021-08-05 12:30:21 +0200 )edit

primary factorization and computing reduced ideals can do those tasks, but using pari may be faster. These operations should not need integral bases or short representations of your number field, although in some cases you may find it's worth investing the time in getting a short representation of your number field to reduce coefficient swell in subsequent operations over it. But other times it can be very pricy: determining integral bases has "integer factorization" complexity. (lazy versions would be able to do better for questions where you actually need integral closedness, but not the value of the discriminant)

nbruin gravatar imagenbruin ( 2021-08-05 18:02:27 +0200 )edit

Hi! I just saw this question. Earlier this year I wrote some script that precisely does this: solving zero-dimensional ideal over the splitting field. In my code I used polredbest from PARI to construct the minpoly for the number fields, which in theory does not compute an integral basis. It is available here. You can try it out to see if the performance is good enough for you.

8d1h gravatar image8d1h ( 2021-09-20 19:18:04 +0200 )edit