Siberian Journal of Numerical Mathematics

Volume 14, 2011

Contents

Number 1, pp. 1-118
Number 2, pp. 119-230
Number 3, pp. 231-332
Number 4, pp. 333-456


Number 1, pp. 1-118

 

Congratulation on the anniversary of Anatoly Nikolaevich Konovalov (in Russian), pp. 1-4

Artemiev S.S., Korneev V.D.

Numerical solution to stochastic differential equations on supercomputers (in Russian), pp. 5-17

 

    This paper deals with some issues of the dependence of the accuracy of algorithms for the numerical solutions of stochastic differential equations (SDEs) on the size of an ensemble of simulated trajectories. The problems of accuracy arise due to the necessity of estimating functionals of SDEs-solutions with an increasing dispersion, a strong asymmetry of solutions distributions, indeterminacy of the time of arrival of trajectories of solutions at the boundaries of given domains. The ways of parallelization of statistical algorithms on a multi-processor cluster are described. The results of numerical experiments obtained on the supercomputer of Siberian Supercomputer Center are presented. 

Key words: stochastic differential equations, stochastic equations, parallelization, supercomputer, cluster.

 

Bondarev E.A., Rozhin I.I., and Argunova K.K.

The influence of non-isothermal effects on gas production in the Northern regions (in Russian), pp. 19-28

 

    In the computational experiment the influence of mathematical model parameters on the dynamics of pressure and temperature fields at non-isothermal gas filtration is investigated. To describe the process, the authors use a nonlinear system of partial differential equations, obtained from the energy and mass conservation laws and the Darcy law, and physical and caloric equations as closing relations. The boundary conditions correspond to a given pressure drop at a bottom-hole. It has been shown that the influence of the temperature field on such integral characteristics as cumulative gas production is most pronounced at moderate pressure drops. An example which shows that a zone of possible hydrate formation in a gas reservoir is of a very small dimension is given. 

Key words: mathematical modeling, non-isothermal filtration, imperfect gas, gas hydrate, finite-difference methods.

 

Derevtsov E.Yu., Pickalov V.V.

Reconstruction of vector fields and their singularities by ray transforms (in Russian), pp.  29-46

 

       In this paper, numerical methods for reconstruction of a singular support of a vector field by its known longitudinal and (or) transverse ray transforms are proposed. Apart from a modification for the Vainberg operator we also use the integral operators of angular moments and back projections as well as differential operators of the tensor analysis for solving the problem. The results of numerical simulation for reconstruction of discontinuous and with discontinuities in derivatives vector fields as well as for visualization of their singular support are presented. 

Key words: vector field, ray transform, angular moment, back projection, inversion formulas, singular support, visualization.

 

Kalgin K.V.

Implementation of algorithms with a fine-grained parallelism on GPUs (in Russian), pp. 59-70 

 

    The efficiency of implementations of algorithms with a fine-grained parallelism on GPUs that support the CUDA architecture is studied. For testing, cellular automata and differential schemes are used. We offer several versions of implementations and analyze their productivity. An example of the GPU application for modeling the process of carbon dioxide oxidation on the catalyst surface is given. 

Key words: graphical processing unit, GPGPU, CUDA, cellular automata, fine-grained algorithms, parallel implementation.

 

Korobeynikov S.N., Reverdatto V.V., Polyansky O.P., Sverdlova V.G., and Babichev A.V.

The influence of the choice of a rheological law on the computer simulation results of slab subduction (in Russian), pp. 71-90

 

    The influence of the choice of the type of the yield surface for elastoplastic materials and material constants for the plate and the mantle on the scenario of mathematical modeling of the plates collision is investigated. Computer simulation is performed by the FEM numerical solution of nonlinear equations for deformable solid mechanics using MSC.Marc 2005 code. The simulation results essentially depend on the choice of material constants for the plate and the mantle, as well as on the type of the yield surface for the elastoplastic material of a subducting plate. The presented numerical simulations have demonstrated that the primary driving mechanism of subduction can be a geometrical inhomogeneity of the subduction plate near to a zone of plates collision, by providing a simultaneous consideration of the consolidation of a plate material as this plate descends into the mantle.

Key words: tectonic processes, subduction, computer simulation, elastoplastic material.

 

Prigarin S.M., Hahn K., and Winkler G.

Estimation of fractal dimension of random fields on the basis of variance analysis of increments (in Russian), pp. 91-102

 

    This paper deals with estimating the fractal dimension of realizations of random fields. The numerical methods in use are based on analysis of the variance of increments. To study the fractal properties, we propose the use of a specific characteristic of random fields called “variational dimension”. For a class of Gaussian fields with homogeneous increments, the variational dimension converges to the Hausdorff dimension. Several examples are presented to illustrate that the concept of variational dimension can be used to construct effective computational methods.

Key words: computation of dimension, random fields, Hausdorff dimension, fractal analysis, variational dimension.

 

Ukhinov S.A., Chimaeva A.S.

Substantiation of convergence of Monte Carlo algorithms for reconstructing a scattering phase function with allowance for polarization (in Russian), pp. 103-116 

    A problem of determination of an atmospheric scattering phase function from the ground-based solar almucantar sky brightness observations is considered. The new iterative algorithm for solving this problem was developed as combination of existing additive and multiplicative methods of refining a single-scattering contribution to the observed brightness with allowance for the scattered radiation polarization in the atmosphere. Also, some modifications of these methods were proposed. The objective of this paper is the numerical substantiation of convergence of these methods. For this purpose, the algorithm for the Jacobi matrix for the transfer statements of the considered methods was developed, and calculations were carried out for different parameters of the atmosphere.

Key words: Monte Carlo methods, reconstructing a scattering phase function, polarization of radiation, substantiation of convergence.

 

Zadorin A.I., Tikhovskaya S.V. 

Analysis of a difference scheme for a singularly perturbed Cauchy problem on a refined mesh (in Russian), pp. 47-57

 

    The Cauchy problem for a singularly perturbed second order ordinary differential equation is considered. The uniform convergence of the upwind difference scheme on the Shishkin mesh is proved. Note, that an application of such a mesh is well known only in the case of a boundary value problem. The results of numerical experiments are discussed.

Key words: second order ordinary differential equation, singular perturbation, Cauchy problem, difference scheme, maximum principle, Shishkin mesh, uniform convergence.

 

 


Number 2, pp. 119-230

 

Amelkin V.A.

Enumerative problems solution for single-transition serial sequences with an adjacent series heights increment bounded from above (in Russian), pp. 119-130

 

    In this paper, sets of n-valued finite serial sequences are investigated. The sequences consist of two serial subsequences as follows. A sequence begins with an increasing subsequence and ends with a decreasing subsequence or vice versa. The structure of such sequences is determined by restrictions on the number of series, the series lengths, and the series heights.

     For sets of sequences, whose difference between heights of the adjacent series does not exceed a certain given value, the algorithms that assign smaller numbers to lexicographically lower sequences and smaller numbers to lexicographically higher sequences have been developed.

Key words: series, series length, series height, constraints.

 

Voytishek A.V., Khmel D.S.

Analytical description for application of 1D Kohonen scheme for constructing adaptive meshes (in Russian), pp. 131-140

 

    In this paper, the analysis of analytical approaches to investigation of an asymptotical disposition for a special iterative discrete-stochastic algorithm for constructing adaptive meshes using the Kohonen self-organizing maps is made. For a simplified one-dimensional case, a «recurrent» approach to obtaining mean most probable dispositions of grid nodes for a small number of iterations has been developed. This approach allows one to conduct interesting analytical investigations and numerical testing for the algorithm considered.

Key words: Kohonen self-organizing maps, adaptive meshes, discretely-stochastic algorithm, simplified 1D case, recurrent formulas for mean most probable dispositions of grid nodes.

 

Gusev S.A.

Minimizing the variance of estimate of mathematical expectation of a diffusion process functional by parametric transformation of the p

arabolic boundary value problem (in Russian), pp. 141-153

 

    This paper is associated with finding the ways of reducing the variance of the estimate of mathematical expectation of the functional of a diffusion process moving in a domain with an absorbing boundary. The estimate of mathematical expectation of the functional is obtained using a numerical solution of stochastic differential equations (SDE's) by the Euler method. A formula of the limiting variance at decreasing the integration step in the Euler method is obtained. A method of reducing the variance value of the estimate based on transformation of the parabolic boundary value problem corresponding to the diffusion process is proposed. Some numerical results are presented.

Key words: diffusion process, stochastic differential equations, absorbing boundary, variance of an estimate of the functional, Euler method.

 

Lisitsa V.V., Vishnevsky D.M.

On peculiarities of the Lebedev scheme for simulation of elastic wave propagation in anisotropic media (in Russian), pp. 155-167

  

    This paper presents the Lebedev scheme on staggered grids for the numerical simulation of wave propagation in anisotropic elastic media. Main attention is being given to the approximation of the elastic wave equation by the Lebedev scheme. Based on the differential approach, it is shown that the scheme approximates a system of equations which differs from the original equation. It is proved that the approximated system has a set of 24 characteristics, six of them coincide with those of the elastic wave equation and the rest ones are «artifacts». Requiring the artificial solutions to be equal to zero and the true ones to coincide with those of the elastic wave equation, one comes to the classical definition of the approximation of a problem on a sufficiently smooth solution. The derived results are of importance for the construction of reflectionless boundary conditions, development of a heterogeneous Lebedev scheme, approximation of point sources, etc.

Key words: finite difference schemes, differential approach, elastic wave equation, anisotropy.

 

Moskalensky E.D.

Formulas for setting a location of the wavefront propagating in a medium with power dependence of velocity on a coordinate (in Russian), pp. 169-178

 

    In this paper, the 2D eikonal equation fx2 + fy2 = (ky)2α is considered. If f is its solution, the relation f(x,y) = C sets the wavefront location. However, obtaining solutions is associated with some difficulties. In this paper, the author develops the earlier proposed technique that enables the detection of a parametric curve to set the wavefront without solving the above equation.

Key words: wave propagation, eikonal equation.

 

Palymskiy I.B.

On simulation of complex regimes of the Rayleigh-Benard convection (in Russian), pp. 179-204

 

    The 2D and 3D turbulent convectional flows of viscous and incompressible fluids in a rectangular parallelepiped are numerically simulated when heating from below. The horizontal boundaries are stress-free for the 3D case, and stress-free or rigid for the 2D simulation. It is shown that in spite of the quantitative discrepancy between the results of the 3D simulation and the experiment, the 3D simulation shows the correct power laws for temperature and vertical velocity pulsations versus supercriticality. In the 2D simulation, a similar correspondence is observed at a relatively low supercriticality (approximately up to 250). At a high superriticality, in the 2D convection, the existence of a large-scale structure is dominating, as it determines the property of a flow.

Key words: simulation, hydrodynamics, convection, heat transfer, turbulence.

 

Sorokin S.B.

Preconditioning in the numerical solution of Dirichlet problem for the biharmonic equation (in Russian), pp. 205-213

 

    The iterative algorithm for the numerical solution of the biharmonic equation with the first kind boundary conditions (a clamped plate) is investigated. At every step of this iterative method it is necessary to solve two Dirichlet problems for Poisson's equation. Constants of energy equivalence for the optimization of the iterative method have been obtained.

Key words: biharmonic equation, boundary conditions, iterative method, Poisson's equation, clamped plate, free edge.

 

Scherbakov A.V., Malakhova V.V.

The influence of the time step size on results of numerical modeling of the global ocean climate (in Russian), pp. 215-230

 

    In this paper, based on the numerical large-scale geostrophic ocean thermohaline circulation model, the influence of a numerical time step for modeling the large-scale temperature and salinity fields with the use of an implicit time integration method is investigated. It is shown that for a more adequate description of processes of a deep vertical convection and modeling a more realistic ocean thermohaline circulation, it is necessary to apply time steps no more than 10 days. At such time steps, the influence of numerical viscosity (diffusion) is insignificant.

Key words: global ocean thermohaline circulation, implicit numerical model, numerical viscosity, equilibrium solutions, convection parametrization.

 


Number 3, pp. 231-332

 

Evstigneev V.A., Tursunbay kyzy Y.

On graph coloring in a class of parallel local algorithms (in Russian), pp. 231-243

 

   One of the ways for improving the performance of a distributed algorithm is representation of the coloring strategy into the algorithm which, as known, is efficient in non-distributed algorithms. In this paper we show that application of a certain sequential coloring algorithm heuristics such as the largest-first (SL), the smallest-last (SL) and the saturation largest-first (SLF) for some classes of graphs and for special cases of the vertex coloring in the distributed algorithms give us optimal or near-optimal coloring.

Key words: graph coloring, local algorithm, distributed algorithm, greedy algorithm, w-perfect graph, T-coloring, sum coloring.

 

Kulikov G.Yu., Kuznetsov E.B., Khrustaleva E.Yu.

On the global error control in nested implicit Runge-Kutta methods of Gauss type (in Russian), pp. 245-259

 

   The automatic global error control based on a combined step size and order control presented by Kulikov and Khrustaleva in 2008 is investigated. A special attention is given to the efficiency of computation because the implicit extrapolation based on the multi-stage implicit Runge-Kutta schemes might be expensive. Especially, we discuss the technique of global error estimation and control in order to compute the numerical solution satisfying the user-supplied accuracy conditions (in exact arithmetic) in the automatic mode. The theoretical results of this paper are confirmed by numerical experiments on test problems.

Key words: implicit Runge-Kutta formulas, effective implementation, nested implicit schemes of Gauss type, global error estimation and control.

 

Lu Z.

A posteriori error estimates of finite element methods for nonlinear quadratic boundary optimal control problem (in Russian), pp. 261-276

 

   This paper is aimed at studying finite element discretization for a class of quadratic boundary optimal control problems governed by nonlinear elliptic equations. We derive a posteriori error estimates for the coupled state and control approximation. Such estimates can be used to construct a reliable adaptive finite element approximation for the boundary optimal control problem. Finally, we present a numerical example to confirm our theoretical results.

Key words: nonlinear boundary optimal control problem, finite element methods, a posteriori error estimates.

 

Nurminski E.A., Bury A.A.

The Parker-Sochacki method for solving systems of ordinary differential equations using graphics processors (in Russian), pp. 277-289

 

   In this paper we describe the Parker-Sochacki method, which is used for solving systems of ordinary differential equations and the implementation of this method on the graphics processors. As a test, we consider the solution of the classical N bodies problem. The algorithm makes possible to effectively use massive parallel graphics processors, and provides an acceptable accuracy at a multiple time reduction as compared to the processors of a conventional architecture.

Key words: numerical integration of ODE systems, parallel computing.

 

Potapov D.K.

A continuous approximation for a 1D analogue of the Gol'dshtik model for separated flows of incompressible fluid (in Russian), pp. 291-296

 

   A modification of a 1D analogue of the Gol'dshtik mathematical model for separated flows of incompressible fluid is considered. The model is a nonlinear differential equation with a boundary condition. Nonlinearity in the equation is continuous and depends on a small parameter. When this parameter tends to zero, we have a discontinuous nonlinearity. The results of the solutions are in accord with the results obtained for the 1D analogue of the Gol'dshtik model for separated flows of incompressible fluid.

Key words: mathematical model, separated flows, nonlinear differential equation, discontinuous nonlinearity, continuous approximation.

 

Rafiullah M.

A fifth order iterative method for solving nonlinear equations (in Russian), pp. 297-302

 

   The object of this paper is to construct a new efficient iterative method for solving nonlinear equations. This method is mainly based on M. Javidi's paper [1] by using a new scheme of a modified homotopy perturbation method. This new method is of the fifth order of convergence, and it is compared with the second, third, fifth, and sixth order methods. Some numerical test problems are given to show the accuracy and fast convergence of the method proposed.

Key words: homotopy perturbation method, nonlinear equations, iterative methods, convergence analysis, root finding techniques.

 

Smirnov S.V.

On the internal Kelvin waves in a two-layer liquid model (in Russian), pp. 303-317

 

   The sub-inertial internal Kelvin wave solutions of a linearized system of the ocean dynamics equations for a semi-infinite two-layer f-plane model basin of a constant depth bordering a straight, vertical coast are described. A rigid lid surface condition and no-slip wall boundary condition are considered. The trapped wave equations are presented. Approximate solutions using the asymptotic method are constructed. In the absence of bottom friction, the solution consists of a frictionally modified Kelvin wave and a vertical viscous boundary layer. On the no-slip bottom boundary condition, the solution consists of a modified Kelvin wave, two vertical viscous boundary layers and a large cross-section scale component. Numerical solutions for the Kelvin waves are considered at such values of modelling parameters, when it is necessary to simultaneously take account of lateral viscosity, bottom stress and the friction between layers.

Key words: ocean dynamics, trapped waves, Kelvin wave.

 

Urev M.V.

Convergence of a discrete scheme in a regularization method for the quasi-stationary Maxwell system in a non-homogeneous conducting medium (in Russian), pp. 319-332

 

   Convergence of a discrete solution to the solution of a regularized system of the Maxwell equations written in terms of a vector magnetic potential with a special calibration of the medium conductance is considered. The problem is discretized by the Nedelec vector finite element method in space and by the implicit Euler scheme in time. An optimal theoretical energy estimate of the approximate solution error in the 3D Lipschitz polyhedral domains is obtained.

Key words: quasi-stationary Maxwell equations, finite element method, discontinuous coefficients, error estimates.


Number 4, pp. 333-456

 

Chen H., Lin Q., Shaidurov V.V., Zhou J. 

Error estimates for triangular and tetrahedral finite elements in combination with a trajectory approximation of the first derivatives for advection-diffusion equations  (in Russian), pp. 425-442

 

     In this paper, a modified method of characteristics in combination with integral identities of triangular and tetrahedral linear elements is used to prove a uniform optimal-order error estimate which depends only on the initial data and right-hand side, but not on a scaling parameter ɛ, for multi-dimensional time-dependent advection-diffusion equations.

Key words: modified method of characteristics, triangular linear element, tetrahedral linear element, integral identities, uniform error estimate.

 

Chistyakov V.F. 

Preservation of stability type of difference schemes when solving stiff differential algebraic equations  (in Russian), pp. 443-456

 

     Implicit methods applied to the numerical solution of systems of ordinary differential equations (ODEs) with an identically singular matrix multiplying the derivative of the sought-for vector-function are considered. The effects produced by losing L-stability of a classical implicit Euler scheme when solving such stiff systems are discussed.

Key words: differential algebraic equations, index, solution space, implicit Euler scheme.

 

Dmitriev M.N., Lisitsa V.V.

Application of M-PML absorbing boundary conditions to the numerical simulation of wave propagation in anisotropic media. Part I: reflectivity  (in Russian), pp. 333-344

 

     This paper presents a detailed study of the construction of reflectionless boundary conditions for anisotropic elastic problems. A Multiaxial Perfectly Matched Layer (M-PML) approach is considered. With a proper stabilization parameter, the M-PML ensures solution stability for arbitrary anisotropic media. It is proved that this M-PML modification is not perfectly matched, and the reflectivity the M-PML exceeds that of the standard PML. Moreover, the reflection coefficient linearly depends on the stabilization parameter. A problem of constructing an optimal stabilization parameter is formulated as follows: find a minimal possible parameter that ensures stability. This problem is considered in a second paper on this work.

Key words: anisotropy, reflectionless boundary conditions, perfectly matched layer, elastic wave equations.

 

Fortin D., Tseveendorj I.

Piecewise convex formulations of binary and permutation problems  (in Russian), pp. 409-423

 

     It is well-known that the problem of maximization of any difference of convex functions can be turned into a convex maximization problem; here the aim is a piecewise convex maximization problem instead. Although this may seem harder, sometimes the dimension may be reduced by 1, and the local search may be improved by using extreme points of the closure of the convex hull of better points. We show that it is always the case for both binary and permutation problems and give, as such instances, piecewise convex formulations for the maximum clique problem and the quadratic assignment problem.

Key words: piecewise convex, maximum clique, QAP, DC.

 

Kamont Z., Kropielnicka K.

A general theory of implicit difference schemes for nonlinear functional differential equations with initial boundary conditions is presented  (in Russian), pp. 361-379

 

       A theorem on error estimates of approximate solutions for implicit functional difference equations of the Volterra type with an unknown function of several variables is given. This general result is employed to investigate the stability of implicit difference schemes generated by first-order partial differential functional equations and by parabolic problems. A comparison technique with nonlinear estimates of the Perron type for given functions with respect to the functional variable is used.

Key words: functional differential equations, implicit difference methods, stability and convergence.

 

Lazarev N.P.

An iterative penalty method for a nonlinear problem of equilibrium of a Timoshenko-type plate with a crack  (in Russian), pp. 381-392

 

     A variational problem of equilibrium of an elastic Timoshenko-type plate in a domain with a slit is considered. A nonpenetration boundary condition in the form of an inequality is specified on the edges of the slit. A penalized equation and an iterative linear equation in integral and differential forms are constructed. Some results on solution convergence and an error estimate are obtained.

Key words: crack, Timoshenko-type plate, penalty operator, energy functional, variational problem.

 

Maksimova (Kushniruk) N.N., Namm R.V. 

Iterative proximal regularization of a modified Lagrangian functional for solving a semicoercive model problem with friction  (in Russian), pp. 393-408

 

      A problem of unconstrained minimization of a semicoercive nondifferentiable functional corresponding to a model friction problem is reduced to a problem of constrained minimization of a differentiable functional. An algorithm based on an iterative proximal regularization of a modified Lagrangian functional is used for solving the problem thus obtained. Convergence of a finite element solution is investigated. The results of numerical calculation are presented.

Key words: semicoercive friction problem, modified Lagrangian functional, saddle point, Udzava method, iterative proximal regularization, finite element method.

 

Zhelezovskii S.E. 

Stability of a three-layer operator-difference scheme for coupled thermoelasticity problems  (in Russian), pp. 345-360

 

     Stability of a three-layer operator-difference scheme with weights that generalizes a class of difference and projection-difference schemes for linear coupled thermoelasticity problems is analyzed. Energy estimates for the solution and its first-order grid derivative are obtained.

Key words: operator-difference scheme, stability, coupled thermoelasticity problems.