Dear Prof.Rudi, As far as i can see,the magic numbers are calculated for each reduced matrix, displaying each basis.
Regarding, the automorphism group of a matroid, we should certainly avoid the full non-bases calculation.Can you please suggest some resource,( if you have something particular in mind ), for studying the hypergraphs that are invariants of a matroid? I'm also reading your paper <http://arxiv.org/pdf/1203.0910v2.pdf> for understanding the projective invariants of matrices. Thanks Rajesh Veeranki. On Mon, Mar 3, 2014 at 1:39 AM, Pendavingh, R.A. <[email protected]>wrote: > Dear Rajesh, > > Great that you are working on this. > > I think i have understood conceptually, what Petr. Helineyny had done, but > regarding the implementation, i'm yet to grasp it completely. > Well, same here. > > Coming to the automorphism group, i think using Hypergraph is the right > thing to do.Thanks to Nathann! > I guess this would do: > > H = Hypergraph(set of nonbases of Matroid M) > G = H.to_bipartite_graph() > G.automorphism_group() > > That would certainly do it, and we should absolutely implement this before > we go on. But calculating the nonbases will eventually heavily dominate the > running time of this procedure. So I wonder if there are ways to > heuristically find a speedup, avoiding the full calculation of the set of > nonbases if possible. I think that if you somehow find a group G (whose > elements are permutations of the ground set of the matroid M) so that: > 1) G contains the automorphism group of M > 2) G is generated by automorphisms of M > then G is the automorphism group M. Various hypergraphs that are > invariants of M may be found in a modest amount of time (low-rank flats, > say) whose automorphism group G will satisfy 1). Then if G fails 2), the > nature of the failure may give a way to augment your invariant hypergraph > to one with a strictly smaller automorphism group, preserving 1). > > > > For minor testing,what Petr Helineny did is to compute some magic numbers > (Numbers that are invariant on operations like scaling and permuting lines > ) of matrices and compare these numbers for faster rejections.The numbers > he had used are zero 2X2 sub determinants,zero patterns of lines, numbers > based on small flats > > Are these magic numbers relative to the choice of a basis of the matroid? > So of the matroid is represented by the matrix [ I A ] , where the columns > of the identity matrix correspond to your basis, the magic numbers depend > on A only? > > > > I think the way to go is inserting these checks in the has_minor() method > we already have. > > For binary, ternary, and quaternary matroids there are a couple of > projective invariants of the representing matrix (invariant under row > operations) which are fast to compute. See my paper in J of algebraic > combinatorics. The isomorphism test in Sage for such matroids already > implements them, but I think they may also be useful for minor testing and > isomorphism testing. > > I'm open to discuss the finer points at any time, but not quite sure > whether we should do that in this discussion group. > > Best, > Rudi > > -- *Rajesh Veeranki** | Senior Undergraduate | **C.S.E** | **IIT Bombay* -- You received this message because you are subscribed to the Google Groups "sage-gsoc" group. To unsubscribe from this group and stop receiving emails from it, send an email to [email protected]. To post to this group, send email to [email protected]. Visit this group at http://groups.google.com/group/sage-gsoc. For more options, visit https://groups.google.com/groups/opt_out.
