Ask Your Question

MattKahle's profile - activity

2019-04-05 12:28:03 -0500 received badge  Popular Question (source)
2019-04-05 12:28:03 -0500 received badge  Notable Question (source)
2016-10-04 08:06:53 -0500 received badge  Nice Question (source)
2016-10-03 21:44:35 -0500 asked a question Bug with simplicial complexes or computing homology in Sage 7.3?

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)
2015-02-13 12:09:24 -0500 received badge  Nice Question (source)
2015-02-12 18:32:19 -0500 asked a question Sage+Gurobi: Can I control how many processors vertex_coloring uses?

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?

2015-01-19 15:19:01 -0500 asked a question Is there a bug with using chromatic_number together with Gurobi?

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.

2015-01-09 13:34:34 -0500 asked a question setting default LP solver

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

2015-01-05 12:49:06 -0500 received badge  Scholar (source)
2015-01-05 02:09:53 -0500 received badge  Student (source)
2015-01-05 02:09:50 -0500 received badge  Self-Learner (source)
2015-01-05 02:09:50 -0500 received badge  Teacher (source)
2015-01-04 22:01:48 -0500 answered a question optimizing graph coloring for small chromatic number

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.

2015-01-04 14:35:41 -0500 asked a question optimizing graph coloring for small chromatic number

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?

2013-03-25 07:53:13 -0500 received badge  Supporter (source)
2013-03-24 11:41:43 -0500 received badge  Editor (source)
2013-03-24 11:40:49 -0500 asked a question homology of simplicial complexes

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?