All issues

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

В данной работе этот алгоритм лежит в основе решения следующих задач.

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

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

Задача 3. Построение непрерывного аналога задачи минимизации вещественного квадратичного многочлена от булевых переменных и новой формы задания необходимых и достаточных условий оптимальности для разработки методов их решения за полиномиальное время. В результате исходная задача сводится к задаче поиска минимального расстояния между началом координат и угловой точкой выпуклого многогранника (полиэдра), который является возмущением $n$-мерного куба и описывается системой двойных линейных неравенств с верхней треугольной матрицей коэффициентов с единицами на главной диагонали. Исследованию подлежат только две грани, одна из которых или обе содержат вершины, ближайшие к началу координат. Для их вычисления достаточно решить $4n – 4$ систем линейных уравнений и выбрать среди них все ближайшие равноудаленные вершины за полиномиальное время. Задача минимизации квадратичного полинома является $NP$-трудной, поскольку к ней сводится $NP$-трудная задача о вершинном покрытии для произвольного графа. Отсюда следует вывод, что $P = NP$, в основе построения которого лежит выход за пределы целочисленных методов оптимизации.

We consider a numerically stable direct multiplicative algorithm of solving linear equations systems, which takes into account the sparseness of matrices presented in a packed form. The advantage of the algorithm is the ability to minimize the filling of the main rows of multipliers without losing the accuracy of the results. Moreover, changes in the position of the next processed row of the matrix are not made, what allows using static data storage formats. Linear system solving by a direct multiplicative algorithm is, like the solving with $LU$-decomposition, just another scheme of the Gaussian elimination method implementation.

In this paper, this algorithm is the basis for solving the following problems:

Problem 1. Setting the descent direction in Newtonian methods of unconditional optimization by integrating one of the known techniques of constructing an essentially positive definite matrix. This approach allows us to weaken or remove additional specific difficulties caused by the need to solve large equation systems with sparse matrices presented in a packed form.

Problem 2. Construction of a new mathematical formulation of the problem of quadratic programming and a new form of specifying necessary and sufficient optimality conditions. They are quite simple and can be used to construct mathematical programming methods, for example, to find the minimum of a quadratic function on a polyhedral set of constraints, based on solving linear equations systems, which dimension is not higher than the number of variables of the objective function.

Problem 3. Construction of a continuous analogue of the problem of minimizing a real quadratic polynomial in Boolean variables and a new form of defining necessary and sufficient conditions of optimality for the development of methods for solving them in polynomial time. As a result, the original problem is reduced to the problem of finding the minimum distance between the origin and the angular point of a convex polyhedron, which is a perturbation of the $n$-dimensional cube and is described by a system of double linear inequalities with an upper triangular matrix of coefficients with units on the main diagonal. Only two faces are subject to investigation, one of which or both contains the vertices closest to the origin. To calculate them, it is sufficient to solve $4n – 4$ linear equations systems and choose among them all the nearest equidistant vertices in polynomial time. The problem of minimizing a quadratic polynomial is $NP$-hard, since an $NP$-hard problem about a vertex covering for an arbitrary graph comes down to it. It follows therefrom that $P = NP$, which is based on the development beyond the limits of integer optimization methods.

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

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

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

A numerically stable direct multiplicative method for solving systems of linear equations that takes into account the sparseness of matrices presented in a packed form is considered. The advantage of the method is the calculation of the Cholesky factors for a positive definite matrix of the system of equations and its solution within 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 to the position of the next processed row of the matrix, which allows using static data storage formats. The solution of the system of linear equations by a direct multiplicative algorithm is, like the solution with LU-decomposition, just another scheme for implementing the Gaussian elimination method.

The calculation of the Cholesky factors for a positive definite matrix of the system and its solution underlies the construction of a new mathematical formulation of the unconditional problem of quadratic programming and a new form of specifying necessary and sufficient conditions for optimality that are quite simple and are used in this paper to construct a new mathematical formulation for the problem of quadratic programming on a polyhedral set of constraints, which is the problem of finding the minimum distance between the origin ordinate and polyhedral boundary by means of a set of constraints and linear algebra dimensional geometry.

To determine the distance, it is proposed to apply the known exact method based on solving systems of linear equations whose dimension is not higher than the number of variables of the objective function. The distances are determined by the construction of perpendiculars to the faces of a polyhedron of different dimensions. To reduce the number of faces examined, the proposed method involves a special order of sorting the faces. Only the faces containing the vertex closest to the point of the unconditional extremum and visible from this point are subject to investigation. In the case of the presence of several nearest equidistant vertices, we investigate a face containing all these vertices and faces of smaller dimension that have at least two common nearest vertices with the first face.

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

Recently, saddle point problems have received much attention due to their powerful modeling capability for a lot of problems from diverse domains. Applications of these problems occur in many applied areas, such as robust optimization, distributed optimization, game theory, and many applications in machine learning such as empirical risk minimization and generative adversarial networks training. Therefore, many researchers have actively worked on developing numerical methods for solving saddle point problems in many different settings. This paper is devoted to developing a numerical method for solving saddle point problems in the nonconvex uniformly-concave setting. We study a general class of saddle point problems with composite structure and H\"older-continuous higher-order derivatives. To solve the problem under consideration, we propose an approach in which we reduce the problem to a combination of two auxiliary optimization problems separately for each group of variables, the outer minimization problem w.r.t. primal variables, and the inner maximization problem w.r.t the dual variables. For solving the outer minimization problem, we use the Adaptive Gradient Method, which is applicable for nonconvex problems and also works with an inexact oracle that is generated by approximately solving the inner problem. For solving the inner maximization problem, we use the Restarted Unified Acceleration Framework, which is a framework that unifies the high-order acceleration methods for minimizing a convex function that has H\"older-continuous higher-order derivatives. Separate complexity bounds are provided for the number of calls to the first-order oracles for the outer minimization problem and higher-order oracles for the inner maximization problem. Moreover, the complexity of the whole proposed approach is then estimated.

Численное решение системы уравнений высокотемпературной радиационной газовой динамики (ВРГД) является вычислительно трудоемкой задачей, так как взаимодействие излучения с веществом нелинейно и нелокально. Коэффициенты поглощения излучения зависят от температуры, а поле температур определяется как газодинамическими процессами, так и переносом излучения. Обычно для решения системы ВРГД используется метод расщепления по физическим процессам, выделяется блок решения уравнения переноса совместно с уравнением баланса энергии вещества при известных давлениях и температурах. Построенные ранее разностные схемы, используемые для решения этого блока, обладают порядками сходимости не выше второго. Так как даже на современном уровне развития вычислительной техники имеются ограничения по памяти, то для решения сложных технических задач приходится применять не слишком подробные сетки. Это повышает требования к порядку аппроксимации разностных схем. В данной работе впервые реализованы бикомпактные схемы высокого порядка аппроксимации для алгоритма совместного решения уравнения переноса излучения и уравнения баланса энергии. Предложенный метод может быть применен для решения широкого круга практических задач, так как обладает высокой точностью и подходит для решения задач с разрывами коэффициентов. Нелинейность задачи и использование неявной схемы приводит к итерационному процессу, который может медленно сходиться. В данной работе используется мультипликативный HOLO-алгоритм — метод квазидиффузии В.Я. Гольдина. Ключевая идея HOLO-алгоритмов состоит в совместном решении уравнений высокого порядка (high order, HO) и низкого порядка (low order, LO). Уравнением высокого порядка (HO) является уравнение переноса излучения, которое решается в многогрупповом приближении, далее уравнение осредняется по угловой переменной и получается система уравнений квазидиффузии в многогрупповом приближении (LO₁). Следующим этапом является осреднение по энергии, при этом получается эффективная одногрупповая система уравнений квазидиффузии (LO₂), которая решается совместно с уравнением энергии. Решения, получаемые на каждом этапе HOLO-алгоритма, оказываются тесно связанными, что в итоге приводит к ускорению сходимости итерационного процесса. Для каждого из этапов HOLO-алгоритма предложены разностные схемы, построенные методом прямых в рамках одной ячейки и обладающие четвертым порядком аппроксимации по пространству и третьим порядком по времени. Схемы для уравнения переноса были разработаны Б.В. Роговым и его коллегами, схемы для уравнений LO₁ и LO₂ разработаны авторами. Предложен аналитический тест, на котором демонстрируются заявленные порядки сходимости. Рассматриваются различные варианты постановки граничных условий и исследовано их влияние на порядок сходимости по времени и пространству.

The numerical solving of the system of high-temperature radiative gas dynamics (HTRGD) equations is a computationally laborious task, since the interaction of radiation with matter is nonlinear and non-local. The radiation absorption coefficients depend on temperature, and the temperature field is determined by both gas-dynamic processes and radiation transport. The method of splitting into physical processes is usually used to solve the HTRGD system, one of the blocks consists of a joint solving of the radiative transport equation and the energy balance equation of matter under known pressure and temperature fields. Usually difference schemes with orders of convergence no higher than the second are used to solve this block. Due to computer memory limitations it is necessary to use not too detailed grids to solve complex technical problems. This increases the requirements for the order of approximation of difference schemes. In this work, bicompact schemes of a high order of approximation for the algorithm for the joint solution of the radiative transport equation and the energy balance equation are implemented for the first time. The proposed method can be applied to solve a wide range of practical problems, as it has high accuracy and it is suitable for solving problems with coefficient discontinuities. The non-linearity of the problem and the use of an implicit scheme lead to an iterative process that may slowly converge. In this paper, we use a multiplicative HOLO algorithm named the quasi-diffusion method by V.Ya.Goldin. The key idea of HOLO algorithms is the joint solving of high order (HO) and low order (LO) equations. The high-order equation (HO) is the radiative transport equation solved in the energy multigroup approximation, the system of quasi-diffusion equations in the multigroup approximation (LO₁) is obtained by averaging HO equations over the angular variable. The next step is averaging over energy, resulting in an effective one-group system of quasi-diffusion equations (LO₂), which is solved jointly with the energy equation. The solutions obtained at each stage of the HOLO algorithm are closely related that ultimately leads to an acceleration of the convergence of the iterative process. Difference schemes constructed by the method of lines within one cell are proposed for each of the stages of the HOLO algorithm. The schemes have the fourth order of approximation in space and the third order of approximation in time. Schemes for the transport equation were developed by B.V. Rogov and his colleagues, the schemes for the LO₁ and LO₂ equations were developed by the authors. An analytical test is constructed to demonstrate the declared orders of convergence. Various options for setting boundary conditions are considered and their influence on the order of convergence in time and space is studied.

Представлен вариант обратного метода характеристик (МОМХ), в алгоритм которого введен дополнительный дробный временной шаг, что позволяет повысить точность вычислений за счет более точной аппроксимации характеристик. Приведены расчетные формулы модифицированного метода для уравнений односкоростной модели газожидкостной смеси, с помощью которого рассчитаны одномерные, а также плоские тестовые задачи, имеющие автомодельные решения. При решении многомерных задач исходная система уравнений расщепляется на ряд одномерных подсистем, для расчета которых применяется обратный метод характеристик с дробным временным шагом. С использованием предложенного метода рассчитаны: одномерная задача распада произвольного разрыва в дисперсной среде; двумерная задача взаимодействия однородного газожидкостного потока с препятствием с присоединенным ударным скачком, а также течение с центрированной волной разрежения. Результаты численных расчетов этих задач сопоставлены с автомодельными решениями и отмечено их удовлетворительное совпадение. На примере задачи Римана с ударным скачком приведено сравнение с рядом консервативных, неконсервативных первого и повышенного порядков точности схем, из которого, в частности, следует, что представленный метод расчета вполне конкурентоспособен. Несмотря на то что применение МОМХ требует в разы больших временных затрат по сравнению с оригинальным обратным методом характеристик (ОМХ), вычисления можно проводить с увеличенным временным шагом и в ряде случаев получать более точные результаты. Отмечено, что метод с дробным временным шагом имеет преимущества в случаях, когда характеристики системы криволинейные. По этой причине для уравнений Эйлера целесообразно использовать ОМХ вместо МОМХ, поскольку в этом случае характеристики в пределах временного шага мало отличаются от прямых линий.

A variant of the inverse method of characteristics (IMH) is presented, in whose algorithm an additional fractional time step is introduced, which makes it possible to increase the accuracy of calculations due to a more accurate approximation of the characteristics. The calculation formulas of the modified method for the equations of the one-velocity model of a gas-liquid mixture are given, with the help of which one-dimensional and also flat test problems with self-similar solutions are calculated. When solving multidimensional problems, the original system of equations is split into a number of one-dimensional subsystems, for the calculation of which the inverse method of characteristics with a fractional time step is used. Using the proposed method, the following were calculated: the one-dimensional problem of the decay of an arbitrary discontinuity in a dispersed medium; a twodimensional problem of the interaction of a homogeneous gas-liquid flow with an obstacle with an attached shock wave, as well as a flow with a centered rarefaction wave. The results of numerical calculations of these problems are compared with self-similar solutions and their satisfactory agreement is noted. On the example of the Riemann problem with a shock wave, a comparison is made with a number of conservative, non-conservative, first and higher orders of accuracy schemes, from which, in particular, it follows that the presented calculation method, i. e. MIMC, quite competitive. Despite the fact that the application of MIMC requires many times more time than the original inverse method of characteristics (IMC), calculations can be carried out with an increased time step and, in some cases, more accurate results can be obtained. It is noted that the method with a fractional time step has advantages over the IMC in cases where the characteristics of the system are significantly curvilinear. For this reason, the use of MIMC, for example, for the Euler equations is inappropriate, since for the latter the characteristics within the time step differ little from straight lines.

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

An important role in the construction of mathematical models of dynamic systems is played by inverse problems, which in particular include the problem of parametric identification. Unlike classical models that operate with point values, interval models give upper and lower boundaries on the quantities under study. The paper considers an interpolation approach to solving interval problems of parametric identification of dynamic systems for the case when experimental data are represented by external interval estimates. The purpose of the proposed approach is to find such an interval estimate of the model parameters, in which the external interval estimate of the solution of the direct modeling problem would contain experimental data or minimize the deviation from them. The approach is based on the adaptive interpolation algorithm for modeling dynamic systems with interval uncertainties, which makes it possible to explicitly obtain the dependence of phase variables on system parameters. The task of minimizing the distance between the experimental data and the model solution in the space of interval boundaries of the model parameters is formulated. An expression for the gradient of the objectivet function is obtained. On a representative set of tasks, the effectiveness of the proposed approach is demonstrated.

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

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.

Рассматривается применение консервативного численного метода потоков для изучения вихревых структур в массивных, быстровращающихся компактных астрофизических объектах, находящихся в условиях самогравитации. Моделирование осуществляется для объектов с различной массой и скоростью вращения. Визуализируются картины вихревой структуры объектов. В расчетах используется газодинамическая модель, в которой газ принимается совершенным и невязким. Численная методика основана на конечно-разностной аппроксимации законов сохранения аддитивных характеристик среды для конечного объема. При этом используются 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.

Статья посвящена разработке вычислительного алгоритма метода декартовых сеток для исследования взаимодействия ударной волны с подвижными телами с кусочно-линейной границей. Интерес к подобным задачам связан с прямым численным моделированием течений двухфазных сред. Эффект формы частицы может иметь значение в задаче о диспергировании пылевого слоя за проходящей ударной волной. Экспериментальные данные по коэффициенту аэродинамического сопротивления несферических частиц практически отсутствуют.

Математическая модель основана на двумерных уравнениях Эйлера, которые решаются в области с подвижными границами. Определяющая система уравнений численно интегрируется по явной схеме с использованием метода декартовых сеток. Вычислительный алгоритм на шаге интегрирования по времени включает: определение величины шага, расчет динамики движения тела (определение силы и момента, действующих на тело; определение линейной и угловой скоростей тела; расчет новых координат тела), расчет параметров газа. На каждом шаге интегрирования по времени все ячейки делятся на два класса — внешние (внутри тела или пересекаются его границами) и внутренние (целиком заполнены газом). Решение уравнений Эйлера строится только во внутренних. Основная сложность заключается в расчете численного потока через ребра, общие для внутренних и внешних ячеек, пересекаемых подвижными границами тел. Для расчета этого потока используются двухволновое приближение при решении задачи Римана и схема Стигера–Уорминга. Представлено подробное описание вычислительного алгоритма.

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

The work is devoted to the development of a computational algorithm of the Cartesian grid method for studying the interaction of a shock wave with moving bodies with a piecewise linear boundary. The interest in such problems is connected with direct numerical simulation of two-phase media flows. The effect of the particle shape can be important in the problem of dust layer dispersion behind a passing shock wave. Experimental data on the coefficient of aerodynamic drag of non-spherical particles are practically absent.

Mathematical model is based on the two-dimensional Euler equations, which are solved in a region with varying boundaries. The defining system of equations is integrated using an explicit scheme and the Cartesian grid method. The computational algorithm at the time integration step includes: determining the step value, calculating the dynamics of the body movement (determining the force and moment acting on the body; determining the linear and angular velocities of the body; calculating the new coordinates of the body), calculating the gas parameters. At each time step, all cells are divided into two classes – external (inside the body or intersected by its boundaries) and internal (completely filled with gas). The solution of the Euler equations is constructed only in the internal ones. The main difficulty is the calculation of the numerical flux through the edges common to the internal and external cells intersected by the moving boundaries of the bodies. To calculate this flux, we use a two-wave approximation for solving the Riemann problem and the Steger-Warming scheme. A detailed description of the numerical algorithm is presented.

The efficiency of the algorithm is demonstrated on the problem of lifting a cylinder with a base in the form of a circle, ellipse and rectangle behind a passing shock wave. A circular cylinder test was considered in many papers devoted to the immersed boundary methods development. A qualitative and quantitative analysis of the trajectory of the cylinder center mass is carried out on the basis of comparison with the results of simulations presented in eight other works. For a cylinder with a base in the form of an ellipse and a rectangle, a satisfactory agreement was obtained on the dynamics of its movement and rotation in comparison with the available few literary sources. Grid convergence of the results is investigated for the rectangle. It is shown that the relative error of mass conservation law fulfillment decreases with a linear rate.

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

Новая модель учитывает, что грузовики имеют более низкую (по сравнению с легковыми автомобилями) максимальную скорость и медленнее стартуют с места. Они менее маневренные, поэтому перестраиваться им сложнее. Кроме того, движение грузовиков может регламентироваться некоторыми ограничивающими правилами, например запретом движения по левым полосам.

Модель основана на теории клеточных автоматов, что позволяет всесторонне описывать особенности отдельных компонент потока. На каждом шаге по времени состояние ячеек автомата обновляется в два этапа: перестроение и движение вперед. Алгоритмы обоих подшагов отличаются для легковых и грузовых транспортных средств. Каждому автомобилю присваивается ряд параметров: вид транспортного средства, длина, максимальная скорость, стратегия при смене полосы, стратегия при движении по полосе.

Модель реализована в виде комплекса программ, позволяющего моделировать движение на различных участках улично-дорожной сети — перекрестках, участках с сужением и расширением дороги, въездах и съездах с автомагистрали. В рамках данной работы для тестирования модели выбраны участок дороги с переменным числом полос и прямой многополосный участок с виртуальным детектором. Результаты представлены в виде локальных диаграмм «скорость – плотность» и «поток – плотность», а также пространственно-временных диаграмм скорости.

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

The objective of this article is to develop a model for a realistic description of a mixed flow of two types of vehicles (cars and trucks) on multi-lane highways, taking into account differences not only in the technical characteristics of vehicles (dimensions, maximum speed), but also differences in driving strategies. The article includes a literature review, including publications of recent years, confirming the relevance of modeling heterogeneous traffic flows.

The new model takes into account that trucks have a lower maximum speed compared to cars and are slower to start. They are less maneuverable, so it is more difficult for them to change lanes. In addition, the movement of trucks can be regulated by some restrictive rules, for example, a ban on driving in left lanes.

The model is based on the cellular automata theory, which allows for a comprehensive description of the features of individual flow components. At each time step, the state of the automaton cells is updated in two stages — changing lanes and moving forward. The algorithms of both substeps for cars and trucks differ. Each vehicle is assigned a number of parameters: vehicle type, length, maximum speed, lane change strategy, in-lane movement strategy.

The model is implemented as a software package that allows simulating traffic on various sections of the road network — intersections, sections with narrowing and widening of the road, entrances and exits from the highway. In this work, a road section with a varying number of lanes and a straight multi-lane section with a virtual detector were selected for testing the model. The results are presented in the form of local speed-density and flow-density diagrams, as well as spatiotemporal speed diagrams.

To test the model, a number of problems with different percentages of passenger cars and trucks are solved, which allows demonstrating a drop in the capacity of elements of the road network with an increase in the share of trucks in the flow. The cases of uniform distribution by lanes and the restriction to the right lane for trucks are simulated. The positive effect of introducing a ban on the movement of trucks in left lanes on a multi-lane highway is illustrated.