Все выпуски

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

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

В настоящей работе схемы расщепления 3-го и 4-го порядка были применены непосредственно к решению двумерной гиперболической системы уравнений в частных производных линейной теории упругости. Это позволило повысить итоговый порядок сходимости расчетного алгоритма. В работе эмпирически оценена сходимость по нормам $L_1$ и $L_\infty$ с использованиемана литических решений определяющей системы достаточной степени гладкости. Для получения объективных результатов рассмотрены случаи продольных и поперечных плоских волн, распространяющихся как вдоль диагонали расчетной ячейки, так и не вдоль нее. Проведенные численные эксперименты подтверждают повышение точности метода и демонстрируют теоретически ожидаемый порядок сходимости. При этом увеличивается в 3 и в 4 раза время моделирования (для схем 3-го и 4-го порядка соответственно), но не возрастает потребление оперативной памяти. Предложенное усовершенствование вычислительного алгоритма сохраняет простоту его параллельной реализации на основе пространственной декомпозиции расчетной сетки.

Предложен метод отображения промежуточных представлений C-, C++-программ в пространство векторов (эмбеддингов) для оценки производительности программ на этапе компиляции, без необходимости исполнения. Использование эмбеддингов для данной цели позволяет не проводить сравнение графов исследуемых программ непосредственно, что вычислительно упрощает задачу сравнения программ. Метод основан на серии трансформаций исходного промежуточного представления (IR), таких как: инструментирование — добавление фиктивных инструкций в оптимизационном проходе компилятора в зависимости от разности смещений в текущей инструкции обращения к памяти относительно предыдущей, преобразование IR в многомерный вектор с помощью технологии IR2Vec с понижением размерности по алгоритму t-SNE (стохастическое вложение соседей с t-распределением). В качестве метрики производительности предлагается доля кэш-промахов 1-го уровня (D1 cache misses). Приводится эвристический критерий отличия программ с большей долей кэш-промахов от программ с меньшей долей по их образам. Также описан разработанный в ходе работы проход компилятора, генерирующий и добавляющий фиктивные инструкции IR согласно используемой модели памяти. Приведено описание разработанного программного комплекса, реализующего предложенный способ оценивания на базе компиляторной инфраструктуры LLVM. Проведен ряд вычислительных экспериментов на синтетических тестах из наборов программ с идентичными потоками управления, но различным порядком обращений к одномерному массиву, показано, что коэффициент корреляции между метрикой производительности и расстоянием до эмбеддинга худшей программы в наборе отрицателен вне зависимости от инициализации t-SNE, что позволяет сделать заключение о достоверности эвристического критерия. Также в статье рассмотрен способ генерации тестов. По результатам экспериментов, вариативность значений метрики производительности на исследуемых множествах предложена как метрика для улучшения генератора тестов.

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

Тем не менее, эти технологии обычно требуют больших объемов размеченных данных и ручной инженерии признаков, что ограничивает их масштабируемость. Данное исследование предлагает новый метод самообучения (Self-Supervised Learning, SSL) с использованием архитектуры SimCLR для улучшения классификации видов деревьев на основе неразмеченных данных. Модель SSL автоматически обнаруживает сильные признаки, объединяя спектральные данные гиперспектральной съемки со структурными данными лидара, исключая необходимость ручного вмешательства.

Мы оцениваем производительность модели SSL по сравнению с традиционными классификаторами, такими как Random Forest (RF), Support Vector Machines (SVM), а также методами обучения с учителем, используя набор данных конкурса ECODSE, который включает как размеченные, так и неразмеченные образцы видов деревьев на биологической станции Ordway-Swisher во Флориде. Метод SSL показал значительно более высокую эффективность по сравнению с традиционными методами, продемонстрировав точность 97,5% по сравнению с 95,56% для Semi-SSL и 95,03% для CNN при обучении с учителем.

Эксперименты по выборке показали, что техника SSL остается эффективной при меньшем количестве размеченных данных, и модель достигает хорошей точности даже при наличии всего 20% размеченных образцов. Этот вывод демонстрирует практическое применение SSL в условиях недостаточного объема размеченных данных, таких как мониторинг лесов в больших масштабах.

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

Задача вероятностного тематического моделирования заключается в том, чтобы по заданной коллекции текстовых документов найти две матрицы: матрицу условных вероятностей тем в документах и матрицу условных вероятностей слов в темах. Каждый документ представляется в виде мультимножества слов, то есть предполагается, что для выявления тематики документа не важен порядок слов в нем, а важна только их частота. При таком предположении задача сводится к вычислению низкорангового неотрицательного матричного разложения, наилучшего по критерию максимума правдоподобия. Данная задача имеет в общем случае бесконечное множество решений, то есть является некорректно поставленной. Для регуляризации ее решения к логарифму правдоподобия добавляется взвешенная сумма оптимизационных критериев, с помощью которых формализуются дополнительные требования к модели. При моделировании больших текстовых коллекций хранение первой матрицы представляется нецелесообразным, поскольку ее размер пропорционален числу документов в коллекции. В то же время тематические векторные представления документов необходимы для решения многих задач текстовой аналитики — информационного поиска, кластеризации, классификации, суммаризации текстов. На практике тематический вектор вычисляется для каждого документа по необходимости, что может потребовать десятков итераций по всем словам документа. В данной работе предлагается способ быстрого вычисления тематического вектора для произвольного текста, требующий лишь одной итерации, то есть однократного прохода по всем словам документа. Для этого в модель вводится дополнительное ограничение в виде уравнения, позволяющего вычислять первую матрицу через вторую за линейное время. Хотя формально данное ограничение не является оптимизационным критерием, фактически оно выполняет роль регуляризатора и может применяться в сочетании с другими критериями в рамках теории аддитивной регуляризации тематических моделей ARTM. Эксперименты на трех свободно доступных текстовых коллекциях показали, что предложенный метод улучшает качество модели по пяти оценкам качества, характеризующим разреженность, различность, информативность и когерентность тем. Для проведения экспериментов использовались библиотеки с открытымк одомB igARTM и TopicNet.

В первой части работы получена оценка скорости сходимости ранее известного ускоренного метода первого порядка AGMsDR на классе задач минимизации, вообще говоря, невыпуклых функций с $M$-липшицевым градиентом и удовлетворяющих условию Поляка – Лоясиевича. При реализации метода не требуется знать параметр $\mu^{PL}>0$ из условия Поляка – Лоясиевича, при этом метод демонстрирует линейную скорость сходимости (сходимость со скоростью геометрической прогрессии со знаменателем $\left.\left(1 - \frac{\mu^{PL}}{M}\right)\right)$. Ранее для метода была доказана сходимость со скоростью $O\left(\frac1{k^2}\right)$ на классе выпуклых задач с $M$-липшицевым градиентом. А также сходимость со скоростью геометрической прогрессии, знаменатель которой $\left(1 - \sqrt{\frac{\mu^{SC}}{M}}\right)$, но только если алгоритму известно значение параметра сильной выпуклости $\mu^{SC}>0$. Новизна результата заключается в том, что удается отказаться от использования методом значения параметра $\mu^{SC}>0$ и при этом сохранить линейную скорость сходимости, но уже без корня в знаменателе прогрессии.

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

Таким образом, представлены адаптивные ускоренные методы с оценкой сходимости $O\left(\min\left\lbrace\frac{M}{k^2},\,\left(1-{\frac{\mu^{PL}}{M}}\right)^{(k-1)}\right\rbrace\right)$ на классе выпуклых функций с $M$-липшицевым градиентом, которые удовлетворяют условию Поляка – Лоясиевича. При этом для работы метода не требуются значения параметров $M$ и $\mu^{PL}$. Если же условие Поляка – Лоясиевича не выполняется, то можно утверждать, что скорость сходимости равна $O\left(\frac1{k^2}\right)$, но при этом методы не требуют никаких изменений.

Также рассматривается адаптивная каталист-оболочка неускоренного градиентного метода, которая позволяет доказать оценку скорости сходимости $O\left(\frac1{k^2}\right)$. Проведено экспериментальное сравнение неускоренного градиентного метода с адаптивным выбором шага, ускоренного с помощью адаптивной каталист-оболочки с методами AGMsDR, Alternating AGMsDR, APDAGD (Adaptive Primal-Dual Accelerated Gradient Descent) и алгоритмом Синхорна для задачи, двойственной к задаче оптимального транспорта.

Проведенные вычислительные эксперименты показали более быструю работу метода Alternating AGMsDR по сравнению как с неускоренным градиентным методом, ускоренным с помощью адаптивной каталист-оболочки, так и с методом AGMsDR, несмотря на асимптотически одинаковые гарантии скорости сходимости $O\left(\frac1{k^2}\right)$. Это может быть объяснено результатом о линейной скорости сходимости метода Alternating AGMsDR на классе задач, удовлетворяющих условию Поляка – Лоясиевича. Гипотеза была проверена на квадратичных задачах. Метод Alternating AGMsDR показал более быструю сходимость по сравнению с методом AGMsDR.

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

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

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

В настоящей работе исследуется механическая стабильность белка клеточной адгезии, кадгерина, методом молекулярной динамики с использованием явной модели растворителя. Было проведено моделирование разворачивания белка за концы с постоянной скоростью для апоформы белка и при наличии в ней ионов разных типов (Ca²⁺, Mg²⁺, Na⁺, K⁺). Было выполнено по 8 независимых вычислительных экспериментов для каждой формы белка и показано, что одновалентные ионы меньше стабилизируют структуру, чем двухвалентные при механическом разворачивании молекулы кадгерина за концы. Модельная система из двух аминокислот и иона металла между ними в опытах по растяжению демонстрирует свойства аналогичные поведению кадгерина: cистемы с ионами калия и натрия обладают меньшей механической стабильностью на внешнее силовое воздействие в сравнении с системами с кальцием и магнием.