Highspeed periodic geometries

A fast and efficient way to generate meshes in high dimension are quasi-periodic meshes. That is:

  • Take $N$ points $(x_j)_{j\in\{1,\dots,N\}}$ within a unit cube $[0,1]^{dim}$
  • for $i=1,\dots,dim$ and natural numbers $(n_i)_{i\in\{1,\dots,dim\}}$ make $\prod_i n_i$ "shifted" copies of $(x_j)_{j\in\{1,\dots,N\}}$, which yields a periodic set of points with $n_i$ repetitions of $(x_j)_{j\in\{1,\dots,N\}}$ in direction $i$.
  • calculated mesh geometry and interfaces areas and volumes with the Polygon-Method
  • if desired: calculate the integral of given functions using the Heuristic method

This is automatised in the following call:

    VG = HighVoronoi.VoronoiGeometry( VoronoiNodes(rand(dim,N)), 
        periodic_grid = ( periodic=[], dimensions=ones(Float64,dim), 
            scale=0.25*ones(Float64,dim), repeat=4*ones(Int64,dim), 
            periodic=[], fast=true ) )

Here, VoronoiNodes(rand(dim,N)) corresponds to the above $X=(x_j)_{j\in\{1,\dots,N\}}$.

A new feature is the field periodic_grid as a keyword that signals to HighVoronoi.jl what we intend to do. periodic_grid is a NamedTuple which can take the following fields:

  • dimensions: The box that contains the data $X$. Its default is ones(Float64,dim).
  • scale: a diagonal matrix to scale $(x_j)_{j\in\{1,\dots,N\}}$ before repeating. Its default is ones(Float64,dim).
  • repeat: corresponds to $(n_i)_{i\in\{1,\dots,dim\}}$, i.e. tells how often the data shall be repeated in each dimension. Its default is 2*ones(Int64,dim).
  • fast: true uses internal copy-and-paste algorithms to speed up the calculation significantly in high dimensions. Integration of functions falls back to Heuristic. false uses classical computations. Integration of functions using Polygon and MonteCarlo is then possible. Default: true.

The resulting domain will be a cuboid(dim,periodic=periodic,dimensions=(scale.*dimensions.*repeat)) of dimensions: scale.*dimensions.*repeat. The second un-named argument usually indicating the domain becomes meaningless.

In view of this fact, periodic boundary conditions on the resulting domain are implemented using:

  • periodic: Tells which dimensions shall have periodic boundary conditions. Default: []

Intention of use

Intentions of use

Using this feature makes sense only if either $n_i>1$ for some $i$ OR if periodic != []. In particular, periodic=[i] internaly increases $n_i$ by $2$.

Gain in performance compared to non-periodic grid

As mentioned above, the algorithm automatically tracks data that can be "copy-pasted" and as such can increase performance for $(n_i)_i = (2,2,\dots,2)$. However, lets assume for simplicitiy that the first $k$ dimensions have $n_i>3$ (actual order of $n_i$ does not matter to the implemented algorithm). We partition the full domain into cubes indexed by $(m_i)_{i\in\mathbb N}$ with $1\leq m_i\leq n_i$. One can observe that $n_i>m_i\geq3$ for $i\leq k$ implies that the volume and area data as well as all verteces of cell $(m_i)_i$ can be obtained as a copy of the respective data from cell $(m_1,\dots,m_{i-1},m_i-1,m_{i+1},\dots m_N)$.

The percentage of small cubes that can be copied from previous existing cubes can then be calculated as

\[P_0=0\,,\qquad P_k = P_{k-1}*\frac{3}{n_k}+\frac{n_k-3}{n_k}\,.\]

The value $P_{dim}$ can be calculated using non-exported method HighVoronoi.redundancy, e.g.

HighVoronoi.redundancy([3,5,2,6,8]) # returns 0.8875
Example

Assume repeat = 4*ones(Int64,dim) then the percentage of copied data increases according to:

\[\begin{array}{rcccc} \mathrm{dim} & 2 & 3 & 4 & 5 & 6 & \dots & \infty\\ \% & \frac{7}{16} & \frac{17}{32} & \frac{37}{64} & \frac{177}{256} & \frac{357}{512} & \dots & 1 \end{array}\]

However, since other cells can be partically recycled, numerical experiments show even higher gain in performance.

Cubic grids: Ultra high speed mesh generation

When the call of VoronoiGeometry looks like the following:

    VG = HighVoronoi.VoronoiGeometry( VoronoiNodes(rand(dim,1)), 
        periodic_grid = ( periodic=[], dimensions=ones(Float64,dim), 
            scale=0.25*ones(Float64,dim), repeat=4*ones(Int64,dim), 
            periodic=[], fast=true ) )

i.e. if only one single node is passed, the resulting grid will be cubic. This apriori knowledge is used by a specialized internal fast computation algorithm.

Fast generation of complex grids

The generation of coarse grids with local refinements in large dimensions can be achieved by calculating one coarse and one fine cubic grid and using substitute