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

  • Published on
    06-Apr-2017

  • View
    216

  • Download
    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 - , ,

Recommended

View more >