[GAP Forum] Time to compute Size(semigroup)

[Andrew Solomon]

Dear Jose Joao Morais,

The semigroups you are working with have different sizes
(S1 is approximately 20 times larger than S2), the elements
are represented differently and may not even have the same number of
generators.

The algorithm used to find the size of a semigroup is the naive one
(see RightSemigroupIdealEnumeratorDataGetElement in smgideal.gi).
At the top level the algorithm involves multiplicative closure of a set
and lower down, it involves insertion into a sorted list.

I can see no reason why the timings for the same functions should be
comparable, as the complexity of each one would depend upon
the number of generators, the size of the semigroup and the number of
points in the transformations.

Future discussions on such rather technical topics might be better
conducted via support at gap-system.org to avoid swamping the forum.

Andrew Solomon


On Tue, Jan 27, 2004 at 11:08:22AM +0000, Jose Joao Morais wrote:
> Dear GAP Forum,
> 
> 	I have a semigroup of transformations S1. Then I do
> 
> gap> Size(S1);
> 39536
> 
> 	and this is what I got with DisplayProfile()
> 
> gap> DisplayProfile();
>   count  self/ms  chld/ms  function
>   39537       10      -10  UnderlyingCollection: system getter
>   39537       30        0  UnderlyingCollection
>   39543       50        0  ADD_LIST
>  276739      260       20  EQ: for two transformations of the same set
>  237221      620      -10  Enumerator: for a collection that is a list
>   39530     1420      700  AddSet: for mutable internally represented
> list, and object
>   39530       80     2110  AddSet
> 3950033     5680     -220  LT: <trans> < <trans>
>  237216     6040     1040  PROD: trans * trans
>  237216     3370     5280  IN: for an object, and a small list
>   39537     1060    18050  ISB_LIST: for a right semigroup ideal
> enumerator
>  790742      480    18710  Size: for a list that is a collection
>       1        0    19190  Size: for a collection
>       3        0    19190  Order: for a group
>       1       60    19130  LENGTH: for a semigroup ideal enumerator
>            19190           TOTAL
> 
> 
> 
> 
> 
> 	For another semigroup S2, which is a semidirect product semigroup,
> whose elements are Tuples, I did
> 
> gap> Size(S2);
> 1764
> 
> 	after clearing the Profile information I got these times
> 
> gap> DisplayProfile();
>   count  self/ms  chld/ms  function
> 165128*     9060     -430  UnderlyingCollection: system getter
> 165128*    18000     9280  UnderlyingCollection
> 8863493     9230      120  EQ: for two transformations of the same set
>  425088      680      570  AddSet
> 1627094     1920      -50  LT: <trans> < <trans>
>  127008     2180      340  PROD: trans * trans
>   63504      670     4270  IN: for an object, and a small list
> 165128*    53310    97690  ISB_LIST: for a right semigroup ideal
> enumerator
> 171496*     9570   141430  Size: for a list that is a collection
>       1        0   151000  Size: for a collection
>       4        0   151000  Order: for a group
>       1        0   151000  LENGTH: for a semigroup ideal enumerator
> 
> (Total    104620)
> 
> 
>   63504       10       40  SemiDirectProductSemigroupElmAction: system
> getter
>  127008       50       20  Enumerator: system getter
>  127008      100      -30  IsSingleValued
>  127010      100        0  FamilySource: system getter
>  127008      100       10  IsTotal
>  127013      130       20  Enumerator: for a collection that is a list
>  127010      120       50  Tester(FamilySource)
>   63504      190        0  SemiDirectProductSemigroupElmAction
>  127008      170       30  Source: for default general mapping
>  127009      180       50  Enumerator
>  127010      180       90  FamilySource
>   65301      140      160  EQ: for two pairs
>  127008      110      210  PreImagesRange: for total general mapping
> (delegate to `Source')
>  508330      190      140  EQ: for two families: delegate to
> `IsIdenticalObj'
>   63540      450       50  Setter(SemiDirectProductSemigroupElmAction):
> system setter
>  425088      500        0  AddSet: for mutable internally represented
> list, and object
>   63540       80      500  Setter(SemiDirectProductSemigroupElmAction)
>   63540      830       60  Setter(IsSemiDirectProductSemigroupElm)
>  127008     2040     1740  ImageElm: for mapping by function
>  127008      140     3790  ImageElm
>  667623     2250     1720  LT: for two pairs
> 8255520    13190    45140  ELM_LIST: for a right semigroup ideal
> enumerator
>  127008    22500   111250  IN: for a semigroup ideal emunerator
>  127008      370   133980  IN: for a domain, and an element
>   63504     2260   143390  PROD: for two elements of a semidirect
> product semigroup
>           151000           TOTAL
> 
> 
> 
> 
> 	I wonder if anyone could give me an hint on why the times for the
> common methods between these two results are so much higher in the case
> of S2.
> 
> 
> 	Thank you,
> 	Jose Morais
> 	
> 
> _______________________________________________
> Forum mailing list
> Forum at mail.gap-system.org
> http://mail.gap-system.org/mailman/listinfo/forum

-- 
http://www-staff.it.uts.edu.au/~andrews/
Department of Computer Systems,
University of Technology, Sydney
PO Box 123, Broadway NSW Australia 2007
phone: +61-2-9514-7938            fax:   +61-2-9514-4535
CRICOS provider code - 00099F