Hi Prof.Stefan, For minor testing, the way it was done is to find line mappings (row to row, col to col) from the parent matroid (by all possible removal of rows,columns) using hashes, to the minor we want to test.Then the resultant small matrix is tested for equivalence with the minor we want,using the magic numbers.
I think i have understood conceptually, what Petr. Helineyny had done, but regarding the implementation, i'm yet to grasp it completely. 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() I think i can now go ahead and implement k-connectivity and automorphism_group computation for matroids.So, can you tell me in which file, each should go. Thanks! On Sun, Mar 2, 2014 at 8:10 PM, Stefan van Zwam <[email protected] > wrote: > Dear Rajesh, > > On Mar 2, 2014, at 9:25 AM, Rajesh Veeranki <[email protected]> wrote: > > Hi, > > I have done a bit of homework on the automorphism group computation of > matroid and efficient minor testing. > > 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* > > > Yes, that's the part I was thinking of. Do you understand these concepts? > > > I think the way to go is inserting these checks in the *has_minor()*method > we already have. > > > Coming to the automorphism group computation, i'm confused as i see two > approaches.One being, constructing the graph as you suggested and call the > *automorphism_group(partition=[X,Y]).*Since the graph is going to be > exponential in the size of groundset, we need to implement it in a clever > way. > > The other approach is to implement the refinement_matroids.pyx with the > three functions > ( all_chidren_equivalent,refine_and_return_invariant,compare_structures). > I've seen this approach discussed last year in the group. > > > Indeed. But for a third option, look at Nathann's comment about > Hypergraphs. They already implement automorphism_group, so this makes it > very easy to get something going! > > > Please comment if i'm going in the right direction. > > > Thanks > Rajesh Veeranki. > > > > > On Wed, Feb 26, 2014 at 6:53 PM, Nathann Cohen <[email protected]>wrote: > >> Hellooooooooooo !!! >> >> > For the automorphism group, the way to go is to construct an >> appropriate graph (e.g. a bipartite one with the elements on one side, the >> non bases on the other, and an edge if the element is contained in the non >> basis), and compute the automorphism on that graph that preserves the sides >> of the bipartition. >> >> Some thing that ? >> >> sage: Hypergraph.automorphism_group?? >> >> Nathann >> >> -- >> 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. >> > > > > -- > > > *Rajesh Veeranki** | Senior Undergraduate | **C.S.E** | **IIT Bombay* > > -- *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.
