In a variety of modern applications there arises a need to tessellate the domain into representative regions, called Voronoi cells. A particular type of such tessellations, called centroidal Voronoi tessellations or CVTs, are in big demand due to their optimality properties important for many applications. The availability of fast and reliable algorithms for their construction is crucial for their successful use in practical settings. This paper introduces a new multigrid algorithm for constructing CVTs that is based on the MG/Opt algorithm that was originally designed to solve large nonlinear optimization problems. Uniform convergence of the new method and its speedup comparing to existing techniques are demonstrated for linear and nonlinear densities for several 1d and 2d problems, and O(k) complexity estimation is provided for a problem with k generators.

We present an algebraic version of an iterative multigrid method for obstacle problems, called projected algebraic multigrid (PAMG) here. We show that classical algebraic multigrid algorithms can easily be extended to deal with this kind of problem. This paves the way for efficient multigrid solution of obstacle problems with partial differential equations arising, for example, in financial engineering.

In this paper, the dimension of the nonuniform bivariate spline space is discussed based on the theory of multivariate spline space. Moreover, by means of the Conformality of Smoothing Cofactor Method, the basis of composed of two sets of splines are worked out in the form of the values at ten domain points in each triangular cell, both of which possess distinct local supports. Furthermore, the explicit coefficients in terms of B-net are obtained for the two sets of splines respectively.

In this paper, we investigate the superconvergence property and the L∞-error estimates of mixed finite element methods for a semilinear elliptic control problem with an integral constraint. The state and co-state are approximated by the order one Raviart-Thomas mixed finite element space and the control variable is approximated by piecewise constant functions or piecewise linear functions. We derive some super-convergence results for the control variable and the state variables when the control is approximated by piecewise constant functions. Moreover, we derive L∞-error estimates for both the control variable and the state variables when the control is discretized by piecewise linear functions. Finally, some numerical examples are given to demonstrate the theoretical results.

We propose an efficient gradient-type algorithm to solve the fourth-order LLT denoising model for both gray-scale and vector-valued images. Based on the primal-dual formulation of the original nondifferentiable model, the new algorithm updates the primal and dual variables alternately using the gradient descent/ascent flows. Numerical examples are provided to demonstrate the superiority of our algorithm.

An elliptic optimal control problem with constraints on the state variable is considered. The Lavrentiev-type regularization is used to treat the constraints on the state variable. To solve the problem numerically, the multigrid for optimization (MGOPT) technique and the collective smoothing multigrid (CSMG) are implemented. Numerical results are reported to illustrate and compare the efficiency of both multigrid strategies.

With the aid of index functions, we re-derive the ML(n)BiCGStab algorithm in [Yeung and Chan, SIAM J. Sci. Comput., 21 (1999), pp. 1263-1290] systematically. There are n ways to define the ML(n)BiCGStab residual vector. Each definition leads to a different ML(n)BiCGStab algorithm. We demonstrate this by presenting a second algorithm which requires less storage. In theory, this second algorithm serves as a bridge that connects the Lanczos-based BiCGStab and the Arnoldi-based FOM while ML(n)BiCG is a bridge connecting BiCG and FOM. We also analyze the breakdown situation from the probabilistic point of view and summarize some useful properties of ML(n)BiCGStab. Implementation issues are also addressed.

In this paper, we introduce the dissipative spectral methods (DSM) for the first order linear hyperbolic equations in one dimension. Specifically, we consider the Fourier DSM for periodic problems and the Legendre DSM for equations with the Dirichlet boundary condition. The error estimates of the methods are shown to be quasi-optimal for variable-coefficients equations. Numerical results are given to verify high accuracy of the DSM and to compare the proposed schemes with some high performance methods, showing some superiority in long-term integration for the periodic case and in dealing with limited smoothness near or at the boundary for the Dirichlet case.

As is known, the numerical stiffness arising from the small mean free path is one of the main difficulties in the kinetic equations. In this paper, we derive both the split and the unsplit schemes for the linear semiconductor Boltzmann equation with a diffusive scaling. In the two schemes, the anisotropic collision operator is realized by the “BGK”-penalty method, which is proposed by Filbet and Jin [F. Filbet and S. Jin, J. Comp. Phys. 229(20), 7625-7648, 2010] for the kinetic equations and the related problems having stiff sources. According to the numerical results, both of the schemes are shown to be uniformly convergent and asymptotic-preserving. Besides, numerical evidences suggest that the unsplit scheme has a better numerical stability than the split scheme.

We study the time-dependent heat equation on its space-time domain that is discretised by a k-spacetree. k-spacetrees are a generalisation of the octree concept and are a discretisation paradigm yielding a multiscale representation of dynamically adaptive Cartesian grids with low memory footprint. The paper presents a full approximation storage geometric multigrid implementation for this setting that combines the smoothing properties of multigrid for the equation’s elliptic operator with a multiscale solution propagation in time. While the runtime and memory overhead for tackling the all-in-one space-time problem is bounded, the holistic approach promises to exhibit a better parallel scalability than classical time stepping, adaptive dynamic refinement in space and time fall naturally into place, as well as the treatment of periodic boundary conditions of steady cycle systems, on-time computational steering is eased as the algorithm delivers guesses for the solution’s long-term behaviour immediately, and, finally, backward problems arising from the adjoint equation benefit from the the solution being available for any point in space and time.