ВЫЧИСЛИТЕЛЬНЫЕ МЕТОДЫ И ПРОГРАММИРОВАНИЕ

Статья посвящена исследованию нового метода решения сверхбольших задач линейного программирования. Указанный метод получил название “апекс-метод”. Апекс-метод работает по схеме предиктор-корректор. На фазе предиктор находится точка, лежащая на границе n-мерного многогранника, задающего допустимую область задачи линейного программирования. На фазе корректор организуется итерационный процесс, в результате которого строится последовательность точек, сходящаяся к точному решению задачи линейного программирования. В статье дается формальное описание апекс-метода и приводятся сведения о его параллельной реализации на языке C++ с использованием библиотеки MPI. Приводятся результаты масштабных вычислительных экспериментов на кластерной вычислительной системе по исследованию масштабируемости апекс-метода.

В работе предложен алгоритм редукции трехмерных цифровых изображений для ускорения вычисления персистентных диаграмм, характеризующих изменения в топологии порового пространства образцов горной породы. Воксели для удаления выбираются исходя из структуры своей окрестности, что позволяет редуцировать изображение за линейное время. Показано, что эффективность алгоритма существенно зависит от сложности устройства порового пространства и размеров шагов фильтрации.

В данной статье описан подход к созданию прототипа графового фреймворка VGL (Vector Graph Library), нацеленного на эффективную реализацию графовых алгоритмов для современной векторной архитектуры NEC SX–Aurora TSUBASA. Современные векторные системы позволяют значительно ускорять приложения, интенсивно использующие подсистему памяти, подклассом которых являются графовые алгоритмы. Однако подходы к эффективной реализации графовых алгоритмов для векторных систем на сегодняшний день исследованы крайне слабо: вследствие сильно нерегулярной структуры графов реального мира, эффективно задействовать векторные особенности целевых платформ затруднительно. В работе показано, что разработанные на основе предложенного фреймворка VGL реализации графовых алгоритмов не уступают в производительности оптимизированным “вручную” аналогам за счет инкапсуляции большого числа оптимизаций графовых алгоритмов, характерных для векторных систем. Вместе с этим предложенный фреймворк позволяет значительно упростить процесс разработки графовых алгоритмов для векторных систем, на порядок сокращая объем кода реализуемых алгоритмов и скрывая от пользователя особенности программирования систем данного класса.

Показано, что теорема Кенига о нулях аналитической функции, примененная к логарифмической производной целой функции конечного порядка, приводит к алгоритму отыскания нулей, для которого областями сходимости являются многоугольники Вороного искомых нулей. Так как диаграмма Вороного последовательности нулей составляет множество меры нуль, то алгоритм имеет глобальную сходимость. Дана оценка скорости сходимости. Для итераций высших порядков, которые строятся с помощью теоремы Кенига, рассмотрено влияние кратности корня на область сходимости и приводится оценка скорости сходимости.

Рассматривается приближенный метод решения задачи Коши для нелинейных обыкновенных дифференциальных уравнений первого порядка, основанный на применении смещенных рядов Чебышёва и квадратурной формулы Маркова. Приведены способы оценки погрешности приближенного решения, выраженного в виде частичной суммы ряда некоторого порядка. Погрешность оценивается с помощью второго приближенного решения, вычисленного специальным образом и представленного частичной суммой ряда более высокого порядка. На основе предложенных способов оценки погрешности построен алгоритм автоматического разбиения промежутка интегрирования на элементарные сегменты, делающие возможным вычисление приближенного решения с наперед заданной точностью. Работа метода проиллюстрирована примерами, в том числе примером из небесной механики.

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

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

Сформулирована игровая модель противоборства в виде модели “нападение и защита”, указаны способы вычисления ресурсов сторон, анализированы эффективность их стратегий и установлены условия существования оптимального решения рассматриваемых задач.

Предложена нестационарная 2D-модель транспорта донных отложений в прибрежной зоне мелководных водоемов, дополненная уравнениями Навье–Стокса, неразрывности и состояния водной среды. Дискретная модель транспорта наносов получена в результате аппроксимации соответствующей линеаризованной непрерывной модели. Поскольку задачи прогнозирования транспорта наносов требуют решения в реальном или ускоренном масштабах времени, на сетках, включающих 106–109 узлов, необходима разработка параллельных алгоритмов задач гидродинамики на системах с массовым параллелизмом. Представлены результаты работы созданного эффективного программного обеспечения для выполнения гидродинамических вычислительных экспериментов, позволяющие проводить численное моделирование деформации дна в прибрежной зоне водоема. Приведены результаты численных экспериментов.