On the extension of a partial solution of d spreads to a parallelism
Keywords:
Projective space, parallelism, automorphism, parallel algorithmAbstract
A parallel algorithm for enumeration of parallelisms invariant under a predefined automorphism group is proposed. It is a parallelization of the sequential exhausted backtrack search algorithm used in [20]. The algorithm is implemented using MPI and the C++ language. It is applied for the construction of some of the parallelisms of PG(3, 4) possessing an automorphism group of order 2.
References
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.
