Научно-изследователска дейност

Научно-изследователската дейност на секцията е фокусирана върху следните области:

• Нови ефективни паралелни алгоритми
• Монте Карло алгоритми (диференциални и интегрални уравнения, линейна алгебра, спектрални задачи, обработка на данни)
• Обработка на изображения
• Изчислителна геометрия и топологична теория на графите
• Метаевристични и стохастични методи
• Приложения на паралелните алгоритми и високопроизводителните пресмятания (трудоемки задачи, паралелни и/или векторни компютри, клъстери от работни станции)

Сътрудниците на секцията по Паралелни алгоритми са участвали в множество международни проекти, финансирани от Европейската комисия, програмата на НАТО "Наука за мир и сигурност" и Национален фонд "Научни изследвания" (за някои от тях виж Дейности - Национални и Международни Проекти).

Изследванията на учените в секцията са ориентирани към проектирането на нови алгоритми за задачи на линейната алгебра с плътни, разредени и структурирани матрици, в които се прилагат нови подходи. Основно това са паралелни методи Монте Карло за спектрални задачи с плътни и разредени матрици с голяма размерност. Разработените методи се прилагат при изучаване на устойчивостта на големи физични системи чрез т.нар. епсилон-спектри (портрети) на матрици.

Разработват се и ефективни и свръхсходящи алгоритми Монте Карло за числено пресмятане на многомерни интеграли, като се изследва и изчислителната сложност на алгоритмите.

Специален клас от методи Монте Карло за решаване на задачи за пренос на замърсители във въздуха се разработват и изследват. Споменатите процеси се описват с линейни и нелинейни интегрални уравнения на Фредхолм. Получени са нови резултати относно оценката за статистическата грешка, които са публикувани във водещи международни списания.

Проучва се и смесен метод на крайните елементи за елиптични гранични задачи от втори ред, описващи пренос на замърсители във въздуха. Получени са оптимални оценки на грешката в случаите на lumped mass approximation и локално сгъстяване.

Методите Монте Карло се смятат за най-надеждните методи за моделиране на електронен пренос в полупроводници. През последните години при моделирането на устройства се налагат толкова малки скали по отношение на пространството и времето, че протичащите процеси не биха могли да се разглеждат като полупроводников транспорт и затова е необходима квантова интерпретация.

Разработват се и нови паралелни алгоритми за разредени неструктурирани матрици, които се тестват върху едрозърнести паралелни архитектури. Още от основаването на секцията се работи активно в областта на високопроизводителните пресмятания. Нови такива (векторни и паралелни) алгоритми и софтуер за различни типове суперкомпютри (векторни и/или паралелни с обща или разпределена памет) се разработват и тестват. Основните приложения са в областта на екологията (пренос на замърсители във въздуха, source-receptor relations и други), класическа и квантова механика, полупроводници и др. Изследванията са свързани с конструирането на оптимални алгоритми по отношение на изчислителната сложност и комуникациите (отчетени чрез аритметичните операции, необходими за реализирането на даден алгоритъм), както и спрямо оптималното използване на кеш-паметта и отделните нива от йерархичната структура на паметта в компютрите от ново поколение.

Метаевристичните и стохастични методи са общи процедури от високо ниво, които управляват прости евристики и правила за намиране на добро решение при задачи с голяма изчислителска сложност. Между тях са: simulated annealing, tabu search, genetic algorithm, ant colony optimization. Това са едни от най-ефективните стратегии за практическо решаване на комбинаторни оптимизационни задачи. Разработват се алгоритми за задачи, идващи от реалния живот и индустрията, като икономика (управление на ресурси), телекомуникации (разпределение на пакети, управление на сензори и радари, GPS мрежи), биология (тримерна форма на протеин) и др. Изследванията са свързани с намиране на най-подходящия метод за даден тип задачи и конструиране на оптимален алгоритъм по отношение на изчислителната сложност и използването на паметта.

Изследователските усилия са насочени към прилагането на нови подходи в компютърната графика и проектирането на ефективни Монте Карло и квази Монте Карло методи за създаване на фотореалистични изображения. От гледна точка на математиката, синтезът на фотореалистични изображения е еквивалентен на намиране на решение на интегрално уравнение от тип на Фредхолм, наречено рендърингово уравнение. Задачата за намиране на приемливи Монте Карло и квази Монте Карло решения на многомерни рендърингови уравнения, такива чрез които създаваните изображения да изглеждат фотореалистични е много трудна и изчислително сложна. Решаваме тези предизивикателства като прилагаме нови подходи и техники при проектирането на ефективни суперсходящи Монте Карло и квази Монте Карло алгоритми, като същевременно ги изследваме и изучаваме. Нови резултати за изчислителната сложност на суперсходящи Монте Карло и квази Монте Карло алгоритми с равномерно разделяне на областта на интегриране са изведени и публикувани.

Секцията организира редица научни мероприятия - конференции, работни срещи и семинари. На тези срещи традиционно участват и представители от почти всички европейски страни, САЩ, Япония и Русия. Тези научни прояви предоставят възможности за установяване на активно сътрудничество и обмяна на идеи и опит.