Normal,high order discrete velocity models of the Boltzmann equation

This paper aims at approximations of the collision operator in the Boltzmann equation. The developed framework guarantees the “normality” of the approximation, which means correct collision invariants, H-Theorem, and equilibrium solutions. It fits into the discrete velocity model framework, is given in such a way that it is understandable with undergraduate level mathematics and can be used to construct approximations with arbitrary high convergence orders. At last we give an example alongside a numerical verification. Here the convergence orders range up to $3$ ($2$) and the time complexity is given by $3+\frac{1}{2}$ ($4+\frac{2}{3}$) in $2$ ($3$) dimensions.     

Online scheduling of equal-length jobs with incompatible families on multiple batch machines to maximize the weighted number of early jobs

This paper studies the online scheduling of equal-length jobs with incompatible families on multiple batch machines which can process the jobs from a common family in batches, where each batch has a capacity b with $b=\infty$ in the unbounded batching and $b<\infty$ in the bounded batching. Each job J has an equal-length integral processing time $p>0$, an integral release time $r(J)?0$, an integral deadline $d(J)?0$ and a real weight $w(J)?0$. The goal is to determine a preemptive schedule with restart which maximizes the weighted number of early jobs. When $p=1$, we show that a simple greedy online algorithm has a competitive ratio 2, and establish the lower bound $2?1/b$. This means that the greedy algorithm is of the best possible for $b=\infty$. When p is any positive integer, we provide an online algorithm of competitive ratio $3+2\sqrt{2}$ for both $b=\infty$ and $b<\infty$. This is the first online algorithm for the problem with a constant competitive ratio.     

A new approximation algorithm for cut-and-paste sorting of unsigned circular permutations

A cut-and-paste operation can be a reversal, a transposition, or a transreversal on circular or linear permutations. There are several approximation algorithms for sorting signed permutations by combinations of these operations. For sorting unsigned permutations, we only know an algorithm with performance ratio 3 and its improved version with performance ratio $2.8386+\delta$ allowing reversals and transpositions. In this paper, we present a 2.25-approximation algorithm for sorting unsigned circular permutations by cut-and-paste operations. A structure called tie is proposed to represent the alternating path of length 5. We can classify the ties into 6 types and find ways to remove the breakpoints for each type of ties, so that every cut-and-paste operation can reduce at least $\frac{4}{3}$ breakpoints averagely. Our algorithm can be used to sort unsigned linear permutations and achieve the performance ratio 2.25 if another operation named revrev is allowed.     

Analysis and approximation of a fractional Laplacian-based closure model for turbulent flows and its connection to Richardson pair dispersion

We study a turbulence closure model in which the fractional Laplacian ${(?\Delta )}^{\alpha }$ of the velocity field represents the turbulence diffusivity. We investigate the energy spectrum of the model by applying Pao’s energy transfer theory. For the case $\alpha =1∕3$, the corresponding power law of the energy spectrum in the inertial range has a correction exponent on the regular Kolmogorov $?5∕3$ scaling exponent. For this case, this model represents Richardson’s particle pair-distance superdiffusion of a fully developed homogeneous turbulent flow as well as Lévy jumps that lead to the superdiffusion. For other values of $\alpha$, the power law of the energy spectrum is consistent with the regular Kolmogorov $?5∕3$ scaling exponent. We also propose and study a modular time-stepping algorithm in semi-discretized form. The algorithm is minimally intrusive to a given legacy code for solving Navier–Stokes equations by decoupling the local part and nonlocal part of the equations for the unknowns. We prove the algorithm is first-order accurate and unconditionally stable. We also derive error estimates for full discretizations of the model which, in addition to the time stepping algorithm, involves a finite element spatial discretization and a domain truncation approximation to the range of the fractional Laplacian.     

Jacobi elliptic wave solutions for two variable coefficients cylindrical Korteweg–de Vries models arising in dusty plasmas by using direct reduction method

In this paper, generalized models for both ($2+1$)-dimensional cylindrical modified Korteweg–de Vries (cmKdV) equation with variable coefficients and ($3+1$)-dimensional variable coefficients cylindrical Korteweg–de Vries (cKdV) equation are studied by direct reduction method. A direct reduction to nonlinear ordinary differential equations in the form of Riccati equations obtained for the considered equations under some integrability conditions. The search for solutions for the reduced Riccati equations has yielded many Jacobi elliptic wave solutions, solitary and periodic wave solutions for both ($2+1$)-dimensional cmKdV and ($3+1$)-dimensional cKdV equations. Physical application for the obtained solutions as dust ion acoustic waves in plasma physics is given     

Variational mesh segmentation via quadric surface fitting

We present a new variational method for mesh segmentation by fitting quadric surfaces. Each component of the resulting segmentation is represented by a general quadric surface (including plane as a special case). A novel energy function is defined to evaluate the quality of the segmentation, which combines both $L^2$ and $L^{2,1}$ metrics from a triangle to a quadric surface. The Lloyd iteration is used to minimize the energy function, which repeatedly interleaves between mesh partition and quadric surface fitting. We also integrate feature-based and simplification-based techniques in the segmentation framework, which greatly improve the performance. The advantages of our algorithm are demonstrated by comparing with the state-of-the-art methods.     

Faster gossiping on butterfly networks

Gossiping has been considered intensively for butterflies and “simple” butterflies (which have no wrap-around connections). In the “telephone” communication model, for a butterfly of order k, the best previous gossiping algorithms require $2\frac{1}{2}k$ and $3k$ communication rounds, respectively. By new asymptotic methods we break through these bounds. We show that gossiping on a class of “column-based” networks, which also contains the cube-connected cycles, can be reduced to the simpler problem of “row-gossiping”. Row-gossiping in turn is reduced to “coherent row-broadcasting”. This latter problem is sufficiently simple to be solved by a sophisticated computer program for butterflies with up to $15\times 2^{15}$ nodes. Out of the produced solutions a pattern is distilled, which can be used to perform gossiping on butterflies and simple butterflies of order k in $2\frac{1}{4}k+\mathrm{o}(k)$ and $2\frac{1}{2}k+\mathrm{o}(k)$ rounds, respectively, for any k, considerably reducing the gap with the lower bounds. The new upper bounds also hold for gossiping in the weaker “telegraph” model.