Все выпуски

В работе рассматривается задача распознавания графов коллективом агентов. Два агента-исследователя одновременно передвигаются по графу, считывают и изменяют метки элементов графа, передают необходимую информацию агенту-экспериментатору, который строит представление исследуемого графа. Построен алгоритм распознавания линейной (от числа вершин графа) временной сложности, квадратичной емкостной сложности и коммуникационной сложности равной O(n²·log(n)), где n — число вершин графа. Для распознавания два, передвигающиеся по графу, агента используют по две различные краски (всего три краски). Алгоритм основан на методе обхода графа в глубину.

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

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

Предложено обобщение блочного клеточного автомата Марголуса на гексагональную сетку. Проведена статистическая обработка результатов вероятностных клеточно-автоматных вычислений для ряда модификаций схемы, решающей тестовую задачу диффузии вещества. Показано, что выбор блоков в виде гексагонов на 25% эффективнее, чем в виде Y-блоков. Показано, что алгоритмы имеют полиномиальную сложность, причем степень полинома для параллельных вычислителей лежит в пределах 0.6÷0.8, а для последовательных — в пределах 1.5÷1.7. Исследовалось влияние внедренных в поле клеточного автомата дефектных ячеек на скорость сходимости.

Малая практическая ценность многих численных методов решения несимметричных систем линейных уравнений с плохо обусловленными матрицами объясняется тем, что эти методы в реальных условиях ведут себя совсем иначе, чем в случае точных вычислений. Исторически вопросам устойчивости не отводилось достаточного внимания, как в численной алгебре «средних размеров», а делался акцент на решении задач максимального порядка при данных возможностях вычислительной машины, в том числе за счет некоторой потери точности результатов. Поэтому главными объектами исследования были: наиболее целесообразное хранение информации, заключенной в разреженной матрице; поддержание наибольшей степени ее разреженности на всех этапах вычислительного процесса. Таким образом, разработка эффективных численных методов решения неустойчивых систем относится к актуальным проблемам вычислительной математики.

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

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

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

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

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

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

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

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

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

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

$$ \text{Argmin}_{x\in X}{\langle p,\,x \rangle} $$

для заданного вектора $p \in \mathbb{R}^n$. Существует целый ряд методов условного градиента, имеющих линейную скорость сходимости в сильно выпуклом случае. Однако во всех этих методах в оценку скорости сходимости входит размерность задачи, которая в современных приложениях может быть очень большой. В данной работе доказывается, что в сильно выпуклом случае скорость сходимости методов условного градиента в лучшем случае зависит от размерности задачи $n$ как $\widetilde{\Omega}\left(\!\sqrt{n}\right)$. Таким образом, методы условного градиента могут оказаться неэффективными для решения сильно выпуклых оптимизационных задач больших размерностей.

Отдельно рассматривается приложение методов условного градиента к задачам минимизации квадратичной формы. Уже была доказана эффективность метода Франк – Вульфа для решения задачи квадратичной оптимизации в выпуклом случае на симплексе (PageRank). Данная работа показывает, что использование методов условного градиента для минимизации квадратичной формы в сильно выпуклом случае малоэффективно из-за наличия размерности в оценке скорости сходимости этих методов. Поэтому рассматривается метод рестартов условного градиента (Shrinking Conditional Gradient). Его отличие от методов условного градиента заключается в том, что в нем используется модифицированный линейный минимизационный оракул, который для заданного вектора $p \in \mathbb{R}^n$ вычисляет решение задачи $$ \text{Argmin}\{\langle p, \,x \rangle\colon x\in X, \;\|x-x_0^{}\| \leqslant R \}. $$ В оценку скорости сходимости такого алгоритма размерность уже не входит. С помощью рестартов метода условного градиента получена сложность (число арифметических операций) минимизации квадратичной формы на $\infty$-шаре. Полученная оценка работы метода сравнима со сложностью градиентного метода.