All issues

Традиционные методы решения задачи коммивояжера не являются эффективными для задач высокой размерности из-за их высокой вычислительной сложности. Одним из эффективных способов решения этой проблемы является декомпозиционный подход, который включает в себя три основных этапа: кластеризацию вершин, решение подзадач внутри каждого кластера и последующее объединение полученных решений в итоговое. В данной статье основное внимание уделяется третьему этапу — объединению циклов решений подзадач, поскольку этому этапу не всегда уделяется должное внимание, что приводит к менее точному итоговому решению. В статье предлагается новый модифицированный алгоритм Сигала для объединения циклов. Для оценки его эффективности проводится сравнение с двумя алгоритмами объединения циклов: метод соединения средних точек ребер и алгоритм на основе близости центроидов кластеров. Исследуется зависимость качества решения подзадач на алгоритмы объединения циклов. Модифицированный алгоритм Сигала выполняет попарное объединение кластеров, минимизируя количество пересечений и общее расстояние. Метод центроидов ориентирован на соединение кластеров на основе близости центроидов, а алгоритм с использованием средних точек оценивает расстояние между средними точками ребер. Также были рассмотрены два типа кластеризации: алгоритмы k-means и affinity propagation. Для проверки эффективности предложенного алгоритма были проведены численные эксперименты на наборе данных TSPLIB с различным количеством городов. В исследовании анализируются ошибки, вызванные порядком объединения кластеров, качеством решения подзадач и количеством кластеров. Эксперименты показали, что модифицированный алгоритм Сигала демонстрирует наименьшую медиану итогового расстояния и наиболее устойчивые результаты по сравнению с другими методами. Результаты указывают на большую устойчивость качества конечного решения, полученным модифицированным алгоритмом Сигала, от последовательности объединения кластеров. Повышение качества решения подзадачи обычно приводит к линейному улучшению конечного решения, но используемый алгоритм объединения редко влияет на степень этого улучшения.

Traditional methods for solving the traveling salesman problem are not effective for high-dimensional problems due to their high computational complexity. One of the most effective ways to solve this problem is the decomposition approach, which includes three main stages: clustering vertices, solving subproblems within each cluster and then merging the obtained solutions into a final solution. This article focuses on the third stage — merging cycles of solving subproblems — since this stage is not always given sufficient attention, which leads to less accurate final solutions of the problem. The paper proposes a new modified Sigal algorithm for merging cycles. To evaluate its effectiveness, it is compared with two algorithms for merging cycles — the method of connecting midpoints of edges and an algorithm based on closeness of cluster centroids. The dependence of quality of solving subproblems on algorithms used for merging cycles is investigated. Sigal’s modified algorithm performs pairwise clustering and minimizes total distance. The centroid method focuses on connecting clusters based on closeness of centroids, and an algorithm using mid-points estimates the distance between mid-points of edges. Two types of clustering — k-means and affinity propagation — were also considered. Numerical experiments were performed using the TSPLIB dataset with different numbers of cities and topologies to test effectiveness of proposed algorithm. The study analyzes errors caused by the order in which clusters were merged, the quality of solving subtasks and number of clusters. Experiments show that the modified Sigal algorithm has the smallest median final distance and the most stable results compared to other methods. Results indicate that the quality of the final solution obtained using the modified Sigal algorithm is more stable depending on the sequence of merging clusters. Improving the quality of solving subproblems usually results in linear improvement of the final solution, but the pooling algorithm rarely affects the degree of this improvement.

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

This paper presents a non-iterative method for solving an inverse problem for a parabolictype equation with an unknown time-dependent coefficient at the first spatial derivative. The overdetermination condition is specified as a definite integral of the unknown function with a weighting factor over the spatial domain or its subdomain. The study is motivated by the need to identify dynamic parameters in applied problems, particularly in modeling transport processes in biological fluids, where the flow velocity may vary over time. In contrast to conventional iterative methods that require substantial computational effort and careful selection of regularization parameters, an original approach based on solution decomposition is proposed. At each time layer, the solution is represented as a linear combination of solutions to two auxiliary systems with the same matrix and different right-hand sides, followed by the determination of the unknown coefficient from a discrete analogue of the overdetermination condition. This approach eliminates the need for an iterative procedure. In the presence of inexact overdetermination data, the highest reconstruction accuracy is achieved using a quasi-solution. Numerical experiments on test problems demonstrate high accuracy in reconstructing the unknown functions under small perturbations of the overdetermination condition. The results indicate strong potential for applications in medical diagnostics and other fields requiring rapid processing of experimental data.

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

The increased potential for jamming satellite navigation signals, which provide the highest positioning accuracy for moving objects, makes the development of alternative navigation systems comparable in accuracy but autonomous extremely important. One of the most effective such approaches is the integration of inertial and optical navigation systems (NS), as they are more resistant to artificial interference. Among NS data, one can distinguish systems that use a velocity field calculation method when processing optical flow, allowing the determination of the linear and angular velocity vectors of an object in the absence of terrain maps and reference points. However, a serious drawback of this method is the high computational cost of determining the velocity field (optical flow parameters), which is difficult to implement onboard an object. In this regard, the article considers an approach that allows for constructing a tightly coupled autonomous inertial-optical navigation scheme for objects moving along known (programmed) trajectories. This scheme utilizes a navigation algorithm that is easily implemented in onboard computers due to the discovered possibility of estimating the navigation vector without preliminary calculation of optical flow parameters, as well as by utilizing functional dependencies of navigation variables arising on analytical (orthodromic) trajectories. To illustrate the generality of the solution, cases of a rigidly mounted video camera on the object and its two-degree stabilization are studied. The navigation algorithm, providing a stochastic estimate of the full vector of linear and angular motion parameters based on measurements of an integrated tightly coupled inertial-optical NS, is built on the basis of an extended Kalman filter for correlated noise of the object and the observer. A numerical experiment illustrating the effectiveness of the proposed approach is conducted.

Разработан и протестирован новый метод формирования тестовых сигналов для корреляционной идентификации нелинейных динамических систем методом Ли–Шетцена. Для коррекции моментных функций тестовых сигналов применен численный алгоритм оптимизации Гаусса–Ньютона. В экспериментах получены тестовые воздействия длиной до 40 000 точек, позволяющие определять ядра Винера 2-го порядка с линейным разрешением до 32 точек, ядра Винера 3-го порядка с линейным разрешением до 12 точек, ядра Винера 4-го порядка с линейным разрешением до 8 точек.

Тhe new test-signals forming method for correlation identification of a nonlinear system based on Lee–Shetzen cross-correlation approach is developed and tested. Numerical Gauss–Newton algorithm is applied to correct autocorrelation functions of test signals. The achieved test-signals have length less than 40 000 points and allow to measure the 2nd order Wiener kernels with a linear resolution up to 32 points, the 3rd order Wiener kernels with a linear resolution up to 12 points and the 4th order Wiener kernels with a linear resolution up to 8 points.

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

In the context of problems of hydrogen and thermonuclear power engineering intensive research of the hydrogen isotopes properties is being conducted. Mathematical models help to specify physical-chemical ideas about the interaction of hydrogen isotopes with structural materials, to discover the limiting factors. Classical diffusion models are often insufficient. The paper is devoted to the models and numerical solution of the boundary-value problems of hydrogen thermodesorption and permeability taking into account nonlinear sorption-desorption dynamics on the surface and reversible capture of hydrogen atoms in the bulk. Algorithms based on difference approximations. The results of computer simulation of the hydrogen flux from a structural material sample are presented.

Целью данной работы является обобщение макроскопических гидродинамических моделей второго порядка, описывающих автомобильное движение, с помощью алгоритма построения адекватного реальным измерениям уравнения состояния — зависимости давления от плотности транспортного потока, получаемого эмпирическим образом для каждого отдельного участка транспортной сети с использованием данных транспортных детекторов. Доказано, что именно вид уравнения состояния, замыкающего систему модельных уравнений и полученного из экспериментально наблюдаемого вида фундаментальной диаграммы — зависимости интенсивности транспортного потока от его плотности, полностью определяет все свойства любой феноменологической модели. Проверка работоспособности предложенного подхода проводилась с использованием численных расчетов, путем проведения вычисленных экспериментов на типичных данных, предоставляемых системой PeMS (http://pems.dot.ca.gov/), таких как моделирование движения трафика на заданном участке транспортной сети автострады I-580 в Калифорнии.

The goal of this work is to generalize second order mathematical models for automotive flow using algorithm for building state equation — the dependency of pressure on traffic density — which is adequate with regard to real world data. The form of state equation, which closes the system of model equations, is obtained from experimental form of fundamental diagram — the dependency of traffic flow intensity on its density, and completely defines all properties of any phenomenological model. The proposed approach was verified using numerical experiments on typical traffic data, obtained from PeMS system (http://pems.dot.ca.gov/), using segment of I-507 highway in California, USA as model system.

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

Newton and quasi-Newton methods of absolute optimization based on Cholesky factorization with adaptive step and finite difference approximation of the first and the second derivatives. In order to raise effectiveness of the quasi-Newton methods a modified version of Cholesky decomposition of quasi-Newton matrix is suggested. It solves the problem of step scaling while descending, allows approximation by non-quadratic functions, and integration with confidential neighborhood method. An approach to raise Newton methods effectiveness with finite difference approximation of the first and second derivatives is offered. The results of numerical research of algorithm effectiveness are shown.

В статье рассматривается модель антропоморфного механизма типа экзоскелета со звеньями переменной длины. Комплексно рассмотрены четыре модели звеньев переменной длины: модель звена экзоскелета переменной длины с упругим элементом и абсолютно твердым весомым стержнем, модель телескопического звена; модель звена с массами в шарнирах-суставах и между ними, модель звена с произвольным количеством масс. Составлены дифференциальные уравнения движения в форме уравнений Лагранжа второго рода. На основе проведенного анализа дифференциальных уравнений движения для многозвенных стержневых механических систем типа экзосклета выявлена их структура, позволившая представить их в векторно-матричном виде. Впервые установлены общие закономерности построения матриц и получены обобщения выражений для элементов матриц в двухмерном случае. Приводятся новые рекуррентный и матричный методы составления дифференциальных уравнений движения. Предлагается единый подход к построению дифференциальных уравнений движения экзоскелета на основе разработанных рекуррентного и матричного методов записи дифференциальных уравнений движения экзоскелета. Проведено сопоставление времени составления дифференциальных уравнений движения предложенными методами, в сравнении с уравнениями Лагранжа второго рода, в системе компьютерной математики Mathematica. Осуществлено аналитическое исследование модели экзоскелета. Установлено, что для механизмов с $n$ подвижными звеньями решение задачи Коши для систем дифференциальных уравнений движения при любых начальных условиях существует, единственно и неограниченно продолжаемо. Управление экзоскелетом осуществляется с помощью крутящих моментов, расположенных в шарнирах-суставах в местах соединения звеньев и моделирующих управляющие воздействия. Выполнено численное исследование модели экзоскелета, проведено сопоставление результатов расчетов для экзоскелетов с различными моделями звеньев. Для численного исследования использованы эмпирические данные о человеке и его движениях. Установлено, что при выборе конструкции экзоскелета модель с сосредоточенными массами является предпочтительной, нежели модель с абсолютно твердым весомым стержнем, так как экзоскелет, обеспечивающий комфортабельные передвижения человека в нем, должен повторять свойства опорно-двигательного аппарата.

The article discusses the model of the anthropomorphic type of mechanism of the exoskeleton with links of variable length. Four models of parts of variable length are considered comprehensively: the model link of the exoskeleton of variable length with a resilient member and a rigid strong core; the model of the telescopic link; the model link with the masses in the hinge-joint between them; the link model with an arbitrary number of masses. The differential equations of motion in the form of Lagrange equations of the second kind are made. On the basis of analysis of differential equations of motion for multi-link rod of a mechanical system type, exoskeleton revealed their structure, which allowed us to represent them in vector-matrix form. The General pattern of building matrices are established for the first time and the generalization of the expressions for elements of matrices in two-dimensional case are obtained. New recursive and matrix methods of composing of differential equations of motion are given. A unified approach to constructing differential equations of motion of the exoskeleton based on the developed recursive and matrix methods write differential equations of motion of the proposed exoskeleton. Comparison of the time of writing the differential equations of motion proposed methods, in comparison with the Lagrange equations of the second kind, in the system of computer mathematics Mathematica conducted. An analytical study of the model of the exoskeleton carried out. It was found that for mechanisms with n movable links of the Cauchy problem for systems of differential equations of motion for any initial conditions there is no single and unlimited continue. Control of the exoskeleton is accomplished using the torques which are located in the hinge-joints in the joints of the links and simulating control actions. Numerical investigation of a model of the exoskeleton is made, a comparison of results of calculations for exoskeletons with various models of units is held. A numerical study of the empirical evidence about the man and his movements is used. It is established that the choice structure of the exoskeleton model with lumped masses is more preferable to a model with perfectly rigid strong core. As an exoskeleton, providing comfortable movement of people, and you should repeat the properties of the musculoskeletal system.

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

The system of linear hyperbolic kinetic equations with the relaxation term of Bhatnagar–Gross–Krook type for modelling of linear diffusion processes by the lattice Boltzmann method is considered. The coefficients of the equations depend on the discrete velocities from the pattern in velocity space. The system may be considered as an alternative mathematical model of the linear diffusion process. The cases of widely-used patterns on speed variables are considered. The case of parametric coefficients takes into account. By application of the method of Chapman–Enskog asymptotic expansion it is obtained, that the system may be reduced to the linear diffusion equation. The expression of the diffusion coefficient is obtained. As a result of the analysis of this expression, the existence of numerical diffusion in solutions obtained by application of lattice Boltzmann equations is demonstrated. Stability analysis is based on the investigation of wave modes defined by the solutions of hyperbolic system. In the cases of some one-dimensional patterns stability analysis may be realized analytically. In other cases the algorithm of numerical stability investigation is proposed. As a result of the numerical investigation stability of the solutions is shown for a wide range of input parameters. The sufficiency of the positivity of the relaxation parameter for the stability of solutions is demonstrated. The dispersion of the solutions, which is not realized for a linear diffusion equation, is demonstrated analytically and numerically for a wide range of the parameters. But the dispersive wave modes can be damped as an asymptotically stable solutions and the behavior of the solution is similar to the solution of linear diffusion equation. Numerical schemes, obtained from the proposed systems by various discretization techniques may be considered as a tool for computer modelling of diffusion processes, or as a solver for stationary problems and in applications of the splitting lattice Boltzmann method. Obtained results may be used for the comparison of the theoretical properties of the difference schemes of the lattice Boltzmann method for modelling of linear diffusion.

Рассматривается применение консервативного численного метода потоков для изучения вихревых структур в массивных, быстровращающихся компактных астрофизических объектах, находящихся в условиях самогравитации. Моделирование осуществляется для объектов с различной массой и скоростью вращения. Визуализируются картины вихревой структуры объектов. В расчетах используется газодинамическая модель, в которой газ принимается совершенным и невязким. Численная методика основана на конечно-разностной аппроксимации законов сохранения аддитивных характеристик среды для конечного объема. При этом используются upwind-аппроксимации плотностей распределения массы, компонент импульса и полной энергии. Для моделирования объектов, обладающих быстрым вращением, при эволюционном расчете осуществляется контроль сохранения компонент момента импульса, законы сохранения для которых не входят в систему основных уравнений. Эволюционный расчет осуществляется на основе параллельных алгоритмов, реализованных на вычислительном комплексе кластерной архитектуры. Алгоритмы основаны на стандартизованной системе передачи сообщений Message Passing Interface (MPI). При этом используются как блокирующие, так и неблокирующие процедуры обмена с контролем завершения операций. Осуществляется распараллеливание по пространству по двум или трем направле- ниям в зависимости от размера области интегрирования и параметров вычислительной сетки. Одновременно с распараллеливанием по пространству для каждой подобласти осуществляется распараллеливание по физическим факторам: расчет конвективного переноса и гравитационных сил реализуется параллельно на разных процессорах, что позволяет повысить эффективность алгоритмов. Показывается реальная возможность прямого вычисления гравитационных сил посредством суммирования взаимодействия между всеми конечными объемами в области интегрирования. Для методов конечного объема такой подход кажется более последовательным, чем решение уравнения Пуассона для гравитационного потенциала. Численные расчеты осуществлялись на вычислительном комплексе кластерной архитектуры с пиковой производительностью 523 TFlops. В расчетах использовалось до тысячи процессоров.

The application of a conservative numerical method of fluxes is examined for studying the vortex structures in the massive, fast-turned compact astrophysical objects, which are in self-gravity conditions. The simulation is accomplished for the objects with different mass and rotational speed. The pictures of the vortex structure of objects are visualized. In the calculations the gas-dynamic model is used, in which gas is accepted perfected and nonviscous. Numerical procedure is based on the finite-difference approximation of the conservation laws of the additive characteristics of medium for the finite volume. The “upwind” approximations of the densities of distribution of mass, components of momentum and total energy are applied. For the simulation of the objects, which possess fast-spin motion, the control of conservation for the component of moment of momentun is carried out during calculation. Evolutionary calculation is carried out on the basis of the parallel algorithms, realized on the computer complex of cluster architecture. Algorithms are based on the standardized system of message transfer Message Passing Interface (MPI). The blocking procedures of exchange and non-blocking procedures of exchange with control of the completion of operation are used. The parallelization on the space in two or three directions is carried out depending on the size of integration area and parameters of computational grid. For each subarea the parallelization based on the physical factors is carried out also: the calculations of gas dynamics part and gravitational forces are realized on the different processors, that allows to raise the efficiency of algorithms. The real possibility of the direct calculation of gravitational forces by means of the summation of interaction between all finite volumes in the integration area is shown. For the finite volume methods this approach seems to more consecutive than the solution of Poisson’s equation for the gravitational potential. Numerical calculations were carried out on the computer complex of cluster architecture with the peak productivity 523 TFlops. In the calculations up to thousand processors was used.