MattKahle's profile - activity

I have the following code that has been running fine in Sage 6.5––Sage 7.2 on both my Mac OS 10.10.5 and a Unix system. I just tried upgrading to Sage 7.3 on my Mac, and it no longer works correctly. It doesn't crash, it just gives wrong answers.

I will copy the code below, but it reminds me of the issue I had when I posted the following question: https://ask.sagemath.org/question/994...

The code below is complicated, but the output of sampler(n) is supposed to be a random Q-acyclic simplicial complex with n vertices. So if I write

S=sampler(12)
S.homology()

I should expect to see something like

{0: 0, 1: 0, 1: 0} or {0: 0, 1: C2, 1: 0} as outputs,

but definitely not {0: 0, 1: Z, 2: Z}

The homology should be trivial or finite groups. But in Sage 7.3 on my Mac, I get Z parts in the homology. I thought my code was broken at first, but copying and pasting it back into Sage 7.2 on my Mac, it seems to work fine.

@cached_function
def f(X):
    return (X.transpose() * X).inverse()

def ortho(X):
    X.set_immutable()
    return X*f(X)* X.transpose()

def TR(M):
    D=M.diagonal()
    X=GeneralDiscreteDistribution(D)
    return X.get_random_element()

def shrink(X,Q,n):
    W=Q[:,n]
    W.set_immutable()
    X2=X-W*f(W)*W.transpose()*X
    X3=X2.transpose().echelon_form().transpose()
    return X3[:,0:X3.ncols()-1]

def sampler(N):
    S=range(1,N+1)
    Z = SimplicialComplex(Set(range(1, N+1)).subsets(3))
    L=list(Z.n_faces(2))
    T=Z.n_skeleton(1)
    C=Z.chain_complex()
    M=C.differential(2).dense_matrix().transpose()
    M2=M.transpose().echelon_form().transpose()
    R=M2.rank()
    X=M2[:,0:R]    
    Q=ortho(X)
    n=TR(Q)
    T.add_face(list(L[n]))
    j = binomial(N,2) - N
    for i in range(j):
        X=shrink(X,Q,n)
        Q=ortho(X)
        n=TR(Q)
        T.add_face(list(L[n]))
    return(T)

I am using Sage to color some graphs, using a 32-processor Linux server. I am using the vertex_coloring command, with Gurobi as the LP solver.

I've noticed that for graphs that take more than a few minutes, the program seems to eventually settle on using 16 processors. It would be nice if I could tell Sage (or Gurobi?) to allow more or fewer processors. Is this possible?

I have installed the LP solver Gurobi, and it seems to work successfully work with the vertex_coloring() command. But I wanted to compare runtimes with chromatic_number, and Sage seems to hang whenever I try this.

I construct a graph G, and then when I run the command G.chromatic_number(algorithm="MILP"), Sage hangs. I can tell something has gone wrong because it doesn't come back even when I give it a very small simple graph G, and because Linux tells me that I know have a zombie process.

Any suggestions would be much appreciated.

I installed Gurobi, and have gotten Sage to recognize it. So when I use a command such as vertex_coloring(G,solver="GUROBI") everything works fine.

But what if I want to use instead a command such as G.chromatic_number(algorithm="MILP"). How do I make sure that the LP solver that Sage is using is Gurobi, rather than GLPK? Is there one place I can tell Sage that it should always default to Gurobi as its LP solver, or is it possible that Sage is smart enough that once Gurobi is installed it does that anyway?

(Also, peripherally: does anyone have any idea whether chromatic_number or vertex_coloring is more efficient for large graphs?)

I just found that there is another Sage command, called vertex_coloring, which will check whether a graph is k-colorable for any particular k. You can also specify LP solver.

I am using Sage to compute chromatic number of some moderately large graphs G (a few thousand vertices). These graphs are relatively sparse (average degree < 15) and the chromatic number is fairly small–––the graphs I've been looking at tend to have chromatic number either 4 or 5. For my purposes, though, there is a big difference between 4 and 5.

––I've been using G.chromatic_number() as a black box, but is there some way I could just ask Sage directly if the graph is 4-colorable? (If the answer is 'no' maybe I don't care about whether the chromatic number is actually 5, 6, or larger.)

––Also, is there anything else I can do to optimize chromatic number calculations in Sage if I know a priori that the chromatic number is relatively small?

I am building a simplicial complex as follows:

sage: S = range(1,7)
sage: Z = SimplicialComplex([S])
sage: T = Z.n_skeleton(1)
sage: T.faces()
{0: set([(4,), (5,), (3,), (1,), (6,), (2,)]), 1: set([(2, 4), (3, 6),
(5, 6), (2, 6), (1, 4), (3, 5), (3, 4), (2, 3), (4, 6), (2, 5), (1, 2),
(1, 3), (4, 5), (1, 5), (1, 6)]), -1: set([()])}
sage: T.homology()
{0: 0, 1: Z^10}

So far everything seems good. Then I try adding a face to T.

sage: T.add_face([1,2,6])
sage: T.faces()
{0: set([(4,), (5,), (3,), (1,), (6,), (2,)]), 1: set([(2, 4), (3, 6),
(5, 6), (1, 5), (1, 4), (3, 5), (3, 4), (2, 3), (4, 6), (2, 5), (1, 2),
(1, 3), (1, 6), (2, 6), (4, 5)]), 2: set([(1, 2, 6)]), -1: set([()])}

So the face seems to have been added.

But then:

sage: T.homology()

results in:

{0: 0, 1: Z^10, 2: 0}

But this doesn't make any sense --- it should say 0:0, 1:Z^9, 2:0, since adding a 2-face kills a class in $H_1(T)$.

Can anyone tell what I'm doing wrong?