Исследование структурных свойств алгоритма разложения Холецкого:от давно известных фактов до новых выводов

Аннотация

В рамках создания Открытой энциклопедии свойств алгоритмов проведено исследование параллельной структуры алгоритма разложения Холецкого для симметричных положительно определенных матриц. На основе анализа графа алгоритма приводится описание ресурса параллелизма данного алгоритма, а также исследованы характеристики локальности обращений к памяти для данного алгоритма. Полученные в результате численных экспериментов на суперкомпьютере «Ломоносов» данные исследований масштабируемости базовых реализаций разложения Холецкого позволяют дать ряд рекомендаций по соотношению размеров задач и ресурсов, необходимых для их решения. Результаты теоретических исследований дают возможность, как объяснить сравнительно низкую производительность точечного варианта этого метода, так и по-новому взглянуть на некоторые решения, принятые в вычислительном сообществе более полувека назад, и пересмотреть их с позиций новых реалий при современном состоянии вычислительной техники.