Opened 3 years ago
Last modified 14 months ago
#23572 closed task
doctests for the english translation of the book "Calcul mathématique avec Sage" — at Version 17
Reported by: | zimmerma | Owned by: | |
---|---|---|---|
Priority: | critical | Milestone: | sage-8.7 |
Component: | doctest coverage | Keywords: | |
Cc: | mforets, dcoudert, nthiery, vklein, jhpalmieri | Merged in: | |
Authors: | Reviewers: | ||
Report Upstream: | Reported upstream. No feedback yet. | Work issues: | |
Branch: | Commit: | ||
Dependencies: | Stopgaps: |
Description (last modified by )
the purpose of this ticket is to add the doctests corresponding to the examples given in the english translation of the book "Calcul mathématique avec Sage" (see https://members.loria.fr/PZimmermann/sagebook/english.html).
Sage already includes doctests for the original version of this book (published in french in 2013). These doctests are in src/sage/tests/french_book
, and should be updated.
We should probably wait for the final version of the book before adding/updating doctests.
Upstream bugs:
- Using
scipy.sparse.lil_matrix
is now broken: https://github.com/numpy/numpy/pull/9691
Change History (17)
comment:1 Changed 3 years ago by
- Cc mforets added
comment:2 Changed 3 years ago by
comment:3 Changed 3 years ago by
another issue:
┌────────────────────────────────────────────────────────────────────┐ │ SageMath version 8.0, Release Date: 2017-07-21 │ │ Type "notebook()" for the browser-based notebook interface. │ │ Type "help()" for help. │ └────────────────────────────────────────────────────────────────────┘ sage: C = graphs.ChvatalGraph() sage: from sage.graphs.graph_coloring import edge_coloring sage: edge_coloring(C, hex_colors = True) {'#00ffff': [(0, 6), (1, 5), (2, 8), (3, 4), (7, 11), (9, 10)], '#7f00ff': [(0, 4), (1, 7), (2, 6), (3, 9), (5, 11), (8, 10)], '#7fff00': [(0, 9), (1, 2), (3, 7), (4, 8), (5, 10), (6, 11)], '#ff0000': [(0, 1), (2, 3), (4, 5), (6, 10), (7, 8), (9, 11)]}
With Sage 8.1beta3 we get:
{'#00ffff': [(0, 9), (1, 5), (2, 6), (3, 4), (7, 11), (8, 10)], '#7f00ff': [(0, 1), (2, 8), (3, 7), (4, 5), (6, 10), (9, 11)], '#7fff00': [(0, 4), (1, 2), (3, 9), (5, 10), (6, 11), (7, 8)], '#ff0000': [(0, 6), (1, 7), (2, 3), (4, 8), (5, 11), (9, 10)]}
Is there a way to get a deterministic answer? Is there any random seed that controls the edge coloring algorithm?
comment:4 Changed 3 years ago by
comment:5 Changed 3 years ago by
- Cc dcoudert added
comment:6 Changed 3 years ago by
The coloring is done with ILP and the result depends on the ILP solver. #22564 has been merged in 8.1.beta?? The patch only slightly changes the order in which constraints are added to the ILP and it is enough the get a different solution from 8.0.
sage: from sage.graphs.graph_coloring import edge_coloring sage: edge_coloring(C, hex_colors = True, solver='GLPK') {'#00ffff': [(0, 9), (1, 5), (2, 6), (3, 4), (7, 11), (8, 10)], '#7f00ff': [(0, 1), (2, 8), (3, 7), (4, 5), (6, 10), (9, 11)], '#7fff00': [(0, 4), (1, 2), (3, 9), (5, 10), (6, 11), (7, 8)], '#ff0000': [(0, 6), (1, 7), (2, 3), (4, 8), (5, 11), (9, 10)]} sage: edge_coloring(C, hex_colors = True, solver='Cplex') {'#00ffff': [(0, 6), (1, 5), (2, 3), (4, 8), (7, 11), (9, 10)], '#7f00ff': [(0, 1), (2, 6), (3, 4), (5, 10), (7, 8), (9, 11)], '#7fff00': [(0, 9), (1, 2), (3, 7), (4, 5), (6, 11), (8, 10)], '#ff0000': [(0, 4), (1, 7), (2, 8), (3, 9), (5, 11), (6, 10)]} sage: edge_coloring(C, hex_colors = True, solver='PPL') {'#00ffff': [(0, 9), (1, 5), (2, 8), (3, 4), (6, 10), (7, 11)], '#7f00ff': [(0, 6), (1, 7), (2, 3), (4, 5), (8, 10), (9, 11)], '#7fff00': [(0, 4), (1, 2), (3, 9), (5, 10), (6, 11), (7, 8)], '#ff0000': [(0, 1), (2, 6), (3, 7), (4, 8), (5, 11), (9, 10)]} sage: edge_coloring(C, hex_colors = True, solver='Coin') {'#00ffff': [(0, 4), (1, 5), (2, 6), (3, 9), (7, 11), (8, 10)], '#7f00ff': [(0, 6), (1, 2), (3, 7), (4, 8), (5, 10), (9, 11)], '#7fff00': [(0, 1), (2, 3), (4, 5), (6, 11), (7, 8), (9, 10)], '#ff0000': [(0, 9), (1, 7), (2, 8), (3, 4), (5, 11), (6, 10)]} sage: edge_coloring(C, hex_colors = True, solver='Gurobi') {'#00ffff': [(0, 1), (2, 6), (3, 9), (4, 5), (7, 11), (8, 10)], '#7f00ff': [(0, 6), (1, 7), (2, 3), (4, 8), (5, 10), (9, 11)], '#7fff00': [(0, 4), (1, 5), (2, 8), (3, 7), (6, 11), (9, 10)], '#ff0000': [(0, 9), (1, 2), (3, 4), (5, 11), (6, 10), (7, 8)]}
In doctests, you must set the solver to GLPK
. Otherwise, the default solver is used (e.g., Cplex
if you have it).
comment:7 follow-up: ↓ 8 Changed 3 years ago by
David,
1) from the trac page, #22564 has been merged in 8.0, thus the difference I see should be due to subsequent changes
2) is there any reason why the order of the constraints was changed? It makes it difficult to add doctests for this example from our book about Sage
comment:8 in reply to: ↑ 7 Changed 3 years ago by
Replying to zimmerma:
David,
1) from the trac page, #22564 has been merged in 8.0, thus the difference I see should be due to subsequent changes
2) is there any reason why the order of the constraints was changed? It makes it difficult to add doctests for this example from our book about Sage
I changed the code 1) to split the graph into connected components and color them separately (should be faster), and 2) because I don't understand why we should use list comprehension for adding constraints. It was:
# A vertex can not have two incident edges with the same color. [p.add_constraint( p.sum([color[R(e),i] for e in g.edges_incident(v, labels=False)]), max=1) for v in g.vertex_iterator() for i in range(k)] # an edge must have a color [p.add_constraint(p.sum([color[R(e),i] for i in range(k)]), max=1, min=1) for e in g.edge_iterator(labels=False)] # anything is good as an objective value as long as it is satisfiable e = next(g.edge_iterator(labels=False)) p.set_objective(color[R(e),0])
Now it is:
# A vertex can not have two incident edges with the same color. for v in h.vertex_iterator(): for i in range(k): p.add_constraint(p.sum(color[R(u,v),i] for u in h.neighbor_iterator(v)) <= 1) # Nn edge must have a color for u,v in h.edge_iterator(labels=False): p.add_constraint(p.sum(color[R(u,v),i] for i in range(k)) == 1) # We color the edges of the vertex of maximum degree for i,v in enumerate(h.neighbors(X)): p.add_constraint( color[R(v,X),i] == 1 )
So the main changes are:
- use of
neighbor_iterator
instead ofedges_incident
in the first set of constraints (it has always been assumed in this method that the graph is simple) - removal of the objective function (not needed)
- now force the coloring of the edges incident to the vertex of maximum degree (could speed up the resolution).
In fact, I bet that changing the version of GLPK
could already change the result (e.g., faster algorithm converging to a different optimal solution). Furthermore, I assume that some internal heuristics of the solvers are randomized since we can set random seed of Cplex.
comment:9 Changed 3 years ago by
David, thank you for the explanation (by the way there is a typo: "Nn edge must have a color" should be "An edge...").
Since it seems impossible to have a reliable doctest for this example, we won't test it.
comment:10 in reply to: ↑ description Changed 3 years ago by
Replying to zimmerma:
Sage already includes doctests for the original version of this book (published in french in 2013). These doctests are in
src/sage/tests/french_book
, and should be updated.
Didn't you mention at some point that you didn't care any more about these doctests? I seem to remember something along those lines...
comment:11 Changed 3 years ago by
Jeroen,
what I said is that there were too many changes in Sage upstream (with respect to Sage 5.9 which we used in the french book in 2013) so that we could check them (and even, sometimes, we had no chance to give our opinion on them before they were merged into Sage). Those doctests nevertheless did they job since most of the examples still run with current versions of Sage.
Now that we have updated the book to Sage 8.0, we'd like to add the (new) doctests to Sage doctests, so that the new (english) version of the book will not be obsolete too quickly.
comment:12 follow-ups: ↓ 13 ↓ 14 ↓ 15 Changed 3 years ago by
Nicolas Thiery just tested the doctests of our book with Sage 8.1beta5 and several do fail (while all tests pass with Sage 8.0). Here are the issues:
1) the lil_matrix
do not work any more. Cf the example on page 299 of the english translation:
sage: from scipy.sparse.linalg.dsolve import * sage: from scipy.sparse import lil_matrix sage: from numpy import array sage: n = 200 sage: n2 = n*n sage: A = lil_matrix((n2, n2)) sage: h2 = 1./float((n+1)^2) sage: for i in range(0,n2): ....: A[i,i]=4*h2+1. ....: if i+1<n2: A[i,int(i+1)]=-h2 ....: if i>0: A[i,int(i-1)]=-h2 ....: if i+n<n2: A[i,int(i+n)]=-h2 ....: if i-n>=0: A[i,int(i-n)]=-h2 sage: Acsc = A.tocsc() sage: b = array([1 for i in range(0,n2)]) sage: solve = factorized(Acsc) # LU factorisation sage: S = solve(b) # resolution
Now if fails at the A = lil_matrix((n2, n2))
line with:
TypeError: unrecognized lil_matrix constructor usage
Aren't lil_matrix
tested in the current doctests?
2) the category of QQ
changed:
Failed example: QQ.category() Expected: Join of Category of quotient fields and Category of metric spaces Got: Join of Category of number fields and Category of quotient fields and Category of metric spaces
3) we have different output for graphs of the commands minor
and edge_coloring
. We will try to fix those with solver='GLPK'
(cf comment 6 above). If that does not work, is there a random seed that we can set to make those commands deterministic?
comment:13 in reply to: ↑ 12 Changed 3 years ago by
Replying to zimmerma:
3) we have different output for graphs of the commands
minor
andedge_coloring
. We will try to fix those withsolver='GLPK'
(cf comment 6 above). If that does not work, is there a random seed that we can set to make those commands deterministic?
Are these tests really non-deterministic or just different with different versions of Sage?
comment:14 in reply to: ↑ 12 Changed 3 years ago by
Replying to zimmerma:
2) the category of
Failed example: QQ.category() Expected: Join of Category of quotient fields and Category of metric spaces Got: Join of Category of number fields and Category of quotient fields and Category of metric spaces
This is a good and intentional change: just change the expected output.
comment:15 in reply to: ↑ 12 Changed 3 years ago by
Replying to zimmerma:
Aren't
lil_matrix
tested in the current doctests?
lil_matrix
is not used or tested anywhere in Sage. I'll have a look.
comment:16 Changed 3 years ago by
1) the lil_matrix do not work any more.
a scipy update? in sage 8.0.beta5 the version is 0.19.1, while in 8.0 it is 0.17.1.
however, the docstring says it's still valid:
... lil_matrix((M, N), [dtype]) to construct an empty matrix with shape (M, N) dtype is optional, defaulting to dtype='d'.
comment:17 Changed 3 years ago by
- Description modified (diff)
- Report Upstream changed from N/A to Reported upstream. No feedback yet.
one issue we encounter is the following. The code below differs between Sage 8.0 and Sage 8.1beta3:
With Sage 8.0 we get
0.0
, whereas with Sage 8.1beta3 we get-0.0
. I thought the determinant code was deterministic, and since RDF computations follow IEEE 754, we should get a deterministic answer. How can we get different answers?