oscar-system / Oscar.jl

A comprehensive open source computer algebra system for computations in algebra, geometry, and number theory.
https://www.oscar-system.org
Other
364 stars 129 forks source link

Ideal Saturation over F(t)[x,y] for F a number field could be faster. #4213

Open simonbrandhorst opened 1 month ago

simonbrandhorst commented 1 month ago

The saturation of an ideal in F(t)[x,y] for F = QQ(a) a simple number field could be faster.

The following computation terminates in Magma in Total time: 85.219 seconds, Total memory usage: 64.12MB See the attached text file for the magma code saturation_with_magma.txt

It does not terminate with Oscar at all. Here is the file: saturation_with_oscar.txt

Here is the background where these computations came up. For our research @HechtiDerLachs and I had to compute an F(t)-rational point of a curve of genus one over F(t). We knew that the point is contained in a zero dimensional ideal J. To do so we first needed to saturate J by some principal ideal D1 whose vanishing locus would not contain the point. Then we would like to compute the minimal primes of the resulting ideal J1. (But we never got to this point in Oscar.)

@ederc @wdecker @hannes14 @jankoboehm @afkafkafk13 @HechtiDerLachs

wdecker commented 1 month ago

Please check whether the function Oscar._saturation2 behaves any better. It would also be interesting to try the first iteration, that is, to apply quotient.

Am 16.10.2024 um 20:54 schrieb Simon Brandhorst @.***>:

The saturation of an ideal in F(t)[x,y] for F = QQ(a) a simple number field could be faster.

The following computation terminates in Magma in Total time: 85.219 seconds, Total memory usage: 64.12MB See the attached text file for the magma code saturation_with_magma.txt https://github.com/user-attachments/files/17400772/saturation_with_magma.txt It does not terminate with Oscar at all. Here is the file: saturation_with_oscar.txt https://github.com/user-attachments/files/17400819/saturation_with_oscar.txt Here is the background where these computations came up. For our research @HechtiDerLachs https://github.com/HechtiDerLachs and I had to compute an F(t)-rational point of a curve of genus one over F(t). We knew that the point is contained in a zero dimensional ideal J. To do so we first needed to saturate J by some principal ideal D1 whose vanishing locus would not contain the point. Then we would like to compute the minimal primes of the resulting ideal J1. (But we never got to this point in Oscar.)

@ederc https://github.com/ederc @wdecker https://github.com/wdecker @hannes14 https://github.com/hannes14 @jankoboehm https://github.com/jankoboehm @afkafkafk13 https://github.com/afkafkafk13 @HechtiDerLachs https://github.com/HechtiDerLachs — Reply to this email directly, view it on GitHub https://github.com/oscar-system/Oscar.jl/issues/4213, or unsubscribe https://github.com/notifications/unsubscribe-auth/AASSXETDTEZFH5LNLDDLTDTZ32Y5NAVCNFSM6AAAAABQCDWJNSVHI2DSMVQWIX3LMV43ASLTON2WKOZSGU4TENZXGU4DSNI. You are receiving this because you were mentioned.

simonbrandhorst commented 1 month ago

Thank you for the feedback. The computations are running. I will come back to them and see if they terminated in an hour or so. Some comments: The ideal J in question is zero dimensional. Perhaps more special methods apply. After reduction modulo a prime ideal over 113 of degree one, i.e. in GF(113)(t)[x,y] the computation succeeds in reasonable time.

simonbrandhorst commented 1 month ago

After about 2 hours Oscar._saturation2 and quotient keep running. Note that Oscar also cannot compute a groebner_basis for J within 2 hours, magma can compute it within one minute. So it seems the difference is not specific to saturations.

I aborted and got the following stack traces.

julia> Oscar._saturation2(J,D1)
^CERROR: InterruptException:
Stacktrace:
  [1] add!(a::AbsSimpleNumFieldElem, b::AbsSimpleNumFieldElem, c::AbsSimpleNumFieldElem)
    @ Nemo ~/.julia/packages/Nemo/tzyHK/src/antic/nf_elem.jl:769
  [2] add!
    @ ~/.julia/packages/AbstractAlgebra/34P8l/src/fundamental_interface.jl:354 [inlined]
  [3] mod(f::AbstractAlgebra.Generic.Poly{AbsSimpleNumFieldElem}, g::AbstractAlgebra.Generic.Poly{AbsSimpleNumFieldElem})
    @ AbstractAlgebra ~/.julia/packages/AbstractAlgebra/34P8l/src/Poly.jl:1431
  [4] gcd_modular_kronnecker(a::AbstractAlgebra.Generic.Poly{…}, b::AbstractAlgebra.Generic.Poly{…}, test_sqfr::Bool)
    @ Hecke ~/.julia/dev/Hecke/src/NumField/NfAbs/Poly.jl:243
  [5] gcd(a::AbstractAlgebra.Generic.Poly{…}, b::AbstractAlgebra.Generic.Poly{…}, test_sqfr::Bool)
    @ Hecke ~/.julia/dev/Hecke/src/NumField/NfAbs/Poly.jl:74
  [6] gcd(a::AbstractAlgebra.Generic.Poly{AbsSimpleNumFieldElem}, b::AbstractAlgebra.Generic.Poly{AbsSimpleNumFieldElem})
    @ Hecke ~/.julia/dev/Hecke/src/NumField/NfAbs/Poly.jl:64
  [7] -(a::AbstractAlgebra.Generic.FracFieldElem{…}, b::AbstractAlgebra.Generic.FracFieldElem{…})
    @ AbstractAlgebra ~/.julia/packages/AbstractAlgebra/34P8l/src/Fraction.jl:247
  [8] nemoFieldSub(a::Ptr{Nothing}, b::Ptr{Nothing}, cf::Ptr{Nothing})
    @ Singular.libSingular ~/.julia/packages/Singular/lsYSW/src/libsingular/nemo/Fields.jl:111
  [9] id_Saturation(arg1::CxxWrap.CxxWrapCore.CxxPtr{…}, arg2::CxxWrap.CxxWrapCore.CxxPtr{…}, arg3::CxxWrap.CxxWrapCore.CxxPtr{…})
    @ Singular.libSingular ~/.julia/packages/CxxWrap/5IZvn/src/CxxWrap.jl:624
 [10] saturation2(I::Singular.sideal{Singular.spoly{…}}, J::Singular.sideal{Singular.spoly{…}})
    @ Singular ~/.julia/packages/Singular/lsYSW/src/ideal/ideal.jl:631
 [11] _saturation2(I::MPolyIdeal{AbstractAlgebra.Generic.MPoly{…}}, J::MPolyIdeal{AbstractAlgebra.Generic.MPoly{…}})
    @ Oscar ~/.julia/dev/Oscar/src/Rings/mpoly-ideals.jl:351
 [12] top-level scope
    @ REPL[14]:1
Some type information was truncated. Use `show(err)` to see complete types.

The same for quotient

julia> quotient(J,D1)
^CERROR: InterruptException:
Stacktrace:
  [1] numerator(a::QQFieldElem)
    @ Nemo ~/.julia/packages/Nemo/tzyHK/src/flint/fmpq.jl:75
  [2] use_karamul(a::AbstractAlgebra.Generic.Poly{…}, b::AbstractAlgebra.Generic.Poly{…})
    @ Nemo ~/.julia/packages/Nemo/tzyHK/src/antic/nf_elem.jl:994
  [3] *(a::AbstractAlgebra.Generic.Poly{AbsSimpleNumFieldElem}, b::AbstractAlgebra.Generic.Poly{AbsSimpleNumFieldElem})
    @ Nemo ~/.julia/packages/Nemo/tzyHK/src/antic/nf_elem.jl:1006
  [4] mul_karatsuba(a::AbstractAlgebra.Generic.Poly{…}, b::AbstractAlgebra.Generic.Poly{…})
    @ AbstractAlgebra ~/.julia/packages/AbstractAlgebra/34P8l/src/Poly.jl:567
  [5] *(a::AbstractAlgebra.Generic.Poly{AbsSimpleNumFieldElem}, b::AbstractAlgebra.Generic.Poly{AbsSimpleNumFieldElem})
    @ Nemo ~/.julia/packages/Nemo/tzyHK/src/antic/nf_elem.jl:1007
  [6] mul_karatsuba(a::AbstractAlgebra.Generic.Poly{…}, b::AbstractAlgebra.Generic.Poly{…})
    @ AbstractAlgebra ~/.julia/packages/AbstractAlgebra/34P8l/src/Poly.jl:567
  [7] *(a::AbstractAlgebra.Generic.Poly{AbsSimpleNumFieldElem}, b::AbstractAlgebra.Generic.Poly{AbsSimpleNumFieldElem})
    @ Nemo ~/.julia/packages/Nemo/tzyHK/src/antic/nf_elem.jl:1007
  [8] mul_karatsuba(a::AbstractAlgebra.Generic.Poly{…}, b::AbstractAlgebra.Generic.Poly{…})
    @ AbstractAlgebra ~/.julia/packages/AbstractAlgebra/34P8l/src/Poly.jl:564
  [9] *(a::AbstractAlgebra.Generic.Poly{AbsSimpleNumFieldElem}, b::AbstractAlgebra.Generic.Poly{AbsSimpleNumFieldElem})
    @ Nemo ~/.julia/packages/Nemo/tzyHK/src/antic/nf_elem.jl:1007
 [10] mul_karatsuba(a::AbstractAlgebra.Generic.Poly{…}, b::AbstractAlgebra.Generic.Poly{…})
    @ AbstractAlgebra ~/.julia/packages/AbstractAlgebra/34P8l/src/Poly.jl:564
 [11] *(a::AbstractAlgebra.Generic.Poly{AbsSimpleNumFieldElem}, b::AbstractAlgebra.Generic.Poly{AbsSimpleNumFieldElem})
    @ Nemo ~/.julia/packages/Nemo/tzyHK/src/antic/nf_elem.jl:1007
 [12] mul_karatsuba(a::AbstractAlgebra.Generic.Poly{…}, b::AbstractAlgebra.Generic.Poly{…})
    @ AbstractAlgebra ~/.julia/packages/AbstractAlgebra/34P8l/src/Poly.jl:551
 [13] *(a::AbstractAlgebra.Generic.Poly{AbsSimpleNumFieldElem}, b::AbstractAlgebra.Generic.Poly{AbsSimpleNumFieldElem})
    @ Nemo ~/.julia/packages/Nemo/tzyHK/src/antic/nf_elem.jl:1007
 [14] mul_karatsuba(a::AbstractAlgebra.Generic.Poly{…}, b::AbstractAlgebra.Generic.Poly{…})
    @ AbstractAlgebra ~/.julia/packages/AbstractAlgebra/34P8l/src/Poly.jl:551
 [15] *(a::AbstractAlgebra.Generic.Poly{AbsSimpleNumFieldElem}, b::AbstractAlgebra.Generic.Poly{AbsSimpleNumFieldElem})
    @ Nemo ~/.julia/packages/Nemo/tzyHK/src/antic/nf_elem.jl:1007
 [16] mul_karatsuba(a::AbstractAlgebra.Generic.Poly{…}, b::AbstractAlgebra.Generic.Poly{…})
    @ AbstractAlgebra ~/.julia/packages/AbstractAlgebra/34P8l/src/Poly.jl:551
 [17] *(a::AbstractAlgebra.Generic.Poly{AbsSimpleNumFieldElem}, b::AbstractAlgebra.Generic.Poly{AbsSimpleNumFieldElem})
    @ Nemo ~/.julia/packages/Nemo/tzyHK/src/antic/nf_elem.jl:1007
 [18] -(a::AbstractAlgebra.Generic.FracFieldElem{…}, b::AbstractAlgebra.Generic.FracFieldElem{…})
    @ AbstractAlgebra ~/.julia/packages/AbstractAlgebra/34P8l/src/Fraction.jl:246
 [19] nemoFieldSub(a::Ptr{Nothing}, b::Ptr{Nothing}, cf::Ptr{Nothing})
    @ Singular.libSingular ~/.julia/packages/Singular/lsYSW/src/libsingular/nemo/Fields.jl:111
 [20] id_Quotient
    @ ~/.julia/packages/CxxWrap/5IZvn/src/CxxWrap.jl:624 [inlined]
 [21] quotient(I::Singular.sideal{Singular.spoly{…}}, J::Singular.sideal{Singular.spoly{…}})
    @ Singular ~/.julia/packages/Singular/lsYSW/src/ideal/ideal.jl:560
 [22] quotient(I::MPolyIdeal{AbstractAlgebra.Generic.MPoly{…}}, J::MPolyIdeal{AbstractAlgebra.Generic.MPoly{…}})
    @ Oscar ~/.julia/dev/Oscar/src/Rings/mpoly-ideals.jl:290
 [23] top-level scope
    @ REPL[12]:1
Some type information was truncated. Use `show(err)` to see complete types.
lgoettgens commented 1 month ago

This seems to be similar to https://github.com/oscar-system/Oscar.jl/issues/3701, where @HechtiDerLachs observed that a lot of time was spent computing gcds over number fields for some internal FracFieldElem arithmetic. According to that issue, @thofma improved the gcd code a bit

thofma commented 1 month ago

In #3701 it was just arithmetic. Here it is a Gröbner basis computation, which, as far as I understand, seems to go via the functionality in Singular for arbitrary fields. I doubt it is a matter of slow arithmetic, but I am happy to be proven wrong.

wdecker commented 1 month ago

Too bad! I will sit with Hans next weak and we will look into this.

Am 17.10.2024 um 10:14 schrieb Simon Brandhorst @.***>:

After about 2 hours Oscar._saturation2 and quotient keep running. Note that Oscar also cannot compute a groebner_basis for J within 2 hours.

I aborted and got the following stack traces.

julia> Oscar._saturation2(J,D1) ^CERROR: InterruptException: Stacktrace: [1] add!(a::AbsSimpleNumFieldElem, b::AbsSimpleNumFieldElem, c::AbsSimpleNumFieldElem) @ Nemo ~/.julia/packages/Nemo/tzyHK/src/antic/nf_elem.jl:769 [2] add! @ ~/.julia/packages/AbstractAlgebra/34P8l/src/fundamental_interface.jl:354 [inlined] [3] mod(f::AbstractAlgebra.Generic.Poly{AbsSimpleNumFieldElem}, g::AbstractAlgebra.Generic.Poly{AbsSimpleNumFieldElem}) @ AbstractAlgebra ~/.julia/packages/AbstractAlgebra/34P8l/src/Poly.jl:1431 [4] gcd_modular_kronnecker(a::AbstractAlgebra.Generic.Poly{…}, b::AbstractAlgebra.Generic.Poly{…}, test_sqfr::Bool) @ Hecke ~/.julia/dev/Hecke/src/NumField/NfAbs/Poly.jl:243 [5] gcd(a::AbstractAlgebra.Generic.Poly{…}, b::AbstractAlgebra.Generic.Poly{…}, test_sqfr::Bool) @ Hecke ~/.julia/dev/Hecke/src/NumField/NfAbs/Poly.jl:74 [6] gcd(a::AbstractAlgebra.Generic.Poly{AbsSimpleNumFieldElem}, b::AbstractAlgebra.Generic.Poly{AbsSimpleNumFieldElem}) @ Hecke ~/.julia/dev/Hecke/src/NumField/NfAbs/Poly.jl:64 [7] -(a::AbstractAlgebra.Generic.FracFieldElem{…}, b::AbstractAlgebra.Generic.FracFieldElem{…}) @ AbstractAlgebra ~/.julia/packages/AbstractAlgebra/34P8l/src/Fraction.jl:247 [8] nemoFieldSub(a::Ptr{Nothing}, b::Ptr{Nothing}, cf::Ptr{Nothing}) @ Singular.libSingular ~/.julia/packages/Singular/lsYSW/src/libsingular/nemo/Fields.jl:111 [9] id_Saturation(arg1::CxxWrap.CxxWrapCore.CxxPtr{…}, arg2::CxxWrap.CxxWrapCore.CxxPtr{…}, arg3::CxxWrap.CxxWrapCore.CxxPtr{…}) @ Singular.libSingular ~/.julia/packages/CxxWrap/5IZvn/src/CxxWrap.jl:624 [10] saturation2(I::Singular.sideal{Singular.spoly{…}}, J::Singular.sideal{Singular.spoly{…}}) @ Singular ~/.julia/packages/Singular/lsYSW/src/ideal/ideal.jl:631 [11] _saturation2(I::MPolyIdeal{AbstractAlgebra.Generic.MPoly{…}}, J::MPolyIdeal{AbstractAlgebra.Generic.MPoly{…}}) @ Oscar ~/.julia/dev/Oscar/src/Rings/mpoly-ideals.jl:351 [12] top-level scope @ REPL[14]:1 Some type information was truncated. Use show(err) to see complete types. The same for quotient

julia> quotient(J,D1) ^CERROR: InterruptException: Stacktrace: [1] numerator(a::QQFieldElem) @ Nemo ~/.julia/packages/Nemo/tzyHK/src/flint/fmpq.jl:75 [2] use_karamul(a::AbstractAlgebra.Generic.Poly{…}, b::AbstractAlgebra.Generic.Poly{…}) @ Nemo ~/.julia/packages/Nemo/tzyHK/src/antic/nf_elem.jl:994 [3] (a::AbstractAlgebra.Generic.Poly{AbsSimpleNumFieldElem}, b::AbstractAlgebra.Generic.Poly{AbsSimpleNumFieldElem}) @ Nemo ~/.julia/packages/Nemo/tzyHK/src/antic/nf_elem.jl:1006 [4] mul_karatsuba(a::AbstractAlgebra.Generic.Poly{…}, b::AbstractAlgebra.Generic.Poly{…}) @ AbstractAlgebra ~/.julia/packages/AbstractAlgebra/34P8l/src/Poly.jl:567 [5] (a::AbstractAlgebra.Generic.Poly{AbsSimpleNumFieldElem}, b::AbstractAlgebra.Generic.Poly{AbsSimpleNumFieldElem}) @ Nemo ~/.julia/packages/Nemo/tzyHK/src/antic/nf_elem.jl:1007 [6] mul_karatsuba(a::AbstractAlgebra.Generic.Poly{…}, b::AbstractAlgebra.Generic.Poly{…}) @ AbstractAlgebra ~/.julia/packages/AbstractAlgebra/34P8l/src/Poly.jl:567 [7] (a::AbstractAlgebra.Generic.Poly{AbsSimpleNumFieldElem}, b::AbstractAlgebra.Generic.Poly{AbsSimpleNumFieldElem}) @ Nemo ~/.julia/packages/Nemo/tzyHK/src/antic/nf_elem.jl:1007 [8] mul_karatsuba(a::AbstractAlgebra.Generic.Poly{…}, b::AbstractAlgebra.Generic.Poly{…}) @ AbstractAlgebra ~/.julia/packages/AbstractAlgebra/34P8l/src/Poly.jl:564 [9] (a::AbstractAlgebra.Generic.Poly{AbsSimpleNumFieldElem}, b::AbstractAlgebra.Generic.Poly{AbsSimpleNumFieldElem}) @ Nemo ~/.julia/packages/Nemo/tzyHK/src/antic/nf_elem.jl:1007 [10] mul_karatsuba(a::AbstractAlgebra.Generic.Poly{…}, b::AbstractAlgebra.Generic.Poly{…}) @ AbstractAlgebra ~/.julia/packages/AbstractAlgebra/34P8l/src/Poly.jl:564 [11] (a::AbstractAlgebra.Generic.Poly{AbsSimpleNumFieldElem}, b::AbstractAlgebra.Generic.Poly{AbsSimpleNumFieldElem}) @ Nemo ~/.julia/packages/Nemo/tzyHK/src/antic/nf_elem.jl:1007 [12] mul_karatsuba(a::AbstractAlgebra.Generic.Poly{…}, b::AbstractAlgebra.Generic.Poly{…}) @ AbstractAlgebra ~/.julia/packages/AbstractAlgebra/34P8l/src/Poly.jl:551 [13] (a::AbstractAlgebra.Generic.Poly{AbsSimpleNumFieldElem}, b::AbstractAlgebra.Generic.Poly{AbsSimpleNumFieldElem}) @ Nemo ~/.julia/packages/Nemo/tzyHK/src/antic/nf_elem.jl:1007 [14] mul_karatsuba(a::AbstractAlgebra.Generic.Poly{…}, b::AbstractAlgebra.Generic.Poly{…}) @ AbstractAlgebra ~/.julia/packages/AbstractAlgebra/34P8l/src/Poly.jl:551 [15] (a::AbstractAlgebra.Generic.Poly{AbsSimpleNumFieldElem}, b::AbstractAlgebra.Generic.Poly{AbsSimpleNumFieldElem}) @ Nemo ~/.julia/packages/Nemo/tzyHK/src/antic/nf_elem.jl:1007 [16] mul_karatsuba(a::AbstractAlgebra.Generic.Poly{…}, b::AbstractAlgebra.Generic.Poly{…}) @ AbstractAlgebra ~/.julia/packages/AbstractAlgebra/34P8l/src/Poly.jl:551 [17] (a::AbstractAlgebra.Generic.Poly{AbsSimpleNumFieldElem}, b::AbstractAlgebra.Generic.Poly{AbsSimpleNumFieldElem}) @ Nemo ~/.julia/packages/Nemo/tzyHK/src/antic/nf_elem.jl:1007 [18] -(a::AbstractAlgebra.Generic.FracFieldElem{…}, b::AbstractAlgebra.Generic.FracFieldElem{…}) @ AbstractAlgebra ~/.julia/packages/AbstractAlgebra/34P8l/src/Fraction.jl:246 [19] nemoFieldSub(a::Ptr{Nothing}, b::Ptr{Nothing}, cf::Ptr{Nothing}) @ Singular.libSingular ~/.julia/packages/Singular/lsYSW/src/libsingular/nemo/Fields.jl:111 [20] id_Quotient @ ~/.julia/packages/CxxWrap/5IZvn/src/CxxWrap.jl:624 [inlined] [21] quotient(I::Singular.sideal{Singular.spoly{…}}, J::Singular.sideal{Singular.spoly{…}}) @ Singular ~/.julia/packages/Singular/lsYSW/src/ideal/ideal.jl:560 [22] quotient(I::MPolyIdeal{AbstractAlgebra.Generic.MPoly{…}}, J::MPolyIdeal{AbstractAlgebra.Generic.MPoly{…}}) @ Oscar ~/.julia/dev/Oscar/src/Rings/mpoly-ideals.jl:290 [23] top-level scope @ REPL[12]:1 Some type information was truncated. Use show(err) to see complete types. — Reply to this email directly, view it on GitHub https://github.com/oscar-system/Oscar.jl/issues/4213#issuecomment-2418866636, or unsubscribe https://github.com/notifications/unsubscribe-auth/AASSXEXLNKACVQXHUS5Y2O3Z35WWNAVCNFSM6AAAAABQCDWJNSVHI2DSMVQWIX3LMV43OSLTON2WKQ3PNVWWK3TUHMZDIMJYHA3DMNRTGY. You are receiving this because you were mentioned.

fingolfin commented 1 month ago

@ederc will have a look (once he has some time)

fingolfin commented 1 month ago

Some more discussion: we should use modular GB computations; we have the code (in multiple places: Oscar/Julia; msolve; Singular) but we are not using it here (and also in some other places). Some discussion was had here (esp. with @ederc @fieker @jankoboehm) that we should change this and hopefully they will look into it :-)

simonbrandhorst commented 3 weeks ago

Let me just mention that this week someone in slack asked about a standard basis over QQ(a)(t)[x,y,z] (with a algebraic and t transcendental over QQ), i.e. a rational function field over a number field. Hence, functionality for such coefficient rings seems to be of wider interest.

simonbrandhorst commented 1 week ago

Could be related to #232.