Publishing House SB RAS:

Publishing House SB RAS:

Address of the Publishing House SB RAS:
Morskoy pr. 2, 630090 Novosibirsk, Russia

Log In   /  Register

Advanced Search

2018 year, number 1

A discrete stochastic model of water permeation through a porous substance: parallel implementation peculiarities

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, block-synchronous 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.

About the power law of the PageRank vector distribution. Part 2. Backley-Osthus model, power law verification for this model and setup of real search engines

A. Gasnikov1,2, P. Dvurechensky2,3, M. Zhukovskii1,4, S. Kim5, S. Plaunov5, D. Smirnov5, F. Noskov6
1Moscow Institute of Physics and Technology, 9 Institutskiy per., Dolgoprudny, Moscow Region, Russia 141700
2Institute for Information Transmission Problems RAS, Bolshoy Karetny per. 19, build.1, Moscow, Russia 127051
3Weierstrass Institute for Applied Analysis and Stochastics, Mohrenstr. 39, 10117 Berlin, Germany
4OOO «Yandex», Leo Tolstoy st. 16, Moscow, Russia, 119034
5State Budget Educational Institution Physics and Mathematical School 2007, 9-1 Gorchakova str., Moscow, Russia 117042
6National 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 Buckley-Osthus model for the formation of a web-graph. 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 web-page ranking and some approaches to solve the optimization problem arising when learning this model.

Parallel algorithms and probability of large deviation for stochastic convex optimization problems

P.E. Dvurechensky1,2, A.V. Gasnikov2,3, A.A. Lagunovskaya3
1Weierstrass Institute for Applied Analysis and Stochastics, Mohrenstr. 39, 10117 Berlin, Germany
2Institute for Information Transmission Problems RAS, Bolshoy Karetny per. 19, build.1, Moscow, Russia 127051
3Moscow 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 «light-tail» 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.

Recovery of the time-dependent diffusion coefficient by known non-local data

S.I. Kabanikhin1,2,3, M.A. Shishlenin1,2,3
1Institute of Computational Mathematics and Mathematical Geophysics SB RAS, pr. Acad. Lavrentieva 6, Novosibirsk, 630090, Russia
2Sobolev Institute of Mathematics SB RAS, 4 Acad. Koptyug avenue, Novosibirsk, Russia, 630090
3Novosibirsk State University, Pirogova st., 2, Novosibirsk, 630090, Russia
Keywords: параболическое уравнение, коэффициентная обратная задача, численные методы, нелокальное условие, parabolic equation, time-dependent coefficient inverse problem, numerical methods, nonlocal condition

Abstract >>
The inverse problem of recovering the leading time-dependent coefficient by the known non-local 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.

Compact difference scheme with high accuracy for one dimensional unsteady quasi-linear biharmonic problem of second kind: Application to physical problems

R.K. Mohanty1, D. Kaur2
1South Asian University, Akbar Bhawan, Chanakyapuri, New Delhi 110021, India
2University of Delhi, Delhi 110007, India
Keywords: нестационарная квазилинейная бигармоническая задача, внешаговая дискретизация, уравнение Курамото-Сивашинского, расширенное уравнение Фишера-Колмогорова, блочная трехдиагональная матричная структура, неоднородная сетка, unsteady biharmonic problem, off-step discretization, Kuramoto-Sivashinsky equation, extended Fisher-Kolmogorov equation, block tri-diagonal matrix structure, non-uniform 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 non-uniform 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 tri-diagonal 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 fourth-order nonlinear equations like the Kuramoto-Sivashinsky equation and the extended Fisher-Kolmogorov 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.

The properties of difference schemes on oblique stencils for the hyperbolic equations

V.I. Paasonen1,2
1Institute of computational technologies SB RAS, pr. Lavrenteva, 6, 630090, Novosibirsk, Russia
2Novosibirsk State University, Pirogova st., 2, Novosibirsk, 630090, Russia
Keywords: неравномерная сетка, адаптивная сетка, косой шаблон, подвижная сетка, компактная схема, non-uniform 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 non-standard 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 quasi-linear equation of transport and numerical experiments for these schemes.

Consistent numerical schemes for solving nonlinear inverse source problems with the gradient-type algorithms and the Newton-Kantorovich methods

A.V. Penenko
Institute of Computational Mathematics and Mathematical Geophysics SB RAS, pr. Acad. Lavrentieva 6, Novosibirsk, 630090, Russia
Keywords: обратная задача идентификации источников, метод Ньютона-Канторовича, градиентный алгоритм, сопряженные уравнения, оператор чувствительности, согласованные численные схемы, inverse source problem, Newton-Kantorovich method, gradient-type algorithm, adjoint equations, sensitivity operator, consistent numerical schemes

Abstract >>
The algorithms of solving the inverse source problem for systems of the production-destruction 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 Newton-Kantorovich methods to it. The paper provides a numerical comparison of the gradient algorithms based on the consistent and inconsistent numerical schemes and the Newton-Kantorovich algorithm applied to solving the inverse source problem for the nonlinear Lorenz model.

To the numerical solution of one class of systems of the Volterra polynomial equations of the first kind

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, Newton-Kantorovich 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 Newton-Kantorovich method is considered. To verify the efficiency of the algorithms developed, a series of test calculations were carried out.