(47-6) 19 * << * >> * Russian * English * Content * All Issues

Methods, algorithms and programs of computer algebra in problems of registration and analysis of random point structures
A.L. Reznik 1, A.A. Soloviev 1

1 Institute of Automation and Electrometry of the Siberian Branch of the Russian Academy of Sciences,
630090, Novosibirsk, Russia, Academician Koptyug ave. 1

 PDF, 764 kB

DOI: 10.18287/2412-6179-CO-1330

Pages: 1011-1017.

Full text of article: English language.

Abstract:
An original approach to solving difficult time-consuming problems of registration and analysis of random point images is described. The approach is based on the development and application of high-performance specialized computer algebra systems. Three software packages have been created specifically for carrying out equivalent analytical transformations on a computer. The first software system is designed to calculate formulas describing the volumes of convex polyhedra with parametrically specified boundaries in n-dimensional space. The second system is based on the calculation of multidimensional integral expressions by the method of cyclic differentiation of the integral with respect to the parameter. The third system is based on the accelerated implementation of complex combinatorial-recursive transformations on a computer. Another distinctive feature of the work is the extension of the classical Catalan numbers to the multidimensional case (they were required to solve a number of intermediate probabilistic-combinatorial problems). The implementation of the above computer algebra software systems on a multi-core cluster of Novosibirsk State University, together with the direct use of the explicit form of generalized Catalan numbers, allowed the authors to obtain several new previously unknown probabilistic formulas and dependencies required for solving problems in the field of analysis of random point images.

Keywords:
methods of computer algebra, algorithms of computer algebra, programs of computer algebra, random point structures.

Citation:
Reznik AL, Soloviev AA. Methods, algorithms and programs of computer algebra in problems of registration and analysis of random point structures. Computer Optics 2023; 47(6): 1011-1017. DOI: 10.18287/2412-6179-CO-1330.

Acknowledgements:
This work was supported by Ministry of Science and Higher Education of the Russian Federation (project no. № AAA-A17-117052410034-6).

References:
  1. Recio T, Losada-Liste R, Tabera LF, Ueno C. Visualizing a cubic linkage through the use of CAS and DGS. Mathematics 2022; 10(15): 2550. DOI: 10.3390/math10152550.
  2. Koepf W. Computer algebra: An algorithm-oriented introduction. Cham: Springer Nature Switzerland AG; 2022. ISBN: 978-3-030-78016-6.
  3. Bright С, Kotsireas I, Ganesh V. Applying computer algebra systems with SAT solvers to the Williamson conjecture. J Symb Comput 2020; 100: 187-209. DOI: 10.1016/j.jsc.2019.07.024.
  4. Meurer A, Smith C, Paprocki M, et al. SymPy: symbolic computing in Python. PeerJ Comput Sci 2017; 3: e103. DOI: 10.7717/peerj-cs.103.
  5. Moses J. Macsyma: A personal history. J Symb Comput 2012; 47(2): 123-130. DOI: 10.1016/j.jsc.2010.08.018.
  6. Peeters K. Introducing Cadabra: a symbolic computer algebra system for field theory problems. arXiv Preview. 2018. Source: <https://arxiv.org/abs/hep-th/0701238>.
  7. McCallum M. Computer algebra in gravity research. Living Reviews in Relativity, 2018; 21(1): 6. DOI:10.1007/s41114-018-0015-6.
  8. Kantorovich LV. On carrying out numerical and analytical calculations on machines with program control [In Russian]. Izvestiya AN ArmSSR, Seriya Fiz-Mat Nauk 1957; 10(2): 3-16.
  9. Shurygin VA, Yanenko NN. On the realization of algebraic-differential algorithms on the computer [In Russian]. Problems of Cybernetics 1961; 1: 33-43.
  10. Bezhanova MM, Katkov VL, Pottosin IV. Work on analytical transformations in the Computing Center of the Siberian Branch of the USSR Academy of Sciences [In Russian]. T 3. Kharjkov: "FTINT AN USSR" Publisher; 1972: 18-20.
  11. Gerdt VP, Tarasov OV, Shirkov DV. Analytical calculations on computers in the application to physics and mathematics [In Russian]. Uspekhi Fizicheskih Nauk 1980; 130 (1): 113-147.
  12. Glushkov VM, Grinchenko TA, Dorodnicyna AA, et al. ANALITIK-74 [In Russian]. Cybernetics 1978; 5: 114-147.
  13. Reznik AL, Efimov VM, Soloviev AA, Torgov AV. Reliability of readout of random point fields with a limited number of threshold levels of the scanning aperture. Optoelectronics, Instrumentation and Data Processing 2014; 50(6): 582-588. DOI: 10.3103/S8756699014060065.
  14. Reznik AL, Soloviev AA. Software and combinatorial-probabilistic tools for the analysis of random point structures. Pattern Recognit Image Anal 2022; 32(3): 636-638. DOI: 10.1134/S1054661822030348.
  15. Wilks S. Mathematical statistics. Princeton: Princeton University Press; 1944.
  16. Parzen E. Modern probability theory and its applications. New York: John Wiley and Sons; 1960.
  17. Darling DA. On class problems related to the random division of an interval. Ann Math Stat 1953; 24: 239-253.
  18. David G. Ordinal statistics [In Russian]. Moscow: "Nauka" Publisher; 1979.
  19. Reznik AL, Tuzikov AV, Soloviev AA, Torgov AV. Analysis of random point images with the use of symbolic computation codes and generalized Catalan numbers. Optoelectronics, Instrumentation and Data Processing 2016, 52(6): 529-536. DOI: 10.3103/S8756699016060017.
  20. Saracevic M, Adamovic S, Macek N, Selimi A, Pepic S. Source and channel models for secret-key agreement based on Catalan numbers and the lattice path combinatorial approach. J Inf Sci Eng 2021, 37(2): 469-482. DOI: 10.6688/JISE.202103_37(2).0012.
  21. André D. Solution directe du problème résola par M. Bertrand. Comptes Rendus de l’Académie des Sciences 1887; 105: 436-437.
  22. Gessel IM, Zeilberger D. Random walk in a Weyl chamber. Proc Am Math Soc 1992; 115(1): 27-31. DOI: 10.1090/S0002-9939-1992-1092920-8.
  23. Efimov VM, Iskoldsky AM, Krendel YM, Livshits ZA. On the characteristics of various methods for discrete structure images readout [In Russian]. Avtometriya 1973; 1: 3-7.
  24. Anishchenko VV, Vankevich PE, Kovalev VA, Kutsan NV, Lapitsky VA, Linev VN. The use of digital scanning devices and advanced telemedicine technologies in the diagnosis of lung diseases. Minsk: "OIPI NAS of Belarus" Publisher; 2010.
  25. Reznik AL, Tuzikov AV, Soloviev AA, Torgov AV, Kovalev VA. Time-optimal algorithms focused on the search for random pulsed-point sources. Computer Optics 2019; 43(4): 605-610. DOI: 10.18287/2412-6179-2019-43-4-605-610.
  26. Reznik AL, Efimov VM. Computer analytics and generalized Catalan numbers in problems of registration of random discrete objects [In Russian]. Novosibirsk: Publishing House Siberian Department of Russian Academy of Sciences; 2013. ISBN: 978-5-7692-1303-8.
  27. Reznik AL, Efimov VM, Soloviev AA, Torgov AV. About a barber from Ohio and analytical computing on a computer [In Russian]. Collection of popular science articles-winners of the RFBR competition in 2012 2013: 8-19.

© 2009, IPSI RAS
151, Molodogvardeiskaya str., Samara, 443001, Russia; E-mail: journal@computeroptics.ru ; Tel: +7 (846) 242-41-24 (Executive secretary), +7 (846) 332-56-22 (Issuing editor), Fax: +7 (846) 332-56-20