Refinable bivariate quartic -splines for multi-level data representation and surface display

In this paper, a second-order Hermite basis of the space of -quartic splines on the six-directional mesh is constructed and the refinable mask of the basis functions is derived. In addition, the extra parameters of this basis are modified to extend the Hermite interpolating property at the integer lattices by including Lagrange interpolation at the half integers as well. We also formulate a compactly supported super function in terms of the basis functions to facilitate the construction of quasi-interpolants to achieve the highest (i.e., fifth) order of approximation in an efficient way. Due to the small (minimum) support of the basis functions, the refinable mask immediately yields (up to) four-point matrix-valued coefficient stencils of a vector subdivision scheme for efficient display of -quartic spline surfaces. Finally, this vector subdivision approach is further modified to reduce the size of the coefficient stencils to two-point templates while maintaining the second-order Hermite interpolating property.

     

A compact multipoint flux approximation method with improved robustness

Multipoint flux approximation (MPFA) methods were introduced to solve control‐volume formulations on general grids. Although these methods are general in the sense that they may be applied to any grid, their convergence and monotonicity properties vary. We introduce a new MPFA method for quadrilateral grids termed the L‐method. This method seeks to minimize the number of entries in the flux stencils, while honoring uniform flow fields. The methodology is valid for general media. For homogeneous media and uniform grids in two dimensions, this method has four‐point flux stencils and seven‐point cell stencils, whereas the MPFA O‐methods have six‐point flux stencils and nine‐point cell stencils. The reduced stencil of the L‐method appears as a consequence of adapting the method to the closest neighboring cells, or equivalently, to the dominating principal direction of anisotropy. We have tested the convergence and monotonicity properties for this method and compared it with the O‐methods. For moderate grids, the convergence rates are the same, but for rough grids with large aspect ratios, the convergence of the O‐methods is lost, while the L‐method converges with a reduced convergence rate. Also, the L‐method has a larger monotonicity range than the O‐methods. For homogeneous media and uniform parallelogram grids, the matrix of coefficients is an M‐matrix whenever the method is monotone. For strongly nonmonotone cases, the oscillations observed for the O‐methods are almost removed for the L‐method. Instead, extrema on no‐flow boundaries are observed. These undesired solutions, which only occur for parameters not common in applications, should be avoided by requiring that the previously derived monotonicity conditions are satisfied. For local grid refinements, test runs indicate that the L‐method yields almost optimal solutions, and that the solution is considerably better than the solutions obtained by the O‐methods. The efficiency of the linear solver is in many cases better for the L‐method than for the O‐methods. This is due to lower condition number and a reduced number of entries in the matrix of coefficients. © 2008 Wiley Periodicals, Inc. Numer Methods Partial Differential Eq 2008     

Galerkin-wavelet modeling of wave propagation: Optimal finite-difference stencil design

In this paper, we describe a method for design of optimal finite-difference stencils for wave propagation problems using an intrinsically explicit Galerkin-wavelet formulation. The method enables an efficient choice of stencils optimal for a certain problem. We compare group velocity curves corresponding to stencils obtained by our choice of wavelet basis and traditional finite-difference schemes. Generally there exist choices of stencils with superior characteristics compared to conventional finite-difference stencils of the same size. Beside gain in accuracy, this leads to large computational savings.     

A simulated annealing approach to the nesting problem in the textile manufacturing industry

The nesting problem in the textile industry is the problem of placing a set of irregularly shaped pieces (calledstencils) on a rectangularsurface, such that no stencils overlap and that thetrim loss produced when cutting out the stencils is minimized. Certain constraints may put restrictions on the positions and orientation of some stencils in the layout but, in general, the problem is unconstrained. In this paper, an algorithmic approach using simulated annealing is presented covering a wide variety of constraints which may occur in the industrial manufacturing process. The algorithm has high performance, is quite simple to use, is extensible with respect to the set of constraints to be met, and is easy to implement.The work of this author was supported in part by grant Le 491/3-1 from the German Research Association (DFG).     

Models of linear logic

We engage a study of nonmodal linear logic which takes times ⊗ and the linear conditional ⊸ to be the basic connectives instead of times and linear negation ()^⊥ as in Girard's approach. This difference enables us to obtain a very large subsystem of linear logic (called positive linear logic) without an involutionary negation (if the law of double negation is removed from linear logic in Girard's formulation, the resulting subsystem is extremely limited). Our approach enables us to obtain several natural models for various subsystems of linear logic, including a generic model for the so-called minimal linear logic. In particular, it is seen that these models arise spontaneously in the transition from set theory to multiset theory. We also construct a model of full (nonmodal) linear logic that is generic relative to any model of positive linear logic. However, the problem of constructing a generic model for positive linear logic remains open. Bibliography: 2 titles. Published inZapiski Nauchnykh Seminarov POMI, Vol. 220, 1995, pp. 23–35. Original     

Monotone schemes for a class of nonlinear elliptic and parabolic problems

We construct monotone numerical schemes for a class of nonlinear PDE for elliptic and initial value problems for parabolic problems. The elliptic part is closely connected to a linear elliptic operator, which we discretize by monotone schemes, and solve the nonlinear problem by iteration. We assume that the elliptic differential operator is in the divergence form, with measurable coefficients satisfying the strict ellipticity condition, and that the right-hand side is a positive Radon measure. The numerical schemes are not derived from finite difference operators approximating differential operators, but rather from a general principle which ensures the convergence of approximate solutions. The main feature of these schemes is that they possess stencils stretching far from basic grid-rectangles, thus leading to system matrices which are related to M-matrices.     

A fuzzy programming method for deriving priorities in the analytic hierarchy process

The estimation of the priorities from pairwise comparison matrices is the major constituent of the Analytic Hierarchy Process (AHP). The priority vector can be derived from these matrices using different techniques, as the most commonly used are the Eigenvector Method (EVM) and the Logarithmic Least Squares Method (LLSM). In this paper a new Fuzzy Programming Method (FPM) is proposed, based on geometrical representation of the prioritisation process. This method transforms the prioritisation problem into a fuzzy programming problem that can easily be solved as a standard linear programme. The FPM is compared with the main existing prioritisation methods in order to evaluate its performance. It is shown that it possesses some attractive properties and could be used as an alternative to the known prioritisation methods, especially when the preferences of the decision-maker are strongly inconsistent.     

Sum factorization of the static condensed Helmholtz equation in a three-dimensional spectral element discretization

We propose a factorization technique for the Helmholtz operator of a static condensed, three-dimensional, cartesian spectral-element discretization, that yields linear complexity in the number of degrees of freedom. We then compare its performance to a reference implementation of the conventional, unfactorized approach. (© 2014 Wiley-VCH Verlag GmbH & Co. KGaA, Weinheim)     

The triple distribution of codes and ordered codes

We study the distribution of triples of codewords of codes and ordered codes. Schrijver [A. Schrijver, New code upper bounds from the Terwilliger algebra and semidefinite programming, IEEE Trans. Inform. Theory 51 (8) (2005) 2859–2866] used the triple distribution of a code to establish a bound on the number of codewords based on semidefinite programming. In the first part of this work, we generalize this approach for ordered codes. In the second part, we consider linear codes and linear ordered codes and present a MacWilliams-type identity for the triple distribution of their dual code. Based on the non-negativity of this linear transform, we establish a linear programming bound and conclude with a table of parameters for which this bound yields better results than the standard linear programming bound.     

Properties of Difference Schemes with Oblique Stencils for Hyperbolic Equations

In this paper, various difference schemes with oblique stencils, i.e., schemes using different space grids at different time levels, are studied. Such schemes may be useful in solving boundary value problems with moving boundaries, regular grids of a non-standard structure (for example, triangular or cellular ones), and adaptive methods. To study the stability of finite difference schemes with oblique stencils, we analyze the first differential approximation and dispersion. We study stability conditions as constraints on the geometric locations of stencil elements with respect to characteristics of the equation. We compare our results with a geometric interpretation of the stability of some classical schemes. The paper also presents generalized oblique schemes for a quasilinear equation of transport and the results of numerical experiments with these schemes.     

Compact high-order finite-element method for elliptic transport problems with variable coefficients

We present a new conforming bilinear Petrov-Galerkin finite-element scheme for elliptic transport problems with variable coefficients. This scheme combines a generalized test function and artificial diffusion to achieve O(h⁴) grid-point accuracy on uniform stencils of 3 × 3 in two dimensions without resorting to the extended stencils of high-order elements. The method is compared with upwind and high-order finite-difference schemes and the standard Galerkin finite-element method for representative test problems. © 1994 John Wiley & Sons, Inc.     

基于不动点方法求解非线性Falkner-Skan流动方程

Falkner-Skan流动方程描述绕楔面的流动,该方程具有很强的非线性.首先通过引入变换式,将原半无限大区域上的流动问题转化为有限区间上的两点边值问题.接着基于泛函分析中的不动点理论,采用不动点方法求解两点边值问题从而得到Falkner Skan流动方程的解.最后将不动点方法给出的结果和文献中的数值结果相比较,发现不动点方法得到的结果具有很高的精度,并且解的精度很容易通过迭代而不断得到提高.表明不动点方法是一种求解非线性微分方程行之有效的方法.     

Efficient geometric multigrid implementation for triangular grids

This paper deals with a stencil-based implementation of a geometric multigrid method on semi-structured triangular grids (triangulations obtained by regular refinement of an irregular coarse triangulation) for linear finite element methods. An efficient and elegant procedure to construct these stencils using a reference stencil associated to a canonical hexagon is proposed. Local Fourier Analysis (LFA) is applied to obtain asymptotic convergence estimates. Numerical experiments are presented to illustrate the efficiency of this geometric multigrid algorithm, which is based on a three-color smoother.     

Schnyder Woods and Orthogonal Surfaces

In this paper we study connections between planar graphs, Schnyder woods, and orthogonal surfaces. Schnyder woods and the face counting approach have important applications in graph drawing and the dimension theory of orders. Orthogonal surfaces explain connections between these seemingly unrelated notions. We use these connections for an intuitive proof of the Brightwell-Trotter Theorem which says, that the face lattice of a 3-polytope minus one face has order dimension three. Our proof yields a linear time algorithm for the construction of the three linear orders that realize the face lattice. Coplanar orthogonal surfaces are in correspondence with a large class of convex straight line drawings of 3-connected planar graphs. We show that Schnyder’s face counting approach with weighted faces can be used to construct all coplanar orthogonal surfaces and hence the corresponding drawings. Appropriate weights are computable in linear time.     

Stability radius of linear parameter-varying systems and applications

In this paper, we present a unifying approach to the problems of computing of stability radii of positive linear systems. First, we study stability radii of linear time-invariant parameter-varying differential systems. A formula for the complex stability radius under multi perturbations is given. Then, under hypotheses of positivity of the system matrices, we prove that the complex, real and positive stability radii of the system under multi perturbations (or affine perturbations) coincide and they are computed via simple formulae. As applications, we consider problems of computing of (strong) stability radii of linear time-invariant time-delay differential systems and computing of stability radii of positive linear functional differential equations under multi perturbations and affine perturbations. We show that for a class of positive linear time-delay differential systems, the stability radii of the system under multi perturbations (or affine perturbations) are equal to the strong stability radii. Next, we prove that the stability radii of a positive linear functional differential equation under multi perturbations (or affine perturbations) are equal to those of the associated linear time-invariant parameter-varying differential system. In particular, we get back some explicit formulas for these stability radii which are given recently in [P.H.A. Ngoc, Strong stability radii of positive linear time-delay systems, Internat. J. Robust Nonlinear Control 15 (2005) 459-472; P.H.A. Ngoc, N.K. Son, Stability radii of positive linear functional differential equations under multi perturbations, SIAM J. Control Optim. 43 (2005) 2278-2295]. Finally, we give two examples to illustrate the obtained results.     

Approximately linear tracking control of nonlinear systems

An elegant approach to control nonlinear state-space systems is the exact input-to-state linearization, where a nonlinear change of coordinates combined with a nonlinear feedback law yields a linear controllable system. In this contribution, we treat the single-input case, where input-to-state linearizability is equivalent to flatness. Sufficient and necessary existence conditions are well-known, but quite restrictive. We propose the design of a tracking controller for flat single-input systems, where the explicit knowledge of the flat output is not required. Our approach is based on a series expansion of the tracking error along a given reference trajectory. The controller gain can even be computed for non-flat systems with regular controllability matrix. (© 2012 Wiley-VCH Verlag GmbH & Co. KGaA, Weinheim)     

混合层无粘稳定性分析的Legendre级数解

基于泛函分析中的不动点理论,采用不动点方法首次获得混合层无粘线性稳定性方程的显式Legendre级数解,该级数解在整个无界流动区域内一致有效．现有基于传统摄动法得到的无界流动区域一致有效解仅适用于长波扰动和中性扰动两种特殊情况,而使用不动点方法可以得到所有不稳定扰动波数的特征解．另外,在不动点方法框架下,扰动相速度和扰动增长率可根据方程的可解性条件来唯一确定．为了验证该方法的有效性,将该方法和现有文献中的数值计算结果相比较,对比结果表明该方法具有精度高、收敛快等优点．     

A CLASS OF GENERALIZED MULTISPLITTING RELAXATION METHODS FOR LINEAR COMPLEMENTARITY PROBLEMS

In this paper,a class of generalized parallel matrix multisplitting relaxation methods for solving linear complementarity problems on the high-speed multiprocessor systems is set up. This class of methods not only includes all the existing relaxation methods for the linear complementarity problems ,but also yields a lot of novel ones in the sense of multisplittlng. We establish the convergence theories of this class of generalized parallel multisplitting relaxation methods under the condition that the system matrix is an H-metrix with positive diagonal elements.     

Boundary control problems for quasilinear systems of hyperbolic equations

For quasilinear systems of hyperbolic equations, the nonclassical boundary value problem of controlling solutions with the help of boundary conditions is considered. Previously, this problem was extensively studied in the case of the simplest hyperbolic equations, namely, the scalar wave equation and certain linear systems. The corresponding problem formulations and numerical solution algorithms are extended to nonlinear (quasilinear and conservative) systems of hyperbolic equations. Some numerical (grid-characteristic) methods are considered that were previously used to solve the above problems. They include explicit and implicit conservative difference schemes on compact stencils that are linearizations of Godunov’s method. The numerical algorithms and methods are tested as applied to well-known linear examples.     

Further Improvements in High Gain Observer Design for Systems with Structured Nonlinearities

Due to their simple implementation based on a constant gain matrix, high gain observers are very common in practical applications. We consider systems whose dynamics can be decomposed into a linear and a nonlinear part, where the nonlinear part meets some Lipschitz condition. In many cases there exists a finite bound on the maximum feasible Lipschitz constant for which the error dynamics can be stabilized. Necessary and in some sense sufficient conditions for this maximum Lipschitz constant are given in [1]. These results has been improved in [2,3] by taking the structure of the linear part into account. Having a system with one single nonlinearity, the results given in [2,3] are strict. If multiple nonlinearities occur, even this approach tends to be to conservative. In this case, one could additionally take the internal structure of the nonlinearities into account which leads to a larger set of systems for which convergence of the observer error can be guaranteed. Our new approach is based on an approximation of the structured singular value [4] which yields existence conditions in terms of linear matrix inequalities (LMIs). These LMIs may as well be used for the numerical computation of the observer gain. We demonstrate the advantage of our method on an example. (© 2016 Wiley-VCH Verlag GmbH & Co. KGaA, Weinheim)