52 views

Skip to first unread message

May 24, 2015, 12:05:35 PM5/24/15

to sage-...@googlegroups.com, sage-codi...@googlegroups.com

On Saturday, 23 May 2015 22:36:10 UTC+1, vdelecroix wrote:

On 23/05/15 12:53, Dima Pasechnik wrote:

> please review #18480 that fixes the corner case

Thanks for the fix Dima.

>> For r > 5 it seems to hang interminably, while back in

>> November/December I could do r = 7 in a few seconds, and

>> do r = 10 without waiting too long.

this sounds very weird that minimum distance of a code of length 127 and dimension 120 (this is for r=7) can be done in few seconds

using the quite brute force algorithm, that would call GAP's AClosestVectorCombinationsMatFFEVecFFECoords

(see http://gap-system.org/Manuals/doc/ref/chap23.html#X82E5987E81487D18 for the description)

that chases all the linear combinations of i vectors, for i = 1..122 (in this case).

Probably the GAP part was buggy before and didn't return the correct results in general

(I vaguely recall there were reports of this code in GAP being buggy)

Dima

May 24, 2015, 1:38:45 PM5/24/15

to sage-codi...@googlegroups.com, sage-devel

On Sun, May 24, 2015 at 12:05 PM, Dima Pasechnik <dim...@gmail.com> wrote:

>

>

> On Saturday, 23 May 2015 22:36:10 UTC+1, vdelecroix wrote:

>>

>> On 23/05/15 12:53, Dima Pasechnik wrote:

>> > please review #18480 that fixes the corner case

>>

>> Thanks for the fix Dima.

>>

>> >> For r > 5 it seems to hang interminably, while back in

>> >> November/December I could do r = 7 in a few seconds, and

>> >> do r = 10 without waiting too long.

>

>

> this sounds very weird that minimum distance of a code of length 127 and

> dimension 120 (this is for r=7) can be done in few seconds

> using the quite brute force algorithm, that would call GAP's

> AClosestVectorCombinationsMatFFEVecFFECoords

> (see http://gap-system.org/Manuals/doc/ref/chap23.html#X82E5987E81487D18 for

> the description)

> that chases all the linear combinations of i vectors, for i = 1..122 (in

> this case).

>

Once you show that d!=1 and d!=2 (which can be done rather quickly in
>

>

> On Saturday, 23 May 2015 22:36:10 UTC+1, vdelecroix wrote:

>>

>> On 23/05/15 12:53, Dima Pasechnik wrote:

>> > please review #18480 that fixes the corner case

>>

>> Thanks for the fix Dima.

>>

>> >> For r > 5 it seems to hang interminably, while back in

>> >> November/December I could do r = 7 in a few seconds, and

>> >> do r = 10 without waiting too long.

>

>

> this sounds very weird that minimum distance of a code of length 127 and

> dimension 120 (this is for r=7) can be done in few seconds

> using the quite brute force algorithm, that would call GAP's

> AClosestVectorCombinationsMatFFEVecFFECoords

> (see http://gap-system.org/Manuals/doc/ref/chap23.html#X82E5987E81487D18 for

> the description)

> that chases all the linear combinations of i vectors, for i = 1..122 (in

> this case).

>

the binary case), all GAP needs to do is find 1 codeword of weight 3

in the kernel of the check matrix H. It doesn't seem that weird to me

that such a vector can be found quickly.

> Probably the GAP part was buggy before and didn't return the correct results

> in general

> (I vaguely recall there were reports of this code in GAP being buggy)

>

> Dima

>

> You received this message because you are subscribed to the Google Groups

> "sage-coding-theory" group.

> To unsubscribe from this group and stop receiving emails from it, send an

> email to sage-coding-the...@googlegroups.com.

> To post to this group, send email to sage-codi...@googlegroups.com.

> To view this discussion on the web visit

> https://groups.google.com/d/msgid/sage-coding-theory/ae42acec-45b7-4c6f-b818-2e07c4b342c4%40googlegroups.com.

>

> For more options, visit https://groups.google.com/d/optout.

May 24, 2015, 1:59:15 PM5/24/15

to sage-codi...@googlegroups.com

On 24/05/15 19:38, David Joyner wrote:

> On Sun, May 24, 2015 at 12:05 PM, Dima Pasechnik <dim...@gmail.com> wrote:

>>

>>

>> On Saturday, 23 May 2015 22:36:10 UTC+1, vdelecroix wrote:

>>>

>>> On 23/05/15 12:53, Dima Pasechnik wrote:

>>> > please review #18480 that fixes the corner case

>>>

>>> Thanks for the fix Dima.

>>>

>>>>> For r > 5 it seems to hang interminably, while back in

>>>>> November/December I could do r = 7 in a few seconds, and

>>> >> do r = 10 without waiting too long.

>>

>>

>> this sounds very weird that minimum distance of a code of length 127 and

>> dimension 120 (this is for r=7) can be done in few seconds

>> using the quite brute force algorithm, that would call GAP's

>> AClosestVectorCombinationsMatFFEVecFFECoords

>> (see http://gap-system.org/Manuals/doc/ref/chap23.html#X82E5987E81487D18 for

>> the description)

>> that chases all the linear combinations of i vectors, for i = 1..122 (in

>> this case).

>>

>

> Once you show that d!=1 and d!=2 (which can be done rather quickly in

> the binary case), all GAP needs to do is find 1 codeword of weight 3

> in the kernel of the check matrix H. It doesn't seem that weird to me

> that such a vector can be found quickly.

There is perhaps an algorithmic answer, but the problem is not there.
> On Sun, May 24, 2015 at 12:05 PM, Dima Pasechnik <dim...@gmail.com> wrote:

>>

>>

>> On Saturday, 23 May 2015 22:36:10 UTC+1, vdelecroix wrote:

>>>

>>> On 23/05/15 12:53, Dima Pasechnik wrote:

>>> > please review #18480 that fixes the corner case

>>>

>>> Thanks for the fix Dima.

>>>

>>>>> For r > 5 it seems to hang interminably, while back in

>>>>> November/December I could do r = 7 in a few seconds, and

>>> >> do r = 10 without waiting too long.

>>

>>

>> this sounds very weird that minimum distance of a code of length 127 and

>> dimension 120 (this is for r=7) can be done in few seconds

>> using the quite brute force algorithm, that would call GAP's

>> AClosestVectorCombinationsMatFFEVecFFECoords

>> (see http://gap-system.org/Manuals/doc/ref/chap23.html#X82E5987E81487D18 for

>> the description)

>> that chases all the linear combinations of i vectors, for i = 1..122 (in

>> this case).

>>

>

> Once you show that d!=1 and d!=2 (which can be done rather quickly in

> the binary case), all GAP needs to do is find 1 codeword of weight 3

> in the kernel of the check matrix H. It doesn't seem that weird to me

> that such a vector can be found quickly.

In the current situation, Sage has an extra argument to initialize the

minimum distance (curious but it is there). Since #18099, this argument

is used to initialize the attribute _minimum_distance but then this

attribute is completely ignored (since minimum_distance is now a

cached_method and does not rely anymore on the attribute).

So let me first say that before #18099, Sage was *not* computing the

minimum distance. It only returned an integer that was stored as an

attribute! So the timing used to be few micro seconds rather than few

seconds.

I did the review of #18099, so I might take a blame for that. I do not

know what the authors of #18099 intend to do because they talked about

refactoring the different code families.

I would feel more confortable with the method minimum_distance having an

argument force (which default to False). The behavior would be that with

force=True, the computation is always done. What do you think?

Vincent

PS: @DavidJoyner Showing that d != 1 is easy in any case since you just

have to check that your subspace is disjoint from the lines generated by

the basis. But what for d != 2? I am very curious about that! In the

binary case, you can just check explicitely that the vectors with two

entries do not belong to the subspaces. That was what you thought about?

May 24, 2015, 2:02:45 PM5/24/15

to sage-codi...@googlegroups.com

On Sun, May 24, 2015 at 1:59 PM, Vincent Delecroix

...

>>

>> Once you show that d!=1 and d!=2 (which can be done rather quickly in

>> the binary case), all GAP needs to do is find 1 codeword of weight 3

>> in the kernel of the check matrix H. It doesn't seem that weird to me

>> that such a vector can be found quickly.

>

...

>

> Vincent

>

> PS: @DavidJoyner Showing that d != 1 is easy in any case since you just have

> to check that your subspace is disjoint from the lines generated by the

> basis. But what for d != 2? I am very curious about that! In the binary

> case, you can just check explicitely that the vectors with two entries do

> not belong to the subspaces. That was what you thought about?

Not exactly. In the binary case, d=2 iff 2 columns of H are equal.

That can be checked quickly.

>

> --

> You received this message because you are subscribed to the Google Groups

> "sage-coding-theory" group.

> To unsubscribe from this group and stop receiving emails from it, send an

> email to sage-coding-the...@googlegroups.com.

> To post to this group, send email to sage-codi...@googlegroups.com.

> To view this discussion on the web visit

> https://groups.google.com/d/msgid/sage-coding-theory/55621170.2090901%40gmail.com.

...

>>

>> Once you show that d!=1 and d!=2 (which can be done rather quickly in

>> the binary case), all GAP needs to do is find 1 codeword of weight 3

>> in the kernel of the check matrix H. It doesn't seem that weird to me

>> that such a vector can be found quickly.

>

>

> Vincent

>

> PS: @DavidJoyner Showing that d != 1 is easy in any case since you just have

> to check that your subspace is disjoint from the lines generated by the

> basis. But what for d != 2? I am very curious about that! In the binary

> case, you can just check explicitely that the vectors with two entries do

> not belong to the subspaces. That was what you thought about?

That can be checked quickly.

>

> --

> You received this message because you are subscribed to the Google Groups

> "sage-coding-theory" group.

> To unsubscribe from this group and stop receiving emails from it, send an

> email to sage-coding-the...@googlegroups.com.

> To post to this group, send email to sage-codi...@googlegroups.com.

> To view this discussion on the web visit

May 24, 2015, 2:13:35 PM5/24/15

to sage-codi...@googlegroups.com

On Sunday, May 24, 2015 at 7:59:15 PM UTC+2, Vincent Delecroix wrote:

I would feel more confortable with the method minimum_distance having an

argument force (which default to False). The behavior would be that with

force=True, the computation is always done. What do you think?

-1

I think that the minimum_distance argument to LinearCode was a mistake from the beginning. The much more scalable solution is to make different families sub-classes of (what is now) AbstractLinearCode, and these will then override whatever generic stuff for this family. For instance the minimum distance of a Hamming code.

We already have the code for this and the beginning of it is already in Sage. We even have a specialised class for Hamming codes (which know their minimum distance). Soon, we will also propose to remove the minimum_distance argument again (with proper deprecation).

But we are missing reviewers: see http://trac.sagemath.org/ticket/18376

Best,

Johan

May 24, 2015, 2:21:33 PM5/24/15

to sage-codi...@googlegroups.com

potential reviewers on the ticket.

Dima

>

> Best,

> Johan

>

> --

> You received this message because you are subscribed to the Google Groups

> "sage-coding-theory" group.

> To unsubscribe from this group and stop receiving emails from it, send an

> email to sage-coding-the...@googlegroups.com.

> To post to this group, send email to sage-codi...@googlegroups.com.

> To view this discussion on the web visit

> https://groups.google.com/d/msgid/sage-coding-theory/8b4a1e6b-4598-41ab-8f0b-9d9a2163535f%40googlegroups.com.
> --

> You received this message because you are subscribed to the Google Groups

> "sage-coding-theory" group.

> To unsubscribe from this group and stop receiving emails from it, send an

> email to sage-coding-the...@googlegroups.com.

> To post to this group, send email to sage-codi...@googlegroups.com.

> To view this discussion on the web visit

May 24, 2015, 3:29:22 PM5/24/15

to sage-codi...@googlegroups.com

Well, you could have posted about this ticket here, and/or cc

potential reviewers on the ticket.

We are not yet quite sure who potential interested reviewers could be. We'll gladly Cc you another time, if you are?

You're also right: We would probably have posted here on sage-coding-theory in any case quite soon if the ticket stayed unreviewed.

(I keep saying "we" since most of the work is carried out by David Lucas)

Best,

Johan

May 24, 2015, 7:45:13 PM5/24/15

to sage-codi...@googlegroups.com

On May 25, 2015 1:59 AM, "Vincent Delecroix" <20100.d...@gmail.com> wrote:

.

> In the current situation, Sage has an extra argument to initialize the minimum distance (curious but it is there). Since #18099, this argument is used to initialize the attribute _minimum_distance but then this attribute is completely ignored (since minimum_distance is now a cached_method and does not rely anymore on the attribute).

>

> So let me first say that before #18099, Sage was *not* computing the minimum distance. It only returned an integer that was stored as an attribute! So the timing used to be few micro seconds rather than few seconds.

This was introduced by me in #13090. I was working with lot of simulations of communication systems using modifications of well known linear codes and the first stumbling block was the very long time computing the minimum distance took.

Irrespective of how the linear codes are implemented, it would be immensely helpful if some basic stuff is fast. In my usage of linear codes I had come across the following issues:

* getting minimum distance of well known codes was very slow

* iterating through all codewords was very slow

* getting the n-th codeword in some sense of "n-th" was very slow

* decoding of codes was very slow. I am glad that the linear codes are becoming individual classes. That's how I handled decoding in my own work.

@lucas Please feel free to post in this group if you want feedback. I wasn't really free the past few months but I have a bit more time at hand now and will go through the tickets when I can.

Cheers,

basu.

May 25, 2015, 6:07:00 AM5/25/15

to sage-codi...@googlegroups.com

The main issue with the original coding theory structure is that everything is considered as a "generic" linear code. For instance, when one creates a specific code family (like Hamming codes, or Reed-Solomon codes), the program silently computes a generator matrix for this code, and then calls LinearCode with this generator matrix as an argument.

So, all the specific structure was lost, and of course only generic algorithms can be used on codes, which implies slowness in computations that should not be too slow.

As Johan said, we are trying to create a new structure, relying heavily on objects to allow more scalability and flexibility. Our main objective here is to write every code family as an object, in order to be able to use specific (which are often faster) algorithms for "daily basis" computations, like decoding. For instance, with this new structure, one will be able to decode Reed-Solomon codes using Berlekamp-Welch algorithm instead of using generic (and much slower) syndrome decoding algorithm. And it will solve this minimum_distance speed computation problem too, as every code family will get its own, fitted, method to compute it.

We posted a proposition for a new structure on encoding in #18376. After that, we also have a structure to handle decoding. Once all this work will be into Sage, we will be able to focus on code families, rewrite them as classes and thus get faster algorithms for these. And we of course want to enhance implementation of several methods for "generic" linear codes with that new structure.

> @lucas Please feel free to post in this group if you want feedback. I wasn't really free the past few months but I have a bit more time at hand now and will go through the tickets when I can.

Best,

David Lucas

Reply all

Reply to author

Forward

0 new messages

Search

Clear search

Close search

Google apps

Main menu