Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

Sign up for GitHub

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Jump to bottom

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

Open
simonbrandhorst opened this issue Oct 16, 2024 · 8 comments
Open

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

simonbrandhorst opened this issue Oct 16, 2024 · 8 comments
Labels
enhancement New feature or request optimization Simpler/more performant code or more/better tests

Comments

@simonbrandhorst
Copy link
Collaborator

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
@simonbrandhorst simonbrandhorst added enhancement New feature or request optimization Simpler/more performant code or more/better tests labels Oct 16, 2024
@wdecker
Copy link
Collaborator

wdecker commented Oct 16, 2024 via email

@simonbrandhorst
Copy link
Collaborator Author

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
Copy link
Collaborator Author

simonbrandhorst commented Oct 17, 2024 •
edited
Loading

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
Copy link
Member

This seems to be similar to #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
Copy link
Collaborator

thofma commented Oct 17, 2024

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
Copy link
Collaborator

wdecker commented Oct 17, 2024 via email

@fingolfin
Copy link
Member

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

@fingolfin fingolfin removed the triage label Oct 23, 2024
@fingolfin
Copy link
Member

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 :-)

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Assignees
No one assigned
Labels
enhancement New feature or request optimization Simpler/more performant code or more/better tests
Projects
None yet
Milestone
No milestone
Development

No branches or pull requests
5 participants
@fingolfin @wdecker @thofma @lgoettgens @simonbrandhorst