Все выпуски

Задача поиска PageRank вектора представляет большой научный и практический интерес ввиду своей применимости к работе современных поисковых систем. Несмотря на то, что данная задача сводится к поиску собственного вектора стохастической матрицы $P$, потребность в новых алгоритмах для ее решения обусловлена большими размерами входных данных. Для достижения не более чем линейного времени работы применяются различные рандомизированные методы, возвращающие ожидаемый ответ лишь с некоторой достаточно близкой к единице вероятностью. Нами рассматриваются два таких способа, сводящие задачу поиска вектора PageRank к задаче поиска равновесия в антагонистической матричной игре, которая затем решается с помощью алгоритма Григориадиса – Хачияна. При этом данная реализация эффективно работает в предположении о разреженности матрицы, подаваемой на вход. Насколько нам известно, до сих пор не было ни одной успешной реализации ни алгоритма Григориадиса – Хачияна, ни его применения к задаче поиска вектора PageRank. Данная статья ставит перед собой задачу восполнить этот пробел. В работе приводится описание двух версий алгоритма с псевдокодом и некоторые детали их реализации. Кроме того, в работе рассматривается другой вероятностный метод поиска вектора PageRank, а именно Markov chain Monte Carlo (MCMC), с целью сравнения результатов работы указанных алгоритмов на матрицах с различными значениями спектральной щели. Последнее представляет особый интерес, поскольку значение спектральной щели сильно влияет на скорость сходимости MCMC, и не оказывает никакого влияния на два других подхода. Сравнение проводилось на сгенерированных графах двух видов: цепочках и $d$-мерных кубах. Проведенные эксперименты, как и предсказывает теория, демонстрируют эффективность алгоритма Григориадиса – Хачияна по сравнению с MCMC для разреженных графов с маленьким значением спектральной щели. Весь код находится в открытом доступе, так чтобы все желающие могли воспроизвести полученные результаты самостоятельно, или же использовать данную реализацию в своих нуждах. Работа имеет чисто практическую направленность, никаких теоретических результатов авторами получено не было.

Finding PageRank vector is of great scientific and practical interest due to its applicability to modern search engines. Despite the fact that this problem is reduced to finding the eigenvector of the stochastic matrix $P$, the need for new algorithms is justified by a large size of the input data. To achieve no more than linear execution time, various randomized methods have been proposed, returning the expected result only with some probability close enough to one. We will consider two of them by reducing the problem of calculating the PageRank vector to the problem of finding equilibrium in an antagonistic matrix game, which is then solved using the Grigoriadis – Khachiyan algorithm. This implementation works effectively under the assumption of sparsity of the input matrix. As far as we know, there are no successful implementations of neither the Grigoriadis – Khachiyan algorithm nor its application to the task of calculating the PageRank vector. The purpose of this paper is to fill this gap. The article describes an algorithm giving pseudocode and some details of the implementation. In addition, it discusses another randomized method of calculating the PageRank vector, namely, Markov chain Monte Carlo (MCMC), in order to compare the results of these algorithms on matrices with different values of the spectral gap. The latter is of particular interest, since the magnitude of the spectral gap strongly affects the convergence rate of MCMC and does not affect the other two approaches at all. The comparison was carried out on two types of generated graphs: chains and $d$-dimensional cubes. The experiments, as predicted by the theory, demonstrated the effectiveness of the Grigoriadis – Khachiyan algorithm in comparison with MCMC for sparse graphs with a small spectral gap value. The written code is publicly available, so everyone can reproduce the results themselves or use this implementation for their own needs. The work has a purely practical orientation, no theoretical results were obtained.

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

The mathematical model based on the linear integro-differential Boltzmann equation is considered in this article. The model describes the radiation transfer in the scattering medium irradiated by a point source. The inverse problem for the transfer equation is defined. This problem consists of determining the scattering coefficient from the time-angular distribution of the radiation flux density at a given point in space. The Neumann series representation for solving the radiation transfer equation is analyzed in the study of the inverse problem. The zero member of the series describes the unscattered radiation, the first member of the series describes a single-scattered field, the remaining members of the series describe a multiple-scattered field. When calculating the approximate solution of the radiation transfer equation, the single scattering approximation is widespread to calculated an approximate solution of the equation for regions with a small optical thickness and a low level of scattering. An analytical formula is obtained for finding the scattering coefficient by using this approximation for problem with additional restrictions on the initial data. To verify the adequacy of the obtained formula the Monte Carlo weighted method for solving the transfer equation is constructed and software implemented taking into account multiple scattering in the medium and the space-time singularity of the radiation source. As applied to the problems of high-frequency acoustic sensing in the ocean, computational experiments were carried out. The application of the single scattering approximation is justified, at least, at a sensing range of about one hundred meters and the double and triple scattered fields make the main impact on the formula error. For larger regions, the single scattering approximation gives at the best only a qualitative evaluation of the medium structure, sometimes it even does not allow to determine the order of the parameters quantitative characteristics of the interaction of radiation with matter.

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

The numerical methods developed by the author recently for calculating the molecular system based on the direct solution of the Schrodinger equation by the Monte Carlo method have shown a huge uncertainty in the choice of solutions. On the one hand, it turned out to be possible to build many new solutions; on the other hand, the problem of their connection with reality has become sharply aggravated. In ab initio quantum mechanical calculations, the problem of choosing solutions is not so acute after the transition to the classical format of describing a molecular system in terms of potential energy, the method of molecular dynamics, etc. In this paper, we investigate the problem of choosing solutions in the classical format of describing a molecular system without taking into account quantum mechanical prerequisites. As it turned out, the problem of choosing solutions in the classical format of describing a molecular system is reduced to a specific marking of the configuration space in the form of a set of stationary points and reconstruction of the corresponding potential energy function. In this formulation, the solution of the choice problem is reduced to two possible physical and mathematical problems: to find all its stationary points for a given potential energy function (the direct problem of the choice problem), to reconstruct the potential energy function for a given set of stationary points (the inverse problem of the choice problem). In this paper, using a computational experiment, the direct problem of the choice problem is discussed using the example of a description of a monoatomic cluster. The number and shape of the locally equilibrium (saddle) configurations of the binary potential are numerically estimated. An appropriate measure is introduced to distinguish configurations in space. The format of constructing the entire chain of multiparticle contributions to the potential energy function is proposed: binary, threeparticle, etc., multiparticle potential of maximum partiality. An infinite number of locally equilibrium (saddle) configurations for the maximum multiparticle potential is discussed and illustrated. A method of variation of the number of stationary points by combining multiparticle contributions to the potential energy function is proposed. The results of the work listed above are aimed at reducing the huge arbitrariness of the choice of the form of potential that is currently taking place. Reducing the arbitrariness of choice is expressed in the fact that the available knowledge about the set of a very specific set of stationary points is consistent with the corresponding form of the potential energy function.

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

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.

В работе рассматривается метод исследования панельных данных, основанный на использовании агломеративной иерархической кластеризации — группировки объектов на основании сходства и разли- чия их признаков в иерархию вложенных друг в друга кластеров. Применялись 2 альтернативных способа вычисления евклидовых расстояний между объектами — расстояния между усредненными по интервалу наблюдений значениями и расстояния с использованием данных за все рассматриваемые годы. Сравнивались 3 альтернативных метода вычисления расстояний между кластерами. В первом случае таким расстоянием считается расстояние между ближайшими элементами из двух кластеров, во втором — среднее по парам элементов, в третьем — расстояние между наиболее удаленными элементами. Исследована эффективность использования двух индексов качества кластеризации — индекса Данна и Силуэта для выбора оптимального числа кластеров и оценки статистической значимости полученных решений. Способ оценивания статистической достоверности кластерной структуры заключался в сравнении качества кластеризации, на реальной выборке с качеством кластеризаций на искусственно сгенерированных выборках панельных данных с теми же самыми числом объектов, признаков и длиной рядов. Генерация производилась из фиксированного вероятностного распределения. Использовались способы симуляции, имитирующие гауссов белый шум и случайное блуждание. Расчеты с индексом Силуэт показали, что случайное блуждание характеризуется не только ложной регрессией, но и ложной кластеризацией. Кластеризация принималась достоверной для данного числа выделенных кластеров, если значение индекса на реальной выборке оказывалось больше значения 95%-ного квантиля для искусственных данных. В качестве выборки реальных данных использован набор временных рядов показателей, характеризующих производство в российских регионах. Для этих данных только Силуэт показывает достоверную кластеризацию на уровне $p < 0.05$. Расчеты также показали, что значения индексов для реальных данных в целом ближе к значениям для случайных блужданий, чем для белого шума, но имеют значимые отличия и от тех, и от других. Визуально можно выделить скопления близко расположенных друг от друга в трехмерном признаковом пространстве точек, выделяемые также в качестве кластеров применяемым алгоритмом иерархической кластеризации.

The paper considers a method for studying panel data based on the use of agglomerative hierarchical clustering — grouping objects based on the similarities and differences in their features into a hierarchy of clusters nested into each other. We used 2 alternative methods for calculating Euclidean distances between objects — the distance between the values averaged over observation interval, and the distance using data for all considered years. Three alternative methods for calculating the distances between clusters were compared. In the first case, the distance between the nearest elements from two clusters is considered to be distance between these clusters, in the second — the average over pairs of elements, in the third — the distance between the most distant elements. The efficiency of using two clustering quality indices, the Dunn and Silhouette index, was studied to select the optimal number of clusters and evaluate the statistical significance of the obtained solutions. The method of assessing statistical reliability of cluster structure consisted in comparing the quality of clustering on a real sample with the quality of clustering on artificially generated samples of panel data with the same number of objects, features and lengths of time series. Generation was made from a fixed probability distribution. At the same time, simulation methods imitating Gaussian white noise and random walk were used. Calculations with the Silhouette index showed that a random walk is characterized not only by spurious regression, but also by “spurious clustering”. Clustering was considered reliable for a given number of selected clusters if the index value on the real sample turned out to be greater than the value of the 95% quantile for artificial data. A set of time series of indicators characterizing production in the regions of the Russian Federation was used as a sample of real data. For these data only Silhouette shows reliable clustering at the level p < 0.05. Calculations also showed that index values for real data are generally closer to values for random walks than for white noise, but it have significant differences from both. Since three-dimensional feature space is used, the quality of clustering was also evaluated visually. Visually, one can distinguish clusters of points located close to each other, also distinguished as clusters by the applied hierarchical clustering algorithm.

Фотосинтетический аппарат растительной клетки состоит из множества фотосинтетических электронтранспортных цепей (ЭТЦ), каждая из которых участвует в усвоении квантов света, сопряженном с переносом электрона между элементами цепи. Эффективность усвоения квантов света варьирует в зависимости от физиологического состояния растения. Энергия той части квантов, которую не удается усвоить, диссипирует в тепло либо высвечивается в виде флуоресценции. При действии возбуждающего света уровень флуоресценции постепенно растет, доходя до максимума. Кривая роста уровня флуоресценции в ответ на действие возбуждающего света называется кривой индукции флуоресценции (КИФ). КИФ имеет сложную форму, которая претерпевает существенные изменения при различных изменениях состояния фотосинтетического аппарата, что позволяет использовать ее для получения информации о текущем состоянии растения.

В реальном эксперименте, при действии возбуждающего света, мы наблюдаем ответ системы, представляющей собой ансамбль миллионов фотосинтетических ЭТЦ. С целью воспроизведения вероятностной природы процессов в фотосинтетической ЭТЦ разработана кинетическая модель Монте-Карло, в которой для каждой индивидуальной цепи определены вероятности возбуждения молекул светособирающей антенны при попадании кванта света, вероятности захвата энергии либо высвечивания кванта света реакционным центром и вероятности переноса электрона с донора на акцептор в пределах фотосинтетических мультиферментных комплексов в тилакоидной мембране и между этими комплексами и подвижными переносчиками электронов. События, происходящие в каждой из цепей фиксируются, суммируются и формируют кривую индукции флуоресценции и кривые изменения долей различных редокс-состояний переносчиков электрона, входящих в состав фотосинтетической электронтранспортной цепи. В работе описаны принципы построения модели, изучены зависимости кинетики регистрируемых величин от параметров модели, приведены примеры полученных зависимостей, соответствующие экспериментальным данными по регистрации флуоресценции хлорофилла реакционного центра фотосистемы 2 и окислительно-восстановительных превращений фотоактивного пигмента фотосистемы 1 — хлорофилла.

Photosynthetic apparatus of a plant cell consists of multiple photosynthetic electron transport chains (ETC). Each ETC is capable of capturing and utilizing light quanta, that drive electron transport along the chain. Light assimilation efficiency depends on the plant’s current physiological state. The energy of the part of quanta that cannot be utilized, dissipates into heat, or is emitted as fluorescence. Under high light conditions fluorescence levels gradually rise to the maximum level. The curve describing that rise is called fluorescence rise (FR). It has a complex shape and that shape changes depending on the photosynthetic apparatus state. This gives one the opportunity to investigate that state only using the non invasive measuring of the FR.

When measuring fluorescence in experimental conditions, we get a response from millions of photosynthetic units at a time. In order to reproduce the probabilistic nature of the processes in a photosynthetic ETC, we created a Monte Carlo model of this chain. This model describes an ETC as a sequence of electron carriers in a thylakoid membrane, connected with each other. Those carriers have certain probabilities of capturing light photons, transferring excited states, or reducing each other, depending on the current ETC state. The events that take place in each of the model photosynthetic ETCs are registered, accumulated and used to create fluorescence rise and electron carrier redox states accumulation kinetics. This paper describes the model structure, the principles of its operation and the relations between certain model parameters and the resulting kinetic curves shape. Model curves include photosystem II reaction center fluorescence rise and photosystem I reaction center redox state change kinetics under different conditions.