Opened 6 years ago
Closed 6 years ago
#21045 closed enhancement (fixed)
Implement ZariskiVanKampen method to compute fundamental groups of complements of plane curves.
Reported by:  Miguel Marco  Owned by:  

Priority:  major  Milestone:  sage8.0 
Component:  algebraic geometry  Keywords:  
Cc:  Grayson Jorgenson, Ben Hutz, Jorge Caravantes, Travis Scrimshaw  Merged in:  
Authors:  Miguel Marco  Reviewers:  Travis Scrimshaw 
Report Upstream:  N/A  Work issues:  
Branch:  d0b297e (Commits, GitHub, GitLab)  Commit:  d0b297e09603bc2844c2b6c147d0c133f2f0cf6a 
Dependencies:  Stopgaps: 
Description (last modified by )
This ticket implements the computation of the fundamental group of the complement of a plane (affine or projective) curve over the rationals or number fields with an embedding in QQbar (in theory it could be done for more general fields, but most likely wouldn't be practical).
Some use examples:
sage: A.<x,y> = AffineSpace(QQ, 2) sage: C = A.curve(y^2  x^3  x^2) sage: C.fundamental_group() Finitely presented group < x0  >
sage: a = QQ[x](x^2+5).roots(QQbar)[0][0] sage: a 2.236067977499790?*I sage: F = NumberField(a.minpoly(), 'a', embedding=a) sage: P.<x,y,z> = ProjectiveSpace(F, 2) sage: F.inject_variables() Defining a sage: C = P.curve(x^2 + a * y^2) sage: C.fundamental_group() Finitely presented group < x0  >
It relies on version 2 of the SIROCCO library [1] that performs a certified root continuation method specifically tailored for this task.
This same ticket implements the inclusion of Sirocco as an optional package (so it must be installed in order for the functinality to be available). The tarball is available in [2].
Attachments (1)
Change History (20)
Changed 6 years ago by
Attachment:  libsirocco1.1.tar.gz added 

comment:1 Changed 6 years ago by
Description:  modified (diff) 

Add link to Sirocco library in ticket description.
comment:2 Changed 6 years ago by
Branch:  → u/mmarco/implement_zariski_vankampen_method_to_compute_fundamental_groups_of_complements_of_plane_curves_ 

comment:3 Changed 6 years ago by
Authors:  → Miguel Marco 

Cc:  Grayson Jorgenson Ben Hutz added 
Commit:  → 20f7bb2e46f7dd0d646765a8b85c68fb93cca7ca 
Status:  new → needs_review 
New commits:
20f7bb2  Add sirocco package and zariskvankampen implementation

comment:4 Changed 6 years ago by
Status:  needs_review → needs_work 

This does no longer merge with current sage releases.
comment:5 Changed 6 years ago by
Commit:  20f7bb2e46f7dd0d646765a8b85c68fb93cca7ca → bb898e46393284489cb0858205ae27d6457bb69c 

Branch pushed to git repo; I updated commit sha1. New commits:
6e26772  Add sirocco package and zariskvankampen implementation

4562507  Update to sirocco version 2.0

fc3f6b3  Adapt optional extension to c++

97a7598  Fixed imports

bb898e4  Merge branch 'u/mmarco/implement_zariski_vankampen_method_to_compute_fundamental_groups_of_complements_of_plane_curves_' of git://trac.sagemath.org/sage into t/21045/implement_zariski_vankampen_method_to_compute_fundamental_groups_of_complements_of_plane_curves_

comment:6 Changed 6 years ago by
Cc:  Jorge Caravantes Travis Scrimshaw added 

Description:  modified (diff) 
Milestone:  sage7.3 → sage8.0 
Status:  needs_work → needs_review 
Type:  PLEASE CHANGE → enhancement 
comment:7 Changed 6 years ago by
I think it is ready for review.
Note that in order for the functionality to be available, the package sirocco 2 must be installed. The tarball must be downloaded and copied to the upstream directory.
Note also that currently the file name must be corrected (there is a superfluous underscore). I asked the webmaster to correct it.
comment:8 Changed 6 years ago by
The quick comments:
 For bullet points, you need to format them as:
 a really long line continues at the same starting point
 Is there a reason why
contpath_mp
andcontpath
are notcpdef
? Subsequently, they could have a specified return type? Forcontpath_mp
, you could fill in the list in a second for loop to avoid the list comprehension.  For
contpath
, do you want to force input types?  Error messages should start with a lower case.
 Do you want to make zariski_vankampen.py a Cython file for speed?
 You don't need to do this
j = <int>i
; therange
will give youint
, especially if youcdef int i
. res
does not seem to be used incontpath_mp
. I think there are better ways to construct a new (unset)
RealField
(incontpath_mp
), but I don't remember how to do so offhand. You should also create the parent outside of the for loop. fundamental_group
appears twice inaffine_curve.py
.
comment:9 Changed 6 years ago by
Commit:  bb898e46393284489cb0858205ae27d6457bb69c → f3d12bc1a675ceba07e970602e0835bef7ce1f16 

Branch pushed to git repo; I updated commit sha1. New commits:
f3d12bc  Some review fixes.

comment:10 Changed 6 years ago by
Thanks for the review.
Replying to tscrim:
The quick comments:
 For bullet points, you need to format them as:
 a really long line continues at the same starting point
Fixed (I think I didn't miss anyone).
 Is there a reason why
contpath_mp
andcontpath
are notcpdef
? Subsequently, they could have a specified return type? Forcontpath_mp
, you could fill in the list in a second for loop to avoid the list comprehension.
There is a reason for that: I didn't know about cpdef until now.
About the return type, it should be list[list[RealNumber?]], but that doesn't seem to work. list[list] works though.
What is exactly the problem with list comprehension?
 For
contpath
, do you want to force input types?
Done, but I don't see any advantage in doing so. If there is a speedup, it is negligible.
 Error messages should start with a lower case.
Fixed.
 Do you want to make zariski_vankampen.py a Cython file for speed?
I tried it, but got some error messages related to the use of parallel functions.
Anyways, I don't expect a significant speedup by compiling it: the bottlenecks are calls to external functions (mainly discriminant computation and contpath calls). The only part that could benefit from compilation is the braid reconstruction from the piecewise linear paths, but my experience shows that this time is very small compared to the computation of the paths themselves.
I could try to cythonize it, but would need some help.
 You don't need to do this
j = <int>i
; therange
will give youint
, especially if youcdef int i
.
Fixed.
res
does not seem to be used incontpath_mp
.
Fixed.
 I think there are better ways to construct a new (unset)
RealField
(incontpath_mp
), but I don't remember how to do so offhand. You should also create the parent outside of the for loop.
I tried several ways and this was the one that worked. If you remember a better way, please let me know.
fundamental_group
appears twice inaffine_curve.py
.
Fixed.
comment:11 Changed 6 years ago by
I can do a first attempt at cythonizing. Do you have a good test case that is not too slow nor too fast to do profiling on to see where the current bottlenecks are?
The reason I bring up the list comprehension is Cython cannot handle them in c(p)def (maybe just cpdef) functions.
comment:12 Changed 6 years ago by
Commit:  f3d12bc1a675ceba07e970602e0835bef7ce1f16 → e7796fb6c8b631e8e63b8b807c3ebaf4a1e8cdc7 

Branch pushed to git repo; I updated commit sha1. New commits:
e7796fb  Fixed some doctests, and bug when variables are not x,y

comment:13 Changed 6 years ago by
I fixed some doctest and a bug that prevented it to work when the variables where not x and y.
About nontrivial examples to test, here are two:
This one is a good example of the power of sirocco: this group is computed in a few seconds, and as far as I know, it has never been computed before (even though the curve has been explicitely studied)
sage: F = NumberField(QQ[x]('x^2+1'), 'I', embedding = QQbar(I)) sage: F.inject_variables() Defining I sage: P.<x,y,z> = ProjectiveSpace(F,2) sage: c = P.curve((4131/160000*I + 20493/640000)*x^4*y^2 + (21883/240000*I  243083/4320000)*x^3*y^3 + (4301/60000*I + 22393/1440000)*x^2*y^4 + (729/50000*I  145071/1600000)*x^4*y*z + (4391/400000*I + 92699/800000)*x^3*y^2*z + (20251/100000*I + 50513/900000)*x^2*y^3*z + (4301/18750*I  22393/450000)*x*y^4*z + (72171/4000000*I + 767637/16000000)*x^4*z^2 + (121131/1000000*I + 147717/1000000)*x^3*y*z^2 + (42633/125000*I  169493/375000)*x^2*y^2*z^2 + (6341/62500*I + 97183/562500)*x*y^3*z^2 + (8602/46875*I + 22393/562500)*y^4*z^2 + (1323/250000*I  167481/1000000)*x^3*z^3 + (3621/62500*I + 47037/250000)*x^2*y*z^3 + (5189/15625*I + 24559/125000)*x*y^2*z^3 + (14404/46875*I  80002/421875)*y^3*z^3 + (189/5000*I + 81/625)*x^2*z^4 + (177/1250*I  339/1250)*x*y*z^4 + (68/625*I + 253/1875)*y^2*z^4) sage: c.fundamental_group() Finitely presented group < x2, x56  x2^1*x56*(x2^1*x56^1)^3*x2*x56*x2^1*x56^1, (x56^1*x2^1)^2*x56*x2*x56^2*x2^1*x56^1*x2*x56*x2*x56^1, x56^1*x2^1*(x56*x2)^2*x56^1*x2^1*x56^1*x2*x56^2*x2*x56^1*x2^1*x56^1 >
This other one takes a couple of minutes in my laptop. It was the motivation for the writing of GAP3's VKCURVE package (which computes it in almost half an hour in the same computer):
sage: A.<x,y> = AffineSpace(QQ,2) sage: c = A.curve(746496+3732480*x3111936*x*y^293281756/27*x*y^4+58341596/27*x*y^6+7464960*x^2384*y^29334272*x^2*y^2 +17556484/27*x^2*y^4+43196/27*x^2*y^6+7464576*x^3756138248/81*x^3*y^2+192792964/81*x^3*y^4+16/81*x^3*y^6+3730944*x^4 139967996/81*y^484021416/27*x^4*y^2+82088/27*x^4*y^4+744192*x^5+43192/27*x^5*y^21720/27*x^5*y^4 124412/81*x^6 +777600800*y^6+95896/81*x^6*y^28/81*x^6*y^410364/27*x^74/27*x^7*y^2+4/27*x^88/81*y^84/27*x^8*y^2+4/81*x^9) Finitely presented group < x0, x21, x29, x41, x54  x29^1*x54^1*x29*x54*x29*x54^1, x41^1*x29*x41*x29*x41^1*x29^1, x29^1*x0*x29*x0*x29^1*x0^1, x21*x29*x21^1*x29^1*x21^1*x29, x41^1*x0^1*x41^1*x0*x41*x0, x54^1*x21^1*x54^1*x21*x54*x21, x41*x21*x41^1*x21^1*x41^1*x21, x21*x0*x21*x0^1*x21^1*x0^1, x41*x54*x41*x54^1*x41^1*x54^1, x54^1*x0^1*x54^1*x0*x54*x0, x41*x21*x29*x21^1*x41^1*x21*x29^1*x21^1, x41*x54*x41^1*x29*x54^1*x41^1*x54*x29^1, x21^1*x0*x54*x0^1*x21*x0*x54^1*x0^1, x0^1*x41*x21*x41^1*x0*x41*x21^1*x41^1, x21^1*x0*x41*x0^1*x21*x0*x41^1*x0^1, x21^1*x54^1*x0*x54*x21*x54^1*x0^1*x54, x29^1*x54^1*x0^1*x54*x29*x54^1*x0*x54, x29^1*x0*x54*x0^1*x29*x0*x54^1*x0^1, x29*x0^2*x29^1*x54^1*x29*x0^2*x29^1*x54, x29^1*x41*x54*x21*x41^1*x29*x41*x21^1*x54^1*x41^1, x0*x54^1*x41*x54*x0^1*x29^1*x21^1*x54^1*x41^1*x54*x21*x29, x29^1*x21^1*x29*x0*x41*x54*x21*x29*x21^1*x54^1*x41^1*x0^1, x41^1*x0^1*x21*x29*x0*x41*x54*x21*x0^1*x29^1*x21^1*x54^1, x0^1*x29^1*x21*x54^1*x29*x0*x29*x41*x54*x21^1*x29*x41^1*x54^1*x41^1, x41^1*x54^1*x29*x0^1*x41*x54*x21*x29*x21*x41^1*x0*x29^1*x21^1*x54^1, x21^1*x54^1*x29*x21^1*x41^1*x0*x41*x54*x0*x41^1*x0^1*x21*x29^1*x54, x54*x21*x29*x0*x29^1*x54*x21^1*x54^1*x41^1*x0^1*x29^1*x0*x41*x21^1, x41*x54*x21*x29*x0*x21^1*x29*x41*x21*x29^2*x21*x29^1*x21^1*x41^2*x0^1*x29^1*x21^1*x54^1*x41^1*x21^1, x29*x21^1*x0*x54^2*x41*x54*x21*x0*x29^1*x41*x0^1*x21^1*x0^2*x54^1*x41^1*x0^1*x29^1*x21^1*x29*x0^1*x21^2, x29*x41^1*x0*x41*(x21*x54)^2*x0*x54*x21*x0*x29^1*x21^1*x41*x54^1*x41^1*x29^1*(x29^1*x0^1)^2*x29^1*x54^1*x0^1*x21 >
I did some tests cythonizing some of the functions in zariski_vankampen.py
, and I could not observe any speedup at all. I don't think it will be worth the effort.
Are you sure about the list comprehension problem? It seems to work fine in this cpdef'ed function.
comment:14 Changed 6 years ago by
Branch:  u/mmarco/implement_zariski_vankampen_method_to_compute_fundamental_groups_of_complements_of_plane_curves_ → public/topology/zariski_van_kampen_plane_curves21045 

Commit:  e7796fb6c8b631e8e63b8b807c3ebaf4a1e8cdc7 → c55db609706d1f212d252f458067e00244822bbc 
Reviewers:  → Travis Scrimshaw 
I've hit that list comprehension problem before. *shrugs*
From doing some profiling, I agree that there is no real gain from the extra Cythonization.
I made some changes to improve the Cython generated code, removed trailing whitespace, cleaned up the documentation and imports, and some other misc tweaks. So the code should be slight improvement in speed, but likely marginal. Mainly it is cleaner code.
If my changes look good, then you can set a positive review (unless you can add an doctest to the functions in libs/sirocco.pyx
, but this is preferable).
New commits:
a170d3b  Merge branch 'u/mmarco/implement_zariski_vankampen_method_to_compute_fundamental_groups_of_complements_of_plane_curves_' of git://trac.sagemath.org/sage into public/topology/zariski_van_kampen_plane_curves21045

c55db60  Improving Cython code, removing whitespace, doc improvements.

comment:16 Changed 6 years ago by
Status:  positive_review → needs_work 

On 32bit
sage t long src/sage/schemes/curves/zariski_vankampen.py ********************************************************************** File "src/sage/schemes/curves/zariski_vankampen.py", line 196, in sage.schemes.curves.zariski_vankampen.segments Failed example: segments(disc) Expected: [(2.84740787203333  2.84740787203333*I, 2.14285714285714 + 1.11022302462516e16*I), (2.84740787203333 + 2.84740787203333*I, 2.14285714285714 + 1.11022302462516e16*I), (2.50000000000000 + 2.50000000000000*I, 1.26513881334184 + 2.19128470333546*I), (2.50000000000000 + 2.50000000000000*I, 2.50000000000000  2.50000000000000*I), (1.26513881334184 + 2.19128470333546*I, 0.000000000000000), (0.000000000000000, 1.26513881334184  2.19128470333546*I), (2.50000000000000  2.50000000000000*I, 1.26513881334184  2.19128470333546*I), (2.84740787203333 + 2.84740787203333*I, 1.26513881334184 + 2.19128470333546*I), (2.14285714285714 + 1.11022302462516e16*I, 0.000000000000000), (2.84740787203333  2.84740787203333*I, 1.26513881334184  2.19128470333546*I)] Got: [(2.84740787203333  2.84740787203333*I, 2.14285714285714 + 8.65735434729675e17*I), (2.84740787203333 + 2.84740787203333*I, 2.14285714285714 + 8.65735434729675e17*I), (2.50000000000000 + 2.50000000000000*I, 1.26513881334184 + 2.19128470333546*I), (2.50000000000000 + 2.50000000000000*I, 2.50000000000000  2.50000000000000*I), (1.26513881334184 + 2.19128470333546*I, 1.97324795392362e17), (1.97324795392362e17, 1.26513881334184  2.19128470333546*I), (2.50000000000000  2.50000000000000*I, 1.26513881334184  2.19128470333546*I), (2.84740787203333 + 2.84740787203333*I, 1.26513881334184 + 2.19128470333546*I), (2.14285714285714 + 8.65735434729675e17*I, 1.97324795392362e17), (2.84740787203333  2.84740787203333*I, 1.26513881334184  2.19128470333546*I)] ********************************************************************** 1 item had failures: 1 of 6 in sage.schemes.curves.zariski_vankampen.segments [37 tests, 1 failure, 1.29 s]
comment:17 Changed 6 years ago by
Commit:  c55db609706d1f212d252f458067e00244822bbc → d0b297e09603bc2844c2b6c147d0c133f2f0cf6a 

Branch pushed to git repo; I updated commit sha1. New commits:
f88a9db  Fixed optional doctests

f502374  Merge branch 'public/topology/zariski_van_kampen_plane_curves21045' of git://trac.sagemath.org/sage into t/21045/implement_zariski_vankampen_method_to_compute_fundamental_groups_of_complements_of_plane_curves_

d0b297e  Stablish numerical tolerance for doctests

comment:18 Changed 6 years ago by
Status:  needs_work → positive_review 

I guess that is a discrpancy on the rounding unit. Added some tolerance to the doctest.
comment:19 Changed 6 years ago by
Branch:  public/topology/zariski_van_kampen_plane_curves21045 → d0b297e09603bc2844c2b6c147d0c133f2f0cf6a 

Resolution:  → fixed 
Status:  positive_review → closed 
The sirocco library.