Partitioning a segment with optional thickening toward ends

Preface:

The initial line segment is partitioned with “obligatory” points (they should be mesh nodes), which can both be or not be points of thickening. On each part of the segment the method of subpartitioning, described below, can be applied.

Let  – be the minimum acceptable step,  – be the maximum acceptable step and let  be the length of the segment, where . Then the minimal possible number of steps equals – , and the maximal possible is – . If , then the problem statement is incorrect. Assume that .

If both edges of the segment do not require thickening, we can take a uniform partition with any number of steps   so that .

Continue reading

Fast volume computing algorithm of arbitrary polyhedron in 3D space

Introduction

Computing of the volume of polyhedron in 3D space isn’t a trivial problem, but the following trivial method exists: dividing the volume into simple pyramids and counting the sum of these volumes. However, this methodology is difficult for implementation, as well as it is resource-intensive and slow. What is more, computing algorithm according to this methodology is difficult to parallelize. And taking into account trends in the field of parallel computing on GPU development, the ability to increase the rate of computing repeatedly is being lost.

In this article the algorithm for determining the volume of arbitrary geometry in 3D space in terms of fast computing is described.

Input data

Preparatory step. A rectangular grid (pos.1 on fig.1) around geometry (pos.2 on fig.1) is built using its minimum and maximum coordinates.

Continue reading

Alternate directions implicit scheme for a non-linear heat equation

This third Note is dedicated to the discussion of application of the 3D Douglas – Rachford ADI scheme to the solution of a non-linear heat equation. We will discuss the Newton – Raphson method and the “method of frozen coefficients”.

Before starting discussion of how to approach solution of a non-linear equation, let us define what will be called a non-linear heat equation.
Below, we will consider a heat equation with temperature dependent thermal conductivity and heat capacity. Thus, the coefficients of the heat equation appear to be temperature dependent:

, (1)
Continue reading

Alternate directions implicit scheme and the intermediate boundary conditions. Third type boundary conditions.

This second Note is dedicated to the discussion of the case of 3-rd type boundary conditions posed on the edges of the modeling region and will present an outline of the algorithm for the account of both the Dirichlet and 3-rd type boundary conditions on different edges.

Before passing to the discussion of that scheme, a few words should be said about another ADI scheme – namely 2D Peaceman – Rachford finite difference scheme. The correct account of the intermediate boundary conditions for both Dirichlet and 3-rd order types has been thoroughly discussed in [1]. One essential difference between the 3D Douglas – Rachford and 2D Peaceman – Rachford schemes is that in the latter scheme the spatial coordinates enter symmetrically, such that the second equation (in 2D Peaceman – Rachford) contains finite difference representations of both spatial derivatives. This fact leads to a cumbersome infer of relation between the values of the unknown function on different edges – for details see [1].

Surprisingly, although the Douglas – Rachford scheme is designed for a 3D spatial region, it is easier to treat the 3-rd order boundary conditions for it correctly due to the “non-symmetrical” entrance of the spatial coordinates in three equations – see Eq. (1) – (3):

, (1)
Continue reading

Finite-difference approximation of the boundary conditions of the second and third order for the nonlinear heat conduction equation

Let us consider non-linear heat conduction equation

, (1)

where
, (2)

with the initial condition , and boundary conditions
, (3)

At . If , condition (3) is the boundary condition of the second order, but if , it is the boundary condition of the third order.

Let us introduce analytical grids in space and time:, , , .

Then, define grid functions , , , , , , , .

Continue reading

Alternate directions implicit scheme and the intermediate boundary conditions

The ADI (alternate directions implicit) method is widely used for the numerical solution of multidimensional parabolic PDE (partial differential equations). [1]. Although the method is known for a long time and is well described in the text-books, its practical realizations sometimes appear to be inaccurate [2]. The inaccuracy arises every time when one neglects the correct account of the so-called intermediate boundary conditions. This neglect can become the cause of instabilities even when the used ADI-scheme is known to be unconditionally stable in the frame of von Neumann spectral analysis technique [3]. The procedures of a correct account of the intermediate boundary conditions (for the Peaceman-Rachford ADI-scheme), are described in [4, 5, 6].
Below, we are going to consider the correct account of the intermediate boundary conditions for the Douglas-Rachford ADI-scheme [3, 7]:

, (1) 
, (2) 
, (3) 
Continue reading