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 jdemeyer)

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:

  1. 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 mforets

  • Cc mforets added

comment:2 Changed 3 years ago by zimmerma

one issue we encounter is the following. The code below differs between Sage 8.0 and Sage 8.1beta3:

   def NearlySingularMatrix(R,n):
      M=matrix(R,n,n)
      for i in range(0,n):
         for j in range(0,n):
            M[i,j]= (1+log(R(1+i)))/((i+1)^2+(j+1)^2)
      return M
   n=35
   print NearlySingularMatrix(RDF,n).det()

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?

comment:3 Changed 3 years ago by zimmerma

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 zimmerma

for comment 3, I'll ask David Coudert who worked on edge_coloring in #22564.

Paul

comment:5 Changed 3 years ago by zimmerma

  • Cc dcoudert added

comment:6 Changed 3 years ago by dcoudert

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: Changed 3 years ago by 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

comment:8 in reply to: ↑ 7 Changed 3 years ago by dcoudert

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 of edges_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 zimmerma

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.

Last edited 14 months ago by zimmerma (previous) (diff)

comment:10 in reply to: ↑ description Changed 3 years ago by jdemeyer

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 zimmerma

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: Changed 3 years ago by zimmerma

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 jdemeyer

Replying to zimmerma:

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?

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 jdemeyer

Replying to zimmerma:

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

This is a good and intentional change: just change the expected output.

comment:15 in reply to: ↑ 12 Changed 3 years ago by jdemeyer

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.

Last edited 3 years ago by jdemeyer (previous) (diff)

comment:16 Changed 3 years ago by mforets

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'. 
Last edited 3 years ago by mforets (previous) (diff)

comment:17 Changed 3 years ago by jdemeyer

  • Description modified (diff)
  • Report Upstream changed from N/A to Reported upstream. No feedback yet.
Note: See TracTickets for help on using tickets.