Ask Your Question
0

Error computing kernel of matrix over symbolic ring

asked 2021-11-08 22:05:03 +0200

jn21 gravatar image

I am trying to compute the kernel of the Laplacian of the hypercube graph where all nonzero entries are symbolic variables. The below code works for N=2

N = 3 #dimension of hypercube graph
G = graphs.CubeGraph(N).to_directed()

#Assign edge labels as symbolic variables
for u,v,l in G.edges(sort=False):
    this_label = 'e' + str(u) + 'e' + str(v)
    G.set_edge_label(u, v, this_label)
    var(this_label)

#relabel vertices to facilitate conversion to matrix
G.relabel()

#Create edge dictionary to facilitate conversion to matrix
edge_dict = {(u,v):k for u,v,k in G.edges()}

#Construct Laplacian matrix
temp = matrix(SR, G.order(), G.order(), edge_dict)
L = temp - diagonal_matrix(sum(temp))

#compute Laplacian kernel
ker = transpose(L).kernel();

but gives the below error for N=3 at the last line:

TypeError: ECL says: THROW: The catch RAT-ERR is undefined.

During handling of the above exception, another exception occurred:

...

TypeError: Multiplying row by Symbolic Ring element cannot be done over Symbolic Ring, use change_ring or with_added_multiple_of_row instead.

Any ideas as to the cause of the error? Can SAGE handle computing kernels of symbolic matrices of this size?

Thanks!

edit retag flag offensive close merge delete

1 Answer

Sort by ยป oldest newest most voted
2

answered 2021-11-09 21:06:49 +0200

Max Alekseyev gravatar image

updated 2021-11-09 21:08:31 +0200

First, I cannot reproduce an error in Sage 9.4, but computation of the kernel takes forever.

Second, it's better to avoid calculations in the symbolic ring (as inefficient) whenever possible. In this case, the elements of the kernel can be viewed as rational functions in the label variables and thus as elements of the corresponding fraction field. Correspondingly, modifying the code into:

N = 3 #dimension of hypercube graph
G = graphs.CubeGraph(N).to_directed()

#Assign edge labels as symbolic variables
for u,v,l in G.edges(sort=False):
    this_label = 'e' + str(u) + 'e' + str(v)
    G.set_edge_label(u, v, this_label)

#relabel vertices to facilitate conversion to matrix
G.relabel()

#Create edge dictionary to facilitate conversion to matrix
edge_dict = {(u,v):k for u,v,k in G.edges()}

F = PolynomialRing(QQ, list(edge_dict.values()) ).fraction_field()

#Construct Laplacian matrix
temp = matrix(F, G.order(), G.order(), edge_dict)
L = temp - diagonal_matrix(sum(temp))

#compute Laplacian kernel
ker = transpose(L).kernel()

makes it run in a matter of seconds.

edit flag offensive delete link more

Comments

Wow, this is fantastic! Thank you! I am using Sage 9.3 and making your changes does indeed solve this quickly for N=3. My original intention was to solve this for N=4, which still fails on my laptop (Sage does not give an error, the Jupyter kernel just fails. I will try to run on a more powerful machine)

Given that the computations are now being done in the fraction field, does this mean that the resulting elements of the kernel (which are of FractionFieldElement type) are automatically expressed in lowest terms? I noticed that the FractionFieldElement class does not have a simplify_full() method.

jn21 gravatar imagejn21 ( 2021-11-10 22:21:29 +0200 )edit

I believe fraction field elements are stored in the reduced form, i.e numerator and denominator do not share common factors. simplify_full() would be redundant for them.

Max Alekseyev gravatar imageMax Alekseyev ( 2021-11-10 22:48:22 +0200 )edit

Your Answer

Please start posting anonymously - your entry will be published after you log in or create a new account.

Add Answer

Question Tools

1 follower

Stats

Asked: 2021-11-08 22:05:03 +0200

Seen: 117 times

Last updated: Nov 09 '21