Implement Zariski-VanKampen method to compute fundamental groups of complements of plane curves. #21045

miguelmarco · 2016-07-18T08:42:37Z

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].

CC: @sagetrac-gjorgenson @bhutz @sagetrac-caravantes @tscrim

Component: algebraic geometry

Author: Miguel Marco

Branch/Commit: d0b297e

Reviewer: Travis Scrimshaw

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

The text was updated successfully, but these errors were encountered:

miguelmarco · 2016-07-18T08:43:04Z

Attachment: libsirocco-1.1.tar.gz

The sirocco library.

slel · 2016-07-18T09:07:00Z

comment:1

Add link to Sirocco library in ticket description.

miguelmarco · 2016-07-19T14:36:07Z

Branch: u/mmarco/implement_zariski_vankampen_method_to_compute_fundamental_groups_of_complements_of_plane_curves_

miguelmarco · 2016-07-19T15:11:23Z

Author: Miguel Marco

miguelmarco · 2016-07-19T15:11:23Z

New commits:

`20f7bb2`	`Add sirocco package and zarisk-vankampen implementation`

miguelmarco · 2016-07-19T15:11:23Z

Commit: 20f7bb2

cheuberg · 2017-01-12T06:48:43Z

comment:4

This does no longer merge with current sage releases.

sagetrac-git · 2017-04-07T23:45:12Z

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

`6e26772`	`Add sirocco package and zarisk-vankampen 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_`

sagetrac-git · 2017-04-07T23:45:12Z

Changed commit from 20f7bb2 to bb898e4

miguelmarco · 2017-04-08T19:03:15Z

comment:7

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.

tscrim · 2017-04-08T20:05:46Z

comment:8

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 and contpath are not cpdef? Subsequently, they could have a specified return type? For contpath_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; the range will give you int, especially if you cdef int i.
res does not seem to be used in contpath_mp.
I think there are better ways to construct a new (unset) RealField (in contpath_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 in affine_curve.py.

sagetrac-git · 2017-04-09T17:28:42Z

Changed commit from bb898e4 to f3d12bc

sagetrac-git · 2017-04-09T17:28:42Z

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

`f3d12bc`	`Some review fixes.`

miguelmarco · 2017-04-09T17:31:20Z

comment:10

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 and contpath are not cpdef? Subsequently, they could have a specified return type? For contpath_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; the range will give you int, especially if you cdef int i.

Fixed.

res does not seem to be used in contpath_mp.

Fixed.

I think there are better ways to construct a new (unset) RealField (in contpath_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 in affine_curve.py.

Fixed.

tscrim · 2017-04-10T00:35:36Z

comment:11

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.

sagetrac-git · 2017-04-10T17:39:59Z

Changed commit from f3d12bc to e7796fb

sagetrac-git · 2017-04-10T17:39:59Z

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

`e7796fb`	`Fixed some doctests, and bug when variables are not x,y`

miguelmarco · 2017-04-10T17:59:52Z

comment:13

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*x-3111936*x*y^2-93281756/27*x*y^4+58341596/27*x*y^6+7464960*x^2-384*y^2-9334272*x^2*y^2    +17556484/27*x^2*y^4+43196/27*x^2*y^6+7464576*x^3-756138248/81*x^3*y^2+192792964/81*x^3*y^4+16/81*x^3*y^6+3730944*x^4   -139967996/81*y^4-84021416/27*x^4*y^2+82088/27*x^4*y^4+744192*x^5+43192/27*x^5*y^2-1720/27*x^5*y^4 -124412/81*x^6   +777600800*y^6+95896/81*x^6*y^2-8/81*x^6*y^4-10364/27*x^7-4/27*x^7*y^2+4/27*x^8-8/81*y^8-4/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.

tscrim · 2017-04-16T23:55:17Z

Reviewer: Travis Scrimshaw

tscrim · 2017-04-16T23:55:17Z

Changed branch from u/mmarco/implement_zariski_vankampen_method_to_compute_fundamental_groups_of_complements_of_plane_curves_ to public/topology/zariski_van_kampen_plane_curves-21045

tscrim · 2017-04-16T23:55:17Z

comment:14

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_curves-21045`
`c55db60`	`Improving Cython code, removing whitespace, doc improvements.`

tscrim · 2017-04-16T23:55:17Z

Changed commit from e7796fb to c55db60

miguelmarco · 2017-04-17T10:43:42Z

comment:15

Thanks for the review!

vbraun · 2017-04-21T22:28:32Z

comment:16

On 32-bit

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.11022302462516e-16*I),
    (-2.84740787203333 + 2.84740787203333*I,
    -2.14285714285714 + 1.11022302462516e-16*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.11022302462516e-16*I, 0.000000000000000),
    (-2.84740787203333 - 2.84740787203333*I,
    1.26513881334184 - 2.19128470333546*I)]
Got:
    [(-2.84740787203333 - 2.84740787203333*I,
      -2.14285714285714 + 8.65735434729675e-17*I),
     (-2.84740787203333 + 2.84740787203333*I,
      -2.14285714285714 + 8.65735434729675e-17*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.97324795392362e-17),
     (1.97324795392362e-17, 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.65735434729675e-17*I, 1.97324795392362e-17),
     (-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]

sagetrac-git · 2017-04-22T14:56:47Z

Changed commit from c55db60 to d0b297e

sagetrac-git · 2017-04-22T14:56:47Z

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

`f88a9db`	`Fixed optional doctests`
`f502374`	`Merge branch 'public/topology/zariski_van_kampen_plane_curves-21045' 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`

miguelmarco · 2017-04-22T14:58:57Z

comment:18

I guess that is a discrpancy on the rounding unit. Added some tolerance to the doctest.

vbraun · 2017-04-25T17:40:18Z

Changed branch from public/topology/zariski_van_kampen_plane_curves-21045 to d0b297e

miguelmarco added this to the sage-7.3 milestone Jul 18, 2016

miguelmarco added c: algebraic geometry labels Jul 18, 2016

This comment has been minimized.

Sign in to view

miguelmarco added the s: needs review label Jul 19, 2016

cheuberg added s: needs work and removed s: needs review labels Jan 12, 2017

This comment has been minimized.

Sign in to view

miguelmarco added s: needs review and removed s: needs work labels Apr 8, 2017

miguelmarco modified the milestones: sage-7.3, sage-8.0 Apr 8, 2017

miguelmarco added s: positive review and removed s: needs review labels Apr 17, 2017

vbraun added s: needs work and removed s: positive review labels Apr 21, 2017

miguelmarco added s: positive review and removed s: needs work labels Apr 22, 2017

vbraun removed the s: positive review label Apr 25, 2017

vbraun closed this as completed in 3d51375 Apr 25, 2017

Provide feedback

Saved searches

Use saved searches to filter your results more quickly

Implement Zariski-VanKampen method to compute fundamental groups of complements of plane curves. #21045

Implement Zariski-VanKampen method to compute fundamental groups of complements of plane curves. #21045

miguelmarco commented Jul 18, 2016

miguelmarco commented Jul 18, 2016

This comment has been minimized.

slel commented Jul 18, 2016

miguelmarco commented Jul 19, 2016

miguelmarco commented Jul 19, 2016

miguelmarco commented Jul 19, 2016

miguelmarco commented Jul 19, 2016

cheuberg commented Jan 12, 2017

sagetrac-git mannequin commented Apr 7, 2017

sagetrac-git mannequin commented Apr 7, 2017

This comment has been minimized.

miguelmarco commented Apr 8, 2017

tscrim commented Apr 8, 2017

sagetrac-git mannequin commented Apr 9, 2017

sagetrac-git mannequin commented Apr 9, 2017

miguelmarco commented Apr 9, 2017

tscrim commented Apr 10, 2017

sagetrac-git mannequin commented Apr 10, 2017

sagetrac-git mannequin commented Apr 10, 2017

miguelmarco commented Apr 10, 2017

tscrim commented Apr 16, 2017

tscrim commented Apr 16, 2017

tscrim commented Apr 16, 2017

tscrim commented Apr 16, 2017

miguelmarco commented Apr 17, 2017

vbraun commented Apr 21, 2017

sagetrac-git mannequin commented Apr 22, 2017

sagetrac-git mannequin commented Apr 22, 2017

miguelmarco commented Apr 22, 2017

vbraun commented Apr 25, 2017

Implement Zariski-VanKampen method to compute fundamental groups of complements of plane curves. #21045

Implement Zariski-VanKampen method to compute fundamental groups of complements of plane curves. #21045

Comments

miguelmarco commented Jul 18, 2016

miguelmarco commented Jul 18, 2016

This comment has been minimized.

slel commented Jul 18, 2016

miguelmarco commented Jul 19, 2016

miguelmarco commented Jul 19, 2016

miguelmarco commented Jul 19, 2016

miguelmarco commented Jul 19, 2016

cheuberg commented Jan 12, 2017

sagetrac-git mannequin commented Apr 7, 2017

sagetrac-git mannequin commented Apr 7, 2017

This comment has been minimized.

miguelmarco commented Apr 8, 2017

tscrim commented Apr 8, 2017

sagetrac-git mannequin commented Apr 9, 2017

sagetrac-git mannequin commented Apr 9, 2017

miguelmarco commented Apr 9, 2017

tscrim commented Apr 10, 2017

sagetrac-git mannequin commented Apr 10, 2017

sagetrac-git mannequin commented Apr 10, 2017

miguelmarco commented Apr 10, 2017

tscrim commented Apr 16, 2017

tscrim commented Apr 16, 2017

tscrim commented Apr 16, 2017

tscrim commented Apr 16, 2017

miguelmarco commented Apr 17, 2017

vbraun commented Apr 21, 2017

sagetrac-git mannequin commented Apr 22, 2017

sagetrac-git mannequin commented Apr 22, 2017

miguelmarco commented Apr 22, 2017

vbraun commented Apr 25, 2017