On Fri, Feb 22, 2008 at 12:04 PM, Jason Grout <[EMAIL PROTECTED]> wrote: > > [EMAIL PROTECTED] wrote: > > I've found a nice implementation of the DLX algorithm, which "quickly" > solves the NP-Complete exact cover problem. For those who aren't in Seattle > and haven't heard me blathering on and on and on and on about how awesome DLX > is... > > > > Let M be a binary matrix. An exact cover is a subset of the rows of the > matrix who sum (exactly) to the vector 1,1,...,1. > >
Isn't that exactly the same thing as solving M*x = [1,...,1], over GF(2)? I.e., the cost should be the same as 1 (or maybe 2) reduced echelon forms over GF(2)? If so, is "your nice implementation of the DLX algorithm" better than Gregory Bard's existing implementation of computation of reduced row echelon form of matrices over GF(2)? If the number of bits in your rows is 1000 how long does it take? On sage.math Gregory Bard's code computes the rref of a 1000x1000 random matrix over GF(2) in 0.03 seconds: sage: a = random_matrix(GF(2),1000) sage: time a.echelonize() CPU times: user 0.03 s, sys: 0.00 s, total: 0.03 s Wall time: 0.03 A 4000x4000 takes 1.46 seconds: sage: a = random_matrix(GF(2),4000) sage: time a.echelonize() CPU times: user 1.46 s, sys: 0.00 s, total: 1.46 s Wall time: 1.46 Here's an example of this relating to your example: sage: a = matrix(GF(2),4,[1,0,1,0, 1,1,0,0, 1,0,1,1, 0,1,0,1]) sage: b = matrix(GF(2), a.nrows(), [1]*a.nrows()) sage: a.solve_right(b) [0] [1] [1] [0] That solve_right uses rref behind the scenes. -- I'm naive and just curious? And I also realize that there is probably a big difference between the dense and sparse cases (also for graphs). -- William > > For example, an exact cover of > > > > 1010 > > 1100 > > 1011 > > 0101 > > 0111 > > > > is > > > > 1010 > > 0101 > > > > Just now, I've completed wrapping Antti Ajanki's implementation of DLX so > that one can easily compute the exact cover of a Sage matrix, and I've > constructed a mapping from the graph coloring problem into the exact cover > problem. Further, I've applied that to compute the chromatic number and > chromatic polynomial of graphs. I think there is sufficient interest in this > (ref #1313, #1311). > > > > Arguments for including Ajanki's code: > > 1) It's the only Python implementation of DLX I've seen. > > 2) I emailed the author, who happily added the "or later" bit after > the GPL2 > > 3) With my Sage Matrix -> DLXMatrix code (plus docstrings to > everything I added), the file dlx.py is only 8kB! > > 4) It will resolve tickets #1311 and #1313 > > > > So - I'm thinking this should be added to the combinat directory (of > course, the graph-oriented stuff will go into graphs). I'll file a ticket & > some patches today if nobody objects. > > > > *Wow* > > I'd be really happy with getting chromatic number and chromatic > polynomial into the graph theory stuff. I've been sort of embarrassed > we didn't have it :) > > Jason > > > > > > > -- William Stein Associate Professor of Mathematics University of Washington http://wstein.org --~--~---------~--~----~------------~-------~--~----~ To post to this group, send email to sage-devel@googlegroups.com To unsubscribe from this group, send email to [EMAIL PROTECTED] For more options, visit this group at http://groups.google.com/group/sage-devel URLs: http://www.sagemath.org -~----------~----~----~----~------~----~------~--~---
