Opened 4 years ago
Last modified 3 years ago
#19913 needs_work enhancement
Linear Code's covering_radius method forces the use of optional package Guava
Reported by:  dlucas  Owned by:  

Priority:  major  Milestone:  sage7.2 
Component:  coding theory  Keywords:  
Cc:  Merged in:  
Authors:  David Lucas  Reviewers:  
Report Upstream:  N/A  Work issues:  
Branch:  u/dlucas/covering_radius (Commits)  Commit:  15a108ce3f7a742fca65044a695dda7ec84c4cf0 
Dependencies:  Stopgaps: 
Description
The method covering_radius
for linear codes (in linear_code.py
), uses optional package Guava for Gap by default.
If this package is not installed, the method crashes without a proper error message.
This ticket proposes a reimplementation of covering_radius
, with a generic algorithm written in Python. If Guava is not installed on the user's system, it uses the generic algorithm, else it uses the Guava one.
Change History (17)
comment:1 Changed 4 years ago by
 Branch set to u/dlucas/covering_radius
comment:2 Changed 4 years ago by
 Commit set to ce9b19cdfd3c6dece69a2eb73a6b651dc5749dcd
 Status changed from new to needs_review
comment:3 Changed 4 years ago by
 Commit changed from ce9b19cdfd3c6dece69a2eb73a6b651dc5749dcd to c13dc05eb34d6fe59be06b651760478aa537d87e
Branch pushed to git repo; I updated commit sha1. New commits:
c13dc05  covering_radius is now a cached method

comment:4 Changed 4 years ago by
As computing the covering radius is quite slow, I made this method a cached method. This is still open for review.
comment:5 Changed 4 years ago by
Could you only nest inside of the try/except what needs to be, i.e. the 'load_package' command?
As it is, any 'RuntimError?' raised by another line would be interpreted as a missing package, though it may well have another cause.
Thanks,
Nathann
comment:6 Changed 4 years ago by
Alternatively, there is this trick that Dima used somewhere else:
if not bool(libgap.LoadPackage("grape")): <code>
comment:7 Changed 4 years ago by
 Commit changed from c13dc05eb34d6fe59be06b651760478aa537d87e to 37dad1a7c7504bde31fabdf450f325a591f4a08c
Branch pushed to git repo; I updated commit sha1. New commits:
37dad1a  Better test to check if Guava is installed

comment:8 Changed 4 years ago by
Hello,
Thanks for your remark! I picked Dima's trick and fixed my code.
David
comment:9 Changed 4 years ago by
 Commit changed from 37dad1a7c7504bde31fabdf450f325a591f4a08c to 654b4e24b961fd63c20e6cfd737554339177e5ce
comment:10 Changed 4 years ago by
It actually seems that
if not bool(libgap.LoadPackage("Guava")): <code>
calls an error message which invites the user to install Guava if it's not installed.
Anyway, I went back to a (proper) try
except
block.
comment:11 Changed 3 years ago by
 Commit changed from 654b4e24b961fd63c20e6cfd737554339177e5ce to 15a108ce3f7a742fca65044a695dda7ec84c4cf0
Branch pushed to git repo; I updated commit sha1. New commits:
15a108c  Merged with latest beta and fixed conflict

comment:12 Changed 3 years ago by
 Milestone changed from sage7.1 to sage7.2
I updated this ticket to the latest beta and fixed merge conflict. This is still open for review.
comment:13 Changed 3 years ago by
 Status changed from needs_review to positive_review
Hi
this is incredibly slow, up to the point of being not usable. Yet the code is correct, works on very small instances, and tests are passed.
I send the status to positive review.
Daniel
comment:14 Changed 3 years ago by
 Status changed from positive_review to needs_work
Reviewer name is missing
comment:15 Changed 3 years ago by
Before setting to positive_review
again, please read comment 13 on #21339.
comment:16 Changed 3 years ago by
You might also look at this implementation: u/ylchapuy/coset_leaders
comment:17 Changed 3 years ago by
We don't really need Guava, there's all we need in gap.
I provide a sample implementation but it's buggy (try it with the code codes.ExtendedQuadraticResidueCode(17, GF(4))
)
The branch up there could also be used in #21339 , and in the method _build_lookup_table
from linear_code.py
This branch is quite efficient and computes the 177147 coset_leaders of a random linear code [30, 19] over GF(3) in less than 4 seconds, and the covering radius (5 in my example) in 3 seconds.
I pushed the patch, this is now open for review.
New commits:
Rewrote covering_radius method to have a nonguava implementation