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: sage-7.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 dlucas

  • Branch set to u/dlucas/covering_radius

comment:2 Changed 4 years ago by dlucas

  • Authors set to David Lucas
  • Commit set to ce9b19cdfd3c6dece69a2eb73a6b651dc5749dcd
  • Status changed from new to needs_review

I pushed the patch, this is now open for review.


New commits:

ce9b19cRewrote covering_radius method to have a non-guava implementation

comment:3 Changed 4 years ago by git

  • Commit changed from ce9b19cdfd3c6dece69a2eb73a6b651dc5749dcd to c13dc05eb34d6fe59be06b651760478aa537d87e

Branch pushed to git repo; I updated commit sha1. New commits:

c13dc05covering_radius is now a cached method

comment:4 Changed 4 years ago by dlucas

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 ncohen

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 ncohen

Alternatively, there is this trick that Dima used somewhere else:

if not bool(libgap.LoadPackage("grape")):
    <code>

comment:7 Changed 4 years ago by git

  • Commit changed from c13dc05eb34d6fe59be06b651760478aa537d87e to 37dad1a7c7504bde31fabdf450f325a591f4a08c

Branch pushed to git repo; I updated commit sha1. New commits:

37dad1aBetter test to check if Guava is installed

comment:8 Changed 4 years ago by dlucas

Hello,

Thanks for your remark! I picked Dima's trick and fixed my code.

David

comment:9 Changed 4 years ago by git

  • Commit changed from 37dad1a7c7504bde31fabdf450f325a591f4a08c to 654b4e24b961fd63c20e6cfd737554339177e5ce

Branch pushed to git repo; I updated commit sha1. New commits:

88f0d6fUpdate to 7.0
654b4e2Fixed bug with check on Guava

comment:10 Changed 4 years ago by dlucas

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 git

  • Commit changed from 654b4e24b961fd63c20e6cfd737554339177e5ce to 15a108ce3f7a742fca65044a695dda7ec84c4cf0

Branch pushed to git repo; I updated commit sha1. New commits:

15a108cMerged with latest beta and fixed conflict

comment:12 Changed 3 years ago by dlucas

  • Milestone changed from sage-7.1 to sage-7.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 danielaugot

  • 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 vbraun

  • Status changed from positive_review to needs_work

Reviewer name is missing

comment:15 Changed 3 years ago by dlucas

Before setting to positive_review again, please read comment 13 on #21339.

comment:16 Changed 3 years ago by ylchapuy

You might also look at this implementation: u/ylchapuy/coset_leaders

Last edited 3 years ago by ylchapuy (previous) (diff)

comment:17 Changed 3 years ago by ylchapuy

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.

Note: See TracTickets for help on using tickets.