Re: [sage-combinat-devel] Re: How to solve this combinatorial problem in Sage?
Thanks a lot Simon. Just trying to get my head around it now in order
to compare it to my problem, I need to convert the finite field part into
simple language that I can understand ...
Kind regards
Gary
On Wed, Apr 24, 2013 at 10:53 AM, Simon King simon.k...@uni-jena.de wrote:
Hi Gary,
On 2013-04-22, Gary McConnell garymako...@googlemail.com wrote:
I kind-of went quiet on this because Nicolas was way ahead of me :)
but (obviously only if you have time) I would be fascinated to hear how
you
resolve this because I have some not dissimilar problems in finite field
vector spaces which may benefit from the techniques (see for example
https://groups.google.com/forum/?fromgroups=#!topic/sage-combinat-devel/5i0IeAsyjTE
)
Before I explain my current heuristics, let's fix some notations:
I have an approximation (knowing generators and relations out to a
certain degree) of a graded commutative algebra R over a finite (prime)
field F. I know a basis for the degree d part. I know a finite subset
P of the ring approximation which is guaranteed to generate an ideal in
R of Krull dimension 1. I have reasons to believe that there is a degree-d
element p of the ring approximation such that P and p together generate an
ideal of Krull dimension 0 in R (in fact, I know that there exists some
finite extension F' of F such that R\otimes_F F' contains such element
in degree d).
The aim is to find p.
Moreover, I have morphisms of graded algebras phi_i:R - R_i (i=1,...,k),
where the R_i are free graded commutative algebras. The construction of
the phi_i ensures that a subset S of R generates an ideal of Krull
dimension 0 in R if and only if phi_i(S) generates an ideal of Krull
dimension 0 in R_i, for all i=1,...,k.
And now comes the potentially most expensive part: I compute a Gröbner
basis of the radical of phi_i(P) for all i=1,...,k. Hence, for each
degree-d monomial s of R, I can compute the normal form of phi_i(s) with
respect to the radical of phi(P). For each s, I combine the sequences of
coefficients (for all i together) into a row.
By Gaussian elimination, I get linear combinations c_1,...,c_t of the
degree-d monomials of R, such that the rows obtained from c_1,...,c_t
form a matrix in echelon form.
For each i=1,...,k and each j=1,...,t, I can test whether phi_i(c_j) is
contained in the radical of phi_i(P) or whether phi_i(P\cup c_j)
generates an ideal of Krull dimension 0.
By the dancing links algorithm, I try to find a subset
c_{j_1},...,c_{j_r}, such that for each i=1,...,k there is precisely one
c_{j_y} such that phi_i(P\cup c_{j_y}) generates an ideal of Krull
dimension 0, and all others are mapped to an element of the radical of
phi_i(P).
It is easy to see that then the sum of the c_{j_1},...,c_{j_y} is an
element p that I was looking for. Because of the intermediate step of
computing an echelon form, it quite often happens that the dancing link
algorithm succeeds. If it does not succeed, then I enumerate a bounded
number (at most 512) of linear combinations of the c_{j_1},...,c_{j_y}.
I have no idea if this heuristics is useful in your application. But in
my situation, I see that it succeeds far more often than my previous
heuristics (namely: try at most 512 linear combinations of degree-d
monomials of R).
Best regards,
Simon
--
You received this message because you are subscribed to a topic in the
Google Groups sage-combinat-devel group.
To unsubscribe from this topic, visit
https://groups.google.com/d/topic/sage-combinat-devel/eKNz3fM5yJo/unsubscribe?hl=en
.
To unsubscribe from this group and all its topics, send an email to
sage-combinat-devel+unsubscr...@googlegroups.com.
To post to this group, send email to sage-combinat-devel@googlegroups.com.
Visit this group at
http://groups.google.com/group/sage-combinat-devel?hl=en.
For more options, visit https://groups.google.com/groups/opt_out.
--
You received this message because you are subscribed to the Google Groups
sage-combinat-devel group.
To unsubscribe from this group and stop receiving emails from it, send an email
to sage-combinat-devel+unsubscr...@googlegroups.com.
To post to this group, send email to sage-combinat-devel@googlegroups.com.
Visit this group at http://groups.google.com/group/sage-combinat-devel?hl=en.
For more options, visit https://groups.google.com/groups/opt_out.
Re: [sage-combinat-devel] Re: How to solve this combinatorial problem in Sage?
Hell everybody !!! I'm sorry to answer this late but I don't always read the sage-combinat posts ^^; Well, here's the thing if you did not work it out already : With Sage's MILP support, you will be able to answer easily those two questions : Is there a subcollection of sets that partition your point set ? What is the family that covers your point set and has the least possible amount of points covered several times (with multiplicity) You cannot really get all the answers right now, except it you really, really want them are if you are not ashamed of the algorithmic implications of what you want Sage to compute. Anyway, if you really want to do it don't tell me, 'cause it hurts :-P Here's the code : from sage.numerical.mip import MIPSolverException # Set collection n = 15 S = [Subsets(range(n)).random_element() for i in range(30)] # A Mixed Integer Linear Program object p = MixedIntegerLinearProgram(maximization = False) # You associate a binary variable b[s] to each of your set s b = p.new_variable(binary = True) # You want all points to be covered at least once (a covering of your vertex set) for i in range(n): p.add_constraint( p.sum([b[s] for s in S if i in s]) = 1) # You want to minimize the number of times each point is taken, with multiplicity. Actually, you want to minimize the sum of the cardinalities of the sets you take ! p.set_objective(p.sum([ len(s)*b[s] for s in S])) # compute the solution try: p.solve() print Here's the answer : b_sol = p.get_values(b) print [s for s in S if b_sol[s] == 1] except MIPSolverException: print No answer ! So once more, Sage cannot tell you right now all solutions as you may want. I would like to, though. But... If you rey want it, what you can do is the following : Run the LP code above Use the solution, do whatever you want to it Add to the LP a constraint which excludes ONLY the solution you just received Solve the LP again, which will give you another solution. Here's the kind of constraint I have in mind : p.add_constraint( p.sum([(1-b[s] if b_sol[s] else b[s]) for s in S ]) = 1) That is to say I want ANY of the values b_sol[s] to be different from what they were just before. Hope that helps. I don't want to know if this second trick helps, as I told you it hurts me to think of what it does :-P And for anything about the most practical aspects of LP, two pages whose only purpose is to make it understandable : http://steinertriples.fr/ncohen/tut/LP/ http://steinertriples.fr/ncohen/tut/LP_examples/ Have funnn !!! Nathann -- You received this message because you are subscribed to the Google Groups sage-combinat-devel group. To unsubscribe from this group and stop receiving emails from it, send an email to sage-combinat-devel+unsubscr...@googlegroups.com. To post to this group, send email to sage-combinat-devel@googlegroups.com. Visit this group at http://groups.google.com/group/sage-combinat-devel?hl=en. For more options, visit https://groups.google.com/groups/opt_out.
Re: [sage-combinat-devel] Re: How to solve this combinatorial problem in Sage?
Dear Simon I kind-of went quiet on this because Nicolas was way ahead of me :) but (obviously only if you have time) I would be fascinated to hear how you resolve this because I have some not dissimilar problems in finite field vector spaces which may benefit from the techniques (see for example https://groups.google.com/forum/?fromgroups=#!topic/sage-combinat-devel/5i0IeAsyjTE) !! I took a look at MILP but the assumed knowledge was way over my head, for now ... Many thanks and kind regards Gary On Mon, Apr 22, 2013 at 8:38 AM, Simon King simon.k...@uni-jena.de wrote: Hi Marco, On 2013-04-21, mmarco mma...@unizar.es wrote: The linear combinations that have some zero coefficient are the intersections of the corresponding subspace with the coordinate hyperplanes. That is, the set of bad linear combinations is a subset of codimension 1. The generic elements of the subspace would not belong to it. In the following matrix over GF(2), you will not find a combination of rows that is non-zero everywhere: [1 1 0] [0 1 1] [1 0 1] Hence, over finite fields, it is generally not true that the complement of the bad linear combinations is non-empty. Anyway, for my real problem (finding parameters by clever enumeration) I did make some progress: After some preprocessing, it is often possible to find a good linear combination with the dancing links algorithm. Best regards, Simon -- You received this message because you are subscribed to a topic in the Google Groups sage-combinat-devel group. To unsubscribe from this topic, visit https://groups.google.com/d/topic/sage-combinat-devel/eKNz3fM5yJo/unsubscribe?hl=en . To unsubscribe from this group and all its topics, send an email to sage-combinat-devel+unsubscr...@googlegroups.com. To post to this group, send email to sage-combinat-devel@googlegroups.com. Visit this group at http://groups.google.com/group/sage-combinat-devel?hl=en. For more options, visit https://groups.google.com/groups/opt_out. -- You received this message because you are subscribed to the Google Groups sage-combinat-devel group. To unsubscribe from this group and stop receiving emails from it, send an email to sage-combinat-devel+unsubscr...@googlegroups.com. To post to this group, send email to sage-combinat-devel@googlegroups.com. Visit this group at http://groups.google.com/group/sage-combinat-devel?hl=en. For more options, visit https://groups.google.com/groups/opt_out.
Re: [sage-combinat-devel] Re: How to solve this combinatorial problem in Sage?
On Tue, Apr 16, 2013 at 09:09:19AM +, Simon King wrote:
On 2013-04-16, Nicolas M. Thiery nicolas.thi...@u-psud.fr wrote:
For non exact covers, this can be formulated straightforwardly as a
Mixed Integer Linear Program (MILP): take a 0-1 variable y_S for each
set S, and an inequation $\sum_{S, x\in S} y_S \geq 1$. So the problem
can be reduced (efficiently???) to that of iterating through the
integer points in a polytope. There are very optimized software using
backtracking algorithm to find optimal solutions for such systems of
equations.
How can this be done in Sage?
sage: MixedIntegerLinearProgram?
:-)
But Nathann will be the one to tell you about the status for the
iteration feature.
Cheers,
Nicolas
--
Nicolas M. Thiéry Isil nthi...@users.sf.net
http://Nicolas.Thiery.name/
--
You received this message because you are subscribed to the Google Groups
sage-combinat-devel group.
To unsubscribe from this group and stop receiving emails from it, send an email
to sage-combinat-devel+unsubscr...@googlegroups.com.
To post to this group, send email to sage-combinat-devel@googlegroups.com.
Visit this group at http://groups.google.com/group/sage-combinat-devel?hl=en.
For more options, visit https://groups.google.com/groups/opt_out.
Re: [sage-combinat-devel] Re: How to solve this combinatorial problem in Sage?
Hi Simon
I'm struggling a little to understand what the programming bottleneck is in
all this. Clearly you do not want a completely naive search as you said
above; but are the 'tests' of the f_i on each m expensive in time, and is
the proof of the zero-dimensionality of the ideal also a slow process (ie I
assume you have to proceed via Groebner bases over the poly ring in some
number t of indeterminates over F_p right?) ? ie I guess what I'm getting
at is, how much (and where in the algorithm) are we able to get away with
'brute force', and where do we have to be clever? :)
Because to be honest the best solution that occurs to me from what you have
said so far is exactly what you tried to do with the matrices over finite
fields approach. So I would also like to understand better why that did not
work.
thanks and kind regards
Gary
On Mon, Apr 15, 2013 at 11:13 PM, Simon King simon.k...@uni-jena.de wrote:
Hi Gary,
On 2013-04-15, garymako...@googlemail.com garymako...@googlemail.com
wrote:
how big is M, how big is F, and is M sparse or do you have few zeros?
F is typically a small prime field, M is not sparse, but also not
particularly big, say, 200x100.
However, it turns out that after all I was mistaken: In contrast to what
I thought, the problem of enumerating covers starting with as few overlaps
as possible is more important for me than the problem with nowhere-zero row
combinations.
As you probably guessed, both problems are just attempts to solve
something else. So, perhaps it makes sense to formulate my *real*
problem:
I am computing the mod-p cohomology ring R of a finite group G. It is known
that the Krull dimension of the cohomology ring is equal to the p-rank r
of G. Now, I have given elements p_1,..., p_{r-1}, and I try to find an
element p_r of degree d such that p_1,..., p_r generate a sub-algebra
over which R is finite, i.e., p_1,...,p_r are parameters for R (Let's
call the problem: find a last parameter in degree d).
What I am looking for is a good heuristics, i.e., I would accept that
sometimes the algorithm can't find a last parameter in degree d even
though it exists.
R comes with a couple of maps f_1,...,f_k whose codomains are finite over a
polynomial ring (namely: the restriction maps to maximal p-elementary
abelian subgroups). It is known that p_1,...,p_r are parameters for R if
and only if their images under f_i forms a 0-dimensional ideal,
simultaneously
for all i=1,...,k.
The brute force approach would be: Let S a basis of the degree-d part of
R (lets call them standard monomials). One can list all linear
combinations of the elements of S, and by applying the f_i one can test
whether the linear combination is a last parameter. Since S can easily
contain more than 40 elements, a cleverer approach seems needed.
For each element m of S, we can test for which i=1,...,k the images of
p_1,...,p_{r-1} together with the image of m span a zero-dimensional
ideal (let's say that m is fine at i). If two elements m, m' are both
fine at i, it could be that a linear combination of m and m' is not fine
at i. But if we find a subset of S such that for all i=1,...,k there is
exactly one element of the subset that is fine at i, then the sum of
elements of this subset yields a last parameter.
So, this should explain my interest in finding covers. If the cover has
some overlap (i.e., for some i there are several elements fine at i),
then the corresponding sum of elements of S is not guaranteed to provide
a parameter, but I would expect that with small overlap it is still rather
likely to find a last parameter.
For the other problem: I tried to construct a matrix over GF(p) whose
rows correspond to the elements of S and somehow encode the images under
the f_1,...,f_k. This idea was to do it in such a way that having a
linear combination of rows that has no zero entry is a necessary but
perhaps not sufficient condition that the corresponding linear
combination of elements of S is a last parameter. But the construction I
had in mind did not work.
Best regards,
Simon
--
You received this message because you are subscribed to a topic in the
Google Groups sage-combinat-devel group.
To unsubscribe from this topic, visit
https://groups.google.com/d/topic/sage-combinat-devel/eKNz3fM5yJo/unsubscribe?hl=en
.
To unsubscribe from this group and all its topics, send an email to
sage-combinat-devel+unsubscr...@googlegroups.com.
To post to this group, send email to sage-combinat-devel@googlegroups.com.
Visit this group at
http://groups.google.com/group/sage-combinat-devel?hl=en.
For more options, visit https://groups.google.com/groups/opt_out.
--
You received this message because you are subscribed to the Google Groups
sage-combinat-devel group.
To unsubscribe from this group and stop receiving emails from it, send an email
to sage-combinat-devel+unsubscr...@googlegroups.com.
To post to this group, send email to
Re: [sage-combinat-devel] Re: How to solve this combinatorial problem in Sage?
Hi Simon, Nathann,
On Mon, Apr 15, 2013 at 11:17:14AM +, Simon King wrote:
On 2013-04-15, Simon King simon.k...@uni-jena.de wrote:
I have a finite set X and a set S of subsets of X. I'd like to get a
list (or better: an iterator) of all subsets U of S (i.e., subsets of
subsets) such that the union of the elements of U is equal to X.
Ideally, I'd like that the number of intersection points (counted with
multiplicity) of elements of U is ascending.
Hence, if there is a disjoint cover of X by elements of S, then I'd like
to get this first, and otherwise I'd like to first get a cover that is as
close to being disjoint as possible.
I have found that one can get disjoint (exact) covers via dancing
links.
For non exact covers, this can be formulated straightforwardly as a
Mixed Integer Linear Program (MILP): take a 0-1 variable y_S for each
set S, and an inequation $\sum_{S, x\in S} y_S \geq 1$. So the problem
can be reduced (efficiently???) to that of iterating through the
integer points in a polytope. There are very optimized software using
backtracking algorithm to find optimal solutions for such systems of
equations.
As for iterating: Nathann, I haven't been following up on this one; do
you know what's the current status of this feature?
On a related note: Serge Guelton is working on Python bindings for the
ISL library, which might have this kind of features. Last time I got
in touch, he was considering coming to the Sage-Combinat days in June.
Cheers,
Nicolas
--
Nicolas M. Thiéry Isil nthi...@users.sf.net
http://Nicolas.Thiery.name/
--
You received this message because you are subscribed to the Google Groups
sage-combinat-devel group.
To unsubscribe from this group and stop receiving emails from it, send an email
to sage-combinat-devel+unsubscr...@googlegroups.com.
To post to this group, send email to sage-combinat-devel@googlegroups.com.
Visit this group at http://groups.google.com/group/sage-combinat-devel?hl=en.
For more options, visit https://groups.google.com/groups/opt_out.
