Linear Code's covering_radius method forces the use of optional package Guava

[sagetrac-dlucas]

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.

Component: coding theory

Author: David Lucas

Branch/Commit: u/dlucas/covering_radius @ 15a108c

Issue created by migration from https://trac.sagemath.org/ticket/19913

[sagetrac-dlucas]

Branch: u/dlucas/covering_radius

[sagetrac-dlucas]

comment:2

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

---

New commits:

ce9b19c

Rewrote covering_radius method to have a non-guava implementation

[sagetrac-dlucas]

Commit: ce9b19c

[sagetrac-dlucas]

Author: David Lucas

[sagetrac-git]

Changed commit from ce9b19c to c13dc05

[sagetrac-git]

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

c13dc05

covering_radius is now a cached method

[sagetrac-dlucas]

comment:4

As computing the covering radius is quite slow, I made this method a cached method.
This is still open for review.

[nathanncohen]

comment:5

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

[nathanncohen]

comment:6

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

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

[sagetrac-git]

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

37dad1a

Better test to check if Guava is installed

[sagetrac-git]

Changed commit from c13dc05 to 37dad1a

[sagetrac-dlucas]

comment:8

Hello,

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

David

[sagetrac-git]

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

88f0d6f	Update to 7.0
654b4e2	Fixed bug with check on Guava

[sagetrac-git]

Changed commit from 37dad1a to 654b4e2

[sagetrac-dlucas]

comment:10

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.

[sagetrac-git]

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

15a108c

Merged with latest beta and fixed conflict

[sagetrac-git]

Changed commit from 654b4e2 to 15a108c

[sagetrac-dlucas]

comment:12

I updated this ticket to the latest beta and fixed merge conflict.
This is still open for review.

[sagetrac-danielaugot]

comment:13

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

[vbraun]

comment:14

Reviewer name is missing

[sagetrac-dlucas]

comment:15

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

[sagetrac-ylchapuy]

comment:16

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

[sagetrac-ylchapuy]

comment:17

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.