Upgrade to Sirocco 2.1.0 and improve fundamental group of curves

miguelmarco commented 3 years ago

libsirocco 2.1.0 provides the option of treating separately the factors of a polynomial, speeding up homotopy continuation for reducible curves.

In this ticket, I also address a possible issue with the selection of paths to compute the braid monodromy of a curve. The preexisting code used floating points approximations, without a complete proof of the correctness of the results. Here we use rationals, which are slower, but much more robust. In some cases, this slowdown can be compensated by the improvements in sirocco.

Finally, it includes the option of getting the braid monodromy as a list of braids (some colleagues have been asking for this feature for a while).

CC: @tscrim @soehms @sagetrac-pportilla @baldursigdurs @enriqueartal @slel

Component: algebraic geometry

Author: Miguel Marco

Branch/Commit: 1145168

Reviewer: Travis Scrimshaw

Issue created by migration from https://trac.sagemath.org/ticket/32090

miguelmarco commented 3 years ago

Branch: u/mmarco/sirocco_braid_monodromy

7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 3 years ago

Branch pushed to git repo; I updated commit sha1. New commits:

`952d654`	`Add interface to new sirocco functions`
`bdc7223`	`partial reqrite for the new sirocco version`
`8f20e1f`	`Add braid monodromy`
`f7c1491`	`update to newer sirocco version`

7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 3 years ago

Commit: f7c1491

tscrim commented 3 years ago

Reviewer: Travis Scrimshaw

tscrim commented 3 years ago

comment:4

+1 to moving to rationals and exact arithmetic.

cpdef functions will need doctests. Same for def roots_interval_cached.

Code formatting versus latex:

-no other root of `f`, nor any root of the polynomials in `factors`,
+no other root of ``f``, nor any root of the polynomials in ``factors``,

 @cached_function
 def corrected_voronoi_diagram(points):
     r"""
-    compute a Voronoi diagram of a set of points with rational coordinates, such
+    Compute a Voronoi diagram of a set of points with rational coordinates, such
     that the given points are granted to lie one in each bounded region.

     INPUT:

-    - ``points`` -- a list of complex numbers.
+    - ``points`` -- a list of complex numbers

 def orient_circuit(circuit):
     r"""
-    reverses a circuit if it goes clockwise
+    Reverses a circuit if it goes clockwise; otherwise leaves it unchanged.

     INPUT:

-    - `circuit` --  a circuit in the graph of a Voronoi Diagram, given
-        by a list of edges
+    - ``circuit`` -- a circuit in the graph of a Voronoi diagram, given
+      by a list of edges

-    OUTPUT: The same circuit if it goes counterclockwise, and its reverse otherwise
+    OUTPUT:
+
+    The same circuit if it goes counterclockwise, and its reverse otherwise.

(Although you don't really need the OUTPUT: here since it is obvious from the 1-line description.)

 def geometric_basis(G, E, p):
     r"""
     Return a geometric basis, based on a vertex.

     INPUT:

-    - ``G`` -- The graph of the bounded regions of a Voronoi Diagram
+    - ``G`` -- the graph of the bounded regions of a Voronoi diagram

-    - ``E`` -- The subgraph of `G` formed by the edges that touch an unbounded
-    region
+    - ``E`` -- the subgraph of ``G`` formed by the edges that touch an
+      unbounded region

-    - ``p`` -- A vertex of `E`
+    - ``p`` -- a vertex of ``E``

-raise ValueError("can't compute a correct path")
+raise ValueError("unable to compute a correct path")

 def braid_monodromy(f):
     r"""
     Compute the braid monodromy of a projection of the curve defined by a polynomial

     INPUT:

     - ``f`` -- a polynomial with two variables, over a number field with an embedding
-    in the complex numbers.
+      in the complex numbers

     OUTPUT:

     A list of braids. The braids correspond to paths based in the same point;
     each of this paths is the conjugated of a loop around one of the points
-    in the discriminant of the projection of `f`.
+    in the discriminant of the projection of ``f``.

-    NOTE:
+    .. NOTE::

-    The projection over the `x` axis is used if there are no vertical asymptotes.
-    Otherwise, a linear change of variables is done to fall into the previous case.
+        The projection over the `x` axis is used if there are no vertical asymptotes.
+        Otherwise, a linear change of variables is done to fall into the previous case.

You can do

-p = E.vertices()[0]
+p = next(E.vertex_iterator())

to get one vertex without building the entire list.

Two places:

-not (g, v) in roots_interval_cache.keys()
+(g, v) not in roots_interval_cache

Also, the number of blanklines in a few places is a little strange.

7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 3 years ago

Branch pushed to git repo; I updated commit sha1. New commits:

d761ca3 Address reveiwer's corrections, and add method in affine_curve

7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 3 years ago

Changed commit from f7c1491 to d761ca3

miguelmarco commented 3 years ago

comment:6

When I run this with SAGE_NUM_THREADS bigger than one, I get the following error:

sage: A.<x,y> = AffineSpace(QQ,2)                                                                                                                                                                   
sage: C = A.curve((x^2-y^3)*(y-1))                                                                                                                                                                  
sage: C.braid_monodromy()                                                                                                                                                                           
---------------------------------------------------------------------------
ChildProcessError                         Traceback (most recent call last)
<ipython-input-6-f0f066e7f668> in <module>
----> 1 C.braid_monodromy()

~/sage/local/lib/python3.7/site-packages/sage/schemes/curves/affine_curve.py in braid_monodromy(self)
   1771                                       " to the algebraic field")
   1772         f = self.defining_polynomial()
-> 1773         return braid_monodromy(f)
   1774 
   1775 

~/sage/local/lib/python3.7/site-packages/sage/schemes/curves/zariski_vankampen.py in braid_monodromy(f)
    870     braidscomputed = braid_in_segment([(gfac, seg[0], seg[1]) for seg in segs])
    871     segsbraids = dict()
--> 872     for braidcomputed in braidscomputed:
    873         seg = (braidcomputed[0][0][1], braidcomputed[0][0][2])
    874         beginseg = (QQ(seg[0].real()), QQ(seg[0].imag()))

~/sage/local/lib/python3.7/site-packages/sage/parallel/use_fork.py in __call__(self, f, inputs)
    190 
    191                     try:
--> 192                         pid = os.wait()[0]
    193                         cancel_alarm()
    194                         W = workers.pop(pid)

It only happens the first time I run it (after that, it works ok). It seems that something is going on with the parallel framework, but can't pinpoint it.

Any clue about what would that be?

7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 3 years ago

Changed commit from d761ca3 to c7edf95

7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 3 years ago

Branch pushed to git repo; I updated commit sha1. New commits:

c7edf95 Fix some doctests

tscrim commented 3 years ago

comment:9

Unfortunately I don't really know from a quick look. It might be that there is some other error that is happening in the child and it just isn't printing it correctly. It is strange it is working on the second try.

tscrim commented 3 years ago

comment:10

Also, you now have a merge conflict. :/

enriqueartal commented 3 years ago

comment:11

Maybe I did something wrong but I get an error: ModuleNotFoundError: No module named 'sage.libs.sirocco', even for fundamental group. There was also a difficulty for git pull with affine_curve.py.

I am doing it again since I rebased with develop and #31786 to avoid recompiling gcc in Fedora 34. This time without rebasing.

7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 3 years ago

Branch pushed to git repo; I updated commit sha1. New commits:

9205fa2 Several fixes

7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 3 years ago

Changed commit from c7edf95 to 9205fa2

miguelmarco commented 3 years ago

comment:14

I added/fixed the doctests, made fundamental group depend on braid monodromy (which produces zariski-vankampen presentations, and avoids code duplication). I also tried to track the problem with failing parallel computations the first time in each session...but didn't find the source. So I did an ugly hack via a try/except trick. It is horrible, but it seems to work.

Please test and review carefully, since there are a lot of potential corner cases that could produce subtle errors. I think I did manage to make sure they won't happen, but would be much safer to have more eyes looking.

7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 3 years ago

Changed commit from 9205fa2 to 41b89a1

7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 3 years ago

Branch pushed to git repo; I updated commit sha1. New commits:

`98c2ffd`	`Add interface to new sirocco functions`
`358e6d6`	`partial reqrite for the new sirocco version`
`f8cc3d5`	`Add braid monodromy`
`42a367c`	`update to newer sirocco version`
`f483ea9`	`Address reveiwer's corrections, and add method in affine_curve`
`16c0757`	`Fix some doctests`
`9982f46`	`Several fixes`
`fb9e76c`	`Merge branch 'u/mmarco/sirocco_braid_monodromy' of git://trac.sagemath.org/sage into t/32090/sirocco_braid_monodromy`
`41b89a1`	`Fix errors due to rebasing`

7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 3 years ago

Changed commit from 41b89a1 to 25fd72f

7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 3 years ago

Branch pushed to git repo; I updated commit sha1. New commits:

25fd72f Stronger check for Voronoi Diagram

tscrim commented 3 years ago

comment:18

I am a little worried about the global cache and things running in parallel since they are running in different processes. However, that won't cause the error above and it will likely mean that the cache is not working as effectively as it could. What might be related is calling a @parallel function within a @parallel function. That was not done before this ticket. It might be better to have a more direct implementation rather than using the @parallel, but since this is currently working, that could be a follow-up.

A few things I noticed that could offer improvements:

-            if not any([a.overlaps(b) for a,b in Subsets(intervals[f], 2)]):
-            intervals[f] = [r.interval(ComplexIntervalField(precision[f])) for r in y0sf]
+            CIFp = ComplexIntervalField(precision[f])
+            intervals[f] = [r.interval(CIFp) for r in y0sf]
+            if not any(a.overlaps(b) for a,b in itertools.combinations(intervals[f], 2)):

     global roots_interval_cache
-    if (f,x0) in roots_interval_cache.keys():
+    try:
         return roots_interval_cache[(f,x0)]
-    else:
+    except KeyError:
         result = roots_interval(f,x0)
         roots_interval_cache[(f,x0)] = result
         return result

-        diam = min([(CF(r)-CF(r0)).abs() for r0 in roots[:i]+roots[i+1:]])/divisor
+        diam = min((CF(r)-CF(r0)).abs() for r0 in roots[:i]+roots[i+1:]) / divisor

7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 3 years ago

Branch pushed to git repo; I updated commit sha1. New commits:

`b7484e2`	`Merge branch 'develop' into t/32090/sirocco_braid_monodromy`
`7c59e2b`	`Linting`

7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 3 years ago

Changed commit from 25fd72f to 7c59e2b

enriqueartal commented 3 years ago

comment:20

It works after rebasing with #31786 to avoid gcc package in Fedora 34

tscrim commented 3 years ago

comment:21

Any thoughts about comment:18 Miguel?

7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 3 years ago

Changed commit from 7c59e2b to 97cac42

7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 3 years ago

Branch pushed to git repo; I updated commit sha1. New commits:

`4d2882c`	`Merge branch 'develop' into sirocco`
`54c507e`	`Merge branch 'u/mmarco/sirocco_braid_monodromy' of git://trac.sagemath.org/sage into sirocco`
`97cac42`	`Some changes suggested by reviewer`

miguelmarco commented 3 years ago

comment:23

If I am not mistaken, current code does not call a @parallel function from a @parallel function.

I agree the current design is hacky, but couldn't find another way to achieve both cache and parallelism in a less hacky way. (Maybe encapsulating it in a specific class for that, but that does sound overkill).

What would you suggest?

tscrim commented 3 years ago

comment:24

Replying to @miguelmarco:

If I am not mistaken, current code does not call a @parallel function from a @parallel function.

You have braid_in_segment -> roots_interval_cached -(if not cached)-> roots_interval. Perhaps this never happens because you have fully populated the cache, but this is not obvious to me.

I agree the current design is hacky, but couldn't find another way to achieve both cache and parallelism in a less hacky way. (Maybe encapsulating it in a specific class for that, but that does sound overkill).

What would you suggest?

You would have to roll your own calls to Python's multiprocessing module. For now this should be okay as that could take a bit of work to do and it likely won't have a major impact. Note that if the cache is not fully computed, you would have to call roots_interval for the same input multiple times as the cache is not shared across different processes (only what it was initially at when everything was forked).

7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 3 years ago

Branch pushed to git repo; I updated commit sha1. New commits:

5557c79 Explicitely populate cache

7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 3 years ago

Changed commit from 97cac42 to 5557c79

miguelmarco commented 3 years ago

comment:26

I have Added a function to explicitely populate the cache before the parallel call. It still uses the cached version of the function inside the parallel calls, but just as a safeguard: all the calls should be cached.

tscrim commented 3 years ago

comment:27

Thanks. This will be good for now. It would be nice to figure out why we get that child process error (I confirmed it still exists with the current change), but this will work for now.

slel commented 3 years ago

Description changed:

--- 
+++ 
@@ -1,5 +1,5 @@
-libsirocco 2.1.0 provides the option of treating separatedly the factors of a polynomial, which would make homotopy continuation faster in the case of reducible curves.
+libsirocco 2.1.0 provides the option of treating separately the factors of a polynomial, speeding up homotopy continuation for reducible curves.

-In this ticket, I also address a possible issue with the selection of paths to compute the braid monodromy of a curve. The preexisting code used floating points approximations, without a complete proof of the correctness of the results. Here we use rationals, which are slower, but much more robust (depending on the case, this slowness can be compensated by the improvements in sirocco.
+In this ticket, I also address a possible issue with the selection of paths to compute the braid monodromy of a curve. The preexisting code used floating points approximations, without a complete proof of the correctness of the results. Here we use rationals, which are slower, but much more robust. In some cases, this slowdown can be compensated by the improvements in sirocco.

 Finally, it includes the option of getting the braid monodromy as a list of braids (some colleagues have been asking for this feature for a while).

vbraun commented 3 years ago

comment:30

sage -t --long --warn-long 44.1 --random-seed=0 src/sage/libs/sirocco.pyx
**********************************************************************
File "src/sage/libs/sirocco.pyx", line 41, in sage.libs.sirocco.contpath_mp
Failed example:
    from sage.libs.sirocco import contpath_mp
Exception raised:
    Traceback (most recent call last):
      File "/home/release/Sage/local/lib64/python3.9/site-packages/sage/doctest/forker.py", line 718, in _run
        self.compile_and_execute(example, compiler, test.globs)
      File "/home/release/Sage/local/lib64/python3.9/site-packages/sage/doctest/forker.py", line 1137, in compile_and_execute
        exec(compiled, globs)
      File "<doctest sage.libs.sirocco.contpath_mp[0]>", line 1, in <module>
        from sage.libs.sirocco import contpath_mp
    ModuleNotFoundError: No module named 'sage.libs.sirocco'
**********************************************************************

mkoeppe commented 3 years ago

comment:31

The doctests need more of # optional - sirocco

tscrim commented 3 years ago

Changed commit from 5557c79 to 6e16034

tscrim commented 3 years ago

Changed branch from u/mmarco/sirocco_braid_monodromy to public/packages/sirocco_braid_monodromy-32090

tscrim commented 3 years ago

comment:32

This should take care of it.

New commits:

`b327d32`	`Merge branch 'u/mmarco/sirocco_braid_monodromy' of git://trac.sagemath.org/sage into u/mmarco/sirocco_braid_monodromy`
`6e16034`	`Adding more optional sirocco markers.`

miguelmarco commented 3 years ago

comment:33

So, do you think can we set a positive review?

tscrim commented 2 years ago

comment:34

Yes, I think so.

vbraun commented 2 years ago

comment:35

File "src/sage/schemes/curves/zariski_vankampen.py", line 334, in sage.schemes.curves.zariski_vankampen.followstrand
Failed example:
    followstrand(f, [fup, fdown], x0, x1, -1.0)
Exception raised:
    Traceback (most recent call last):
      File "/home/release/Sage/local/lib64/python3.9/site-packages/sage/doctest/forker.py", line 694, in _run
        self.compile_and_execute(example, compiler, test.globs)
      File "/home/release/Sage/local/lib64/python3.9/site-packages/sage/doctest/forker.py", line 1088, in compile_and_execute
        exec(compiled, globs)
      File "<doctest sage.schemes.curves.zariski_vankampen.followstrand[6]>", line 1, in <module>
        followstrand(f, [fup, fdown], x0, x1, -RealNumber('1.0'))
    NameError: name 'followstrand' is not defined
**********************************************************************
1 item had failures:
   1 of   8 in sage.schemes.curves.zariski_vankampen.followstrand
    [100 tests, 1 failure, 0.24 s]
----------------------------------------------------------------------
sage -t --long --warn-long 43.0 --random-seed=93097112693405690428202520811084416543 src/sage/schemes/curves/zariski_vankampen.py  # 1 doctest failed
----------------------------------------------------------------------

enriqueartal commented 2 years ago

comment:37

I have the branch installed in my laptop (singular) and in the computer in the office (zariski) in both cases the branch is merged with the last develop branch. In singular the same test as above passed with no problem, in zariski it gave the same error. After reinstalling sirocco-2.1.0 (which was installed) the test passed. It was not in the mirrors I got it from https://github.com/miguelmarco/SIROCCO2/releases/download/2.1.0/libsirocco-2.1.0.tar.gz

7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 2 years ago

Branch pushed to git repo; I updated commit sha1. New commits:

`4818969`	`Merge branch 'public/packages/sirocco_braid_monodromy-32090' of git://trac.sagemath.org/sage into public/packages/sirocco_braid_monodromy-32090`
`1145168`	`One last # optional - sirocco tag.`

7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 2 years ago

Changed commit from 6e16034 to 1145168

tscrim commented 2 years ago

comment:39

Just a missing # optional - sirocco tag. Now fully tested both with and without sirocco installed.

vbraun commented 2 years ago

Changed branch from public/packages/sirocco_braid_monodromy-32090 to 1145168

sagemath / sage

Upgrade to Sirocco 2.1.0 and improve fundamental group of curves #32090