Все выпуски

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

Программа создавалась на компьютере с шестиядерным процессором. С помощью симулятора gem5, позволяющего моделировать работу различных компьютерных систем, была произведена оценка масштабируемости программы при переходе на большее число ядер (вплоть до 32) на нескольких моделях компьютерной системы вида «вычислительные ядра – кэш-память – оперативная память» с разной степенью детализации ее элементов. Отмечено существенное влияние состава компьютерной системы на степень масштабируемости исполняемой на ней программы: максимальное ускорение на 32-х ядрах при переходе от двухуровневого кэша к трехуровневому увеличивается с 14.2 до 22.2. Время выполнения программы на модели компьютера в gem5 превосходит время ее выполнения на реальном компьютере в 104–105 раз в зависимости от состава модели и составляет 1.5 часа для наиболее детализированной и сложной модели.

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

In this work we have developed a new efficient program for the numerical simulation of 3D global chemical transport on an adaptive finite-difference grid which allows us to concentrate grid points in the regions where flow variables sharply change and coarsen the grid in the regions of their smooth behavior, which significantly minimizes the grid size. We represent the adaptive grid with a combination of several dynamic (tree, linked list) and static (array) data structures. The dynamic data structures are used for a grid reconstruction, and the calculations of the flow variables are based on the static data structures. The introduction of the static data structures allows us to speed up the program by a factor of 2 in comparison with the conventional approach to the grid representation with only dynamic data structures.

We wrote and tested our program on a computer with 6 CPU cores. Using the computer microarchitecture simulator gem5, we estimated the scalability property of the program on a significantly greater number of cores (up to 32), using several models of a computer system with the design “computational cores – cache – main memory”. It has been shown that the microarchitecture of a computer system has a significant impact on the scalability property, i.e. the same program demonstrates different efficiency on different computer microarchitectures. For example, we have a speedup of 14.2 on a processor with 32 cores and 2 cache levels, but we have a speedup of 22.2 on a processor with 32 cores and 3 cache levels. The execution time of a program on a computer model in gem5 is 104–105 times greater than the execution time of the same program on a real computer and equals 1.5 hours for the most complex model.

Also in this work we describe how to configure gem5 and how to perform simulations with gem5 in the most optimal way.

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

The equilibrium configurations of charged electrons, confined in the hard disk potential, are analysed by means of the hybrid numerical algorithm. The algorithm is based on the interpolation formulas, that are obtained from the analysis of the equilibrium configurations, provided by the variational principle developed in the circular model. The solution of the nonlinear equations of the circular model yields the formation of the shell structure which is composed of the series of rings. Each ring contains a certain number of particles, which decreases as one moves from the boundary ring to the central one. The number of rings depends on the total number of electrons. The interpolation formulas provide the initial configurations for the molecular dynamics calculations. This approach makes it possible to significantly increase the speed at which an equilibrium configuration is reached for an arbitrarily chosen number of particles compared to the Metropolis annealing simulation algorithm and other algorithms based on global optimization methods.

Реконструкция траекторий заряженных частиц в трековых детекторах является ключевой проблемой анализа экспериментальных данных для физики высоких энергий и ядерной физики. Поток данных в современных экспериментах растет день ото дня, и традиционные методы трекинга уже не в состоянии соответствовать этим объемам данных по скорости обработки. Для решения этой проблемы нами были разработаны два нейросетевых алгоритма, использующих методы глубокого обучения, для локальной (каждый трек в отдельности) и глобальной (все треки в событии) реконструкции треков применительно к данным трекового GEM-детектора эксперимента BM@N ОИЯИ. Преимущество глубоких нейронных сетей обусловлено их способностью к обнаружению скрытых нелинейных зависимостей в данных и возможностью параллельного выполнения операций линейной алгебры, лежащих в их основе.

В данной статье приведено описание исследования по обобщению этих алгоритмов и их адаптации к применению для внутреннего поддетектора CGEM (BESIII ИФВЭ, Пекин). Нейросетевая модель RDGraphNet для глобальной реконструкции треков, разработанная на основе реверсного орграфа, успешно адаптирована. После обучения на модельных данных тестирование показало обнадеживающие результаты: для распознавания треков полнота (recall) составила 98% и точность (precision) — 86%. Однако адаптация «локальной» нейросетевой модели TrackNETv2 потребовала учета специфики цилиндрического детектора CGEM (BESIII), состоящего всего из трех детектирующих слоев, и разработки дополнительного нейроклассификатора для отсева ложных треков. Полученная программа TrackNETv2.1 протестирована в отладочном режиме. Значение полноты на первом этапе обработки составило 99%. После применения классификатора точность составила 77%, при незначительном снижении показателя полноты до 94%. Данные результаты предполагают дальнейшее совершенствование модели локального трекинга.

The reconstruction of charged particle trajectories in tracking detectors is a key problem in the analysis of experimental data for high energy and nuclear physics.

The amount of data in modern experiments is so large that classical tracking methods such as Kalman filter can not process them fast enough. To solve this problem, we have developed two neural network algorithms of track recognition, based on deep learning architectures, for local (track by track) and global (all tracks in an event) tracking in the GEM tracker of the BM@N experiment at JINR (Dubna). The advantage of deep neural networks is the ability to detect hidden nonlinear dependencies in data and the capability of parallel execution of underlying linear algebra operations.

In this work we generalize these algorithms to the cylindrical GEM inner tracker of BESIII experiment. The neural network model RDGraphNet for global track finding, based on the reverse directed graph, has been successfully adapted. After training on Monte Carlo data, testing showed encouraging results: recall of 98% and precision of 86% for track finding.

The local neural network model TrackNETv2 was also adapted to BESIII CGEM successfully. Since the tracker has only three detecting layers, an additional neuro-classifier to filter out false tracks have been introduced. Preliminary tests demonstrated the recall value at the first stage of 99%. After applying the neuro-classifier, the precision was 77% with a slight decrease of the recall to 94%. This result can be improved after the further model optimization.

Новый асинхронный алгоритм дифференциальной эволюции использован для определения параметров микроскопического оптического потенциала упругого рассеяния пионов на ядрах ²⁸Si, ⁵⁸Ni и ²⁰⁸Pb при энергиях 130, 162 и 180 МэВ.

New Asynchronous Differential Evolution algorithm is used to determine the parameters of microscopic optical potential of elastic pion scattering on ²⁸Si, ⁵⁸Ni and ²⁰⁸Pb nuclei at energy 130, 162 and 180 MeV.

Проведенное исследование основано на сочетании трехмерной гидродинамической модели глобального климата, включая модель океана с реальными глубинами и конфигурацией континентов, модель эволюции морского льда и энерго-, влагобалансовую модель атмосферы. Концентрация аэрозоля от 2010 г. до 2100 г. рассчитывается как управляющий параметр для стабилизации среднегодовой температуры воздуха у поверхности земли. На основе расчетов предполагается, что выбросы серы от 2010 г. до 2100 г. изменяются линейно для первого сценария и квадратично — для второго роста СО₂. Граница Парето исследована и визуализирована для двух параметров — среднеквадратичного отклонения атмосферной температуры для зимнего и летнего сезонов.

The study is based on a three-dimensional hydrodynamic global climate coupled model, including ocean model with real depths and continents configuration, sea ice evolution model and energy and moisture balance atmosphere model. Aerosol concentration from the year 2010 to 2100 is calculated as a controlling parameter to stabilize mean year surface air temperature. It is shown that by this way it is impossible to achieve the space and seasonal uniform approximation to the existing climate, although it is possible significantly reduce the greenhouse warming effect. Climate will be colder at 0.1–0.2 degrees in the low and mid-latitudes and at high latitudes it will be warmer at 0.2–1.2 degrees. The Pareto frontier is investigated and visualized for two parameters — atmospheric temperature mean square deviation for the winter and summer seasons. The Pareto optimal amount of sulfur emissions would be between 23.5 and 26.5 TgS/year.

В данной статье предлагаются методы оптимизации высокого порядка (тензорные методы) для решения двух типов седловых задач. Первый тип — это классическая мин-макс-постановка для поиска седловой точки функционала. Второй тип — это поиск стационарной точки функционала седловой задачи путем минимизации нормы градиента этого функционала. Очевидно, что стационарная точка не всегда совпадает с точкой оптимума функции. Однако необходимость в решении подобного типа задач может возникать в случае, если присутствуют линейные ограничения. В данном случае из решения задачи поиска стационарной точки двойственного функционала можно восстановить решение задачи поиска оптимума прямого функционала. В обоих типах задач какие-либо ограничения на область определения целевого функционала отсутствуют. Также мы предполагаем, что целевой функционал является $\mu$-сильно выпуклыми $\mu$-сильно вогнутым, а также что выполняется условие Липшица для его $p$-й производной.

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

In this paper we propose high-order (tensor) methods for two types of saddle point problems. Firstly, we consider the classic min-max saddle point problem. Secondly, we consider the search for a stationary point of the saddle point problem objective by its gradient norm minimization. Obviously, the stationary point does not always coincide with the optimal point. However, if we have a linear optimization problem with linear constraints, the algorithm for gradient norm minimization becomes useful. In this case we can reconstruct the solution of the optimization problem of a primal function from the solution of gradient norm minimization of dual function. In this paper we consider both types of problems with no constraints. Additionally, we assume that the objective function is $\mu$-strongly convex by the first argument, $\mu$-strongly concave by the second argument, and that the $p$-th derivative of the objective is Lipschitz-continous.

For min-max problems we propose two algorithms. Since we consider strongly convex a strongly concave problem, the first algorithm uses the existing tensor method for regular convex concave saddle point problems and accelerates it with the restarts technique. The complexity of such an algorithm is linear. If we additionally assume that our objective is first and second order Lipschitz, we can improve its performance even more. To do this, we can switch to another existing algorithm in its area of quadratic convergence. Thus, we get the second algorithm, which has a global linear convergence rate and a local quadratic convergence rate.

Finally, in convex optimization there exists a special methodology to solve gradient norm minimization problems by tensor methods. Its main idea is to use existing (near-)optimal algorithms inside a special framework. I want to emphasize that inside this framework we do not necessarily need the assumptions of strong convexity, because we can regularize the convex objective in a special way to make it strongly convex. In our article we transfer this framework on convex-concave objective functions and use it with our aforementioned algorithm with a global linear convergence and a local quadratic convergence rate.

Since the saddle point problem is a particular case of the monotone variation inequality problem, the proposed methods will also work in solving strongly monotone variational inequality problems.

The Lipschitz continuous property has been used for a long time to solve the global optimization problem and continues to be used. Here we can mention the work of Piyavskii, Yevtushenko, Strongin, Shubert, Sergeyev, Kvasov and others. Most papers assume a priori knowledge of the Lipschitz constant, but the derivation of this constant is a separate problem. Further still, we must prove that an objective function is really Lipschitz, and it is a complicated problem too. In the case where the Lipschitz continuity is established, Strongin proposed an algorithm for global optimization of a satisfying Lipschitz condition on a compact interval function without any a priori knowledge of the Lipschitz estimate. The algorithm not only finds a global extremum, but it determines the Lipschitz estimate too. It is known that every function that satisfies the Lipchitz condition on a compact convex set is uniformly continuous, but the reverse is not always true. However, there exist models (Arutyunova, Dulliev, Zabotin) whose study requires a minimization of the continuous but definitely not Lipschitz function. One of the algorithms for solving such a problem was proposed by R. J. Vanderbei. In his work he introduced some generalization of the Lipchitz property named $\varepsilon$-Lipchitz and proved that a function defined on a compact convex set is uniformly continuous if and only if it satisfies the $\varepsilon$-Lipchitz condition. The above-mentioned property allowed him to extend Piyavskii’s method. However, Vanderbei assumed that for a given value of $\varepsilon$ it is possible to obtain an associate Lipschitz $\varepsilon$-constant, which is a very difficult problem. Thus, there is a need to construct, for a function continuous on a compact convex domain, a global optimization algorithm which works in some way like Strongin’s algorithm, i.e., without any a priori knowledge of the Lipschitz $\varepsilon$-constant. In this paper we propose an extension of Strongin’s global optimization algorithm to a function continuous on a compact interval using the $\varepsilon$-Lipchitz conception, prove its convergence and solve some numerical examples using the software that implements the developed method.

The Lipschitz continuous property has been used for a long time to solve the global optimization problem and continues to be used. Here we can mention the work of Piyavskii, Yevtushenko, Strongin, Shubert, Sergeyev, Kvasov and others. Most papers assume a priori knowledge of the Lipschitz constant, but the derivation of this constant is a separate problem. Further still, we must prove that an objective function is really Lipschitz, and it is a complicated problem too. In the case where the Lipschitz continuity is established, Strongin proposed an algorithm for global optimization of a satisfying Lipschitz condition on a compact interval function without any a priori knowledge of the Lipschitz estimate. The algorithm not only finds a global extremum, but it determines the Lipschitz estimate too. It is known that every function that satisfies the Lipchitz condition on a compact convex set is uniformly continuous, but the reverse is not always true. However, there exist models (Arutyunova, Dulliev, Zabotin) whose study requires a minimization of the continuous but definitely not Lipschitz function. One of the algorithms for solving such a problem was proposed by R. J. Vanderbei. In his work he introduced some generalization of the Lipchitz property named $\varepsilon$-Lipchitz and proved that a function defined on a compact convex set is uniformly continuous if and only if it satisfies the $\varepsilon$-Lipchitz condition. The above-mentioned property allowed him to extend Piyavskii’s method. However, Vanderbei assumed that for a given value of $\varepsilon$ it is possible to obtain an associate Lipschitz $\varepsilon$-constant, which is a very difficult problem. Thus, there is a need to construct, for a function continuous on a compact convex domain, a global optimization algorithm which works in some way like Strongin’s algorithm, i.e., without any a priori knowledge of the Lipschitz $\varepsilon$-constant. In this paper we propose an extension of Strongin’s global optimization algorithm to a function continuous on a compact interval using the $\varepsilon$-Lipchitz conception, prove its convergence and solve some numerical examples using the software that implements the developed method.

Задачи негладкой оптимизации нередко возникают во многих приложениях. Вопросы разработки эффективных вычислительных процедур для негладких задач в пространствах больших размерностей весьма актуальны. В таких случаях разумно применятьмет оды первого порядка (субградиентные методы), однако в достаточно общих ситуациях они приводят к невысоким скоростным гарантиям. Одним из подходов к этой проблеме может являться выделение подкласса негладких задач, допускающих относительно оптимистичные результаты о скорости сходимости в пространствах больших размерностей. К примеру, одним из вариантов дополнительных предположений может послужитьуслови е острого минимума, предложенное в конце 1960-х годов Б. Т. Поляком. В случае доступности информации о минимальном значении функции для липшицевых задач с острым минимумом известен субградиентный метод с шагом Б. Т. Поляка, который гарантирует линейную скорость сходимости по аргументу. Такой подход позволил покрыть ряд важных прикладных задач (например, задача проектирования точки на выпуклый компакт или задача отыскания общей точки системы выпуклых множеств). Однако как условие доступности минимального значения функции, так и само условие острого минимума выглядят довольно ограничительными. В этой связи в настоящей работе предлагается обобщенное условие острого минимума, аналогичное известному понятию неточного оракула. Предложенный подход позволяет расширить класс применимости субградиентных методов с шагом Б. Т. Поляка на ситуации неточной информации о значении минимума, а также неизвестной константы Липшица целевой функции. Более того, использование в теоретической оценке качества выдаваемого методом решения локальных аналогов глобальных характеристик целевой функции позволяет применять результаты такого типа и к более широким классам задач. Показана возможностьпр именения предложенного подхода к сильно выпуклым негладким задачам и выполнено экспериментальное сравнение с известным оптимальным субградиентным методом на таком классе задач. Более того, получены результаты о применимости предложенной методики для некоторых типов задач с релаксациями выпуклости: недавно предложенное понятие слабой $\beta$-квазивыпуклости и обычной квазивыпуклости. Исследовано обобщение описанной методики на ситуацию с предположением о доступности на итерациях $\delta$-субградиента целевой функции вместо обычного субградиента. Для одного из рассмотренных методов найдены условия, при которых на практике можно отказаться от проектирования итеративной последовательности на допустимое множество поставленной задачи.

Non-smooth optimization often arises in many applied problems. The issues of developing efficient computational procedures for such problems in high-dimensional spaces are very topical. First-order methods (subgradient methods) are well applicable here, but in fairly general situations they lead to low speed guarantees for large-scale problems. One of the approaches to this type of problem can be to identify a subclass of non-smooth problems that allow relatively optimistic results on the rate of convergence. For example, one of the options for additional assumptions can be the condition of a sharp minimum, proposed in the late 1960s by B. T. Polyak. In the case of the availability of information about the minimal value of the function for Lipschitz-continuous problems with a sharp minimum, it turned out to be possible to propose a subgradient method with a Polyak step-size, which guarantees a linear rate of convergence in the argument. This approach made it possible to cover a number of important applied problems (for example, the problem of projecting onto a convex compact set). However, both the condition of the availability of the minimal value of the function and the condition of a sharp minimum itself look rather restrictive. In this regard, in this paper, we propose a generalized condition for a sharp minimum, somewhat similar to the inexact oracle proposed recently by Devolder – Glineur – Nesterov. The proposed approach makes it possible to extend the class of applicability of subgradient methods with the Polyak step-size, to the situation of inexact information about the value of the minimum, as well as the unknown Lipschitz constant of the objective function. Moreover, the use of local analogs of the global characteristics of the objective function makes it possible to apply the results of this type to wider classes of problems. We show the possibility of applying the proposed approach to strongly convex nonsmooth problems, also, we make an experimental comparison with the known optimal subgradient method for such a class of problems. Moreover, there were obtained some results connected to the applicability of the proposed technique to some types of problems with convexity relaxations: the recently proposed notion of weak $\beta$-quasi-convexity and ordinary quasiconvexity. Also in the paper, we study a generalization of the described technique to the situation with the assumption that the $\delta$-subgradient of the objective function is available instead of the usual subgradient. For one of the considered methods, conditions are found under which, in practice, it is possible to escape the projection of the considered iterative sequence onto the feasible set of the problem.

Молекулярно-динамические методы, использующие силовое поле ReaxFF, позволяют получать достаточно хорошие результаты при моделировании больших многокомпонентных химически-реактивных систем. Здесь представлены алгоритм поиска оптимальных параметров силового поля ReaxFF для произвольных химических систем, а также его реализация. Метод основан на способе многомерного поиска глобального минимума, предложенном Р. Г. Стронгиным. Алгоритм хорошо масштабируемый и хорошо подходит для работы на параллельных вычислительных кластерах.

Molecular dynamic methods that use ReaxFF force field allow one to obtain sufficiently good results in simulating large multicomponent chemically reactive systems. Here is represented an algorithm of searching optimal parameters of molecular-dynamic force field ReaxFF for arbitrary chemical systems and its implementation. The method is based on the multidimensional technique of global minimum search suggested by R.G. Strongin. It has good scalability useful for running on distributed parallel computers.