В статье предлагается алгоритмическая реализация элементарной версии метода Рунге для семейства диофантовых уравнений 4-й степени с двумя неизвестными. К уравнениям рассматриваемого типа сводится любое диофантово уравнение 4-й степени, старшая однородная часть которого разлагается в произведение линейного и кубического многочленов. Компьютерную реализацию алгоритма решения (в его оптимизированном виде) предполагается осуществить в системе компьютерной алгебры PARI/GP.
Компьютерная алгебра все шире применяется в научных и прикладных вычислениях. В качестве примера приведем тензорные вычисления или в более широком смысле этого слова – упрощение выражений с индексами. В настоящей статье развивается метод цветных графов для упрощения абстрактных выражений с индексами на случай, когда индексы могут быть отнесены к нескольким различным типам. Примерами таких индексов могут быть верхние и нижние индексы в тензорных выражениях. Предложенный подход позволяет значительно уменьшить число перебираемых вариантов при поиске канонической формы выражения, что резко ускоряет процесс вычислений.
В исследовательских задачах, требующих применения численных методов решения систем обыкновенных дифференциальных уравнений, часто возникает необходимость выбора наиболее эффективного и оптимального для конкретной задачи численного метода. В частности, для решения задачи Коши, сформулированной для системы обыкновенных дифференциальных уравнений, применяются методы Рунге–Кутты (явные или неявные, с управлением шагом сетки или без и т.д.). При этом приходится перебирать множество реализаций численного метода, подбирать коэффициенты или другие параметры численной схемы. В данной статье предложено описание разработанной авторами библиотеки и скриптов автоматизации генерации функций программного кода на языке Julia для набора численных схем методов Рунге–Кутты. При этом для символьных манипуляций использовано программное средство подстановки по шаблону. Предлагаемый подход к автоматизации генерации программного кода позволяет вносить изменения не в каждую подлежащую сравнению функцию по отдельности, а использовать для редактирования единый шаблон, что с одной стороны дает универсальность в реализации численной схемы, а с другой позволяет свести к минимуму число ошибок в процессе внесения изменений в сравниваемые реализации численного метода. Рассмотрены методы Рунге–Кутты без управления шагом, вложенные методы с управлением шагом и методы Розенброка также с управлением шагом. Полученные автоматически с помощью разработанной библиотеки программные коды численных схем протестированы при численном решении нескольких известных задач.
В работе исследуется задача символьного представления общего решения системы обыкновенных дифференциальных уравнений с постоянными коэффициентами, заданными в символьном виде, при условии, что некоторые символьные константы могут обращаться в ноль. Кроме того, символьное представление собственных векторов матрицы коэффициентов системы не единственно. В работе на примере исследуемой системы показано, что стандартные процедуры компьютерной алгебры отыскивают конкретные символьные представления собственных векторов, игнорируя существование других символьных представлений собственных векторов. В свою очередь предлагаемые системой компьютерной алгебры собственные векторы могут быть непригодны для построения численных алгоритмов на их основе, что продемонстрировано в работе. Авторами предложен алгоритм отыскания различных символьных представлений собственных векторов символьно заданных матриц. В работе рассматривается конкретная система дифференциальных уравнений, полученная при исследовании решений уравнений Максвелла, однако предложенный алгоритм исследования применим к произвольной системе с нормальной матрицей коэффициентов.
В данной работе представлен алгоритм вычисления решения задачи Коши для двумерного разностного уравнения с постоянными коэффициентами в точке по коэффициентам разностного уравнения и начальным данным задачи Коши методами компьютерной алгебры. В одномерном случае решение задачи Коши для разностного уравнения не представляет сложности, однако уже в двумерном случае число неизвестных растет на каждом шаге очень быстро. Для автоматизации процесса вычисления решения задачи Коши для двумерного разностного уравнения с постоянными коэффициентами в заданной точке в среде MATLAB был разработан алгоритм, где входными данными являются: матрица коэффициентов, полученная исходя из структуры двумерного полиномиального разностного уравнения; координаты точки, регламентирующей структуру матрицы начальных данных; координаты точки, регламентирующей размерность матрицы начальных данных; матрица начальных данных. Результатом работы алгоритма является решение задачи Коши для двумерного разностного уравнения, представляющее собой значение функции в искомой точке.
Поиск типичных подпоследовательностей временного ряда является одной из актуальных задач интеллектуального анализа временных рядов. Данная задача предполагает нахождение набора подпоследовательностей временного ряда, которые адекватно отражают течение процесса или явления, задаваемого этим рядом. Поиск типичных подпоследовательностей дает возможность резюмировать и визуализировать большие временные ряды в широком спектре приложений: мониторинг технического состояния сложных машин и механизмов, интеллектуальное управление системами жизнеобеспечения, мониторинг показателей функциональной диагностики организма человека и др. Предложенная недавно концепция сниппета формализует типичную подпоследовательность временного ряда следующим образом. Сниппет представляет собой подпоследовательность, на которую похожи многие другие подпоследовательности данного ряда в смысле специализированной меры схожести, основанной на евклидовом расстоянии. Поиск типичных подпоследовательностей с помощью сниппетов показывает адекватные результаты для временных рядов из широкого спектра предметных областей, однако соответствующий алгоритм имеет высокую вычислительную сложность. В настоящей работе предложен новый параллельный алгоритм поиска сниппетов во временном ряде на графическом ускорителе. Распараллеливание выполнено с помощью технологии программирования CUDA. Разработаны структуры данных, позволяющие эффективно распараллелить вычисления на графическом процессоре. Представлены результаты вычислительных экспериментов, подтверждающих высокую производительность разработанного алгоритма.
The paper covers an intelligent support system that allows to describe and construct solutions to various scientific problems. In this study, in particular, we consider geophysical problems. This system is being developed at the Institute of Computational Mathematics and Mathematical Geophysics of the Russian Academy of Sciences (ICMMG SB RAS) and Institute of Informatics System of the Russian Academy of Sciences (IIS SB RAS). The system contains a knowledge base, the core of which is a set of several interconnected ontologies such as the ontology of supercomputer architectures, the ontology of algorithms and methods. Ontology can be viewed as a set of concepts and how those concepts are linked. As the result, the authors present an ontological description of two geophysical problems via the means of the intelligent support system: 1) the seismic wavefield simulation and 2) the reconstruction of a seismic image through pre-stack time or depth migration. For a better visual understanding of the system described and the results obtained, the paper also contains several schematic diagrams and images.
This paper is concerned with implementation of wave tomography algorithms on modern SIMD CPU and GPU computing platforms. The field of wave tomography, which is currently under development, requires powerful computing resources. Main applications of wave tomography are medical imaging, nondestructive testing, seismic studies. Practical applications depend on computing hardware. Tomographic image reconstruction via wave tomography technique involves solving coefficient inverse problems for the wave equation. Such problems can be solved using iterative gradient-based methods, which rely on repeated numerical simulation of wave propagation process. In this study, finite-difference time-domain (FDTD) method is employed for wave simulation. This paper discusses software implementation of the algorithms and compares the performance of various computing devices: multi-core Intel and ARM-based CPUs, NVidia graphics processors.
Схема КАБАРЕ, являющаяся представителем семейства балансно-характеристических методов, широко используется при решении многих задач для систем дифференциальных уравнений гиперболического типа в эйлеровых переменных. Возрастающая актуальность задач взаимодействия деформируемых тел с потоками жидкости и газа требует адаптации этого метода на лагранжевы и смешанные эйлерово-лагранжевы переменные. Ранее схема КАБАРЕ была построена для одномерных уравнений газовой динамики в массовых лагранжевых переменных, а также для трехмерных уравнений динамической упругости. В первом случае построенную схему не удалось обобщить на многомерные задачи, а во втором - использовался необратимый по времени алгоритм передвижения сетки. В данной работе представлено обобщение метода КАБАРЕ на двумерные уравнения газовой динамики и динамической упругости в смешанных эйлерово-лагранжевых и лагранжевых переменных. Построенный метод является явным, легко масштабируемым и обладает свойством временной обратимости. Метод тестируется на различных одномерных и двумерных задачах для обеих систем уравнений (соударение упругих тел, поперечные колебания упругой балки, движение свободной границы идеального газа).
Выделенные свойства циклов DFS-базиса блока карты простого графа позволили составить математическую модель вычисления циклов ячеек карты графа. По данной модели предложен практический алгоритм вычисления циклов ячеек карты графа. Алгоритм имеет квадратическую сложность относительно числа вершин в графе.