[ToricVarieties] Fix for is_effective of toric divisor class

[HereAround]

So far, the check is_effective of a divisor_class proceeded as follows:

• Compute one (!) (torus-invariant) divisor D in the given divisor class [D].
• Express this divisor D as linear combination of the torus-invariant prime divisor, a.k.a. those associated to the rays.
• Return true if all coefficients in this linear combination are non-negative and otherwise false.

The trouble with this approach is that we may pick a divisor D in the given divisor class which involves a negative multiple of one (or even multiple) torus-invariant prime divisors. Therefore, the correct criterion is to verify that D is linearly equivalent to an effective divisor.

To fix this, I propose a different approach: [D] is effective iff O_(X_Sigma)([D]) has at least one global section.

[HereAround]

@lkastner Is this PR good to be merged?

[lkastner]

I wanted to do a runtime analysis of this, but I am not done yet.

In general I thought that taking all torus-invariant divisors linearly equivalent to a given one should be some affine space. Then one intersects this with the positive orthant to figure out whether the divisor class has an effective representative. This is the runtime I want to compare to.

[HereAround]

I wanted to do a runtime analysis of this, but I am not done yet.

In general I thought that taking all torus-invariant divisors linearly equivalent to a given one should be some affine space. Then one intersects this with the positive orthant to figure out whether the divisor class has an effective representative. This is the runtime I want to compare to.

I see your point. In fact, I believe that the "intersection gymnastics" will likely be superior to my fix. (You can kill cohomCalg, which computes the basis of global sections, if you look at a toric variety with a very large number of homogeneous variables in the Cox ring.)

(To be honest: I was simply too lazy to code the intersection approach as the global section approach seemed sufficient for all that we currently have in OSCAR.)

[lkastner]

I tried the following:

function is_effective_tmp(tdc::ToricDivisorClass)
   amb = toric_variety(tdc)
   pi = matrix(map_from_torusinvariant_weil_divisor_group_to_class_group(amb))       
   coeffs = coefficients(toric_divisor(tdc))
   P = polyhedron((-identity_matrix(QQ, nrows(pi)), zeros(QQ, nrows(pi))), (transpose(pi), transpose(pi)*coeffs))
   is_feasible(P)
end

and then benchmarked it. Then I got:

julia> @benchmark is_effective(ac)
BenchmarkTools.Trial: 10000 samples with 998 evaluations.
 Range (min … max):  14.711 ns … 41.884 ns  ┊ GC (min … max): 0.00% … 0.00%
 Time  (median):     16.014 ns              ┊ GC (median):    0.00%
 Time  (mean ± σ):   16.661 ns ±  1.913 ns  ┊ GC (mean ± σ):  0.00% ± 0.00%

       █             ▂                                         
  ▃▇▄▃▄█▅▇▆▂▄▁▁▂▄▅▂▁▃█▆▂▄▂▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁ ▂
  14.7 ns         Histogram: frequency by time        24.3 ns <

 Memory estimate: 0 bytes, allocs estimate: 0.

julia> @benchmark is_effective_tmp(ac)
BenchmarkTools.Trial: 814 samples with 1 evaluation.
 Range (min … max):  5.469 ms … 29.513 ms  ┊ GC (min … max): 0.00% … 0.00%
 Time  (median):     5.923 ms              ┊ GC (median):    0.00%
 Time  (mean ± σ):   6.137 ms ±  1.080 ms  ┊ GC (mean ± σ):  0.00% ± 0.00%

   ▂▆█▇▄▇▅▄▄                                                  
  ▅██████████▇▅▄▄▄▄▄▄▃▃▃▃▄▃▃▃▃▂▃▂▃▂▃▃▁▂▂▂▃▂▃▂▂▁▁▁▁▁▁▁▁▁▁▁▁▁▂ ▃
  5.47 ms        Histogram: frequency by time        9.19 ms <

 Memory estimate: 34.93 KiB, allocs estimate: 2362.

For the example you put in the test. So lets go ahead with your solution.

[lkastner]

Ok, accounting for the @attr I get the following:

julia> function f1()
          test_space = normal_toric_variety(cs, rs)
          ac = anticanonical_divisor_class(test_space)
          return is_effective(ac)
       end
f1 (generic function with 1 method)

julia> @benchmark f1()
BenchmarkTools.Trial: 40 samples with 1 evaluation.
 Range (min … max):  116.167 ms … 146.484 ms  ┊ GC (min … max): 0.00% … 0.00%
 Time  (median):     122.440 ms               ┊ GC (median):    0.00%
 Time  (mean ± σ):   125.523 ms ±   9.047 ms  ┊ GC (mean ± σ):  0.00% ± 0.00%

  ▁▄▄▄ ▁  ▁   █         ▁             ▁                       ▄  
  ████▁█▆▆█▁▁▁█▆▆▁▁▆▁▆▁▆█▆▁▁▁▁▆▆▆▁▁▆▁▁█▁▁▁▁▁▁▁▁▆▁▁▁▁▁▁▁▁▁▁▁▁▆▁█ ▁
  116 ms           Histogram: frequency by time          146 ms <

 Memory estimate: 1.91 MiB, allocs estimate: 49469.

julia> function f2() 
          test_space = normal_toric_variety(cs, rs)
          ac = anticanonical_divisor_class(test_space)
          return is_effective_tmp(ac)
       end
f2 (generic function with 1 method)

julia> @benchmark f2()
BenchmarkTools.Trial: 48 samples with 1 evaluation.
 Range (min … max):   98.140 ms … 118.047 ms  ┊ GC (min … max): 0.00% … 0.00%
 Time  (median):     105.138 ms               ┊ GC (median):    0.00%
 Time  (mean ± σ):   105.364 ms ±   5.135 ms  ┊ GC (mean ± σ):  0.00% ± 0.00%

   ▃ ▃▃█   ▃▃         ▃ ▃▃      ▃ █▃                             
  ▇█▁███▇▇▇██▇▁▇▇▁▁▁▇▇█▁██▁▁▇▇▇▁█▇██▁▁▇▇▁▁▇▇▇▁▁▁▁▇▁▁▁▁▇▁▁▇▁▁▁▁▇ ▁
  98.1 ms          Histogram: frequency by time          118 ms <

 Memory estimate: 178.27 KiB, allocs estimate: 11752.

What do you think about my variant @HereAround ? Does it look correct?

[lkastner]

A problem could be that this only shows effectiveness over QQ, i.e. there might still not be a divisor with positive integral coefficients that is linearly equivalent to the input.

[HereAround]

A problem could be that this only shows effectiveness over QQ, i.e. there might still not be a divisor with positive integral coefficients that is linearly equivalent to the input.

I am afraid this indeed is a problem. The code should work over ZZ. (Details exchanged on slack.)

[HereAround]

A few more tests would be nice though. Some standard examples.

The test added here returns false with the current OSCAR master, despite this divisor class actually being effective. Hence, the is_effective test for this divisor must return true. This might thus be a good check?

In addition, the tests for toric varieties execute is_effective for toric divisor classes in the following places:

• toric_divisor_classes.jl: @test is_effective(DC7) == true
• toric_divisor_classes.jl: @test is_effective(DC8) == false

Two additional executions in the doc tests (unless I am mistaken). Do you think we need more tests?

[codecov[bot]]

Codecov Report

All modified and coverable lines are covered by tests :white_check_mark:

Project coverage is 81.34%. Comparing base (3ea7272) to head (e560852). Report is 44 commits behind head on master.

Additional details and impacted files

@@            Coverage Diff             @@
##           master    #3668      +/-   ##
==========================================
- Coverage   82.89%   81.34%   -1.56%     
==========================================
  Files         577      577              
  Lines       78301    78618     +317     
==========================================
- Hits        64908    63952     -956     
- Misses      13393    14666    +1273     

Files	Coverage Δ
...y/ToricVarieties/ToricDivisorClasses/properties.jl	100.00% <100.00%> (ø)

... and 89 files with indirect coverage changes

[HereAround]

Thank you @lkastner !