Разширяване на частично решение от d спреда до паралелизъм
Ключови думи :
проективно пространство, паралелизъм, автоморфизъм, паралелен алгоритъмАбстракт
Предложен е паралелен алгоритъм за построяване на паралелизми, инвариантни спрямо предварително зададена група от автоморфизми. Той представлява паралелизация на последователния алгоритъм за търсене с връщане, използван в New parallelisms of PG(3, 4) (от Топалова и Железова, в Electronic Notes in Discrete Mathematics, 57, (2017) 193–198). Алгоритъмът е реализиран с помощта на MPI и езика С++. В статията е тествана работата му при използване на различен брой процеси и при конструиране на някои паралелизми на PG(3, 4), притежаващи група от автоморфизми от ред 2.
Литература (библиография)
R. Baker. Partitioning the planes of AG2m(2) into 2-designs. Discrete Math, 15 (1976), 205–211.
A. Betten. The packings of P G(3, 3). Des. Codes Cryptogr., 79, 3 (2016), 583–595.
A. Betten. Spreads and Packings – an Update. Booklet of Combinatorics 2016, Maratea (PZ), Italy, 29th May–5th June, 2016, 45.
A. Betten, S. Topalova, S. Zhelezova. Parallelisms of PG(3, 4) invariant under a Baer involution. Proceedings of the 16th International Workshop on Algebraic and Combinatorial Coding Theory, Svetlogorsk, Russia, 2018, 57–61.
A. Betten, S. Topalova, S. Zhelezova. Parallelisms of PG(3, 4) invariant under cyclic groups of order 4. In: Algebraic Informatics. CAI 2019. (eds M. Ciric, M. Droste, J. E. Pin) Lecture Notes in Computer Science, vol. 11545, 2019, 88–99.
A. Beutelspacher. On parallelisms in finite projective spaces. Geometriae Dedicata, 3, 1 (1974), 35–45.
R. Denniston. Packings of P G(3, q). Finite Geometric Structures and Their Applications, Edizioni Cremonese, Rome, (1973) 193–199.
J. Eisfeld, L. Storme. (Partial) t-spreads and minimal t-covers in finite projective spaces. Lecture notes from the Socrates Intensive Course on Finite Geometry and its Applications, Ghent, April 2000.
N. Johnson. Combinatorics of Spreads and Parallelisms. Iowa City, CRC Press, 2010.
C. Kaklamanis, G. Persiano. Branch-and-bound and backtrack search on mesh- connected arrays of processors. Theory of Computing Systems, 27 (1994), 471–489.
K. Richard, Y. Zhang. Randomized Parallel Algorithms for Backtrack Search and Branch-and-Bound Computation. Journal of the ACM, 40, 3 (1993), 765–789.
T. Penttila and B. Williams, Regular packings of PG(3,q), European Journal of Combina- torics 19 (6) (1998) 713–720.
A. Prince. The cyclic parallelisms of P G(3, 5). European Journal of Combinatorics, 19, 5 (1998), 613–616.
P. Sanders. Better algorithms for parallel backtracking. In: LNCS (eds A. Ferreira, J. D. P. Rolim), vol. 980, 1995, 333–347
L. Storme. Finite Geometry. In: The CRC Handbook of Combinatorial Designs, CRC Press, second edition, 2006, 702–729.
S. Topalova. Conjugates for finding the automorphism group and isomorphism of design resolutions. Serdica Journal of Computing, 10, 1 (2016), 79–92.
S. Topalova, S. Zhelezova. On transitive parallelisms of P G(3, 4). Appl. Algebra Engrg. Comm. Comput., 24, 3–4 (2013), 159–164.
S. Topalova, S. Zhelezova. On point-transitive and transitive deficiency one parallelisms of P G(3, 4). Designs, Codes and Cryptography, 75, 1 (2015), 9–19.
S. Topalova, S. Zhelezova. New Regular Parallelisms of PG(3, 5). Journal of Combinatorial Designs, 24 (2016), 473–482.
S. Topalova, S. Zhelezova. New parallelisms of PG(3, 4). Electronic Notes in Discrete Mathematics, 57 (2017), 193–198.
S. Topalova, S. Zhelezova. Types of spreads and duality of the parallelisms of PG(3, 5) with automorphisms of order 13. Designs, Codes and Cryptography, 87 (2019), 2–3.
G. Zaicev, V. Zinoviev, N. Semakov. Interrelation of Preparata and Hamming codes and extension of Hamming codes to new double-errorcorrecting codes. Proc. of Second Intern. Symp. on Information Theory, (Armenia, USSR, 1971), Budapest, Academiai Kiado, 1973, 257–263.
Y. Zhang. Parallel Algorithms for Combinatorial Search Problems. EECS Department, University of California, Berkeley Technical Report No. UCB/CSD-89-543, 1989.