Все выпуски

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

Two algorithms of evaluation of the continuous wavelet transform with the Morlet wavelet are presented. The first one is the solution of PDE with transformed signal, which plays a role of the initial value. The second allows to explore the influence of central frequency variation via the diffusion smoothing of the data modulated by the harmonic functions. These approaches are illustrated by the analysis of the chaotic oscillations of the coupled Roessler systems.

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

This paper presents definition and solution problem of correct conditions on the boundary, separating subdomains for hyperbolic linear equation systems. The solution algorithm is demonstrated by means of an example system of elastodynamic equations for two spatial variables. Stated approach can be easily expanded on systems of first-order linear hyperbolic equations with random number of spatial variables.

Рассматривается модель стека длинных джозефсоновских переходов (ДДП), состоящего из чередующихся сверхпроводящих слоев и слоев диэлектрика, с учетом индуктивной и емкостной связи между слоями. Модель описывается системой нелинейных дифференциальных уравнений в частных производных относительно разности фаз и напряжения между соседними сверхпроводящими слоями в стеке ДДП, с соответствующими начальными и граничными условиями. Численное решение этой системы уравнений основано на использовании стандартных трехточечных конечно-разностных формул для дискретной аппроксимации по пространственной координате и применении четырехшагового метода Рунге–Кутты для решения полученной задачи Коши. Разработанный параллельный алгоритм реализован на основе технологии MPI (Message Passing Interface). В работе дана математическая постановка задачи в рамках рассматриваемой модели, описаны вычислительная схема и методика расчета вольт-амперных характеристик системы ДДП, представлены два варианта параллельной реализации. Продемонстрировано влияние индуктивной и емкостной связи между ДДП на структуру вольт-амперной характеристики в рамках рассматриваемой модели. Представлены результаты методических расчетов с различными параметрами длины и количества джозефсоновских переходов в стеке ДДП в зависимости от количества задействованных параллельных вычислительных узлов. Расчеты выполнены на многопроцессорных кластерах HybriLIT и ЦИВК Многофункционального информационно-вычислительного комплекса Лаборатории информационных технологий Объединенного института ядерных исследований (Дубна). На основе полученных численных результатов обсуждается эффективность рассмотренных вариантов распределения вычислений для численного моделирования системы ДДП в параллельном режиме. Показано, что один из предложенных подходов приводит к ускорению вычислений до 9 раз по сравнению с расчетами в однопроцессорном режиме.

We consider a model of stacked long Josephson junctions (LJJ), which consists of alternating superconducting and dielectric layers. The model takes into account the inductive and capacitive coupling between the neighbor junctions. The model is described by a system of nonlinear partial differential equations with respect to the phase differences and the voltage of LJJ, with appropriate initial and boundary conditions. The numerical solution of this system of equations is based on the use of standard three-point finite-difference formulae for discrete approximations in the space coordinate, and the applying the four-step Runge-Kutta method for solving the Cauchy problem obtained. Designed parallel algorithm is implemented by means of the MPI technology (Message Passing Interface). In the paper, the mathematical formulation of the problem is given, numerical scheme and a method of calculation of the current-voltage characteristics of the LJJ system are described. Two variants of parallel implementation are presented. The influence of inductive and capacitive coupling between junctions on the structure of the current-voltage characteristics is demonstrated. The results of methodical calculations with various parameters of length and number of Josephson junctions in the LJJ stack depending on the number of parallel computing nodes, are presented. The calculations have been performed on multiprocessor clusters HybriLIT and CICC of Multi-Functional Information and Computing Complex (Laboratory of Information Technologies, Joint Institute for Nuclear Research, Dubna). The numerical results are discussed from the viewpoint of the effectiveness of presented approaches of the LJJ system numerical simulation in parallel. It has been shown that one of parallel algorithms provides the 9 times speedup of calculations.

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

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

На втором этапе необходимые и достаточные условия оптимальности в форме Куна–Таккера определяют расчет направления спуска — решение двойственной квадратичной задачи сводится к решению системы линейных уравнений с симметричной положительно определенной матрицей коэффициентов для расчета множителей Лагранжа и к подстановке решения в формулу для расчета направления спуска.

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

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

We consider the approaches to the construction of methods for solving four-dimensional programming problems for calculating directions for multiple minimizations of smooth functions on a set of a given set of linear equalities. The approach consists of two stages.

At the first stage, the problem of quadratic programming is transformed by a numerically stable direct multiplicative algorithm into an equivalent problem of designing the origin of coordinates on a linear manifold, which defines a new mathematical formulation of the dual quadratic problem. For this, a numerically stable direct multiplicative method for solving systems of linear equations is proposed, taking into account the sparsity of matrices presented in packaged form. The advantage of this approach is to calculate the modified Cholesky factors to construct a substantially positive definite matrix of the system of equations and its solution in the framework of one procedure. And also in the possibility of minimizing the filling of the main rows of multipliers without losing the accuracy of the results, and no changes are made in the position of the next processed row of the matrix, which allows the use of static data storage formats.

At the second stage, the necessary and sufficient optimality conditions in the form of Kuhn–Tucker determine the calculation of the direction of descent — the solution of the dual quadratic problem is reduced to solving a system of linear equations with symmetric positive definite matrix for calculating of Lagrange's coefficients multipliers and to substituting the solution into the formula for calculating the direction of descent.

It is proved that the proposed approach to the calculation of the direction of descent by numerically stable direct multiplicative methods at one iteration requires a cubic law less computation than one iteration compared to the well-known dual method of Gill and Murray. Besides, the proposed method allows the organization of the computational process from any starting point that the user chooses as the initial approximation of the solution.

Variants of the problem of designing the origin of coordinates on a linear manifold, a convex polyhedron and a vertex of a convex polyhedron are presented. Also the relationship and implementation of methods for solving these problems are described.

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

We develop the software tool for integration of dynamics models, which are inhomogeneous over mathematical properties and/or over requirements to the time step. The family of algorithms for the parallel computation of heterogeneous models with different time steps is offered. Analytical estimates and direct measurements of the error of these algorithms are made with reference to weakly coupled ODE sets. The advantage of the algorithms in the time cost as compared to accurate methods is shown.

В работе рассматриваются свойства рандомизированной системы итеративных функций (РСИФ), полученной в результате обобщения известного алгоритма «игра в хаос». Для моделирования РСИФ была использована свободная система статистического анализа и визуализации данных R. Показано, что для полигональных протофрактальных множеств Z = {z_j}, j = 1, 2, . . . , k зависимость размерности подобия от параметров РСИФ d_S(μ|k) носит немонотонный характер с экстремальным значением max d_S(μ|k)=− ln k/ln(1/(1+μ)).

In this paper we consider the properties of the random iterated function systems (RIFS) obtained using a generalization of the Chaos game algorithm. Used for the RIFS simulation R is a free software environment for statistical computing and graphics. The similarity dimension by the polygonal protofractals Z = {z_j}, j = 1, 2, . . . , k nonmonotonically depends on the RIFS parameters d_S(μ|k) with an extreme value max d_S(μ|k)=−ln k/ln(1/(1+μ)).

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

The method of conversion of surface representation to the voxel data is developed. Voxel data based algorithm of hexahedral mesh generation is proposed.

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

The approach to increase efficiency of Gill and Murray's algorithm of Newtonian methods of unconstrained optimization with step adjustment creation is offered, rests on Cholesky’s factorization. It is proved that the strategy of choice of the descent direction also determines the solution of the problem of scaling of steps at descent, and approximation by non-quadratic functions, and integration with a method of a confidential vicinity.

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

Problem of exploration finite undirected graphs by a collective of agents is considered in this work. Two agents-researchers simultaneously move on graph, they read and change marks of graph elements, transfer the information to the agent-experimenter (it builds explored graph representation). It was constructed an algorithm linear (from amount of the graph’s nodes) time complexity, quadratic space complexity and communication complexity, that is equal to O(n²·log(n)). Two agents (which move on graph) need two different colors (in total three colors) for graph exploration. An algorithm is based on depth-first traversal method.