High-accuracy cubic spline alternating group explicit methods for 1D quasi-linear parabolic equations†

In this article, we study the application of the alternating group explicit (AGE) and Newton-AGE iterative methods to a two-level implicit cubic spline formula of O(k ²+kh ²+h ⁴) for the solution of 1D quasi-linear parabolic equation u _xx =φ (x, t, u, u _x , u _t ), 0<x<1, t>0 subject to appropriate initial and natural boundary conditions prescribed, where k>0 and h>0 are mesh sizes in t- and x-directions, respectively. The proposed cubic spline methods require 3-spatial grid points and are applicable to problems in both rectangular and polar coordinates. The convergence analysis at advanced time level is briefly discussed. The proposed methods are then compared with the corresponding successive over relaxation (SOR) and Newton-SOR iterative methods both in terms of accuracy and performance.     

Parametric quintic spline solution of third-order boundary value problems

In this paper, we develop parametric quintic spline function to approximate the solution of third-order boundary value problems of the form u″′=f(x, u), a≤x≤b, subject to the boundary conditions u(a)=k ₁, u′(a)=k ₂ and u(b)=k ₃. The class of methods are second-, fourth- and sixth-order accurate. End equations of the splines are derived and truncation error is given. Three numerical examples are presented to illustrate the practical use of our methods as well as their accuracies when compared with some existing spline function methods. It is shown that the new methods give approximations, which are better than those produced by other methods.     

PHLST5: A Practical and Improved Version of Polyharmonic Local Sine Transform

We introduce a practical and improved version of the Polyharmonic Local Sine Transform (PHLST) called PHLST5. After partitioning an input image into a set of rectangular blocks, the original PHLST decomposes each block into a polyharmonic component and a residual. Each polyharmonic component solves a polyharmonic equation with the boundary conditions that match the values and normal derivatives of even orders along the boundary of the corresponding block with those of the original image block. Thanks to these boundary conditions, the residual component can be expanded into a Fourier sine series without facing the Gibbs phenomenon, and its Fourier sine coefficients decay faster than those of the original block. Due to the difficulty of estimating normal derivatives of higher orders, however, only the harmonic case (i.e., Laplace’s equation) has been implemented to date, which was called Local Laplace Sine Transform (LLST). In that case, the Fourier sine coefficients of the residual decay in the order O(‖k‖⁻³), where k is the frequency index vector. Unlike the original PHLST, PHLST5 only imposes the boundary values and the first order normal derivatives as the boundary conditions, which can be estimated using the information of neighbouring image blocks. In this paper, we derive a fast algorithm to compute a 5th degree polyharmonic function that satisfies such boundary conditions. Although the Fourier sine coefficients of the residual of PHLST5 possess the same decaying rate as in LLST, by using additional information of first order normal derivative from the boundary, the blocking artifacts are largely suppressed in PHLST5 and the residual component becomes much smaller than that of LLST. Therefore PHLST5 provides a better approximation result. We shall also show numerical experiments that demonstrate the superiority of PHLST5 over the original LLST in terms of the efficiency of approximation.

A family of third-order parallel splitting methods for parabolic partial differential equations

A family of numerical methods, based upon a new rational approximation to the matrix exponential function, is developed for solving parabolic partial differential equations. These methods are L-acceptable, third-order accurate in space and time, and do not require the use of complex arithmetic. In these methods second-order spatial derivatives are approximated by third-order finite-difference approximations.- Parallel algorithms are developed and tested on the one-dimensional heat equation, with constant coefficients, subject to homogeneous boundary conditions and time-dependent boundary conditions. These methods are also extended to two- and three-dimensional heat equations, with constant coefficients, subject to homogeneous boundary conditions.     

求解大规模谱聚类的近似加权核k-means算法

谱聚类将聚类问题转化成图划分问题,是一种基于代数图论的聚类方法.在求解图划分目标函数时,一般利用Rayleigh熵的性质,通过计算Laplacian矩阵的特征向量将原始数据点映射到一个低维的特征空间中,再进行聚类.然而在谱聚类过程中,存储相似矩阵的空间复杂度是O(n²),对Laplacian矩阵特征分解的时间复杂度一般为O(n³),这样的复杂度在处理大规模数据时是无法接受的.理论证明,Normalized Cut图聚类与加权核k-means都等价于矩阵迹的最大化问题.因此,可以用加权核k-means算法来优化Normalized Cut的目标函数,这就避免了对Laplacian矩阵特征分解.不过,加权核k-means算法需要计算核矩阵,其空间复杂度依然是O(n²).为了应对这一挑战,提出近似加权核k-means算法,仅使用核矩阵的一部分来求解大数据的谱聚类问题.理论分析和实验对比表明,近似加权核k-means的聚类表现与加权核k-means算法是相似的,但是极大地减小了时间和空间复杂性.     

A Supra-Convergent Finite Difference Scheme for the Poisson and Heat Equations on Irregular Domains and Non-Graded Adaptive Cartesian Grids

We present finite difference schemes for solving the variable coefficient Poisson and heat equations on irregular domains with Dirichlet boundary conditions. The computational domain is discretized with non-graded Cartesian grids, i.e., grids for which the difference in size between two adjacent cells is not constrained. Refinement criteria is based on proximity to the irregular interface such that cells with the finest resolution is placed on the interface. We sample the solution at the cell vertices (nodes) and use quadtree (in 2D) or octree (in 3D) data structures as efficient means to represent the grids. The boundary of the irregular domain is represented by the zero level set of a signed distance function. For cells cut by the interface, the location of the intersection point is found by a quadratic fitting of the signed distance function, and the Dirichlet boundary value is obtained by quadratic interpolation. Instead of using ghost nodes outside the interface, we use directly this intersection point in the discretization of the variable coefficient Laplacian. These methods can be applied in a dimension-by-dimension fashion, producing schemes that are straightforward to implement. Our method combines the ability of adaptivity on quadtrees/octrees with a quadratic treatment of the Dirichlet boundary condition on the interface. Numerical results in two and three spatial dimensions demonstrate second-order accuracy for both the solution and its gradients in the L ¹ and L ^∞ norms.     

Three point discretization of order four and six for (du :dx) of the solution of non-linear singular two point boundary value problem

We present finite difference methods of order four and six for the numerical solution of (du/dx) for the non-linear differential equation u″ = f(x,u,u′), 0 < x > 1 subject to the boundary conditions u(0) = A, u(l) =B. The proposed methods require only three grid points and applicable to both singular and non-singular problems. Numerical examples are given to illustrate the methods and their convergence.     

On the accuracy assessment of Laplacian models in MPS

From the basis of the Gauss divergence theorem applied on a circular control volume that was put forward by Isshiki (2011) in deriving the MPS-based differential operators, a more general Laplacian model is further deduced from the current work which involves the proposal of an altered kernel function. The Laplacians of several functions are evaluated and the accuracies of various MPS Laplacian models in solving the Poisson equation that is subjected to both Dirichlet and Neumann boundary conditions are assessed. For regular grids, the Laplacian model with smaller N$N$ is generally more accurate, owing to the reduction of leading errors due to those higher-order derivatives appearing in the modified equation. For irregular grids, an optimal N$N$ value does exist in ensuring better global accuracy, in which this optimal value of N$N$ will increase when cases employing highly irregular grids are computed. Finally, the accuracies of these MPS Laplacian models are assessed in an incompressible flow problem.     

Optimal shape and position of the actuators for the stabilization of a string

The energy in a string subject to constant viscous damping k on a subset ω of length l>0 decays exponentially in time; we consider the problem of optimizing the decay rate for the ω which are the unions of at most N intervals. This rate is given by the spectral abscissa of the linear operator associated to the wave equation. We are interested in small values of k; therefore, we consider the derivative of the spectral abscissa at k=0. We prove that, except for the case , when the number of intervals is not fixed a priori an optimal domain does not exist. We study numerically the case of one or two intervals using a genetic algorithm. These numerical results are not intuitive. In particular, the optimal position of one interval is never at the middle of the string.     

A new unconditionally stable ADI compact scheme for the two-space-dimensional linear hyperbolic equation

We formulate a new alternating direction implicit compact scheme of O(τ²+h ⁴) for the linear hyperbolic equation u _tt +2α u _t +β² u=u _xx +u _yy +f(x, y, t), 0<x, y<1, 0<t≤T, subject to appropriate initial and Dirichlet boundary conditions, where α>0 and β≥0 are real numbers. In this article, we show the method is unconditionally stable by the Von Neumann method. At last, numerical demonstrations are given to illustrate our result.     

Accuracy of the difference scheme of solving the eigenvalue problem for the Laplacian

The finite-difference approximation of the eigenvalue problem with the Dirichlet boundary conditions for the Laplacian in a two-dimensional domain of complex form is analyzed for accuracy and the error of eigenfunctions from the class W₂²( W) W_2^2\left( \Omega \right) in the mesh norm of W₂¹( w) W_2^1\left( \omega \right) is estimated.     

Spectral feature selection for shape characterization and classification

This paper proposes a framework for selecting the Laplacian eigenvalues of 3D shapes that are more relevant for shape characterization and classification. We demonstrate the redundancy of the information coded by the shape spectrum and discuss the shape characterization capability of the selected eigenvalues. The feature selection methods used to demonstrate our claim are the AdaBoost algorithm and Support Vector Machine. The efficacy of the selection is shown by comparing the results of the selected eigenvalues on shape characterization and classification with those related to the first k eigenvalues, by varying k over the cardinality of the spectrum. Our experiments, which have been performed on 3D objects represented either as triangle meshes or point clouds, show that working directly with point clouds provides classification results that are comparable with respect to those related to surface-based representations. Finally, we discuss the stability of the computation of the Laplacian spectrum to matrix perturbations.     

Extrapolation of Nystrom Solution for Two-Dimensional Nonlinear Fredholm Integral Equations

In this paper, we analyze the existence of asymptotic error expansion of Nystrom solution for two-dimensional nonlinear Fredholm integral of the second kind. We show that the Nystrom solution admits an error expansion in powers of the step-size h and the step-size k. For a special choice of the numerical quadrature, the leading terms in the error expansion for the Nystrom solution contain only even powers of h and k, beginning with terms h ^2p and k ^2q . These expansions are useful for the application of Richardson extrapolation and for obtaining sharper error bounds. Numerical examples show that how Richardson extrapolation gives a remarkable increase of precision, in addition to faster convergence.     

A further result on the oscillation of delay difference equations

In this paper, we are concerned with the delay difference equations of the form

(*)

y_n+1 − y_n + p_ny_n−k = 0, N = 0, 1, 2, …,

(*)where p_n ≥ 0 and k is a positive integer. We prove by using a new technique that

guarantees that all solutions of equation (*) oscillate, which improves many previous well-known results. In particular, our theorems also fit the case where Σⁿ⁻¹_i=n−kp_i ≤ k^k+1/(k + 1)^k+1. In addition, we present a nonoscillation sufficient condition for equation (*).     

The persistence of nonoscillatory solutions of difference equations under impulsive perturbations

We obtain a sufficient condition for the persistence of nonoscillatory solutions of the difference equation with continuous variable, ,under the impulsive perturbations, x(t_k+τ)−x(t_k)=I_k(x(t_k)),kN(1),     

A linear-time algorithm to construct a rectilinear Steiner minimal tree fork-extremal point sets

Ak-extremal point set is a point set on the boundary of ak-sided rectilinear convex hull. Given ak-extremal point set of sizen, we present an algorithm that computes a rectilinear Steiner minimal tree in timeO(k ⁴ n). For constantk, this algorithm runs inO(n) time and is asymptotically optimal and, for arbitraryk, the algorithm is the fastest known for this problem.     

Factorization of disconjugate higher-order Sturm-Liouville difference operators

Using a recently proved equivalence between disconjugacy of the 2n^th-order difference equation

and solvability of the corresponding Riccati matrix difference equation, it is shown that the equation L(y) = 0 is disconjugate on a given interval if and only if the operator L admits the factorization of the form

L(y)_k+n=M^*(c_kM(y)_k)_k+n,

where M and its adjoint M* are certain n^th-order difference operators and c_k is a sequence of positive numbers.     

A generalization of concavity for finite differences

The concept of concavity is generalized to discrete functions, u, satisfying the n^th-order difference inequality, (−1)^n−kΔⁿu(m) ≥ 0, M = 0, 1,..., N and the homogeneous boundary conditions, u(0) = … = u(k−1) = 0, u(N + k + 1) = … = u(N + n) = 0 for some k “1, …, n − 1”. A piecewise polynomial is constructed which bounds u below. The piecewise polynomial is employed to obtain a positive lower bound on u(m) for m = k, …, N + k, where the lower bound is proportional to the supremum of u. An analogous bound is obtained for a related Green's function.     

Numerical aspects of including wall roughness effects in the SST k–ω eddy-viscosity turbulence model

This paper presents a study on the numerical requirements of including sand-grain wall roughness effects in the SST k–ω eddy-viscosity model. Three implementations are tried: two retain the direct application of the no-slip condition at the wall, the third is based on a wall function formulation. In the first two options the roughness effect is introduced via a change in wall boundary conditions, either for ω only or for k and ω. The two-dimensional flow along a finite flat plate is adopted to assess the numerical accuracy of the three approaches. The computed results are also compared with semi-empirical formula available in the open literature. It is demonstrated that sand-grain roughness effects can be simulated with acceptable numerical uncertainties with all three options, but the numerical settings to achieve that goal differ significantly.     

Boundary value methods: The third way between linear multistep and Runge-Kutta methods

It is well known that the approximation of the solutions of ODEs by means of k-step methods transforms a first-order continuous problem in a k^th-order discrete one. Such transformation has the undesired effect of introducing spurious, or parasitic, solutions to be kept under control. It is such control which is responsible of the main drawbacks (e.g., the two Dahlquist barriers) of the classical LMF with respect to Runge-Kutta methods. It is, however, less known that the control of the parasitic solutions is much easier if the problem is transformed into an almost equivalent boundary value problem. Starting from such an idea, a new class of multistep methods, called Boundary Value Methods (BVMs), has been proposed and analyzed in the last few years. Of course, they are free of barriers. Moreover, a block version of such methods presents some similarity with Runge-Kutta schemes, although still maintaining the advantages of being linear methods. In this paper, the recent results on the subject are reviewed.