Improving MinimalGeneratingSystem algorithm

[Rhuancpq]

I'm researching in NumericalSemigroups and currently working on a different algorithm that can solve the problem of finding minimal generating system.

My implemented algorithm appears to be more efficient, in means of time complexity, and uses Breadth-first search (BFS).

I'm interested in bringing this algorithm to NumericalSGPS package. 🤩

[pedritomelenas]

@Rhuancpq, thank you for your interest. Sure, you can implement your algorithm, then we will run tests to see if it improves the existing one.

[Rhuancpq]

Which tests do you use? Can I run some of them?

[pedritomelenas]

We have random functions to generate numerical semigroups. With these we produce large lists of semigroups and then see if the new algorithm is faster.
The package itself has a test file, to check for consistency everytime we change something.
You can post your code here or do a pull request.

[pedritomelenas]

One may try examples like this.

gap> l:=RandomListForNS(70,100,1500);;
gap> MinimalGenerators(NumericalSemigroup(l));time;
[ 132, 162, 190, 216, 229, 231, 233, 238, 296, 308, 313, 337, 472 ]
6
gap> FindMinimalSet(l);time;
9
gap> l:=RandomListForNS(200,100,1500);;
gap> MinimalGenerators(NumericalSemigroup(l));time;
[ 120, 150, 167, 182, 222, 305, 308, 328, 339, 376, 416, 493, 535, 701, 705,
  773 ]
4
gap> FindMinimalSet(l);time;
18
gap> l:=RandomListForNS(300,100,2500);;
gap> MinimalGenerators(NumericalSemigroup(l));time;
[ 393, 609, 669, 710, 818, 866, 1023, 1204, 1540, 1602, 1740, 1821, 1909,
  1932, 1984, 1989, 2056, 2059, 2065, 2109, 2364 ]
1
gap> FindMinimalSet(l);time;
4
gap> l:=RandomListForNS(400,100,2500);;
gap> MinimalGenerators(NumericalSemigroup(l));time;
[ 131, 134, 135, 138, 155, 166, 187, 198, 220, 239, 245, 248, 275, 291, 309,
  323, 334, 343, 345, 359, 367, 389 ]
13
gap> FindMinimalSet(l);time;
35

Where FindMinimalSet is taken from https://github.com/Rhuancpq/NumericalSemigroups/blob/develop/geradores/bfs_sub.g

[Rhuancpq]

Sure, My algorithm works like some part of MinimalGeneratingSystemOfNumericalSemigroup method in basics.gi.
To be more precise, works as same in line 380 - 400; I will fork this repository.
There is a way to run these tests as a fork of this package?

[pedritomelenas]

Yes, MinimalGenerators "call" that MinimalGeneratingSystemOfNumericalSemigroup (it is just a synonim). So we would be happy if you can improve the timings for FindMinimalSet. You can simply use the idea in my last post to compare both procedures.