2022 №1(54)

СОДЕРЖАНИЕ

1. Васильев Е.П., Болотов Д.И., Болотов М.И., Смирнов Л. А. Нейросетевой подход к решению задачи самовоздействия волновых полей в нелинейных средах   
2. Исупов К. С., Князьков В. С., Коржавина, А. С. Реализация и оценка сходимости ите-рационных CG и PCG решателей многократной точности для графических процессоров
3. Пирова, А. Ю. Гибридный MPI — ОрспМР алгоритм переупорядочения симметричных разреженных матриц и его применение к решению СЛАУ
4. Холькин С.Д., Филимонов А. В. Нахождение хроматического числа графа с помощью методов глубокого обучения
5. Старостин Н. В., Штанюк А. А., Годовицын М. М., Живчикова Ю. А. Параллельная реализация алгоритма логических операций над множествами ортогональных многоуголь-ников       
6. Каледина, Е. А., Каледин О. Е., Кулагина Т. И. Применение методов машинного обучения для предсказания сердечно-сосудистых заболеваний па малых наборах данных          
7. Родионов Д. М., Карчков Д.А., Москаленко В. А., Никольский А. В., Осипов Г. В., Золотых Н. Ю. Диагностика синусового ритма и мерцательной аритмии средствами искусственного интеллекта

Васильев Е.П.,Болотов Д.И., Болотов М.И., Смирнов Л.А.

Нижегородский государственный университет им. Н.И. Лобачевского, 603950, Нижний Новгород, Россия

НЕЙРОСЕТЕВОЙ ПОДХОД К РЕШЕНИЮ ЗАДАЧИ  САМОВОЗДЕЙСТВИЯ ВОЛНОВЫХ ПОЛЕЙ В НЕЛИНЕЙНЫХ СРЕДАХ

УДК: 517.957

DOI:10.24412/2073-0667-2022-1-5-16

В работе рассматривается задача о распространении оптических импульсов в средах с нелинейностью Керра. В качестве математической модели, описывающей процессы распространения оптического импульса, выбрано обобщенное параболическое уравнение, которое в безразмерных переменных имеет вид одномерного модифицированного Нелинейного Уравнения Шредингера. Были проведены эксперименты по обучению полносвязной нейронной сети с различными функциями оптимизации. Проведенные эксперименты показали перспективность использования квази-ньютоновской функции оптимизации L-BGFS над функциями первого порядка в данной задаче.

Ключевые слова: нелинейное уравнение Шредингера, нейронные сети, глубокое обучение, функции оптимизации

статья

Библиографическая ссылка: Васильев Е.П., Болотов Д.И., Болотов М.И., Смирнов Л. А. Нейросетевой подход к решению задачи самовоздействия волновых полей в нелинейных средах/ "Проблемы информатики", 2022, № 1, с.5-16. DOI: 10.24412/2073-0667-2022-1-5-16              

Исупов К.С., Князькова* В.С., Коржавина А.С.

РЕАЛИЗАЦИЯ И ОЦЕНКА СХОДИМОСТИ ИТЕРАЦИОННЫХ CG И PCG РЕШАТЕЛЕЙ МНОГОКРАТНОЙ ТОЧНОСТИ ДЛЯ ГРАФИЧЕСКИХ ПРОЦЕССОРОВ

УДК: 004.222+004.272.25

DOI: 10.24412/2073-0667-2022-1-17-27

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

Ключевые слова: разреженная линейная алгебра, метод сопряженных градиентов, арифметика многократной точности, система остаточных классов, CUDA.

статья

Библиографическая ссылка: Исупов К. С., Князьков В. С., Коржавина, А. С. Реализация и оценка сходимости итерационных CG и PCG решателей многократной точности для графических процессоров/"Проблемы информатики", 2022, № 1, с.17-27. DOI: 10.24412/2073-0667-2022-1-17-27

А. Ю. Пирова

Национальный исследовательский Нижегородский государственный университет им. Н. И. Лобачевского, 603950, Нижний Новгород, Россия

ГИБРИДНЫЙ MPI + OPENMP АЛГОРИТМ ПЕРЕУПОРЯДОЧЕНИЯ  СИММЕТРИЧНЫХ РАЗРЕЖЕННЫХ МАТРИЦ И ЕГО ПРИМЕНЕНИЕ К РЕШЕНИЮ СЛАУ

УДК 519.688, 004.428

DOI: 10.24412/2073-0667-2022-1-28-41

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

Ключевые слова: метод вложенных сечений, переупорядочение разреженных матриц, параллельный алгоритм, решение разреженных СЛАУ.

статья

Библиографическая ссылка: Пирова, А. Ю. Гибридный MPI — ОрспМР алгоритм переупорядочения симметричных разреженных матриц и его применение к решению СЛАУ/"Проблемы информатики", 2022, № 1, с.28-41. DOI: 10.24412/2073-0667-2022-1-28-41

С. Д. Холькин, А. В. Филимонов

Нижегородский государственный университет им. Н.И. Лобачевского, 603950, Нижний Новгород, Россия

НАХОЖДЕНИЕ ХРОМАТИЧЕСКОГО ЧИСЛА ГРАФА С ПОМОЩЬЮ МЕТОДОВ ГЛУБОКОГО ОБУЧЕНИЯ

УДК 004.855.5

DOI: 10.24412/2073-0667-2022-1-42-54

Алгоритмы глубокого обучения сильно развились в последнее десятилетие и стали стандартом во многих сферах. При этом количество архитектур глубокого обучения растет и существуют модели, работающие со структурой графа Graph Neural Network или GNN, которые показали свою эффективность в различных доменах. Также глубокое обучение применяют и для решения задач комбинаторной оптимизации. Поскольку многие задачи комбинаторной оптимизации изначально формулируются в терминах теории графов или же могут быть конвертированы в подобное представление, то архитектура GNN может стать эффективным методом для их приблизительного решения. В этой работе рассматривается задача о нахождении хроматического числа графа и ее приблизительное решение с помощью GNN. Вершины и цвета, в которые предположительно можно раскрасить граф, задаются случайными эмбеддингами, далее GNN, c учетом структуры графа, преобразовывает все эмбеддинги и производит на их основе бинарную классификацию, может граф быть раскрашен в данное количество цветов или нет. Данные для обучения сети являются сгенерированными и представляют собой сложные случаи раскраски. Также для тестирования обобщенности приведены замеры на данных, сильно отличающихся от тренировочных. Натренированная на синтетических данных GNN сравнивается по точности и времени исполнения с эвристиками: tabucol и жадный алгоритм.

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

статья

Библиографическая ссылка: Холькин С.Д., Филимонов А. В. Нахождение хроматического числа графа с помощью методов глубокого обучения/"Проблемы информатики", 2022, № 1, с.42-54. DOI: 10.24412/2073-0667-2022-1-42-54

Н.В. Старостин, А.А. Штанюк, М.М. Годовицын, Ю.А. Живчикова

Нижегородский государственный университет им. Н.И. Лобачевского, 603950, Нижний Новгород, Россия

ПАРАЛЛЕЛЬНАЯ РЕАЛИЗАЦИЯ АЛГОРИТМА ЛОГИЧЕСКИХ ОПЕРАЦИЙ НАД МНОЖЕСТВАМИ ОРТОГОНАЛЬНЫХ МНОГОУГОЛЬНИКОВ

УДК: 519.175.1, 621.3.049.771.14

DOI: 10.24412/2073-0667-2022-1-55-65

В рамках разработки отечественных САПР для верификации норм конструкторско-технологических ограничений (КТО), необходима разработка библиотеки выполнения логических операций над ортогональными многоугольниками, составляющими топологию интегральной схемы. Функции библиотеки выполняют операции над слоями. Под слоем понимается множество ортогональных прямоугольников (полигонов). К этим операциям предъявляются жесткие требования по времени выполнения. Существует реализация, построенная на основе алгоритма заметающей прямой и позволяющая добиться времени работы алгоритма порядка O(N log N).

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

Представленные в работе реализации алгоритмов и процедур вошли в состав подключаемой библиотеки функций работы со слоями топологического описания, которая, в свою очередь, является частью разрабатываемой системы верификации норм КТО. Данная библиотека реализована на языке С++, с использованием стандарта С++17. Имплементация параллельных схем реализации логических операций выполнена с использованием библиотеки OpenMP.

Ключевые слова: САПР, проверка конструктивно-технологических ограничений, логические операции, полигоны, параллельная реализация алгоритма заметающей прямой, OpenMP

статья

Библиографическая ссылка: Старостин Н. В., Штанюк А. А., Годовицын М. М., Живчикова Ю. А. Параллельная реализация алгоритма логических операций над множествами ортогональных многоугольников/"Проблемы информатики", 2022, № 1, с.55-65. DOI: 10.24412/2073-0667-2022-1-55-65

Е. А. Каледина ¹, О. Е. Каледин ¹, Т. И. Кулягина ²

 ПРИМЕНЕНИЕ МЕТОДОВ МАШИННОГО ОБУЧЕНИЯ ДЛЯ ПРЕДСКАЗАНИЯ  СЕРДЕЧНО-СОСУДИСТЫХ ЗАБОЛЕВАНИЙ НА МАЛЫХ НАБОРАХ ДАННЫХ

УДК 004.89

DOI: 10.24412/2073-0667-2022-1-66-76

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

Ключевые слова: алгоритмы машинного обучения, анализ данных, предсказание сердечно-сосудистых заболеваний.

статья

Библиографическая ссылка: Каледина, Е. А., Каледин О. Е., Кулагина Т. И. Применение методов машинного обучения для предсказания сердечно-сосудистых заболеваний па малых наборах данных/"Проблемы информатики", 2022, № 1, с.66-76. DOI: 10.24412/2073-0667-2022-1-66-76

Д.М. Родионов*, Д.А. Карчков*, В.А. Москаленко* ,А.В. Никольский*^,**, Г.В. Осипов* , Н.Ю. Золотых*

ДИАГНОСТИКА СИНУСОВОГО РИТМА И МЕРЦАТЕЛЬНОЙ АРИТМИИ СРЕДСТВАМИ ИСКУССТВЕННОГО ИНТЕЛЕКТА

УДК: 004.891.3

DOI: 10.24412/2073-0667-2022-1-77-88

Электрокардиограмма (ЭКГ) – наиболее используемая запись биологического сигнала в клинической медицине. Сигнал ЭКГ представляет собой график электрической активности сердца, получаемый с поверхности тела, чаще всего неинвазивно, с использованием электродов. На заре электрокардиографии врачу приходилось рассматривать график, записанный на листе бумаге, распознавая возможные патологии глазами, что нередко приводило к ошибкам при постановке диагноза. Сегодня же существует множество систем поддержки принятия решений, базирующихся на сложных алгоритмах, помогающих врачу в поиске артефактов, которые устанавливают как вид патологии, так и локализацию ее маркеров в сигнале. Однако, существует большое количество диагнозов, детектирование которых разработанными алгоритмами неэффективно. Более того, такие алгоритмы редко, но совершают ошибку. Перспективным решением для устранения существующих недостатков в экспертных системах специалисты видят применение методов искусственного интеллекта, показавших свою эффективность во множестве прикладных задач. В рамках данной статьи рассматривается применение нейронных сетей для решения задач диагностики. В качестве базовой архитектуры нейронной сети была выбрана UNet, адаптированная под обработку одномерного ЭКГ сигнала. Среди большого спектра состояний сердечно-сосудистой системы человека основное внимание было сконцентрировано на детектировании в сигнале большой длительности участков, классифицируемых специалистами как комплексы с превалированием синусового ритма и фибрилляции предсердий (мерцательной аритмии). Стоит отметить, что рассматриваемая в рамках работы нейронная сеть, после необходимых доработок, будет интегрирована в существующий диагностический комплекс «Кардио-Маяк», разработанный на базе ННГУ им. Лобачевского.

Ключевые слова: анализ сигнала электрокардиограммы, искусственный интеллект в медицине, синусовый ритм, фибрилляция предсердий, мерцательная аритмия.

статья

Библиографическая ссылка: Родионов Д. М., Карчков Д.А., Москаленко В. А., Никольский А. В., Осипов Г. В., Золотых Н. Ю. Диагностика синусового ритма и мерцательной аритмии средствами искусственного интеллекта/"Проблемы информатики", 2022, № 1, с.77-88. DOI: 10.24412/2073-0667-2022-1-77-88