All issues

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

Images of surface topography of ultrathin magnetic films have been used for Monte Carlo simulations in the framework of the ferromagnetic Ising model to study the hysteresis and thermal properties of nanomaterials. For high performance calculations was used super-scalable parallel algorithm for the finding of the equilibrium configuration. The changing of a distribution of spins on the surface during the reversal of the magnetization and the dynamics of nanodomain structure of thin magnetic films under the influence of changing external magnetic field was investigated.

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

В настоящей работе схемы расщепления 3-го и 4-го порядка были применены непосредственно к решению двумерной гиперболической системы уравнений в частных производных линейной теории упругости. Это позволило повысить итоговый порядок сходимости расчетного алгоритма. В работе эмпирически оценена сходимость по нормам $L_1$ и $L_\infty$ с использованиемана литических решений определяющей системы достаточной степени гладкости. Для получения объективных результатов рассмотрены случаи продольных и поперечных плоских волн, распространяющихся как вдоль диагонали расчетной ячейки, так и не вдоль нее. Проведенные численные эксперименты подтверждают повышение точности метода и демонстрируют теоретически ожидаемый порядок сходимости. При этом увеличивается в 3 и в 4 раза время моделирования (для схем 3-го и 4-го порядка соответственно), но не возрастает потребление оперативной памяти. Предложенное усовершенствование вычислительного алгоритма сохраняет простоту его параллельной реализации на основе пространственной декомпозиции расчетной сетки.

The grid-characteristic method is successfully used for solving hyperbolic systems of partial differential equations (for example, transport / acoustic / elastic equations). It allows to construct correctly algorithms on contact boundaries and boundaries of the integration domain, to a certain extent to take into account the physics of the problem (propagation of discontinuities along characteristic curves), and has the property of monotonicity, which is important for considered problems. In the cases of two-dimensional and three-dimensional problems the method makes use of a coordinate splitting technique, which enables us to solve the original equations by solving several one-dimensional ones consecutively. It is common to use up to 3-rd order one-dimensional schemes with simple splitting techniques which do not allow for the convergence order to be higher than two (with respect to time). Significant achievements in the operator splitting theory were done, the existence of higher-order schemes was proved. Its peculiarity is the need to perform a step in the opposite direction in time, which gives rise to difficulties, for example, for parabolic problems.

In this work coordinate splitting of the 3-rd and 4-th order were used for the two-dimensional hyperbolic problem of the linear elasticity. This made it possible to increase the final convergence order of the computational algorithm. The paper empirically estimates the convergence in L1 and L∞ norms using analytical solutions of the system with the sufficient degree of smoothness. To obtain objective results, we considered the cases of longitudinal and transverse plane waves propagating both along the diagonal of the computational cell and not along it. Numerical experiments demonstrated the improved accuracy and convergence order of constructed schemes. These improvements are achieved with the cost of three- or fourfold increase of the computational time (for the 3-rd and 4-th order respectively) and no additional memory requirements. The proposed improvement of the computational algorithm preserves the simplicity of its parallel implementation based on the spatial decomposition of the computational grid.

Механические свойства клеток эукариот играют важную роль в условиях жизненного цикла и при развитии патологических процессов. В работе обсуждается проблема идентификации и верификации параметров вязкоупругих конститутивных моделей на основе данных силовой спектроскопии клеток эукариот. Предлагается использовать одномерное непрерывное вейвлет-преобразование для расчета ядра релаксации. Приводятся аналитические выкладки и результаты численных расчетов, позволяющие на основе экспериментально установленных силовых кривых и теоретических зависимостей «напряжение – деформация» с применением алгоритмов вейвлет-дифференцирования получать аналогичные друг другу функции релаксации. Анализируются тестовые примеры, демонстрирующие корректности программной реализации предложенных алгоритмов. Рассматриваются модели клетки, на примере которых демонстрируется применение предложенной процедуры идентификации и верификации их параметров. Среди них структурно-механическая модель с параллельно соединенными дробными элементами, которая является на данный момент наиболее адекватной с точки зрения соответствия данным атомно-силовой микроскопии широкого класса клеток, и новая статистико-термодинамическая модель, которая не уступает в описательных возможностях моделям с дробными производными, но имеет более ясный физический смысл. Для статистико-термодинамической модели подробно описывается процедура ее построения, которая в себя включает следующее: введение структурной переменной, параметра порядка, для описания ориентационных свойств цитоскелета клетки; постановку и решение статистической задачи для ансамбля актиновых филаментов представительного объема клетки относительно данной переменной; установление вида свободной энергии, зависящей от параметра порядка, температуры и внешней нагрузки. Также предложено в качестве модели представительного элемента клетки использовать ориентационно-вязкоупругое тело. Согласно теории линейной термодинамики получены эволюционные уравнения, описывающие механическое поведение представительного объема клетки, которые удовлетворяют основным термодинамическим законам. Также поставлена и решена задача оптимизации параметров статистико-термодинамической модели клетки, которая может сопоставляется как с экспериментальными данными, так и с результатами симуляций на основе других математических моделей. Определены вязкоупругие характеристики клеток на основе сопоставления с литературными данными.

Mechanical properties of eukaryotic cells play an important role in life cycle conditions and in the development of pathological processes. In this paper we discuss the problem of parameters identification and verification of viscoelastic constitutive models based on force spectroscopy data of living cells. It is proposed to use one-dimensional continuous wavelet transform to calculate the relaxation function. Analytical calculations and the results of numerical simulation are given, which allow to obtain relaxation functions similar to each other on the basis of experimentally determined force curves and theoretical stress-strain relationships using wavelet differentiation algorithms. Test examples demonstrating correctness of software implementation of the proposed algorithms are analyzed. The cell models are considered, on the example of which the application of the proposed procedure of identification and verification of their parameters is demonstrated. Among them are a structural-mechanical model with parallel connected fractional elements, which is currently the most adequate in terms of compliance with atomic force microscopy data of a wide class of cells, and a new statistical-thermodynamic model, which is not inferior in descriptive capabilities to models with fractional derivatives, but has a clearer physical meaning. For the statistical-thermodynamic model, the procedure of its construction is described in detail, which includes the following. Introduction of a structural variable, the order parameter, to describe the orientation properties of the cell cytoskeleton. Setting and solving the statistical problem for the ensemble of actin filaments of a representative cell volume with respect to this variable. Establishment of the type of free energy depending on the order parameter, temperature and external load. It is also proposed to use an oriented-viscous-elastic body as a model of a representative element of the cell. Following the theory of linear thermodynamics, evolutionary equations describing the mechanical behavior of the representative volume of the cell are obtained, which satisfy the basic thermodynamic laws. The problem of optimizing the parameters of the statisticalthermodynamic model of the cell, which can be compared both with experimental data and with the results of simulations based on other mathematical models, is also posed and solved. The viscoelastic characteristics of cells are determined on the basis of comparison with literature data.

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

This work is devoted to molecular dynamic modeling of the thermal impact processes on the metal sample consisting of nickel atoms. For the solution of this problem, a continuous mathematical model on the basis of the classical Newton mechanics equations has been used; a numerical method based on the Verlet scheme has been chosen; a parallel algorithm has been offered, and its realization within the MPI and OpenMP technologies has been executed. By means of the developed parallel program, the investigation of thermodynamic equilibrium of nickel atoms’ system under the conditions of heating a sample to desired temperature has been executed. In numerical experiments both optimum parameters of calculation procedure and physical parameters of analyzed process have been defined. The obtained numerical results are well corresponding to known theoretical and experimental data.

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

The paper presents a software system aimed at finding best (in some sense) parameters of an algorithm. The system handles both discrete and continuous parameters and employs massive parallelism offered by public clouds. The paper presents an overview of the system, a method to measure algorithm's performance in the cloud and numerical results of system's use on several problem sets.

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

The decomposition algorithms provide approaches to deal with NP-hardness in solving discrete optimization problems (DOPs). In this article one of the promising ways to exploit sparse matrices — local elimination algorithm in parallel interpretation (LEAP) are demonstrated. That is a graph-based structural decomposition algorithm, which allows to compute a solution in stages such that each of them uses results from previous stages. At the same time LEAP heavily depends on elimination ordering which actually provides solving stages. Also paper considers tree- and block-parallel for LEAP and required realization process of it comparison of a several heuristics for obtaining a better elimination order and shows how is related graph structure, elimination ordering and solving time.

Молекулярно-динамические методы, использующие силовое поле 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.

Объектом исследований является создание алгоритма для расчета цен большого числа опционов с целью формирования безрискового портфеля. Метод базируется на обобщении подхода Блэка–Шоулза. Задача состоит в моделировании поведения всех опционов, а также инструментов их страхования. Для данной задачи характерен большой объем параллельных вычислений, которые требуется производить в режиме реального времени. Проблематика исследования: в зависимости от исходных данных используются разные подходы к решению. Существует три метода, которые могут использоваться при разных условиях: конечно-разностный метод, метод функционального интегрирования и метод, который связан с остановкой торгов на рынке. Распределенные вычисления в каждом из этих случаев организуются по- разному и требуют использования различных подходов. Сложность задачи также связана с тем, что в литературе ее математическая постановка не является корректной. Отсутствует полное описание граничных и начальных условий, а также некоторые предположения, лежащие в основе модели, не соответствуют реальным условиям рынка. Необходимо дать математически корректную постановку задачи и убрать несоответствие между предположениями модели и реальным рынком. Для этих целей необходимо расширить стандартную постановку за счет дополнительных методов и улучшить методы реализации для каждого направления решения задачи.

Object of research: The creation of algorithm for mass computations of options‘ price for formation of a riskless portfolio. The method is based on the generalization of the Black–Scholes method. The task is the modeling of behavior of all options and tools for their insurance. This task is characterized by large volume of realtime complex computations that should be executed concurrently The problem of the research: depending on conditions approaches to the solution should be various. There are three methods which can be used with different conditions: the finite difference method, the path-integral approach and methods which work in conditions of trade stop. Distributed computating in these three cases is organized differently and it is necessary to involve various approaches. In addition to complexity the mathematical formulation of the problem in literature is not quite correct. There is no complete description of boundary and initial conditions and also several hypotheses of the model do not correspond to real market. It is necessary to give mathematically correct formulation of the task, and to neutralize a difference between hypotheses of the model and their prototypes in the market. For this purpose it is necessary to expand standard formulation by additional methods and develop methods of realization for each of solution branches.

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

In this paper, we introduce the concept of non-uniform cellular genetic algorithm, in which a number of parameters that affect the operation of genetic operators is dependent on the location of the cells of a given cellular space. The results of numerical comparison of non-uniform cellular genetic algorithms with the standard genetic algorithms, showing the advantages of the proposed approach while minimizing multimodal functions with a large number of local extrema, are presented. The coarse-grained parallel implementation of the non-uniform algorithms using the technology of MPI is considered.

Курс «Естественные модели параллельных вычислений», читаемый студентам старших курсов факультета ВМК МГУ, посвящен рассмотрению вопросов суперкомпьютерной реализации естественных вычислительных моделей и является, по сути, введением в теорию естественных вычислений (natural computing) относительно нового раздела науки, образовавшегося на стыке математики, информатики и естественных наук (прежде всего биологии). Тематика естественных вычислений включает в себя как классические разделы, например клеточные автоматы, так и относительно новые, появившиеся в последние 10–20 лет, например методы роевого интеллекта. Несмотря на свое биологическое «происхождение», все эти модели находят широчайшее применение в областях, связанных с компьютерной обработкой данных. Исследования в области естественных вычислений также тесно связаны с вопросами и технологиями параллельных вычислений. Изложение теоретического материала курса сопровождается рассмотрением возможных схем распараллеливания вычислений, а в практической части курса предполагается выполнение студентами программной реализации рассматриваемых моделей с использованием технологии MPI и проведение численных экспериментов по исследованию эффективности выбранных схем распараллеливания вычислений.

Course “Natural models of parallel computing”, given for senior students of the Faculty of Computational Mathematics and Cybernetics, Moscow State University, is devoted to the issues of supercomputer implementation of natural computational models and is, in fact, an introduction to the theory of natural computing, a relatively new branch of science, formed at the intersection of mathematics, computer science and natural sciences (especially biology). Topics of the natural computing include both already classic subjects such as cellular automata, and relatively new, introduced in the last 10–20 years, such as swarm intelligence. Despite its biological origin, all these models are widely applied in the fields related to computer data processing. Research in the field of natural computing is closely related to issues and technology of parallel computing. Presentation of theoretical material of the course is accompanied by a consideration of the possible schemes for parallel computing, in the practical part of the course it is supposed to perform by the students a software implementation using MPI technology and numerical experiments to investigate the effectiveness of the chosen schemes of parallel computing.