

2018 year, number 1
O.L. Bandman
Institute of Computational Mathematics and Mathematical Geophysics SB RAS, pr. Acad. Lavrentieva 6, Novosibirsk, 630090, Russia
Keywords: дискретное моделирование, стохастический клеточный автомат, стохастичность алгоритма, правила переходов, параллельные вычисления, блочносинхронный режим, пористый материал, дискретная модель просачивания, discrete simulation methods, stochastic cellular automata, stochasticity of the algorithm, transition rules, parallel computing, blocksynchronous mode of functioning, porous material, permeation model
Abstract >>
The parallel implementation peculiarities of a discrete stochastic model that simulates water permeation through a porous substance (soil) with a complex morphology are studied. The simulation should reveal the fluid flowing along pore curves and filling wets and cavities. The discrete stochastic model of the process, proposed earlier, is a stochastic cellular automaton (SCA), whose functioning is represented by a set of elementary local operators acting in a cellular space and imitating displacement (diffusion. convection, adsorption) and transformations (reaction, phase transition) of abstract or real particles. The microlevel of the process representation requires the cellular space of a huge size, and hence, the computations should be implemented on supercomputers. With this, the main problem is in the fact that obtaining an acceptable parallelization efficiency is possible only by inserting some determinism into the computation algorithm, i.e., by decreasing the model stochasticity. Although stochastic models are under intensive investigation, the parallel implementation methods for them are poorly studied. This gap is partially covered by the results of computational experiments, given in this paper, which allow one to assess the advantages and drawbacks of methods for the discrete stochastic mode of water permeation though implementing a porous medium on a multicore cluster.

A. Gasnikov^{1,2}, P. Dvurechensky^{2,3}, M. Zhukovskii^{1,4}, S. Kim^{5}, S. Plaunov^{5}, D. Smirnov^{5}, F. Noskov^{6}
^{1}Moscow Institute of Physics and Technology, 9 Institutskiy per., Dolgoprudny, Moscow Region, Russia 141700 ^{2}Institute for Information Transmission Problems RAS, Bolshoy Karetny per. 19, build.1, Moscow, Russia 127051 ^{3}Weierstrass Institute for Applied Analysis and Stochastics, Mohrenstr. 39, 10117 Berlin, Germany ^{4}OOO «Yandex», Leo Tolstoy st. 16, Moscow, Russia, 119034 ^{5}State Budget Educational Institution Physics and Mathematical School 2007, 91 Gorchakova str., Moscow, Russia 117042 ^{6}National Research University Higher School of Economics, 20 Myasnitskaya str., Moscow 101000
Keywords: марковская цепь, эргодическая теорема, мультиномиальное распределение, концентрация меры, оценка максимального правдоподобия, Google problem, градиентный спуск, автоматическое дифференцирование, степенной закон распределения, Markov chain, ergodic theorem, multinomial distribution, measure concentration, maximum likelihood estimate, Google problem, gradient descent, automatic differentiation, power law distribution
Abstract >>
In the second part of this paper, we consider the BuckleyOsthus model for the formation of a webgraph. For the networks generated according to this model, we numerically calculate the PageRank vector. We show that the components of this vector are distributed according to the power law. We also discuss the computational aspects of this model with respect to different numerical methods for the calculation of the PageRank vector, presented in the first part of the paper. Finally, we describe a general model for the webpage ranking and some approaches to solve the optimization problem arising when learning this model.

P.E. Dvurechensky^{1,2}, A.V. Gasnikov^{2,3}, A.A. Lagunovskaya^{3}
^{1}Weierstrass Institute for Applied Analysis and Stochastics, Mohrenstr. 39, 10117 Berlin, Germany ^{2}Institute for Information Transmission Problems RAS, Bolshoy Karetny per. 19, build.1, Moscow, Russia 127051 ^{3}Moscow Institute of Physics and Technology, 9 Institutskiy per., Dolgoprudny, Moscow Region, Russia 141700
Keywords: стохастическая выпуклая оптимизация, оценки вероятностей больших уклонений, метод зеркального спуска, параллельные алгоритмы, stochastic convex optimization, probability of large deviation, mirror descent, parallel algorithm
Abstract >>
In this paper, convex stochastic optimization problems under different assumptions on the properties of the available stochastic subgradients are considered. It is known that if a value of the objective function is available, one can obtain, in parallel, several independent approximate solutions in terms of the objective residual expectation. Then, choosing a solution with the minimum function value, one can control the probability of large deviations of the objective residual. On the contrary, in this short paper we address the situation when the objective function value is unavailable or is too expensive to calculate. Under the «lighttail» assumption for stochastic subgradients and in the general case with a moderate probability of large deviations, it is shown that parallelization combined with averaging gives bounds for the probability of large deviations similar to those of a serial method. Thus, in these cases one can benefit from parallel computations and reduce the computational time without any loss in the solution quality.

S.I. Kabanikhin^{1,2,3}, M.A. Shishlenin^{1,2,3}
^{1}Institute of Computational Mathematics and Mathematical Geophysics SB RAS, pr. Acad. Lavrentieva 6, Novosibirsk, 630090, Russia ^{2}Sobolev Institute of Mathematics SB RAS, 4 Acad. Koptyug avenue, Novosibirsk, Russia, 630090 ^{3}Novosibirsk State University, Pirogova st., 2, Novosibirsk, 630090, Russia
Keywords: параболическое уравнение, коэффициентная обратная задача, численные методы, нелокальное условие, parabolic equation, timedependent coefficient inverse problem, numerical methods, nonlocal condition
Abstract >>
The inverse problem of recovering the leading timedependent coefficient by the known nonlocal additional information is investigated. For an approximate solution of the nonlinear inverse problems we propose the gradient method of minimizing the target functional. The comparative analysis with the method based on the linearized approximation scheme with respect to time is made. The results of the numerical calculations are presented.

R.K. Mohanty^{1}, D. Kaur^{2}
^{1}South Asian University, Akbar Bhawan, Chanakyapuri, New Delhi 110021, India ^{2}University of Delhi, Delhi 110007, India
Keywords: нестационарная квазилинейная бигармоническая задача, внешаговая дискретизация, уравнение КурамотоСивашинского, расширенное уравнение ФишераКолмогорова, блочная трехдиагональная матричная структура, неоднородная сетка, unsteady biharmonic problem, offstep discretization, KuramotoSivashinsky equation, extended FisherKolmogorov equation, block tridiagonal matrix structure, nonuniform mesh
Abstract >>
The present paper uses a new two level implicit difference formula for the numerical study of one dimensional unsteady biharmonic equation with appropriate initial and boundary conditions. The proposed difference scheme is second order accurate in time and third order accurate in space on a nonuniform grid and in case of a uniform mesh, it is of order two in time and four in space. The approximate solutions are computed without using any transformation and linearization. The simplicity of the proposed scheme lies in its three point spatial discretization which yields a block tridiagonal matrix structure without the use of any fictitious nodes for handling the boundary conditions. The proposed scheme is directly applicable to singular problems, which is the main utility of our work. The method is shown to be unconditionally stable for a model linear problem for a uniform mesh. The efficacy of the proposed approach has been tested on several physical problems, including complex fourthorder nonlinear equations like the KuramotoSivashinsky equation and the extended FisherKolmogorov equation, where comparison is made with some earlier work. It is clear from the numerical experiments that the obtained results are not only in good agreement with the exact solutions but also competitive with the solutions derived in earlier research studies.

V.I. Paasonen^{1,2}
^{1}Institute of computational technologies SB RAS, pr. Lavrenteva, 6, 630090, Novosibirsk, Russia ^{2}Novosibirsk State University, Pirogova st., 2, Novosibirsk, 630090, Russia
Keywords: неравномерная сетка, адаптивная сетка, косой шаблон, подвижная сетка, компактная схема, nonuniform grid, adaptive grid, oblique stencil, moving grid, compact scheme
Abstract >>
In this paper, we study various difference schemes on oblique stencils, i.e., the schemes using different space grids on different time levels. Such schemes can be useful when solving boundary value problems with moving boundaries and when using the regular grids of a nonstandard structure (for example, triangular or cellular) and, also, when applying the adaptive methods. To study the stability, we use the analysis of First Differential Approximation of finite difference schemes and the dispersion analysis. We study the meaning of the stability conditions as constraints on the geometric location of stencil elements with respect to the characteristics of the equation. In addition, we compare our results with the geometric interpretation of the stability of classical schemes. The paper also presents the generalization of oblique schemes in the case of the quasilinear equation of transport and numerical experiments for these schemes.

A.V. Penenko
Institute of Computational Mathematics and Mathematical Geophysics SB RAS, pr. Acad. Lavrentieva 6, Novosibirsk, 630090, Russia
Keywords: обратная задача идентификации источников, метод НьютонаКанторовича, градиентный алгоритм, сопряженные уравнения, оператор чувствительности, согласованные численные схемы, inverse source problem, NewtonKantorovich method, gradienttype algorithm, adjoint equations, sensitivity operator, consistent numerical schemes
Abstract >>
The algorithms of solving the inverse source problem for systems of the productiondestruction equations are considered. Consistent in the sense of the Lagrangian identity numerical schemes for solving direct and conjugate problems have been built. With the adjoint equations, the sensitivity operator and its discrete analogue have been constructed. It links the measured values perturbations with the perturbations of the model parameters. This operator transforms the inverse problem to a quasilinear form and allows applying the NewtonKantorovich methods to it. The paper provides a numerical comparison of the gradient algorithms based on the consistent and inconsistent numerical schemes and the NewtonKantorovich algorithm applied to solving the inverse source problem for the nonlinear Lorenz model.

S.V. Solodusha
L.A. Melentiev Energy Systems Institute, Siberian Branch of the Russian Academy of Sciences, Lermontova st., 130, Irkutsk, 664033
Keywords: системы полиномиальных интегральных уравнений Вольтерра I рода, численное решение, метод НьютонаКанторовича, systems of the polynomial Volterra equations of the first kind, numerical solution, NewtonKantorovich method
Abstract >>
In this paper, we consider a class of second order systems of the Volterra nonlinear integral equations. This class is related to the automatic control problem of a dynamic object with vector inputs and outputs. A numerical solution technique based on the NewtonKantorovich method is considered. To verify the efficiency of the algorithms developed, a series of test calculations were carried out.

