An algorithm for fast multiplication of elements in 2-groups based on the Zhegalkin polynomials
Автор: Kuznetsov A.А., Kuznetsova A.S., Kishkan V.V.
Журнал: Siberian Aerospace Journal @vestnik-sibsau-en
Рубрика: Informatics, computer technology and management
Статья в выпуске: 4 vol.24, 2023 года.
Бесплатный доступ
Network design for a multiprocessor computing system or data center is an important problem where the search for graph models that have attractive topological properties and allow the use of efficient routing algorithms is carried out. Cayley graphs have the indicated properties, in particular such as high symmetry, hierarchical structure, recursive design, high connectivity and fault tolerance. The definition of the Cayley graph implies that the vertices of the graph are elements of some algebraic group. Selecting a group and its generating elements allows us to obtain a graph that meets the necessary requirements for diameter, degree of vertices, number of nodes, etc. A large number of scientific articles and monographs are devoted to solving this problem. The goal of this work is to create an algorithm for fast multiplication of elements in finite 2-groups whose exponent is 2n. The first section of the article provides a theoretical justification for the algorithm for fast multiplication in finite 2-groups. It is shown that elements of these groups can be represented in the form of bit strings, and their multiplication is carried out based on the Zhegalkin polynomials. The second section presents the pseudocode of the algorithm on the basis of which the Zhegalkin polynomials are calculated. The third section demonstrates an example of obtaining the Zhegalkin polynomials for a two-generated group of exponent 4. In conclusion, the prospects for using the algorithm on the real hardware are discussed.
2-group, the Cayley graph, the Zhegalkin polynomial
Короткий адрес: https://sciup.org/148329710
IDR: 148329710 | DOI: 10.31772/2712-8970-2023-24-4-673-680
Список литературы An algorithm for fast multiplication of elements in 2-groups based on the Zhegalkin polynomials
- Heydemann M. Cayley graphs and interconnection networks, in Graph symmetry: algebraic methods and applications (Editors: Hahnand Sabidussi). Dordrecht: Kluwer Academic Publishers. 1997, P. 167–226.
- Loz E. New record graphs in the degree-diameter problem. Australasian Journal of Combinatorics. 2008, Vol. 41, P.63–80.
- Sims C. Computation with Finitely Presented Groups. Cambridge: Cambridge University Press, 1994, 628 p.
- Holt D., Eick B., O'Brien E. Handbook of computational group theory. Boca Raton: Chapman & Hall/CRC Press, 2005, 514 p.
- Schibell S., Stafford R. Processor interconnection networks and Cayley graphs. Discrete Applied Mathematics. 1992, Vol. 40, P. 337–357.
- Stamoulis G., Tsitsiklis J. Effcient routing Scheme for Multiple Broadcasts in Hypercubes. IEEE Trans. on Parallel and Distributed Systems. 1993, Vol. 4(7), P. 725–739.
- Stamoulis G., Tsitsiklis J. The Effciency of Greedy Routing in Hypercubes and Butteries. IEEE Transaction on Communication. 1994, Vol. 42(11), P. 3051–3061.
- Kiasari A., Sarbazi-Azad H. Analytic performance comparison of hypercubes and star graphs with implementation constraints. Journal of Computer and System Sciences. 2008, No. 6, P. 1000–1012.
- Akers S., Krishnamurthy B. A group theoretic model for symmetric interconnection networks. Proceedings of the International Conference on Parallel Processing. 1986, P. 216–223.
- Tang K., Arden B. Vertex-transitivity and routing for Cayley graphs in GCR representations. Proceedings of ACM Symposium on Applied Computing SAC. 1992, P. 1180–1187.
- Wang L., Tang K. Topology-Based Routing for Xmesh in Wireless Sensor Networks. Lecture Notes in Electrical Engineering. 2009. Vol.44. P. 229–239.
- Ryu J., Noel E., and Tang K. Fault-tolerant Routing on Borel Cayley Graph // IEEE ICC Next Generation Networking Symposium. 2012, P. 2872–2877.
- Shin J., Sirer E., Weatherspoon H., Kirovski D. On the feasibility of completely wireless datacenters. EEE/ACM Transaction On Networking. 2013, Vol. 21(5), P. 1666–1679.
- Kuznetsov A. A., Kuznetsova A. S. [A parallel algorithm for study of the Cayley graphs of permutation groups]. Vestnik SibGAU. 2014, No. 1(53), P. 34–39 (In Russ.).
- Camelo M., Papadimitriou D., Fabrega L., Vila P. Efficient Routing in Data Center with Underlying Cayley Graph. Proceedings of the 5th Workshop on Complex Networks CompleNet. 2014. P. 189–197.
- Kuznetsov A. A. [The Cayley graphs of Burnside groups of exponent 3]. Siberian Electronic Mathematical Reports. 2015, Vol. 12, P. 248–254 (In Russ.).
- Kuznetsov A. A., Kuznetsova A. S. [Perspective topologies of multiprocessor computing systems based on the Cayley graphs of groups of period 4]. Vestnik SibGAU. 2016, No. 3 (17), P. 575–578 (In Russ.).
- Kuznetsov A. A. [An algorithm of computation of the growth functions in finite two-generated groups of exponent five]. Prikladnaya Diskretnaya Matematika. 2016, No. 3 (33), P. 116–125 (In Russ.).
- Kuznetsov A. A., Kishkan V. V. The Cayley graphs of finite two-generator burnside groups of exponent 7. Siberian Journal of Science and Technology. 2018. No. 2, P. 217–222 (In Russ.).
- Hall P. Nilpotent groups, Notes of lectures given at the Canadian Mathematical Congress 1957 Summer Seminar, in The collected works of Philip Hall. Oxford: Clarendon Press, 1988. P. 415–462.
- Yablonsky S. V. Vvedeniye v diskretnuyu matematiku [Introduction to discrete mathematics]. Moscow, Nauka Publ., 1989, 384 p.
- Kuznetsov A. A., Kuznetsova A. S. [Fast multiplication in finite two-generated groups of exponent five]. Prikladnaya Diskretnaya Matematika. 2013, No. 1 (18), P. 110–1116 (In Russ.).
