Одабрани алгоритми теорије графова и линеарне алгебре прилагођени великим количинама података

Abstract

Предмет ове дисертације је прилагођавање комплексних алгоритама, који се користе у индустријским наменама, захтевима које диктирају потребе велике количине података (енгл. Big Data). Потребно је одређене алгоритме прилагодити дистрибуираном извршавању и великим улазним подацима на такав начин, да се пораст величине проблема може компензовати скалирањем, са акцентом на хоризонтално скалирање, тј. повећање броја дистрибуираних станица, рачунарске моћи система. Конкретно, у фокусу су следећи проблеми: 1. Проблем тока снага у електроенергетском систему 2. Проблем анализе испада у електроенергетском систему 3. Проблем спектралне спарсификације графова у општем смислу Резултати извршавања указују на прихватљива времена извршавања које постиже програмска подршка отвореног кода, која се лако скалира и подстиче даља истраживања превазилажењем тренутних ограничења. У ширем смислу, иако су проблеми наизглед везани искључиво за електроенергетске системе, у њиховој сржи се налазе општи математички проблеми који су примењиви у далеко ширем опсегу области.

Predmet ove disertacije je prilagođavanje kompleksnih algoritama, koji se koriste u industrijskim namenama, zahtevima koje diktiraju potrebe velike količine podataka (engl. Big Data). Potrebno je određene algoritme prilagoditi distribuiranom izvršavanju i velikim ulaznim podacima na takav način, da se porast veličine problema može kompenzovati skaliranjem, sa akcentom na horizontalno skaliranje, tj. povećanje broja distribuiranih stanica, računarske moći sistema. Konkretno, u fokusu su sledeći problemi: 1. Problem toka snaga u elektroenergetskom sistemu 2. Problem analize ispada u elektroenergetskom sistemu 3. Problem spektralne sparsifikacije grafova u opštem smislu Rezultati izvršavanja ukazuju na prihvatljiva vremena izvršavanja koje postiže programska podrška otvorenog koda, koja se lako skalira i podstiče dalja istraživanja prevazilaženjem trenutnih ograničenja. U širem smislu, iako su problemi naizgled vezani isključivo za elektroenergetske sisteme, u njihovoj srži se nalaze opšti matematički problemi koji su primenjivi u daleko širem opsegu oblasti.

The overreaching topic of this dissertation is the adaptation of complex algorithms, which are extensively used in industrial applications, to the requirements dictated by the Big Data needs. Chosen algorithms are adapted to a distributed environment and made suitable for large amounts of data in such a way, that the increasing problem size can be compensated with scaling of the computing environment. Here is the emphasis particularly on horizontal scaling, i.e. the increase of the number of distributed computing units. The following problems are considered: 1. The power flow problem in a smart grid system 2. The contingency analysis problem in a smart grid system 3. The spectral sparsification problem of graphs in the broader sense The results indicate a reasonable execution time achieved by open-source software that is easily scalable and serve to direct further research in overcoming the current limitations. In a broader sense, although these problems seem very specific in their domain of application, the underlying core mechanics contain common mathematical challenges, applicable to a broad spectrum of problems.