[sage-support] Re: List the codewords of minimum weight

[Simon King]

Hi Nathann,

On 2015-09-10, Nathann Cohen  wrote:
>> Seriously? At first, it crashed Sage with an error message asking me to
>> install some package---which my OS did not know. Volker eventually told
>> me that I have to install -devel...
>
> But I know that I have all the packages, for it worked in the past.

Funny...

> I cannot interupt and interruption of an interruption in order to do
> this right now.

OK, sorry.
Perhaps we are lucky and Volker (isn't he the author of the %crun
feature?) reads it and knows a solution...

Best regards,
Simon

-- 
You received this message because you are subscribed to the Google Groups 
"sage-support" group.
To unsubscribe from this group and stop receiving emails from it, send an email 
to sage-support+unsubscr...@googlegroups.com.
To post to this group, send email to sage-support@googlegroups.com.
Visit this group at http://groups.google.com/group/sage-support.
For more options, visit https://groups.google.com/d/optout.

[sage-support] Re: List the codewords of minimum weight

[Johan S. R. Nielsen]

Hi Nathann,

There is no significantly faster method than trying all possibilities. 
Finding the minimum-weight codewords of a linear code is a hard problem. 
Since your code is not too big, the naive method takes only a few seconds.

There are clever algorithms (still exponential) for computing the weight of 
the minimal weight codewords (the minimum distance of the code). I'm 
unaware whether these might be (or have been) modified to provide all 
minimum weight codewords, which could result in a practically significant 
speedup over the naive method.

Best,
Johan

On Thursday, September 10, 2015 at 9:47:25 AM UTC+2, Nathann Cohen wrote:
>
> Hell everybody, 
>
> I am trying to build an interesting 2-design from the following code: 
>
> sage: c=codes.ExtendedQuadraticResidueCode(47,GF(2)) 
> sage: c 
> Linear code of length 48, dimension 24 over Finite Field of size 2 
>
> This is to be done by listing all codewords of minimum weight (here 
> the weight is 12), but the *total* number of codewords is big. Is 
> there a faster way to obtain  only the list of light codewords? 
>
> THanks! 
>
> Nathann 
>

-- 
You received this message because you are subscribed to the Google Groups 
"sage-support" group.
To unsubscribe from this group and stop receiving emails from it, send an email 
to sage-support+unsubscr...@googlegroups.com.
To post to this group, send email to sage-support@googlegroups.com.
Visit this group at http://groups.google.com/group/sage-support.
For more options, visit https://groups.google.com/d/optout.

Re: [sage-support] Re: List the codewords of minimum weight

[Nathann Cohen]

Hello !

> There is no significantly faster method than trying all possibilities.
> Finding the minimum-weight codewords of a linear code is a hard problem.
> Since your code is not too big, the naive method takes only a few seconds.

Thanks for your answer. As it takes something like 40s and that it is
meant to become a Sage function, I hardcoded the result as compacty as
possible. We will have two versions of that code, the hardcoded one
(default) and the one that builds it from scratch (very long..) if we
need to check, or if the running time ever improves.

The ticket is http://trac.sagemath.org/ticket/19180.

> There are clever algorithms (still exponential) for computing the weight of
> the minimal weight codewords (the minimum distance of the code). I'm unaware
> whether these might be (or have been) modified to provide all minimum weight
> codewords, which could result in a practically significant speedup over the
> naive method.

HMmm... The odd thing is that %prun does not say much about what the
bottleneck is in those computations. It seems that GAP works in the
background, but I do not see it there ...

Nathann

-- 
You received this message because you are subscribed to the Google Groups 
"sage-support" group.
To unsubscribe from this group and stop receiving emails from it, send an email 
to sage-support+unsubscr...@googlegroups.com.
To post to this group, send email to sage-support@googlegroups.com.
Visit this group at http://groups.google.com/group/sage-support.
For more options, visit https://groups.google.com/d/optout.

[sage-support] Re: List the codewords of minimum weight

[Simon King]

Hi Nathann,

On 2015-09-10, Nathann Cohen  wrote:
> HMmm... The odd thing is that %prun does not say much about what the
> bottleneck is in those computations. It seems that GAP works in the
> background, but I do not see it there ...

Perhaps %crun helps?

Best regards,
Simon

-- 
You received this message because you are subscribed to the Google Groups 
"sage-support" group.
To unsubscribe from this group and stop receiving emails from it, send an email 
to sage-support+unsubscr...@googlegroups.com.
To post to this group, send email to sage-support@googlegroups.com.
Visit this group at http://groups.google.com/group/sage-support.
For more options, visit https://groups.google.com/d/optout.

Re: [sage-support] Re: List the codewords of minimum weight

[Nathann Cohen]

> Seriously? At first, it crashed Sage with an error message asking me to
> install some package---which my OS did not know. Volker eventually told
> me that I have to install -devel...

But I know that I have all the packages, for it worked in the past.

> Anyway, if it crashes, I think you should report on sage-devel, and/or
> open a ticket.

I know Simon, I know that I must do reports, create tickets, work on a
fix and everything. I was working on a patch, and noticed that I
needed to add another thing first. So now I am doing that. And to do
that I must read GAP documentation to see how it works.

I cannot interupt and interruption of an interruption in order to do
this right now.

Nathann

-- 
You received this message because you are subscribed to the Google Groups 
"sage-support" group.
To unsubscribe from this group and stop receiving emails from it, send an email 
to sage-support+unsubscr...@googlegroups.com.
To post to this group, send email to sage-support@googlegroups.com.
Visit this group at http://groups.google.com/group/sage-support.
For more options, visit https://groups.google.com/d/optout.

[sage-support] Re: List the codewords of minimum weight

[Simon King]

On 2015-09-10, Simon King  wrote:
> At first, it crashed Sage with an error message asking me to
> install some package---which my OS did not know. Volker eventually told
> me that I have to install -devel...

Now I recall: The error mentioned gperftools, but I had to install
gperftools-devel.


-- 
You received this message because you are subscribed to the Google Groups 
"sage-support" group.
To unsubscribe from this group and stop receiving emails from it, send an email 
to sage-support+unsubscr...@googlegroups.com.
To post to this group, send email to sage-support@googlegroups.com.
Visit this group at http://groups.google.com/group/sage-support.
For more options, visit https://groups.google.com/d/optout.

[sage-support] Re: List the codewords of minimum weight

[Simon King]

Hi Nathann,

On 2015-09-10, Nathann Cohen  wrote:
>> Perhaps %crun helps?
>
> Ahahaa. Well I gave it a try and it crashed Sage every time without
> any error message. Didn't feel like debugging this now ^^;

Seriously? At first, it crashed Sage with an error message asking me to
install some package---which my OS did not know. Volker eventually told
me that I have to install -devel...

Anyway, if it crashes, I think you should report on sage-devel, and/or
open a ticket.

Best regards,
Simon

-- 
You received this message because you are subscribed to the Google Groups 
"sage-support" group.
To unsubscribe from this group and stop receiving emails from it, send an email 
to sage-support+unsubscr...@googlegroups.com.
To post to this group, send email to sage-support@googlegroups.com.
Visit this group at http://groups.google.com/group/sage-support.
For more options, visit https://groups.google.com/d/optout.

Re: [sage-support] Re: List the codewords of minimum weight

[Nathann Cohen]

> Perhaps %crun helps?

Ahahaa. Well I gave it a try and it crashed Sage every time without
any error message. Didn't feel like debugging this now ^^;

"perf top" does not say much either.

Nathann

-- 
You received this message because you are subscribed to the Google Groups 
"sage-support" group.
To unsubscribe from this group and stop receiving emails from it, send an email 
to sage-support+unsubscr...@googlegroups.com.
To post to this group, send email to sage-support@googlegroups.com.
Visit this group at http://groups.google.com/group/sage-support.
For more options, visit https://groups.google.com/d/optout.

Re: [sage-support] Re: List the codewords of minimum weight

[Nathann Cohen]

Helloo again,

With this other code cleared, and I went back to this problem. You
were indeed right, I was missing the executable -_-

For some reason it was not here anymore, well. I installed it, and it
did its job. Most of the time seems to be spend on free module
elements, which is "expected", even though it probably wastes most of
the cycles.

It is still relatively easy to make this %crun crash, though:

sage: %crun -s cumlative BIBD_45_9_8(True)
/home/ncohen/.Sage//sage: line 134:  3174 Profiling timer expired
"$SAGE_ROOT/src/bin/sage" "$@"
~$

Nathann

-- 
You received this message because you are subscribed to the Google Groups 
"sage-support" group.
To unsubscribe from this group and stop receiving emails from it, send an email 
to sage-support+unsubscr...@googlegroups.com.
To post to this group, send email to sage-support@googlegroups.com.
Visit this group at http://groups.google.com/group/sage-support.
For more options, visit https://groups.google.com/d/optout.

[sage-support] Re: List the codewords of minimum weight

[Simon King]

Hi Nathann,

On 2015-09-10, Nathann Cohen  wrote:
> It is still relatively easy to make this %crun crash, though:
>
> sage: %crun -s cumlative BIBD_45_9_8(True)
> /home/ncohen/.Sage//sage: line 134:  3174 Profiling timer expired
> "$SAGE_ROOT/src/bin/sage" "$@"

I got a similar error from time to time. I have no idea how it is
triggered.

Cheers,
Simon

-- 
You received this message because you are subscribed to the Google Groups 
"sage-support" group.
To unsubscribe from this group and stop receiving emails from it, send an email 
to sage-support+unsubscr...@googlegroups.com.
To post to this group, send email to sage-support@googlegroups.com.
Visit this group at http://groups.google.com/group/sage-support.
For more options, visit https://groups.google.com/d/optout.

Re: [sage-support] Re: List the codewords of minimum weight

[Nathann Cohen]

>> sage: %crun -s cumlative BIBD_45_9_8(True)
>> /home/ncohen/.Sage//sage: line 134:  3174 Profiling timer expired
>> "$SAGE_ROOT/src/bin/sage" "$@"
>
> I got a similar error from time to time. I have no idea how it is
> triggered.

Ticket 19185 apparently fixes it. And I hope that it will also fix all
crashes due to this function.

Sorry for earlier, Simon. I really have a *lot* of things to do this
week, and when some thing triggers another which triggers another
which triggers another, I just see my mental todo-list go beyond what
I can manage and I switch to "survival mode", where I *must* finish
things so that the stack decreases.

I am on a more optimistic slope, now. Even though I still can't type
with my right index because of yesterday's "cooking" :-P

Have fun,

Nathann

http://trac.sagemath.org/ticket/19185

-- 
You received this message because you are subscribed to the Google Groups 
"sage-support" group.
To unsubscribe from this group and stop receiving emails from it, send an email 
to sage-support+unsubscr...@googlegroups.com.
To post to this group, send email to sage-support@googlegroups.com.
Visit this group at http://groups.google.com/group/sage-support.
For more options, visit https://groups.google.com/d/optout.