2022 № 3(56)

CONTENTS

  1. Britvin A.V., Nikitenko N. S., Poller A.B., Poller В. V., Shakhov N. V. Characteristics of trends in the radiation dynamics of polymer planar waveguide structures with phosphors for ultraviolet information systems during long-term held tests
  2. Bobrov E.A. Algorithm for predicting human age based on a convolutional neural network using only anonymized images of eye corners        
  3. Scherbakova N. G. Modeling group interactions of complex systems. Review    
  4. Belyaev N.A. Automated construction of highly-efficient parallel programs for sparse linear algebra in LuNA system
  5. Vlasenko A. Yu, Michurov M.A., Mustafin D. E. Automating debugging and load balancing in fragmented programs
  6. Gerb A.R., Omarova G. A. Fpplication of graph theory in algebraic multigrid methods for solving sparse SLAES   

A.V. Britvin*, N.S. Nikitenko*, A.B. Poller*, B.V. Poller*’**, N. V. Shakhov *’**

* Institute of Laser Physics SB RAS, 630090, Novosibirsk, Russia
**Novosibirsk State Technical University, 630087, Novosibirsk, Russia

CHARACTERISTICS OF TRENDS IN THE RADIATION DYNAMICS OF POLYMER PLANAR WAVEGUIDE

STRUCTURES WITH PHOSPHORS FOR ULTRAVIOLET INFORMATION SYSTEMS DURING LONG-TERM FIELD TESTS

DOI: 10.24412/2073-0667-2022-3-5-13

EDN: IZOMFV

Polymer film and fiber phosphor converters — luminescent antennas — offer significant prospects for the construction of UV information sensor and telecommunication systems. Unlike lens and reflex optical elements, they have a large area and light weight, have large angles of field of view. Due to the complete internal reflection of UV radiation from phosphors in the film or fiber, the signal is concentrated at the output ends, which can be connected to photodetectors or optical cables.

Key words: ultraviolet, atmospheric optical communication lines, communication without direct visibility.

References

1.  Poller В. V. Ul’trafiolctovwc lazcrnvvc informatsionnvvc sistemv. Sostovanive i pcrspcktivv razvitiya // Sb. mater. Mezhdun. nauchn. kongr. „GEO -Sibir’“ - 2005. T. N 4. S. 181-183.
2.  Britvin A. V. Otsenka impul’snykh kharaktcristik optichcskogo atmosfernogo ul’trafiolctovogo kanala s rasscyaniycm // Vestnik NGU, scriya fizika, 2010 g. T. 5. V. 2. S. 3-5.
3.  Belov V. V., Abramochkin V. N., Gridnev YU. V. i dr. Bistatichcskaya optiko-clcktronnaya svyaz’ v UF-diapazone dlin voln. Polevyye ckspcrimcnty v 2016 g. / / Optika atmosfery i океана. 2017. N 2. S. 111-114.
4.  Popkov V. K., Zhumagulov В. T., Kalimoldaycv M. N., Poller В. V., Britvin A. V., Kuz’min A. M., Shchctinin YU. I. / / Komplcksnyyc sistcmy monitoringa nefteprovodov na baze lazcrnykh i plcnochnykh tckhnologiy, Т-Comm: Tclckommunikatsii i transport. 2013. N 3. S. 51-54.
5. Britvin A. V., Konyayev S. I., Nikitenko N. S., Povazhayev A. V., Poller В. V., Shchctinin YU. I. Mctodv postroveniva i ckspcrimcntal’nvvc kharakteristiki ul’trafiolctovvkh atmosfcrnvkh liniv svvazi. // Uspekhi sovremennoy radioelektroniki - M. ,,RADIOTEKHNIKA“. 2019 g. N 1, S. 25-28.
6.  Gari A. Shaw, Andrew M. Siegel, Melissa L. Nischan Demonstration System and Applications for Compact Wireless Ultraviolet Communications / / Proceedings of SPIE Vol. 5071 (2003).
7.  Haipeng D., Chen G., Arun K., Sadler В. M., Xu Z. Modeling of non-line-of-sight ultraviolet scattering channels for communication / / IEEE J. Sei. Areas Commun. 2009. V. 27, N 9. P. 1535-1544.
8.  Golubcnkov A. A., Karapuzikov A. I., Poller В. V. Characteristics of ultraviolet gas-discharge emitter and polimcric spectrum transformers for laser telecommunications / / MPLP, Novosibirsk, Russia, July 2-7, 2000.
9.   Shilov А. М., Poller В. V. Polimernvve svetovodv s Ivuminofornvmi dobavkami diva privemnikov opticheskogo izlucheniya // Trudy VNKSF-9. Krasnoyarsk. 2003, CH.2, S. 614.
10. Bagayev S. N., Poller В. V., Britvin A. V. i dr. Razvitiye lazernykh informatsionno- sensornykh sistem s planarnymi volnovodami i elementami mikrooptiki dlya nazemno-kosmicheskikh telekommunikatsiv i lokal’nvkh setev svvazi i kontrolva / / Materialv 11 mezhdunarodnov konferentsii „Problemy funktsionirovaniya informatsionnykh setey“ SO RAN, Novosibirsk, 2006 g. S. 22-26.
11. Manousiadis P. P., Rajbliandari S., Mulyawan R., Vithanage D. A., Chun H., Faulkner G., O’Brien D. C., Turnbull G. A., Collins S., and Samuel I. D. W. Wide field-of-view fluorescent antenna for visible light communications beyond the etendue limit // Optica. 2016. N 3 7, P. 702-706.
12. Peyronel T., Quirk K. J., Wang S. C., and Tiecke T. G. Luminescent detector for free-space optical communication // Optica. 2016. N 3 7, P. 787-792.
13. Poller В. V., Britvin A. V., Borisov B. D. i dr. Kharakteristiki energoinformatsionnoy modeli i metodov postroveniva telekommunikatsionnov i kvantovo-kriptograficheskov lazernov sistemv sputnikovoy svyazi // Problemy informatiki. 2013. N 1. S. 69-75.
14. Britvin A. V., Glushkov G. S., Nikitenko N. S., Povazhayev A. V., Poller В. V., Poller A. B., Shchetinin YU. I. Voprosv postroveniva i rezul’tatv eksperimental’nvkh issledovaniv sredstv lazerno-radiovolnovov nazemno-kosmicheskov svvazi i monitoringa / / III vserossivskava nauchno- tekhnicheskaya konferentsiya „Sistemy svyazi i radionavigatsii“ g. Krasnoyarsk, 22-23 Sentyabrya, 2016, S. 387-390.
15. Barashkov N. N., Gunder O. A. Fluorestsiruvushchive polimerv. M.:Khimiva, 1987. S. 224.
16. Tekhnicheskive svovstva polimernvkh materialov: Ucheb.-sprav. Posobive / V. K. Krvzhanovskiv, V. V. Burlov, A. D. Panimatchenko, YU. V. Krvzhanovskava. SPb.: Professiva, 2005.          
17. Serova V. N. Opticheskiye i drugiye materialy na osnove prozrachnykh polimerov. Kazan’, KGTU, 2010.
18. Britvin A. V., Nikitenko N. S., Plyusnin V. F., Poller В. V., Poller A. B., Shakhov N. V. О fotostabil’nosti akrilatnvkh i polimetilmetakrilatnvkh planarno-volokonnvkh struktur s Ivuminoforami CUMARIN 7,47,120; POPOP 6, NOL8, 12 dlya ul’trafioletovykh informatsionnykh sistem // Optika i spektroskopiya. 2022 g. N 2.

Bibliographic reference:               Britvin A.V., Nikitenko N. S., Poller A.B., Poller В. V., Shakhov N. V. Characteristics of trends in the radiation dynamics of polymer planar waveguide structures with phosphors for ultraviolet information systems during long-term held tests //journal “Problems of informatics”. 2022, № 3. P.5-13. DOI:10.24412/2073-0667-2022-3- 5-13. EDN: IZOMFV

E. A. Bobrov

M. V. Lomonosov Moscow State University

ALGORITHM FOR PREDICTING HUMAN AGE BASED ON ACONVOLUTIONAL NEURAL NETWORK USING ONLY ANONYMIZED IMAGES OF EYE CORNERS

DOI: 10.24412/2073-0667-2022-3-14-23

EDN: KVNXKW

Age-related biomarkers are qualitative and quantitative indicators of the human body’s aging processes. An organism’s biological age is critical in defining its physiological state. Machine learning has resulted in the development of a wide range of age predictors that differ in importance, simplicity of use, cost, applicability, and interpretability. The current work presents and investigates a noninvasive class of visual photographic markers of aging. This research describes a simple and reliable age indicator based on deep neural networks that uses just anonymised images of a person’s eye corners. In a large age range of a specific human population, the trained neural network has an average absolute error of less than three years.

Key words: Age Prediction, Biomedical Imaging, Computer Vision, Deep Learning, Photographic Aging Biomarker.

References

1.  Ricanek K., Tcsafayc T. Morph: A longitudinal image database of normal adult age-progression /7 Auto- matic Face and Gesture Recognition, 2006. FGR 2006. 7th International Conference on / IEEE. 2006. P. 341-345.
2.  Eidinger E., Enbar R., Hassncr T. Age and gender estimation of unfiltered faces // IEEE Transactions on Information Forensics and Security. 2014. Vol. 9, No. 12. P. 2170-2179.
3.  Rothe R., Timoftc R., Van Gool L. Deep expectation of real and apparent age from a single image without facial landmarks // International Journal of Computer Vision. 2016. P. 1-14.
4.  Guo G., Fu Y., Dyer C. R., Huang T. S. Image-based human age estimation by manifold learning and locally adjusted robust regression / / IEEE Transactions on Image Processing. 2008. Vol. 17, No. 7. P. 1178-1188.
5.  Guo G., Mu G., Fu Y., Huang T. S. Human age estimation using bio-inspired features // Computer Vision and Pattern Recognition, 2009. CVPR 2009. IEEE Conference on / IEEE. 2009. P. 112-119.
6.  Guo G., Mu G. Joint estimation of age, gender and ethnicity: CCA vs. PLS // Automatic face and gesture recognition (fg), 2013 10th ieee international conference and workshops on / IEEE. 2013. P. 1-6.
7.  Qawaqnch Z., Mallouh A. A., Barkana B. D. Deep Convolutional Neural Network for Age Estimation based on VGG-Facc Model / / arXiv preprint arXiv:1709.01664. 2017.
8.  Zhang K., Gao C., Guo L. et al. Age Group and Gender Estimation in the Wild With Deep RoR Archi- tccturc // IEEE Access. 2017. Vol. 5. P. 22492-22503.
9.   Russakovsky О., Deng J., Su Н. et al. Imagenet large scale visual recognition challenge // International Journal of Computer Vision. 2015. Vol. 115, No. 3. P. 211-252.
10.  Antipov G., Baccouche M., Dugelay J.-L. Face aging with conditional generative adversarial networks // 2017 IEEE international conference on image processing (ICIP) / IEEE. 2017. P. 2089-2093.
11.  Upchurch P., Gardner J., Pleiss G. et al. Deep feature interpolation for image content changes // Pro- ceedings of the IEEE conference on computer vision and pattern recognition. 2017. P. 7064-7073.
12.  Putin E., Mamoshina P., Aliper A. et al. Deep biomarkers of human aging: application of deep neural networks to biomarker development // Aging (Albany NY). 2016. Vol. 8, No. 5. P. 1021.
13. Horvath S. DNA methylation age of human tissues and cell types // Genome biology. 2013. Vol. 14, No. 10. P. 3156.
14. Flament F., Bazin R., Laquieze S. et al. Effect of the sun on visible clinical signs of aging in Caucasian skin // Clinical, cosmetic and investigational dermatology. 2013. Vol. 6. P. 221.
15.  Bobrov E., Georgievskaya A., Kiselev K. et al. PhotoAgeClock: deep learning algorithms for development of non-invasive visual biomarkers of aging // Aging (Albany NY). 2018. Vol. 10, No. 11. P. 3249.
16. Chollet F. Xception: Deep learning with depthwise separable convolutions // Proceedings of the IEEE conference on computer vision and pattern recognition. 2017. P. 1251-1258.
17. El Dib M. Y., El-Saban M. Human age estimation using enhanced bio-inspired features (EBIF) // Image Processing (ICIP), 2010 17th IEEE International Conference on / IEEE. 2010. P. 1589-1592.
18. Kingma D. P., Ba J. Adam: A method for stochastic optimization // arXiv preprint arXiv:1412.6980. 2014.
19. He K., Zhang X., Ren S., Sun J. Deep residual learning for image recognition // Proceedings of the IEEE conference on computer vision and pattern recognition. 2016. P. 770-778.
20.  King D. E. Dlib-ml: A machine learning toolkit // Journal of Machine Learning Research. 2009. Vol. 10, No. Jul. P. 1755-1758.
21.  Samek W., Binder A., Montavon G. et al. Evaluating the visualization of what a deep neural network has learned // IEEE transactions on neural networks and learning systems. 2016. Vol. 28, No. 11. P. 2660-2673.

Bibliographic reference: Bobrov E.A. Algorithm for predicting human age based on a convolutional neural network using only anonymized images of eye corners //journal “Problems of informatics”. 2022, № 3. P.14-23. DOI:10.24412/2073-0667-2022-3- 14-23. EDN: KVNXKW

N. G.Scherbakova

Institute of Computational Mathematics and Mathematical Geophysics SB RAS, 630090, Novosibirsk, Russia

MODELING GROUP INTERACTIONS OF COMPLEX SYSTEMS. REVIEW

DOI: 10.24412/2073-0667-2022-3-24-45

EDN: MHBGVI

Many important properties of complex systems can be described using networks. The analysis of such complex networks is based on graph theory Diestel (2005) and statistical mechanics Albert, Barabasi (2002), which provide universal tools for studying the structural and dynamic properties of the system and its components. The study of complex networks made it possible to reveal such important properties inherent in many real systems as the power law of the distribution of degrees of nodes, belonging to a small world, the presence of a giant component, evolution models. Many methods have been developed to identify important network actors and the presence of communities of actors. Reviews of research methods for complex networks can be found in publications Albert, Barabasi (2002), Newman (2010).

In many cases the use of complex networks does not provide complete information about the investigated systems. The real-life systems have many heterogeneous parts with complicated subsystem dependencies that can’t be derived from a simple graph. The concept of “higher-order networks” refers to three main lines of research designed to overcome the limitations associated with traditional models that capture only pairwise connections Battiston etal. (2020), Lambiotte etal. (2019). The first line is based on the assumption that multiple link types can be described in terms of multilayer networks, reviews of the approach can be found in Boccalctti et al. (2014), Bianconi (2018). The second has introduced non-Markovian model of nodes interactions, taking into account the correlation and temporal characteristics to identify the implicit influence of components on each other Holme (2015). The third line generalizes pairwise interactions to arbitrary node sets, these are “networks beyond pairwise interactions” Battiston etal. (2020). This direction is the scope of our short review.

To analyze complex data, a number of techniques have been developed that use various mathematical structures to represent “multiple” relationships. Hire we examine three methods of explicit encoding higher order interactions in terms of a social system that includes a certain set of individuals. Any attribute or a number of attributes that can be associated with the individuals of the system can provide a basis for forming a collection of subsets of individuals, where the subset corresponds to the individuals that have the given property. Thus, the structural framework imposed on the set of individuals by such set of subsets is considered.

R. H. Atkin in Atkin (1972, 1974, 1976) uses an algebraic approach in which the basis for the study is the concept of a simplex, a geometric figure that is an n-dimensional generalization of a triangle. Analytical methodology is based on the algebraic topology, which uses algebraic methods for studying topological spaces (see, for example, Hatcher (2002).  This work was carried out under state contract with ICMMG SB RAS (0251-2021-0005).

The simplicial complex is the set of simplices closed under the inclusion of all faces of all simplices. Q-analysis is a mathematical framework for describing and analyzing simplicial complexes.

In Seidman (1981), a collection of subsets is considered as the backcloth of a set of individuals. To the subset the term “event” (or group), which contributes to the formation of the subset, is applied. The analysis of structures imposed on a set by a collection of subsets is based on the concept of a hypergraph

S. B. Seidman noted that while the hypergraph focuses on the incidence relationships between vertices and edges (individuals and events), structures representing relationships between individuals (or between events) can be derived from the hypergraph. As an example of using the hypergraph representation, the problem of searching for “anomalies” in the original basic structure is considered.

In Wilson (1982), a research method is based on treating data as a bipartite graph. A graph is bipartite if the vertices may be partitioned into exactly two mutually exclusive sets, so that every edge has its ends in different sets: vertices of the same set cannot be adjacent Diestel (2005). In this case the two sets are the set of actors and the set of events. Such an approach, as shown in Wilson (1982), makes it possible, for example, to reveal the division of a set into groups that do not have common individuals and at the same time cover the entire set of individuals or to find sets of groups that allow activity only within the selected set of groups, forming a collective. The methods of visualizing and analyzing higher order interactions can rely on traditional network analytic technique.

Despite different approaches, the relationship between individuals and events can be represented by an incidence matrix, in which 1 in the intersection of the ith row and jth column indicates that the individual i belongs to the group j: However, simplicial complexes, hypergraphs and bipartite graphs are different structural formations. In Ouvrard (2020), comments are formulated regarding the fact that instead of studying hypergraphs, one can restrict oneself to bipartite graphs. In Torres etal. (2021), the relationships between simplicial complexes and hypergraphs were explored and showed that some information can be lost when moving from one to another.

As many applications of high-order models arose from systems initially modeled with graphs, many analysis methods imitate those originally used for graphs. This is a study of the underlying structure based on the distribution of degrees and clustering coefficients Malefic et al. (2008), Estrada, Rodriguez-Velazquez (2005) as well as identifying important actors based on measures of centrality Estrada, Ross (2018), Borgatti, Everett (1997), Faust (1997). But the definitions of classical centrality measures require generalization and clarification, since it is desirable that they reflect the relationship between the centralities of groups and the centralities of the actors that belong to the groups.

Conclusion. There is no universal complex system framework. As noted in Johnson (2013), the simplest structure can be used in any situation, but it should be choosed a framework that best fits the data and gives the necessary representational power.

Key words: complex system, hypernetwork, bipartite graph, hypergraph, simplicial complex, centrality measures.

References

1. DIESTEL R. Graph theory. Graduate texts in mathematics. Springer, 2005. ISBN 978-3-642-14278-9.
2. ALBERT R., BARABASI A-L. Statistical mechanics of complex networks // Rev. of Modern Phys. 2002. V. 74. P. 47-97. DOI: 10.1103/RevModPhys.74.47.
3. NEWMAN М. Е. J. Networks: An introduction. Oxford, NY: Oxford Univ. Press., 2010. ISBN-13: 9780199206650.
4. ROSVALL M., ESQUIVEL A. V., LANCICHINETTI A., WEST J. D., LAMBIOTTE R. Memory in network flows and its effects on spreading dynamics and community detection // Nature commun. 2014. V. 5, 4630. DOI: 10.1038/ncomms5630.
5. ON B.-W., ELMACIOGLU E., LEE D., KANG J., PEI J. Improving grouped-entity resolution using quasi-cliques // Proc, of the 6th Intern, conf, on data mining (ICDM’06). 2006. P. 1008-1015. DOI: 10.1109/ICDM.2006.85.
6.   BENSON A. R., ABEBE R., SCHAUB M. T., JADBABAIE A., KLEINBERG J. Simplicial closure and higher-order link prediction // Proc. Nat. Acad. Sci. 2018.V. 115, No. 48: E11221-E11230. DOI: 10.1073/pnas. 1800683115.
7.  JOHNSON J. Hypernetworks in the science of complex systems. UK: Imperial College Press. 2013. ISSN: 1755-7453.
8.  BATTISTON F., CENCETTI G., IACOPINI I., LATORA V., LUCAS M., PATANIA A. YOUNG J-G., PETRI G. Networks beyond pairwise interactions: Structure and dynamics // Phys. Rep. 2020. V. 874. P. 1-92. DOI: 10.1016/j.physrep.2020.05.004.
9.  LAMBIOTTE R., ROSVALL M., SCHOLTES I. From networks to optimal higher-order models of complex systems // Nature Phys. 2019. V. 15. P. 313-320. DOI: 10.1038/s41567-019-0459-y.
10. BOCCALETTI S., BlANCONI G., CRIADO R., DEL GENIO C. L, GyMEZ-GARDECES J., ROMANCE M., SENDINA-NADAL L, WANG Z., ZANIN M. The structure and dynamics of multilayer networks // Phys. Rep. 2014. V. 544(1). P. 1-122. DOI: 10.1016/j.physrep.2014.07.001.
11. BIANCONI G. Multilayer networks: Structure and function. Oxford Univ. Press. 2018. ISBN-13: 9780198753919.
12. HOLME P.Modern temporal network theory: A colloquium // Eur. Phys. J. В 88, 234. 2015. DOI: 10.1140/epjb/e2015-60657-4.
13. BORGATTI S. P., EVERETT M. G. Network analysis of 2-mode data // Soc. networks. 1997. V. 19. P. 243-269. DOI: 10.1016/S0378-8733(96)00301-2. '
14. NEWMAN M. E. J., STROGATZ, S. H., WATTS D. J. Random graphs with arbitrary degree distributions and their applications // Phys. Rev. E 64, 026118. 2001. DOI: 10.1103/PhysRevE. 64.026118.
15.  BREIGER R. L. The duality of persons and groups // Soc. Forces. 1974. V. 53, No. 2. P. 1981-1990. DOI: 10.2307/2576011.
16.  ATKIN R. H. From cohomology in physics to q-connectivity in social science // Intern. J. Man-Machine Stud. 1972. V. 4, iss. 2. R 139-167. DOI: 10.1016/S0020-7373(72)80029-4.
17.  ATKIN R. H. An algebra for patterns on a complex, I // Intern. J. Man-Machine Stud. 1974.
V. 6, iss. 3. P. 285-307. DOI: 10.1016/S0020-7373(74)80024-6.
18. ATKIN R. H. An algebra for patterns on a complex, II // Intern. J. Man-Machine Stud. 1976.
V. 8, iss. 5. P. 483-498. DOI: 10.1016/80020-7373(76)80015-6.
19. HATCHER A. Algebraic topology. Cambridge, UK: Cambridge Univ. Press, 2002.
20. SEIDMAN S. Structures induced by collections of subsets: A hypergraph approach // Math. Soc. Sci. 1981. V. 1, iss. 4. P. 381-396. DOI: 10.1016/0165-4896(81)90016-0.
21.  BERGE C. Graphs and hypergraphs. Amsterdam: North-Holland. 1976.
22.  POPKOV V.K. Giperseti i strukturnye modeli slozhnykh sistem // Matematicheskie i immitatsvonnve modeli slozhnvkh sistem: SM 6, sb. navch. trudov. Novosibirsk, 1981. P. 26-48.
23. WILSON T. P. Relational networks: An extension of sociometric concepts // Soc. Networks. 1982. V. 4, iss. 2. P. 105-116. DOI: 10.1016/0378-8733(82)90028-4.
24. ANDJELKOVIC M., TADIC B., MALETIC S., RAJKOVIC M. Hierarchical sequencing of online social graphs // Phys. A: Statistical Mechanics and its Applications. 2015. V. 436, iss. 15. P. 582-595. DOI: 10.1016/j.physa.2015.05.075.
25. ZHOU D., HUANG J., SCHOLKOPF В. Learning with hypergraphs: Clustering, classification, and embedding // Proc, of the 19th Intern, conf, on neural information processing systems. 2007. P. 1601-1608. DOI: 10.7551/mitpress/7503.003.0205.
26. BOTHOREL C., BOUKLIT M. An algorithm for detecting communities in folksonomy hypergraphs. I2CS 2011: the 11th Intern, conf, on innovative Internet community services, Berlin (Germany), June 2011. P. 159-168. hal-00724991.
27. ESTRADA E., RODRIGUEZ-VELAZQUEZ J. A. Complex networks as hypergraphs // arxiv: physics/0505137, 2005. DOI: 10.1016/j.physa.2005.12.002.
28. MORRIS S. A., YEN G. G. Construction of bipartite and unipartite weighted networks from collections of journal papers // arxiv: physics/0503061, 2005.
29. GUILLAUME J.-L., LATAPY M. Bipartite graphs as models of complex networks // Phys. A: Stat. Meehan, and its Appl. 2006. V. 371, iss. 2. P. 795-813. DOI: 10.1016/j.physa.2006.04.047.
30. GHOSHAL G., ZLATIC V., CALDARELLI G., NEWMAN M. E. J. Random hypergraphs and their applications // Phys. Rev. E 79(6), 066118. 2009. DOI: 10.1103/PhysRevE.79.066118.
31. TORRES J. J., BIANCONI G. Simplicial complexes: higher-order spectral dimension and dynamics // J. Phys.: Complexity. V. 1, iss. 1. 2020. 015002. DOI: 10.1088/2632-072X/ab82f5.
32. CARLETTI T., FANELLI D., NICOLETTI S. Dynamical systems on hypergraphs // J. of Phys.: Complexity. 2020. V. 1, iss. 3, 035006. DOI: 10.1088/2632-072X/aba8el.
33. BREDIKHIN S. V., LYAPUNOV V. M, SCHERBAKOVA N. G. Struktura i parametry nevzveshennoi seti soavtorstva na osnove dannykh BD RePEc // Problem, inform. 2021. No 3. P. 56-67. DOI: 10.24411/2073-0667-2021-3-56-57.
34.  BREDIKHIN S. V., LYAPUNOV V. M, SCHERBAKOVA N. G. Ranzhyrovanie uzlov vzveshennoy seti soavtorstva: analiz dannykh BD RePEc // Problem. Inform. 2021. No 4. P. 5-15. DOI: 10.24412/2073-0667-2021-4-67-83.
35. BERGE C. Hypergraphs. North-Holland. 1989.
36. VOLOSHIN V. I. Introduction to graph and hypergraph theory. Nova Science PubL, 2009. ISBN: 978-1-60692372-6.
37.  BRETTO A. Hypergraph theory: An introduction (Mathematical Engineering). Heidelberg: Springer Intern. Publishing, 2013. ISBN: 978-3-319-00079-4. DOI: 10.1007/978-3-319-00080-0.
38. ZYKOV A. A. Gipergrafy // Uspekhi mat. nauk. 1974. Vol. 29, iss. 6. P. 89-156.
39. STELL J. G. Relations on hypergraphs // RAMiCS’12: Proc, of the 13th Intern, conf, on relational and algebraic methods in computer science. 2012. P. 326-341. DOI: 10.1007/978-3-642- 33314-9_22.
40. OUVRARD X. Hypergraphs: An introduction and review // arxiv: 2002.05014v2, 2020.
41. BENSON A. R., GLEICH D. F., LESKOVEC J. Higher-order organization of complex networks // Science. 2016. V. 353 (6295). P. 163-166. DOI: 10.1126/science.aad9029.
42. MAKINEN E. HOW to draw a hypergraph // Intern. J. of Comput. Math. 1990. V. 34, iss. 3-4. DOI: 10.1080/00207169008803875.
43. JOHNSON D. S., POLLAK H. O. Hypergraph planarity and the complexity of drawing Venn diagrams // J. Graph Theory. 1987. V. 10. P. 309-325. DOI: 10.1002/jgt.31901103067.
44. KAUFMANN M., VAN KREVELD M., SPECKMANN B. Subdivision drawings of hypergraphs // Graph Drawing. V. 5417. P. 396-407. Berlin, Heidelberg: Springer Berlin Heidelberg, 2009. ISBN: 978-3-642-00218-2 978-3-642-00219-9. DOI: 10.1007/978-3-642-00219-9_39.
45.  TORRES L., BLEVINS A. S., BASSETT D. S., ELIASSI-RAD T. The why, how, and when of representations for complex systems // SIAM Rev. 2021. V. 63, iss. 3. P. 435-485.
46.  MALETIC S., RAJKOVIC M., VASILJEVIC D. Simplicial complexes of networks and their statistical properties // Proc. Intern, conf, on computational science, Springer. 2008. P. 568-575.
47.  ESTRADA E., ROSS G. J. Centrality in simplicial complexes. Application to protein interaction networks // J. Theor. Biol. 2018. V. 438. P. 46-60. DOI: 10.1016/j.jtbi.2017.11.003.
48. SERRANO D. Н., GOMEZ D. Centrality measures in simplicial complexes: applications of topological data analysis to network science // Appl. Math. Comput. 2020. V. 383, iss. 3, 125331. DOI: 10.1016/j.amc.2020.125331.
49. PATANIA A., PETRI G., VACCARINO F. The shape of collaboration // EPJ Data Sci. 2017. V. 6, iss. 18. DOI: 10.1140/epjds/sl3688-017-0114-8.
50. SERRANO D. H., HERNANDEZ-SERRANO J., GOMEZ D. Simplicial degree in complex networks. Applications of topological data analysis to network science // Chaos, Solitons & Fractals. 2020. V. 137, 109839. DOI: 10.1016/j.chaos.2020.109839.
51. ZHOU W., NAKHLEH U. Properties of metabolic graphs: biological organization or representation artifacts? // BMC Bioinformatics. 2011. V. 12. P. 132-144.
52. GALLAGHER S. R., GOLDBERG D. S. Clustering coefficients in protein interaction hypernetworks // BCBT3: Proc, of the Intern. Conf, on Bioinformatics, Comput. Biology and Biomedical Informatics, Washington (USA), Sept. 22-25, 2013. P. 552-560. DOI: 10.1145/2506583.2506635.
53. FREEMAN L. C. Centrality in social networks. Conceptual clarification // Soc. Networks. 1978/1979. V. 1. P. 215-239. DOI: 10.1016/0378-8733(78)90021-7.
54. FRIEDKIN N. E. Theoretical foundations for centrality measures // Amer. J. Soc. 1991. V. 96. P. 1478-1504. DOI: 10.1086/229694.
55. WASSERMAN S., FAUST K. Social network analysis. Cambridge Univ. Press, 1984. ISBN: 9780511815478. DOI: 10.1017/CBO9780511815478.
56. BOLDI P., VlGNA S. Axioms for centrality // Intern. Math. 2013. V. 10(3-4). P. 222-262. DOI: 10.1080/15427951.2013.865686.
57.  FAUST K. Centrality in affiliation networks // Social Networks. 1997. V. 19. P. 157-191. DOI: 10.1016/80378-8733(96)00300-0.
58.  KAPOOR K., SHARMA D., SRIVASTAVA J. Weighted node degree centrality for hypergraphs // Proc, of the IEEE 2nd Intern. Network Science Workshop (NSW). 2013. P. 152-155. United States, West Point, NY, April 20 - May 1, 2013. DOI: 10.1109/NSW.2013.6609212.
59. BONACICH P. Simultaneous group and individual centralities // Soc. networks 1991. V. 13, iss. 2. P. 155-168. DOI: 10.1016/0378-8733(91)90018-0.
60. BUSSENIERS E. General centrality in a hypergraph // arXiv: 1403.5162, 2014.
61. BONACICH P. Factoring and weighting approaches to status scores and clique identification // J. of Math. Soc. 1972. V. 2, No. 1. P. 113-120. DOI: 10.1080/0022250X.1972.9989806.
62.  BONACICH P. Power and centrality: A family of measures // Amer. J. Soc. 1987. V. 92, No. 5. P. 1170-1182.
63.  CHEN X. The shortest path algorithms of hypergraphs based on search strategies // J. of Software. 2015. V. 10, No. 1. P. 94-105. DOI: 10.17706/jsw.l0.1.94-105.
64.  BRANDES U. A faster algorithm for betweenness centrality // Math. Sociol. 2001. V. 25. P. 163-177. DOI: 10.1080/0022250X.2001.9990249.
65. BRANDES U. On variants of shortest-path betweenness centrality and their generic computation // Soc. Networks. 2008. V. 30. P. 136-145. DOI: 10.1016/j.socnet.2007.11.001.
66. Puzis R., PUROHIT M., SUBRAHMANIAN V. S. Betweenness computation in the single graph representation of hypergraphs // Soc. networks. 2013. V. 35, iss. 4. P. 561-572. DOI: 10.1016/j.socnet.2013.07.006.
67. COOPER J., DUTLE A. Spectra of uniform hypergraphs // Linear Algebra Appl. 2012. V. 436, iss. 9. P. 3268-3292. DOI: 10.1016/j.laa.2011.11.018.
68. Hu S., Qi L. The Laplacian of a uniform hypergraph // J. Comb. Optim. 2015. V. 29, iss. 2. P. 331-366. DOI 10.1007/sl0878-013-9596-x.
69. BANERJEE A., CHAR A., MONDAL B. Spectra of general hypergraphs // Linear Algebra Appl. 2016. V. 518, iss. 1. P. 14-30. D01:10.1016/j.laa.2016.12.022.
70. RODRIGUEZ J. A. On the Laplacian spectrum and walk-regular hypergraphs // Lin. and Multilin. Alg. 2003. V. 51, No. 3. P. 285-297.
71. SHI J., MALIK J. Normalized cuts and image segmentation // IEEE Trans, on Pattern Analysis and Machine Intell. 2000. V. 22(8). P. 888-905.
72. MEILA M., SHI J. A random walks view of spectral segmentation //In Proc. 8th Inti. Workshop on Artif. Intell, and Statistics. PMLR R3:203-208, 2001.
73. Lu L., PENG X. High-ordered random walks and generalized Laplacians on hypergraphs // Intern. Workshop on Algorithms and Models for the Web-Graph. Springer, 2011. P. 14-25.
74. MUHAMMAD A., EGERSTEDT M. Control using higher order Laplacians in network topologies // Proc, of 17th Intern. Symp. on Math. Theory of Networks and Systems, Citeseer, 2006. P. 1024-1038.
75. MOORE T. J., DROST R. J., SWAMI A. The communications and networks collaborative technology alliance publication network: a case study on graph and simplicial complex analysis // Comput. and inform, sci. Directorate, ARL, US army research Laboratory. 2015.
 

Bibliographic reference: Scherbakova N. G. Modeling group interactions of complex systems. Review //journal “Problems of informatics”. 2022, № 3. P.24-45. DOI:10.24412/2073-0667-2022-3- 24-45. EDN: MHBGVI

N. Belyaev

Institute of Computational Mathematics and Mathematical Geophysics SB RAS, 630090, Novosibirsk, Russia

AUTOMATED CONSTRUCTION OF HIGHLY-EFFICIENT PARALLEL PROGRAMS FOR SPARSE LINEAR ALGEBRA IN LUNA SYSTEM

DOI: 10.24412/2073-0667-2022-3-46-60

EDN: MTTVTE

Automatic construction of efficient scientific parallel programs for supercomputers is in general a complex problem of system parallel programming. Therefore, various specialized system algorithms for automated parallel programs construction are of use. Of interest are algorithms for automated parallel program construction from a given numerical algorithm description. These algorithms can either be general purpose or specialized. The specialized parallel program construction algorithms are of particular interest. Despite the fact that such specialized system algorithms are applicable only for restricted classes of input numerical algorithms, such specialized algorithms have a significant advantage. These algorithms allow parallel program generators to employ parallel programming techniques which are widely used in manual parallel programming to construct highly efficient parallel programs. LuNA system for automatic construction of distributed parallel programs provides a basis for accumulation of such specialized system algorithms to provide high-quality parallel programs construction in particular subject domains. This system allows automated construction of parallel programs for a distributed memory parallel computer from a given numerical algorithm description written with high-level LuNA language. In this paper, a novel specialized algorithm of parallel programs construction for sparse linear algebra domain is presented. It is applicable for a class of sparse linear algebra algorithms which includes widely used preconditioner algorithms for sparse systems of linear equations. This fact makes the developed specialized system algorithm of practical interest. The presented specialized automated parallel program construction algorithm has been implemented as a specialized run-time system which has been integrated into the LuNA system and the module which has been integrated into the LuNA compiler. In order to integrate the implementation of the developed specialized system algorithm into the LuNA system the following approach is used. The LuNA compiler detects if the input numerical algorithm description written with LuNA language belongs to a class of numerical algorithms for which the LuNA system has a specialized support. In this case the corresponding specialized system algorithms are used to construct the so-called intermediate parallel program. Otherwise the previously developed general purpose parallel program construction algorithms are used. The control program constructs an executable representation of the input numerical algorithm at run-time. The executable representation of the input algorithm is a directed acyclic graph of single assignment variables and operations. This representation is then executed by the specialized run-time system. The specialized run-time system employs parallel programming techniques which are widely used in manual development of parallel preconditioners for sparse matrices. In order to assess the performance of parallel programs constructed using the developed specialized system algorithms, a test parallel program was automatically constructed from the description of sparse-vector multiply algorithm. The performance of the automatically constructed parallel program was compared to the

performance of implementation of the same algorithm from Intel MKL and Parallel Sparse BLAS libraries. Experimental results demonstrate that the performance of the automatically generated parallel program is comparable with the performance of the corresponding implementation from Intel MKL (the performance of the automatically constructed parallel program is only 15 % less than the performance of the matrix-vector multiply implementation from Intel MKL) . Also the constructed parallel program outperforms the implementation for Parallel Sparse BLAS library by approximately 10 %. These facts show that the LuNA system is practically applicable for automated construction of high performance distributed parallel programs for supercomputers in the sparse linear algebra field.

Key words: DAG, parallel preconditioner, parallel program synthesis, fragmented programming, task based parallelism, parallel run-time system, parallel programming system.

References

1.  Schenk O., Gunner K., Fichtner W. Efficient sparse LU factorization with left-right looking strategy on shared memory multiprocessors // BIT Numerical Mathematics. 2000. T. 40. N 1. P. 158-176.
2.  Yamazaki L, Li X. S. New scheduling strategies and hybrid programming for a parallel right-looking sparse LU factorization algorithm on multicore cluster systems // 2012 IEEE 26th International Parallel and Distributed Processing Symposium. IEEE, 2012. P. 619-630.
3.  Davis T., Stanley K. Sparse lu factorization of circuit simulation matrices // [Electron. Res.]: www. cise. ufl. edu/davis/techreports/KLU/pp04. pdf.
4. Geist G. A., Romine С. H. LU factorization algorithms on distributed-memory multiprocessor architectures // SIAM Journal on Scientific and Statistical Computing. 1988. T. 9. N 4. P. 639-649.
5.  Choi J. et al. ScaLAPACK: A portable linear algebra library for distributed memory computers— Design issues and performance // Computer Physics Communications. 1996. T. 97. N 1-2. P. 1-15.
6. Choi J. et al. Design and implementation of the ScaLAPACK LU, QR, and Cholesky factorization routines //Scientific Programming. 1996. T. 5. N 3. P. 173-184.
7.  Gates M. et al. Slate: Design of a modern distributed and accelerated linear algebra library // Proceedings of the International Conference for High Performance Computing, Networking, Storage and Analysis. 2019. P. 1-18.
8.  Kurzak J. et al. Designing SLATE: Software for linear algebra targeting exascale. 2017.
9. Grigori L., Demmel J. W., Li X. S. Parallel symbolic factorization for sparse LU with static pivoting // SIAM Journal on Scientific Computing. 2007. T. 29. N 3. P. 1289-1314.
10.  Schenk O. Scalable parallel sparse LU factorization methods on shared memory multiprocessors: dis. ETH Zurich, 2000.
11.  Schenk O., Gunner K., Fichtner W. Efficient sparse LU factorization with left-right looking strategy on shared memory multiprocessors // BIT Numerical Mathematics. 2000. T. 40. N 1. P. 158-176.
12.  Toledo S. Locality of reference in LU decomposition with partial pivoting //SIAM Journal on Matrix Analysis and Applications. 1997. T. 18. N 4. P. 1065-1081.
13.  Schenk O., Gunner K. Solving unsymmetric sparse systems of linear equations with PARDISO // Future Generation Computer Systems. 2004. T. 20. N 3. P. 475-487.
14.  Schenk O. et al. PARDISO: a high-performance serial and parallel sparse linear solver in semiconductor device simulation // Future Generation Computer Systems. 2001. T. 18. N 1. P. 69-78.
15.  Amestoy P. R. et al. MUMPS: a general purpose distributed memory sparse solver // International Workshop on Applied Parallel Computing. Springer, Berlin, Heidelberg, 2000. P. 121-130.
16.  Hysom D., Pothen A. A scalable parallel algorithm for incomplete factor preconditioning // SIAM Journal on Scientific Computing. 2001. T. 22. N 6. P. 2194-2215.
17.  Hysom D., Pothen A. Efficient parallel computation of ILU (k) preconditioners // Proceedings of the 1999 АСМ/IEEE conference on Supercomputing. 1999. P. 29-es.
18.  Kale L. V., Krishnan S. Charm++ A portable concurrent object oriented system based on C++ // Proceedings of the eighth annual conference on Object-oriented programming systems, languages, and applications. 1993. P. 91-108.
19.  Bauer M. et al. Legion: Expressing locality and independence with logical regions // SC’12: Proceedings of the International Conference on High Performance Computing, Networking, Storage and Analysis. IEEE, 2012. P. 1-11.
20.  Slaughter E. et al. Regent: A high-productivity programming language for HPC with logical regions // Proceedings of the International Conference for High Performance Computing, Networking, Storage and Analysis. 2015. P. 1-12.
21.  Malyshkin V. E., Perepelkin V. A. LuNA fragmented programming system, main functions and peculiarities of run-time subsystem // International Conference on Parallel Computing Technologies. Springer, Berlin, Heidelberg, 2011. P. 53-61.
22.  Belyaev N., Perepelkin V. High-Efficiency Specialized Support for Dense Linear Algebra Arithmetic in LuNA System // International Conference on Parallel Computing Technologies. Springer, Cham, 2021. P. 143-150.
23.  Bosilca G. et al. Parsec: Exploiting heterogeneity to enhance scalability //Computing in Science & Engineering. 2013. T. 15. N 6. P. 36-45.
24.  Malyshkin V. E. Tekhnologiya fragmentirovannogo programmirovaniya // Vestnik YUzhno- Ural’skogo gosudarstvennogo universiteta. Seriya: Vychislitel’naya matematika i informatika. 2012. N 46 305.
25.  Bichot С. E., Siarry P. (ed.). Graph partitioning. John Wiley & Sons, 2013.
26.  Pellegrini F. Scotch and libScotch 5.1 user’s guide. 2008.
27.  Karypis G., Kumar V. METIS: A software package for partitioning unstructured graphs, partitioning meshes, and computing fill-reducing orderings of sparse matrices. 1997.
28.  ZHdanov A. L, Bogdanova E. YU. Ob odnoj vychislitel’noj realizacii blochnogo metoda Gaussa- Zejdelya dlya normal’nyh sistem uravnenij // Vestnik Samarskogo gosudarstvennogo tekhnicheskogo universiteta. Seriya Fiziko-matematicheskie nauki. 2016. T. 20. N 4.
29.  Davis T. A., Hu Y. The University of Florida sparse matrix collection //ACM Transactions on Mathematical Software (TOMS). 2011. T. 38. N 1. P. 1-25.
30.  Wang E. et al. Intel math kernel library // High-Performance Computing on the Intel§Xeon Phi™. Springer, Cham, 2014. P. 167-188.
31.  [Electron. Res.]: https://www.jscc.ru/
32.  Filippone S., Colajanni M. PSBLAS: A library for parallel linear algebra computation on sparse matrices // ACM Transactions on Mathematical Software (TOMS). 2000. T. 26. N 4. P. 527-550.
 

Bibliographic reference: Belyaev N.A. Automated construction of highly-efficient parallel programs for sparse linear algebra in LuNA system //journal “Problems of informatics”. 2022, № 3. P.46-60. DOI:10.24412/2073-0667-2022-3- 46-60. EDN: MTTVTE

A. Vlasenko, M. Michurov*, D. Mustafin*

Institute of Computational Mathematics and Mathematical Geophysics of SB RAS, 630090, Novosibirsk, Russia
*Novosibirsk State University, 630090, Novosibirsk, Russia

AUTOMATING DEBUGGING AND LOAD BALANCING IN FRAGMENTED PROGRAMS

DOI: 10.24412/2073-0667-2022-3-61-76

EDN: NBFMPU

The LuNA (Language for Numerical Algorithms) fragmented programming system is a high-level tool for creating parallel applications. Programs created using the LuNA can be run on computing systems with shared or distributed memory. The users create their program using a language resembling the standard imperative programming languages (C/C++, Fortran, Pascal, etc.), but does not specify any constructions regarding parallelism. Each operator of the LuNA language causes the generation of a new calculation fragment (CF) at runtime, which accepts objects called data fragments (DF) as its input and output. The totality of CFs makes up a fragmented program at the execution stage. Thus, the algorithm of a fragmented program is represented as a bipartite oriented graph with vertices of types CF and DF. The paper explains the important properties of fragmented programs: the non- deterministic order of operators execution in procedures, the uniqueness of assigning DF values and the absence of arrays in the programmer’s usual understanding.

The most typical logical errors for fragmented programs are described, which include an attempt to use uninitialized data, repeated initialization of the same data and a mismatch of data types during initialization and during use. In the case of running a fragmented program on a distributed memory computing system, the processes share the work of executing fragments of calculations. During this work, a situation of computational load imbalance may occur. The paper substantiates the importance of solving this problem.

Since LuNA is a high-level parallel programming tool, it is very difficult for the user to solve debugging and load balancing problems. In this regard, the authors of paper develop an automated debugging module based on the ,,post-mortem“ analysis method and an automatic centralized load balancing module for the system.

The automated debugging module collects trace files in JSON format during the execution of a fragmented program on each process. These files record information about the processed CFs, as well as their input and output DFs. After the normal or emergency shutdown of the program, the user can call a special software tool (luna_trace) that analyzes the collected traces. The result of its work is the output of detailed information about the detected errors, including a verbal description of the problem, a program statement indicating the string and file name of the source code, a stack of procedure calls and the names of the DFs with which the error is associated. In addition, information specific to a particular error is displayed, for example, for uninitialized DFs - the places of their possible initialization.

Another important part of this module functionality is the automatic detection of program hangs. The implementation of hang detection is based on a modification of the distributed Dijkstra-Scholten

algorithm. A hang-up situation occurs when one or more errors from frequently occurring classes are made in the LuNA program. In this regard, in the environment of a supercomputer center, where the user loses the ability to interact with the program after queuing the task, this functionality becomes particularly important.

The paper explains the fundamental difference between dynamic and static load balancing approaches and outlines the applicability of both approaches for different cases. The importance of developing a dynamic load balancing module in the LuNA system is explained. There are 2 methods of organizing dynamic balancing: based on centralized and distributed algorithms. The module being created implements the first method. The centralized load balancing module launches a service load balancer process along with the „worker processes“ that execute CFs. The role of this service process is to collect information from worker processes about executed and ready-to-execute CFs in order to redistribute them and minimize the imbalance. By collecting this information, the load balancer monitors the relative value of the imbalance between the most and the least loaded processes. When this imbalance reaches the threshold value (this threshold is setting by the parameter), the load balancer generates a „balancing plan“ deciding which CFs should be transferred from one process to another. The balancing plan is based on the fragment’s „weights“. The execution time of the fragment is taken as the weight. At the same time, if a fragment is transferred from one process to another, then its weight increases by the time of transferring.

The paper shows the results of modules testing on the computing cluster of Novosibirsk State University (NSU). Tests were performed on the problem of block matrix multiplication. The presented results demonstrate the effectiveness of the centralized load balancing module and acceptable overhead costs of the automated debugging module.

Further development plans regarding the functionality of the modules are given at the end.

Key words: fragmented programming, LuNA system, automated debugging, dynamic load balancing.

References

1. Vlasenko, A., Gudov, A. The Use of Erratic Behavior Templates in Debugging Parallel Programs by the Automated Validity Verification Method // Journal of Computer and Systems Sciences International. 2017. V. 56. N 4. P. 708-720.
2. Voevodin, V. V., Voevodin, VI. V. Parallelnie vichisleniya // Spb: BHV-Peterburg, 2002.
3.  Akhmed-Zaki, D., Lebedev, D., Malyshkin, V., Perepelkin, V. Automated Construction of High Performance Distibuted Programs in LuNA System // Malyshkin, V. (ed.) 15th International Conference, PaCT 2019, Almaty, Kazakhstan. August 19-23, 2019. P. 3-9.
4. Malyshkin, V. E. Tehnologiya fragmentirovannogo programmirovaniya // Vestnik YUrGU. Seriya: Vichislitelnaya matematika i informatika. 2012. N 46 305. S. 45-55.
5. Mustafin, D. E. Modul centralizovannoy dinamicheskoy balancirovki nagruzki LuNA-programm // Innovaciyi. Nauka. Obrazovanie. 2021. N 40. S. 365-373.
6. Protze, J., Hilbrich, T., Schulz, M., de Supinski, B. R. MPI Runtime Error Detection with MUST: A Scalable and Crash-Safe Approach // 43rd Intern. Conf, on Parallel Processing Workshops. Minneapolis, MN, USA. 2014. P. 206-215.
7. Michurov, M. A. Sredstvo analiza prichin zavisaniy fragmentirovannih programm v sisteme LuNA // Innovaciyi. Nauka. Obrazovanie. 2021. N 40. S. 354-364.
8. Fokkink, W. Distributed Algorithms: An Intuitive Approach // MIT Press. 2013. P. 38.
9. Irtegov, D. V. Vvedenie v operacionnie sistemi // Izd. 2. — Sankt-Peterburg: BHV-Peterburg. 2008.
10.  Cybenko, G., Dynamic Load Balancing for Distributed Memory Multiprocessors // J. Parallel and Distributed Comp. 1989.
11. П. Zaki, М. J., Li, W., Parthasarathy, S. Customized Dynamic Load Balancing for a Network of Workstations // J. Parallel and Distributed Computing. 1997. V. 43. N 2. P. 156-162.
12. Ob IVC NGU // Informacionno-vichislitelniy centr Novosibirskogo gosudarstvennogo universiteta. [Electron. Res.]: http://nusc.nsu.ru/wiki/doku.php/doc/nusc/about (data obrasheniya: 13.02.2022).
13. El-Zoghdy, S. F. A Load Balancing Policy for Heterogeneous Computational Grids // International Journal of Advanced Computer Science and Applications. 2011. V. 2. N 5. P. 93-100.

 

Bibliographic reference: Vlasenko A. Yu, Michurov M.A., Mustafin D. E. Automating debugging and load balancing in fragmented programs //journal “Problems of informatics”. 2022, № 3. P.61-76. DOI:10.24412/2073-0667-2022-3- 61-76. EDN: NBFMPU

A. Gerb, G. Omarova*

Novosibirsk State University, 630090, Novosibirsk, Russia
*Institute of Computational Mathematics and Mathematical Geophysics SB RAS, 630090, Novosibirsk, Russia

APPLICATION OF GRAPH THEORY IN ALGEBRAIC MULTIGRID METHODS FOR SOLVING SPARSE SLAES

DOI: 10.24412/2073-0667-2022-3-77-89

EDN: NJDXUZ  

In this paper, we discuss geometric and algebraic multigrid methods, graph coarsening algorithms, and metrics used to construct vertex aggregations. A coarsening method based on A. Napov and Y. Notcy’s criteria is implemented. Gustavson’s algorithms for efficient multiplication and transposition of matrices in CSR format are used for computation time optimization, which allowed to process graphs with more than one million vertices. The purpose of the presented work is to develop a data structure and computational environment components for high-performance solution of a wide class of SLAEs.

Key words: graph coarsening, grid graph, metric, sparse matrices, data structures.

References

1.  Kron G. Tensor Analysis of Networks // Wiley, New York. 1939.
2.  Chen J., Saad Y., Zhang Z.. Graph coarsening: from scientific computing to machine learning// ScMA Journal. 2022.
3.  Fedorenko R. P. Rclaksatcionnyi metod resheniia raznostnykh clliptichcskikh uravnenii / / ZH. vychisl. matem. i matem. fiz. 1961.
4.  Fedorenko R. P. О skorosti shodimosti odnogo itcratcionnogo protcessa / / ZH. vychisl. matem. i matem. fiz. 1964.
5.  Hackbusch W. Multigrid Methods and Applications // Springer-Verlag, Berlin, Germany, 1985.
6.  Pennanen, Anssi. A graph-based multigrid with applications// University of Jyvascyla. 2010.
7.  Ruge J. W. and Stabcn K. Algebraic Multigrid (AMG)// In S.F. McCornick, editor, Multigrid Methods, Frontiers in Applied Mathematics, SIAM, Philadelphia, Pennsylvania. 1987.
8.  Napov A. and Notay Y. An efficient multigrid method for Laplacian systems// Kent State University. 2016.
9.  Napov A. and Notay Y. An efficient multigrid method for Laplacian systems II: robust aggregation// Society for Industrial and Applied Mathematics. 2016.
10. Nagclc S., Falgout R. D., and Wittum G. Filtering algebraic multigrid and adaptive strategies// Computing and Visualization in Science. 2008.
11.  Notay Y. An aggregation-based algebraic multigrid method// Electron. Trans. Numcr. Anal. 2010.
12.  Napov A. and Notay Y. An algebraic multigrid method with guaranteed convergence rate// SIAM J. Sci. Comput. 2012'
13.  Beck R. Graph-based algebraic multigrid for Lagrange-type finite elements on simplicial meshes // Preprint SC 99-22, Konrad-Zuse-Zentrum fur Informa-tionstechnik, Berlin, 1999.
14.  Braess D. Towards algebraic multigrid for elliptic problems of second order // Computing. 1995.
15.  Elman H. C., Silvester D. J., and Wathen A. J. Finite Elements and Fast Iterative Solvers: with Applications in Incompressible Fluid Dynamics // Oxford University Press, 2005.
16.  Livne О. E. and Brandt A. Lean algebraic multigrid (LAMG): fast graph laplacian linear solver// SIAM J. Sci. Comput. 2012.
17. Dorfler, F., Bullo, F. Kron reduction of graphs with applications to electrical networks // IEEE Trans. Circuits Syst. I Reg. Pap. 60. 2013.
18. Shuman, D.I., Faraji, M.J., Vandergheynst, P. A multiscale pyramid transform for graph signals// IEEE Trans. Signal Process. 2016.
19. Aspvall, B., Gilbert, J.R. Graph coloring using eigenvalue decomposition // SIAM J. Algebr. Discrete Methods. 1984.
20. Spielman, D.A., Srivastava, N. Graph sparsification by effective resistances // SIAM J. Comput. 2011.
21. Писанецки С. Технология разреженных матриц // Мир. 1988.
22. Ruge J. W. and Staben K. Algebraic multigrid, in Multigrid Methods, Frontiers Appl // Math. 3, S. F. McCormick, ed., SIAM, Philadelphia. 1987.
23. Ron D., Safro L, and A. Brandt A. Relaxation-based coarsening and multiscale graph organization, Multiscale Model// Simul. 2011.

 

Bibliographic reference: Gerb A.R., Omarova G. A. Fpplication of graph theory in algebraic multigrid methods for solving sparse SLAES //journal “Problems of informatics”. 2022, № 3. P.77-89. DOI:10.24412/2073-0667-2022-3- 77-89. EDN: NJDXUZ