ASKSAGE: Sage Q&A Forum - RSS feedhttps://ask.sagemath.org/questions/Q&A Forum for SageenCopyright Sage, 2010. Some rights reserved under creative commons license.Wed, 02 Nov 2022 00:58:58 +0100Computing ratio of two elements in a large ringhttps://ask.sagemath.org/question/64736/computing-ratio-of-two-elements-in-a-large-ring/ I have a ring (a matroid Chow ring) which has a large number of generators. It's structure is well-understood: it's graded, and the top degree is isomorphic to Q via a specific map, called the degree map. I know an explicit element whose image under the degree map is 1, call it a^{r-1}.
I have another element x of the matroid Chow ring, and I would like to compute it's degree. I can do that by computing x/a^{r-1}, but that is very slow (it seems to require a Grobner basis computation which does not finish on my computer).
When I ask sage to output x and a^{r-1}, sage outputs them as constant multiples of the same monomial. So from the output it is easy to read off what the degree is (look at the ratio of the monomials), but I would like to get it an automated way.
Example:
M = matroids.Uniform(4, 8)
A = M.chow_ring(QQ)
def flatToChow(F):
s = 'A'
for i in F:
s = s + str(i)
return A(s)
beta = A(0)
for i in range(1, M.rank()):
for F in M.flats(i):
if (0 not in F):
beta = beta + flatToChow(F)
a = A(0)
for i in range(1, M.rank()):
for F in M.flats(i):
if (0 in F):
a = a + flatToChow(F)
x = beta^3
x/a^3 #long time
vukovWed, 02 Nov 2022 00:58:58 +0100https://ask.sagemath.org/question/64736/Matroids: computing rank of a sethttps://ask.sagemath.org/question/63888/matroids-computing-rank-of-a-set/ Hello,
I would like to compute the rank of a given subset of the ground set of a matroid. I've tried
from sage.matroids.advanced import setprint
M = matroids.named_matroids.Vamos();
M.rank_function(['a','b','c'])
but I get the error
> AttributeError: 'sage.matroids.circuit_closures_matroid.CircuitClos' object has no attribute 'rank_function'
Is there a way to go around this? Also, since I am very new to Sage: is the matroid package included in Sage by default or do I need to somehow install it? If yes, then how?
Thanks in advance!Olga KuznetsovaFri, 02 Sep 2022 09:05:18 +0200https://ask.sagemath.org/question/63888/Checking if dual of matroid is graphic failshttps://ask.sagemath.org/question/63192/checking-if-dual-of-matroid-is-graphic-fails/I want to check whether the dual of a matroid is graphic.
Example:
G1 = Graph([[1, 2], [2, 3], [3, 4], [4, 5], [5, 1],
[1, 6], [2, 6], [3, 6], [4, 6], [5, 6]])
M1 = Matroid(G1)
M2 = M1.dual()
M2.is_graphic()
This raises an error in the last line, saying that `is_graphic` is not defined for `DualMatroid`s:
AttributeError: 'DualMatroid' object has no attribute 'is_graphic'
There should be a straightforward/standard way of solving this.SqFri, 08 Jul 2022 17:49:50 +0200https://ask.sagemath.org/question/63192/Obtaining the Solomon-Orlik algebra in QPA with the help of Sagehttps://ask.sagemath.org/question/57466/obtaining-the-solomon-orlik-algebra-in-qpa-with-the-help-of-sage/The Solomon-Orlik algebra (see [Sage documentation: Orlik-Solomon algebra](https://doc.sagemath.org/html/en/reference/algebras/sage/algebras/orlik_solomon.html)) associates to a finite matroid a finite dimensional algebra.
It is implemented in Sage to obtain generators and relations of those algebras but there seems to be no easy way to translate them into the GAP-package QPA where many more functions are available to study those algebras.
Let M be a finite matroid which we can assume for simplicity given as a finite set X of vectors with set of circuits C, which are simply the minimal linearly dependent subsets of X.
Recall that the exterior algebra on a ground set of variables x1,...,xn (assume them to be ordered x1 < ... < xn) is given as the quotient of the free algebra on x1,...,xn modulo the relations xi^2 and xi xj +xj xi for i < j.
In QPA the exterior algebra for n=4 is for example obtained as follows:
Q := Quiver(1,[[1,1,"x1"],[1,1,"x2"],[1,1,"x3"],[1,1,"x4"]]);
KQ := PathAlgebra(Rationals,Q);
AssignGeneratorVariables(KQ);
rel := [x1^2,x2^2,x3^2,x4^2,x1*x2+x2*x1,x1*x3+x3*x1,x1*x4+x4*x1,x2*x3+x3*x2,x2*x4+x4*x2,x3*x4+x4*x3];
A := KQ/rel;
Now the Solomon-Orlik algebra (see [Sage documentation: Orlik-Solomon algebra](https://doc.sagemath.org/html/en/reference/algebras/sage/algebras/orlik_solomon.html)) of a matroid M is given by adding the relations
$$\\sum_{r=1}^{t}{(-1)^{r-1}{x_{j_1} ... \\hat{x_{j_r}} .... x_{j_t}}$$
for every element (x1< ... < xt) in the circuits C.
For example when M is the matroid given by the vectors
x1=t=(1,-1,0), x2=u=(0,1,-1), x3=v=(-1,0,1), x4=w=(1,1,1).
then we have one circut given by x1 x2 x3 and thus one additional relation
given by x2 x3 - x1 x3 +x1x2 and the algebra in QPA can be obtained as follows:
Q := Quiver(1,[[1,1,"x1"],[1,1,"x2"],[1,1,"x3"],[1,1,"x4"]]);
KQ := PathAlgebra(Rationals,Q);
AssignGeneratorVariables(KQ);
rel := [x1^2,x2^2,x3^2,x4^2,x1*x2+x2*x1,x1*x3+x3*x1,x1*x4+x4*x1,x2*x3+x3*x2,x2*x4+x4*x2,x3*x4+x4*x3,x2*x3-x1*x3+x1*x2];
A := KQ/rel;
Question: Is there a direct way to directly obtain the quiver and relations for QPA in the format as in the examples using Sage for a given matroid?klaaaMon, 07 Jun 2021 18:35:55 +0200https://ask.sagemath.org/question/57466/Memory leak with matroid is_connected methodhttps://ask.sagemath.org/question/47839/memory-leak-with-matroid-is_connected-method/Hello.
I've been using Graphic Matroids to deal with some enumeration problems, where I filter a list of graphs based on their flats. Even without really undestanding what happens at low level, I could verify that the computation is faster when I build the equivalent representation of each graphic matroid using the Incidence matrix of the graph over GF(2).
One big issue that I am facing is that some memory leak is ocurring. As the size of my list of graphs grows, the ram memory got consumed until a point that my computer breaks down and restarts. My way out has been to use a bash script to keep calling the main program until I reach the end of an external text file (the input).
To force the `gc.collect()` seems to not be an option, because the program becomes really slow.
EDIT 1:
The memory leak seems to be related with the `is_connected` method. Here is a piece of my code showing two different situations:
With the use of `is_connected`:
sage: G = [g for g in graphs.nauty_geng("12 16:16 -Ct")]
sage: len(G)
11771
sage: print(get_memory_usage())
....:
....: for g in G:
....: A = g.incidence_matrix()
....: M = Matroid(A, ring = GF(2))
....: if M.is_connected():
....: pass
....: print(get_memory_usage())
....:
3396.38671875
3418.06640625
and without:
sage: print(get_memory_usage())
....: for g in G:
....: A = g.incidence_matrix()
....: M = Matroid(A, ring = GF(2))
....: for r in range(M.corank()):
....: for F in M.coflats(r):
....: pass
....:
....: print(get_memory_usage())
....:
3490.53515625
3490.53515625
EDIT 2:
Ok, I solved my problem by just explicitly declaring the function `is_connected` in the body of my code, instead of using the method present in the abstract matroid class. I'm not sure about why it really worked, I tried this approach because I thought it had something to do with the lists that are created by the `components` method, however I stopped investigating when I notice the memory leak vanished just by using the function. To be honest, I changed the script to not return any output (there was an option to input a certificate flag and return the components).
I'm letting the code below for the case someone faces a similar problem or has any better solution or clue about why it happened:
cpdef components(self):
B = self.basis()
components = [frozenset([e]) for e in self.groundset()]
for e in self.groundset() - B:
C = self.circuit(B | set([e]))
components2 = []
for comp in components:
if len(C & comp) != 0:
C = C | comp
else:
components2.append(comp)
components2.append(C)
components = components2
return components
cpdef is_connected(self):
comp = components(self)
if len(comp) == 1:
return True
else:
return FalsefmorlinThu, 12 Sep 2019 11:20:58 +0200https://ask.sagemath.org/question/47839/Partial Algebrashttps://ask.sagemath.org/question/8022/partial-algebras/Hi!
As part of a future package for matroid theory, I would like to implement an algebraic structure called a "partial field".
A partial field is a tuple P = (S, 0, 1, +, *) such that
1. S - {0} is a group G under * with identity 1
2. Every element p has an additive inverse q such that p + q = 0
3. Otherwise, the sum p + q is defined for only some choices of p + q.
Associativity of + is respected "as much as possible". Formally, this means that there exists a ring R such that G is contained in the group of units of R, and addition in the partial field is the restriction of addition in the ring to S.
Example: the regular partial field. This has elements {-1, 0, 1}, with addition and multiplication as in ZZ, but 1 + 1 is not defined.
How can we best implement such structures? That is, where should the category PartialFields go? One choice would be to subclass Rings. However, for various reasons it is desirable to return an "undefined_element" instead of the sum in the ring. This would break associativity tests that seem to be required for rings.
Example: take the partial field {(-1)^s 2^k : s,k in ZZ} U {0}, with usual multiplication and addition in QQ restricted to this set (e.g. 1/2 - 1 = -1/2 is ok, but 4 - 1/4 is undefined).
* (1 + 1) + (1 -2) = 1
* ((1 + 1) + 1) - 2 = undefined_element
If we do not subclass Ring, then a whole new can of worms is opened: we're no longer allowed to fill matrices with our elements. I'm not looking forward to re-implementing the Matrix class (though we would probably subclass it anyway as PMatrix, since we need a different determinant and rank algorithm, as well as some new methods).
P.S. How does one define ZZ[1/2] in Sage?
P.P.S. How would I coerce from my own, custom ring into QQ?
StefanFri, 25 Mar 2011 04:54:01 +0100https://ask.sagemath.org/question/8022/