# ПАРАЛЛЕЛЬНЫЙ АЛГОРИТМ ВЫЧИСЛЕНИЯ ФУНКЦИЙ РОСТА В КОНЕЧНЫХ ДВУПОРОЖДЁННЫХ ГРУППАХ ПЕРИОДА 5

• Published on
06-Apr-2017

• View
216

0

Embed Size (px)

Transcript

• 119

l 1, N). l - , . l D(l) = (ak 1, N), k = p1p2 . . . pl . l : 1. lmin := 1, lmax := 1. 2. lmax := lmax 2; l = lmax. 3. D = D(l); D = 1, 2; D = N , 4; 1 < D < N , . 4. lmin := lmax/2; lmidl := lmin + (lmax lmin)/2; l := lmidl. 5. D = D(l); D = 1, lmin := lmidl; lmidl := lmin + (lmax lmin)/2; l := lmidl; 5; D = N , lmax := lmidl; lmidl := lmin + (lmax lmin)/2; l := lmidl; 5; 1 < D < N , .

, - , 20, 40 60 . 10000 20 4250, 1,42 . - , , 60 :

1052808008400417645876606027989867285487720871343057551778083 =

= 123547896523698521452369860571 8521456358412963587456325968473,

29 23 .

1. .. - . .: , 2006.2. .. // IV

. . . .: , 2012. . 285286.

519.688

5

.. , .. , ..

5.

: , , -.

p , G p. , gp = e g G. G , G = G1 G2 . . . Gn Gn+1 = e, Gi G, Gi/Gi+1 p G/Gi+1.

1 6 i 6 n ai Gi, ai / Gi+1, g G

g = a11 a22 . . . a

nn , 0 6 i < p. (1)

• 120 .

(pc-) , p-quotient algorithm [1]. GAP Magma. A G, , 12 . . . s, i A, - (1)

12 . . . spq a11 a

22 . . . a

nn . (2)

(2) G. - G A - [2]. , , - .

Ks(G) G, - s; Qs(G) Ks(G), (2).

s0 N , Ks0(G) = Ks0+1(G). s0 G.

, G - A = {a1, a2, . . . , am}:

1) s = 0, K0 = {e}, Q0 = {a01a02 . . . a0n}, T = K0.2) s = s+ 1, Ks = Ks1, Qs = Qs1, V = a1T a2T . . . amT , T = , i = 1.3) vi V vi

pq vi. vi / Qs, Ks = Ks{vi}, Qs = Qs{vi}, T = T{vi}.4) i < |V |, i = i+ 1, . 3, . 5.5) T 6= , . 2; . 6.6) G s 1, Ks1(G) .

f(j) = |Kj(G)| |Kj1(G)|, 1 6 j 6 s 1. .

- . Qs pr -, 1, 2, . . . , r. r .

B0(2, 5, k) 5 k. - B0(2, 5, 12), 534. B0(2, 5, k) -, , - GAP. A = {a1, a2} B0(2, 5, k). k 6 6 B0(2, 5, k) A. , k > 2 - . B0(2, 5, k), Dk(A) A.

k |B0(2, 5, k)| Dk(A) k |B0(2, 5, k)| Dk(A)1 52 8 4 58 302 53 10 5 510 323 55 20 6 514 45

k = 7. B0(2, 5, 7) ( 518), - .

• 121

++ - MPI. - .

1. Halt D., Eick B., and OBrien E. Handbook of computational group theory. Boca Raton:

Chapman & Hall/CRC Press, 2005.2. .., .. B(2, 5)

B0(2, 5) // . - . 2009. 2. . 125132.

519.7

.. , ..

, - . - -, . - , - .

: , , .

. - , ( . pipeline) [1]. - , .

- - [2]. , . , .

- . - p . T , - T . - pT . k (C1, C2, . . . , Ck), C , T 6 kC . ( D), . , - : C D D(clock > C+D). (k + p)clock.

p - , ,