Статьи журнала - Вестник Южно-Уральского государственного университета. Серия: Вычислительная математика и информатика
Все статьи: 316
Гарантированное оценивание параметров дискретных моделей хаотических процессов
Статья научная
Рассматривается задача оценивания параметров дискретных моделей хаотических процессов по зашумленным измерениям. Исследуется применение гарантированного подхода, что предполагает множественное представление неопределенности о неизвестных переменных в модели (переменной состояния, параметре и ошибках измерений). Разрабатываемый алгоритм основан на интервальном анализе и может быть реализован в прямом и обратном времени. Результатом гарантированного оценивания являются множественные (интервальные) оценки, которые содержат истинные значения неизвестных переменных. Предложенный алгоритм может быть эффективно использован в сочетании с методами, разрабатываемыми в рамках оптимизационного и динамического подходов к решению задачи оценивания. Алгоритм гарантированного оценивания можно рассматривать как процедуру уточнения множества возможных значений переменных целевой функции при применении метода наименьших квадратов и его модификаций. Это позволяет уменьшить число локальных экстремумов целевой функции и сократить время вычислений при применении алгоритмов глобальной оптимизации. Найденные множественные оценки также могут быть использованы для проверки корректности оценок, полученных в результате применения модификаций фильтра Калмана для нелинейных моделей. Для анализа эффективности алгоритма исследуется зависимость результатов оценивания от числа измерений и уровня шума.
Бесплатно
Гибридные вычислительные кластеры для изучения структуры, функции и регуляции белков
Статья научная
Изучение структуры, функции и регуляции белков с использованием биоинформатики и молекулярного моделирования является комплексной задачей, требующей сочетания различных методов и способов их исполнения. На практике, речь идет о конвейере из последовательных этапов, исполняемых различными программами, предъявляющими свои требования к вычислительным ресурсам. Гибридные вычислительные кластеры - системы, обладающие существенной мощностью и разнообразием аппаратных возможностей - необходимы для того, чтобы оптимально исполнить каждую отдельную стадию единого комплексного решения. При этом GPU-ускорители открывают новые возможности для поиска эффективных решений ресурсоемких задач биоинформатики и молекулярного моделирования.
Бесплатно
Статья научная
В статье предлагается новый метод распознавания строений на спутниковых снимках. Представленный метод является гибридным, он основан на алгоритме исключения областей и методе жука. Алгоритм исключения областей представляет собой хорошо известный и эффективный способ сегментации изображения на регионы схожих пикселей по различным признакам: цвет, текстура, яркость, форма и т.д. Метод жука - классический метод контурного анализа, выполняющий последовательное вычерчивание границы между объектом и фоном. В рамках работы предлагаемого алгоритма сначала метод исключения областей выделяет потенциальные области, в которых могут находиться строения и устраняет нежелательные элементы на изображении (растительность, водные поверхности и дороги), которые могут быть ложно распознаны как строения. Далее модифицированный метод жука определяет местоположение и контуры строений. На финальном этапе среди обнаруженных объектов выявляются искусственно созданные объекты, у которых имеется объем. Для реализации проверки объектов на искусственное происхождение и объемность разработаны собственные методы. Представленный алгоритм распознавания показывает хорошую точность распознавания и не требует обучающей выборки. В статье описывается программная реализация предлагаемого метода. Демонстрируются результаты вычислительных экспериментов по оцениванию эффективности метода и сравнению с тремя известными алгоритмами распознавания.
Бесплатно
Двумерная модель фасеточного зрения
Статья научная
Одним из современных перспективных направлений исследований в области машинного зрения являются системы визуализации на основе искусственных фасеточных глаз, в основе которых лежат принципы организации зрения насекомых. Такие глаза имеют сложную структуру, основными элементами которой являются зрительные элементы, называемые омматидиями. В данной работе строится математическая модель бинокулярного фасеточного зрения в двумерном пространстве. Модель позволяет описывать задачи навигации робототехнического устройства и детектирования объектов на плоскости. В предложенной модели фасеточный глаз является правильным многоугольником с обзором 360°. Основными параметрами модели являются количество фасеток (омматидиев) в одном глазу, радиус описанной вокруг глаза окружности и расстояние между глазами. Модель предполагает, что области видимости омматидиев одного глаза не пересекаются. В качестве наблюдаемых объектов фигурируют окружности различных диаметров. Выводится формула вычисления номера омматидия, в область видимости которого попадает точка с заданными координатами. Доказывается утверждение о необходимом и достаточном условии попадания заданной окружности в область видимости омматидия с заданным номером. Предлагается алгоритм построения обучающей выборки для искусственной нейронной сети, работающей на основе модели двумерного фасеточного зрения.
Бесплатно
Статья научная
Приводятся описание и анализ параллельных алгоритмов решения начальнокраевых задач для уравнений аномальной диффузии, содержащих производные дробного порядка типа Римана-Лиувилля по пространственным и/или временной переменным. Параллельные алгоритмы построены на основе двухсеточного подхода. При этом грубая сетка используется для расчета эффектов пространственного и временного дальнодействия с использованием сплайн-аппроксимации, а мелкая сетка служит для конечно-разностной дискретизации решаемых уравнений. Рассматриваются алгоритмы с декомпозицией как по пространству, так и по времени. Для распараллеливания по времени используется подход, предложенный в известном алгоритме PARAREAL. Приводятся теоретические оценки параллельной эффективности предложенных алгоритмов. Показано, что алгоритмы имеют сверхлинейное ускорение по сравнению с классическим последовательным конечно-разностным алгоритмом и обеспечивают тот же порядок точности вычислений при условии согласованного выбора шагов точной и грубой сеток. Также приводятся некоторые результаты вычислительных экспериментов, подтверждающие эффективность предложенных алгоритмов.
Бесплатно
Статья научная
Статья посвящена вопросам декомпозиции реляционных операций путем использования распределенных колоночных индексов с доменно-интервальной фрагментацией. Такая декомпозиция позволяет организовать параллельное выполнение ресурсоемких реляционных операций без обменов данными между процессорными ядрами. Все фрагменты колоночного индекса хранятся в оперативной памяти в сжатом виде. При параллельном выполнении реляционной операции упакованные фрагменты индексов входных отношений загружаются на различные процессорные ядра, где происходят их распаковка, выполнение реляционной операции над фрагментами и упаковка частичного результата, представляющего собой наборы ключей. За-тем частичные результаты объединяются в результирующий набор ключей, с использованием которого СУБД собирает результирующее отношение. Указанный подход позволяет организовать эффективное параллельное выполнение запросов к сверхбольшим базам данных на современных кластерных вычислительных системах, оснащенных многоядерными ускорителями.
Бесплатно
Диагностика ландшафтов провинции Эль-Дивания (Ирак) по мультиспектральным снимкам landsat-8
Статья научная
Дистанционные методы мониторинга и прогноза урожайности сельскохозяйственных культур широко используются во всем мире. Однако такие методы не являются универсальными и требуют апробации в каждом ландшафтном регионе. В работе исследуется подходы к использованию мультиспектральных снимков спутника Landsat-8 для классификации ландшафтов провинции Эль-Дивания - одного из главных центров орошаемого земледелия Ирака. Исходными данными для классификации послужили сходные по радиометрическим характеристикам снимки, сделанные в период максимальной вегетации зерновых культур (март 2014, 2015 и 2016 года). Такой подбор снимков предполагал уверенное выделение агроландшафтов на основе вегетационного индекса NDVI (Normalized Difference Vegetation Index). Исследование отклика распределений NDVI на изменения площади зерновых культур и на сезонные осадки позволило обосновать пороговые значения индекса для ландшафтов провинции. В том числе выделены четыре типа ландшафтов: ландшафты со здоровой, умеренно разряженной растительностью (NDVI > 0,34); ландшафты с угнетенной или сильно разряженной растительностью (0,34 ≥ NDVI > 0,19 ); ландшафты без растительности (0,19 ≥ NDVI > -0,1 ) и водные ландшафты (NDVI ≥ -0,1). Сравнение типов автоматически классифицированных и визуально дешифрованных ландшафтов, формализованное в матрицу ошибок, показывает, что общая точность, F-мера и другие метрики качества классификации близки к 90 %.
Бесплатно
Диагностика неисправностей подшипников качения с использованием пиков спектра и нейронных сетей
Статья научная
Важнейшими составляющими деталей машин являются подшипники качения, контроль за состоянием которых необходим, так как возможные дефекты в их конструкции могут привести к неправильной работе или общему выходу машин из строя. Современные решения по диагностике неисправностей подшипников обычно используют сложные процессы извлечения признаков, например, построение их изображений спектра Гильберта и дальнейшую мощную нейронную сеть для их классификации. В этой статье мы предлагаем простой, но, тем не менее, эффективный алгоритм решения данной задачи. Для выделения признаков из сигнала мы делим спектр сигнала на равные подинтервалы и находим максимум амплитуды и соответствующее значение частоты в каждом из них. В статье, на основе метода t-SNE, показано, что выделенные таким образом признаки, несмотря на свой небольшой размер, хорошо представляют разного типа сигналы. На втором этапе выделенные признаки поступают на вход простой нейронной сети классификатора. Предложенный метод обладает простотой в вычислительном отношении, как на этапе выделения признаков, так и на этапе обучения нейронной сети. Несмотря на это, метод дает 100% точность для всех типов сигналов на коротких данных из набора данных IMS.
Бесплатно
Статья научная
В статье дано описание дискретных моделей нейронных сетей со связями типа small world с вероятностью перенаправления связей внутри сети p, изменяющейся от 0 до 1. При значении p = 0 получим модель регулярной нейронной сети. Регулярной нейронной сетью выступает кольцевая нейронная сеть, в которой каждый нейрон взаимодействует с несколькими соседями по кольцу. При значении p = 1 получим модель, нейроны которой случайным образом соединены с другими нейронами сети без образования изолированных нейронов. Рассматриваемые нейронные сети имеют широкое применение при моделировании различные нейронных структур в живых организмах, например, гипокамп мозга млекопитающих. В работе проведено исследование динамики изменения областей устойчивости рассматриваемых нейронных сетей в случае изменения вероятности перенаправления связей, коэффициента кластеризации и длины кратчайшего пути в среднем графа нейронной сети. В ходе численных экспериментов были построены области устойчивости исследуемых моделей нейронных сетей для различных параметров сети и сделан вывод об увеличении области устойчивости при одновременном уменьшении длины кратчайшего пути в среднем и коэффициента кластеризации графа сети.
Бесплатно
Дискретные динамические системы с помехой и их приложения к решению задачи управления запасами
Статья научная
Рассматриваются две модели дискретных динамических управляемых систем с помехой. В одной из них представлена дискретная задача управления, в которой вектограмма управления линейно зависит от заданных множеств. Во второй задаче предполагается, что вектограммы управления и помехи являются однотипными множествами. В обоих случаях цель выбора управления заключается в том, чтобы в момент окончания процесса управления фазовая точка содержалась в заданном множестве. При построении управления предполагается, что в каждый дискретный момент времени поступает информация о реализации помехи. Записан оператор программного поглощения, с помощью которого сформулированы условия на множество начальных положений, при которых гарантируется выполнение требуемого включения в заданный момент времени. В практической части работы показано применение полученных результатов на примере решения задачи управления запасами товара на складе. Пополнение товара происходит за счет его производства, а величина отгрузки товара определяется спросом. Предполагается, что о величине спроса на товар известно только множество его значений. Цель управления состоит в том, чтобы в заданный момент времени количество товара удовлетворяло определенным ограничениям. Получено множество начальных запасов товара, для которых возможно осуществить поставленную цель при любой реализации спроса.
Бесплатно
Задача агрегирования при выделении границ объектов на изображении
Статья научная
В данной статье детально рассматриваются градиентные методы выделения границ на цифровых изображениях для поиска объектов: Робертса, Превитта, Собеля и Щарра. Для их усовершенствования применяются агрегационные операторы. В результате выполнения работы были разработаны алгоритмы дифференцирования изображений, алгоритмы выбора агрегационных операторов для поиска границ объектов, алгоритмы статистической оценки продифференцированных изображений. Результаты проведенных экспериментов позволили установить достоинства и недостатки применения градиентных методов в обработке цифро-вых изображений.
Бесплатно
Имитационное моделирование подсети коллективных операций сети «Ангара»
Статья научная
В ОАО «НИЦЭВТ» разрабатывается высокоскоростная коммуникационная сеть «Ангара» с топологией «многомерный тор». Для исследования и оценки производительностиразрабатываемой сети при большом количестве используемых узлов создана параллельная потактовая имитационная модель сети. Сеть «Ангара» имеет аппаратную поддержку двух коллективных операций - broadcast и reduce. В статье описана реализация коллективных операций в имитационной модели, и представлены результаты оценки их производительности при помощи модели. Оценки производительности получены на базовых тестах broadcastи reduce, а также на прикладных задачах - умножение разреженной матрицы на вектор и численное решение нелинейного уравнения теплопроводности.
Бесплатно
Имитационное моделирование социально-экономических систем на примере древнего общества земледельцев
Статья научная
Проводимое научное исследование заключается в моделировании социальноэкономической системы с использованием положений теории физической экономики. Основной принцип данной теории состоит в оценке экономической деятельности человека с помощью физических параметров. Производительные силы должны выражаться в социальном времени (бюджет социального времени - величина доступного человечеству труда в год, измеренная в человеко-часах). Подзадачей исследования является проверка положений теории на симуляционных моделях. В ходе уже проведенного исследования был проверен принцип, гласящий, что по мере развития человеческого общества доля свободного (время, отличное от необходимого, расходуемого обществом для восполнения потраченных ресурсов) времени в общем фонде социального времени должна расти.
Бесплатно
Статья научная
Работа посвящена разработке архитектуры инструментальных средств для поддержки формальной верификации функционально-потоковых параллельных программ на языке Пифагор. Используемый метод формальной верификации - дедуктивный анализ на базе исчисления Хоара. Процесс доказательства корректности программы представляется в виде дерева, каждый узел которого - информационный граф программы в котором дуги размечены формулами на языке спецификации. Корнем дерева является исходная тройка Хоара: информационный граф с предусловием и постусловием. В работе рассматриваются основные преобразования, применяемые к информационному графу программы: разметка дуг, эквивалентное преобразование, расщепление, свертка программы. Посредством данных преобразований исходная тройка модифицируется и в конечном счете сводится к набору формул на языке спецификации, истинность которых будет свидетельствовать о корректности программы. Предложена архитектура системы поддержки формальной верификации функционально-потоковых параллельных программ, которая позволяет строить дерево доказательства. Представлена реализация этой системы, описана ее основная функциональность.
Бесплатно
Статья научная
В работе предлагается усовершенствованный метод распараллеливания алгоритма Полларда решения задачи дискретного логарифмирования в группе точек эллиптической кривой и в мультипликативной группе конечного поля для систем с общей памятью. Усовершенствование метода достигается за счет построения детерминированной функции разбиения на множества. Такая функция позволяет организовать два независимых сбалансированных вычислительных потока построения блока элементов группы фиксированной длины. Далее анализируются известные функции итерирования точек в алгоритме Полларда и строится обобщенная детерминированная функция разбиения на множества.
Бесплатно
Статья научная
В статье изложены результаты исследования многоуровневой схемы редукции размерности в задачах глобальной оптимизации. Предложенная схема позволяет свести решение многомерной задачи оптимизации к серии подзадач меньшей размерности, решение которых может быть выполнено параллельно. При этом для редукции размерности комбинируется использование кривых Пеано и схема вложенной (рекурсивной) оптимизации. Для решения редуцированных подзадач используется параллельный алгоритм глобального поиска, принадлежащий классу характеристических алгоритмов. Проведены вычислительные эксперименты на серии тестовых задач разной размерности. Результаты экспериментов показывают, что предложенная схема позволяет эффективно распараллелить процесс поиска и добиться значительного ускорения.
Бесплатно
Статья научная
В 2011 году для новых гетерогенных и гибридных суперкомпьютерных систем в Институте прикладной математики им. М.В. Келдыша РАН была предложена модель DVMH (DVM for Heterogeneous systems), разработаны языки программирования высокого уровня, представляющие собой стандартные языки Фортран и Си, расширенные директивами отображения программы на параллельную машину, оформленными в виде специальных комментариев (или прагм). В статье анализируется эффективность разработанных на языке Fortran DVMH параллельных программ для решения задач гидродинамики «Каверна» и «Контейнер». Приводятся результаты расчетов при использовании нескольких тысяч ядер и более 1200 GPU-ускорителей.
Бесплатно
Статья научная
С использованием трехмерной нелинейной математической модели изучаются динамические процессы, и особенности трансформации примеси в Азовском море, вызванные действием переменного ветра и атмосферного давления при наличии фоновых стационарных течений. На основании результатов численных расчетов сделаны выводы о влиянии скоростей стационарных течений на максимальные отклонения уровня и скорости нестационарных течений, генерируемых полями ветра и атмосферного давления, полученными по данным модели SKIRON. Выполнен анализ влияния изменения интенсивности стационарных течений на размеры областей осушения и затопления в прибрежных районах моря в зависимости от угла наклона (подъема) рельефа береговой зоны. Показано, что совместное действие постоянного ветра с полями прогностической модели SKIRON приводит к существенному увеличению площади распространения пассивной примеси и времени ее рассеивания по сравнению с воздействием только стационарных течений.
Бесплатно
Исследование газодинамического потока и конструкции в модельной экспериментальной установке
Краткое сообщение
В данной работе проводится анализ влияния распараллеливания задачи и параметров расчетной сетки на время выполнения задачи по расчету газодинамического потока и напряженно-деформированного состояния конструкции рабочей камеры экспериментальной установки. Разработаны физическая, математическая, твердотельная и сеточная модели отдельно для газодинамической задачи и задачи теории упругости. Обсуждаются некоторые полученные результаты вычислительных экспериментов.Обнаружено, что масштабируемость прочностного расчета ниже, чем при оценке газодинамического процесса. Предварительный анализ показал, что скорость расчета газодинамических процессов повышается при оптимизации процессов распараллеливания и построения сетки. Масштабируемость по оценке напряженно-деформированного состояния конструкции при этом не повышается. При решении связанных задач, применительно к динамическим системам «газ-конструкция» в системе инженерного анализа Ansys возможно, что продолжительность расчета окажется неприемлемой. Для решения такого рода задач, возможно, потребуется разработка новых алгоритмов.
Бесплатно
Статья научная
Работа посвящена исследованию масштабируемости алгоритма Чиммино для решения систем неравенств. Данный алгоритм является типичным представителем класса итерационных проекционных алгоритмов для решения систем линейных уравнений и неравенств. Для аналитического анализа масштабируемости используется модель параллельных вычислений BSF (Bulk Synchronous Farm). Дается представление алгоритма Чиммино в виде операций над списками с использованием функций высшего порядка Map и Reduce. Выводятся аналитические оценки верхней границы масштабируемости алгоритма для многопроцессорных вычислительных систем с распределенной памятью. Приводятся данные о реализация алгоритма Чиммино над списками на языке С++ с использованием программного шаблона BSF и библиотеки параллельного программирования MPI. Демонстрируются результаты масштабных вычислительных экспериментов, выполненных на кластерной вычислительной системе. На основе экспериментальных результатов дается анализ адекватности оценок, полученных аналитическим путем с помощью стоимостных метрик модели BSF.
Бесплатно
