Complete lagrange family for the cube in finite element interpolations

Noting a vagueness in the Serendipity definition, the complete Lagrange family for the cube and the mixed complete Lagrange family are introduced. The unisolvent Lagrange interpolations over rectangular finite elements are then presented definitively in hierarchy-ranking expressions so that the polynominal completeness is realized with appropriately necessary minimum nodes. The corresponding interpolation bases in the conventional form can easily be derived through the basis transformation without matrix inversion.     

A new thin plate finite element by basis transformation

A simple nine-freedom thin plate finite element is obtained by using cubic Hermitian interpolation to define displacements at the third points on each side. A tenth “local” freedom at the centroid is then approximated using an interpolation devised by Bazeley et al. together with Hermitian interpolation on the sides. The result is a ten freedom “local” element to which the standard cubic Lagrangian areal coordinate interpolation can be applied. The element is of similar accuracy to a number of other well-known elements of comparable complexity and it provides another useful example of the “method of nested interpolations” which, along with penalty factors and Lagrange multipliers, brings us to the state of the art of the finite element method[1].     

Geometric validity (positive jacobian) of high-order Lagrange finite elements,theory and practical guidance

Finite elements of degree two or more are needed to solve various P.D.E. problems. This paper discusses a method to validate such meshes for the case of the usual Lagrange elements of various degrees. The first section of this paper comes back to Bézier curve and Bézier patches of arbitrary degree. The way in which a Bézier patch and a finite element are related is recalled. The usual Lagrange finite elements of various degrees are discussed, including simplices (triangle and tetrahedron), quads, prisms (pentahedron), pyramids and hexes together with some low-degree Serendipity elements. A validity condition, the positivity of the jacobian, is exhibited for these elements. Elements of various degrees are envisaged also including some “linear” elements (therefore straight-sided elements of degree 1) because the jacobian (polynomial) of some of them is not totally trivial.     

A type insensitive code for delay differential equations basing on adaptive and explicit Runge-Kutta interpolation methods

For the numerical solution of initial value problems for delay differential equations with constant delay a partitioned Runge-Kutta interpolation method is studied which integrates the whole system either as a stiff or as a nonstiff one in subintervals. This algorithm is based on an adaptive Runge-Kutta interpolation method for stiff delay equations and on an explicit Runge-Kutta interpolation method for nonstiff delay equations. The retarded argument is approximated by appropriate Lagrange or Hermite interpolation. The algorithm takes advantage of the knowledge of the first points of jump discontinuities. An automatic stiffness detection and a stepsize control are presented. Finally, numerical tests and comparisons with other methods are made on a great number of problems including real-life problems.     

On multivariate interpolation by generalized polynomials on subsets of grids

This note may be regarded as a complement to a paper of H. Werner [17] who has carried over Newton's classical interpolation formula to Hermite interpolation by algebraic polynomials of several real variables on certain subsets of grids. Here generalized polynomials of several real or complex variables are treated. Recursive procedures are presented showing that interpolation by generalized multivariate polynomials is performed nearly as simply as interpolation by algebraic polynomials. Having in general the same approximation power, generalized polynomials may be better adapted to special situations. In particular, the results of this note can be used for constructing nonpolynomial finite elements since in that case the interpolation points usually are rather regular subsystems of grids. Though the frame is more general than in [17] some of our proofs are simpler. As an alternative method to evaluate multivariate generalized interpolation polynomials for rectangular grids a Neville-Aitken algorithm is presented.     

Hermite type moving-least-squares approximations

The moving-least-squares approach, first presented by McLain [1], is a method for approximating multivariate functions using scattered data information. The method is using local polynomial approximations, incorporating weight functions of different types. Some weights, with certain singularities, induce C^∞ interpolation approximation in ℝⁿ. In this work we present a way of generalizing the method to enable Hermite type interpolation, namely, interpolation to derivatives' data as well. The essence of the method is the use of an appropriate metric in the construction of the local polynomial approximations.     

Constructing up to G 2 continuous curve on freeform surface

This paper presents new methods for G ¹ and G ² continuous interpolation of an arbitrary sequence of points on an implicit or parametric surface with prescribed tangent direction and both tangent direction and curvature vector, respectively, at every point. We design a G ¹ or G ² continuous curve in three-dimensional space, construct a so-called directrix vector field using the space curve and then project a special straight line segment onto the given surface along the directrix vector field. With the techniques in classical differential geometry, we derive a system of differential equations for the projection curve. The desired interpolation curve is just the projection curve, which can be obtained by numerically solving the initial-value problems for a system of first-order ordinary differential equations in the parametric domain associated to the surface representation for the parametric case or in three-dimensional space for the implicit case. Several shape parameters are introduced into the resulting curve, which can be used in subsequent interactive modification such that the shape of the resulting curve meets our demand. The presented method is independent of the geometry and parameterization of the base surface, and numerical experiments demonstrate that it is effective and potentially useful in patterns design on surface.     

A Kirchhoff-mode method for C0 bilinear and serendipity plate elements

A new formulation for the C⁰ quadrilateral and Serendipity plate elements is presented. It is an extension of the mode-decomposition approach that has been successfully applied in evaluating the C⁰ triangular linear plate element. In contrast to the triangular element, the concept of an equivalent discrete Kirchhoff configuration is utilized. The elements are applied to several examples and the performance of these elements is shown to be quite good.     

Learning the dynamics of two-dimensional stochastic Markov processes

We show that it is possible to learn the forces causing an observed two-dimensional stochastic Markov process. Hereby, we extend the ideas presented in our earlier work [1–3], where we discussed one-dimensional processes. Appropriate short-time correlation function measurements are used as constraints in the maximum information principle of Jaynes, allowing us to formulate the joint probability distribution function of the process. This is done using the method of Lagrange multipliers, which we determine by means of a dynamical learning method. Next, we derive explicit formulas expressing the drift- and diffusion coefficients of the Ito-Langevin equation corresponding to the process in terms of the Lagrange multipliers. This provides us with the sought for underlying deterministic and stochastic dynamics. The method was tested on a simulated Ornstein-Uhlenbeck process, showing good confirmation of the theory.     

New constructions of balanced Boolean functions with high nonlinearity and optimal algebraic degree

In this paper, we propose a technique for constructing balanced Boolean functions on even numbers of variables. The main technique is to utilize a set of disjoint spectra functions and a special Boolean permutation to derive a balanced Boolean function with high nonlinearity and optimal algebraic degree. It is shown that the functions we construct are different from both Maiorana-McFarland's (M-M) super-class functions introduced by Carlet and modified M-M super-class functions presented by Zeng and Hu. Furthermore, we show that they have no nonzero linear structures.     

Singularity-free dynamic equations of vehicle–manipulator systems

In this paper we derive the singularity-free dynamic equations of vehicle–manipulator systems using a minimal representation. These systems are normally modeled using Euler angles, which leads to singularities, or Euler parameters, which is not a minimal representation and thus not suited for Lagrange’s equations. We circumvent these issues by introducing quasi-coordinates which allows us to derive the dynamics using minimal and globally valid non-Euclidean configuration coordinates. This is a great advantage as the configuration space of the vehicle in general is non-Euclidean. We thus obtain a computationally efficient and singularity-free formulation of the dynamic equations with the same complexity as the conventional Lagrangian approach. The closed form formulation makes the proposed approach well suited for system analysis and model-based control. This paper focuses on the dynamic properties of vehicle–manipulator systems and we present the explicit matrices needed for implementation together with several mathematical relations that can be used to speed up the algorithms. We also show how to calculate the inertia and Coriolis matrices and present these for several different vehicle–manipulator systems in such a way that this can be implemented for simulation and control purposes without extensive knowledge of the mathematical background. By presenting the explicit equations needed for implementation, the approach presented becomes more accessible and should reach a wider audience, including engineers and programmers.     

Image reconstruction from scattered Radon data by weighted positive definite kernel functions

We propose a novel kernel-based method for image reconstruction from scattered Radon data. To this end, we employ generalized Hermite–Birkhoff interpolation by positive definite kernel functions. For radial kernels, however, a straightforward application of the generalized Hermite–Birkhoff interpolation method fails to work, as we prove in this paper. To obtain a well-posed reconstruction scheme for scattered Radon data, we introduce a new class of weighted positive definite kernels, which are symmetric but not radially symmetric. By our construction, the resulting weighted kernels are combinations of radial positive definite kernels and positive weight functions. This yields very flexible image reconstruction methods, which work for arbitrary distributions of Radon lines. We develop suitable representations for the weighted basis functions and the symmetric positive definite kernel matrices that are resulting from the proposed reconstruction scheme. For the relevant special case, where Gaussian radial kernels are combined with Gaussian weights, explicit formulae for the weighted Gaussian basis functions and the kernel matrices are given. Supporting numerical examples are finally presented.     

A symbolic system for computer-aided development of surface interpolants

The design and implementation of a symbolic input end computation package and its application to the development of several new surface interpolation schemes are described. Capabilities such as the composition of operators and symbolic differentiation have been incorporated into the system. This allows, in particular, the specification of Boolean sum projectors. The new schemes which have been implemented include an interpolant to randomly spaced data and a 'shape operator1 which has quadratic precision.     

An iterative algorithm for spline interpolation

One of the fundamental results in spline interpolation theory is the famous Schoenberg-Whitney Theorem, which completely characterizes those distributions of interpolation points which admit unique interpolation by splines. However, until now there exists no iterative algorithm for the explicit computation of the interpolating spline function, and the only practicable method to obtain this function is to solve explicitly the corresponding system of linear equations. In this paper we suggest a method which computes iteratively the coefficients of the interpolating function in its B-spline basis representation; the starting values of our one-step iteration scheme are quotients of two low order determinants in general, and sometimes even just of two real numbers. Furthermore, we present a generalization of Newton's interpolation formula for polynomials to the case of spline interpolation, which corresponds to a result of G. Mühlbach for Haar spaces.     

求解最优控制问题的Chebyshev-Gauss伪谱法

提出了一种求解最优控制问题的Chebyshev-Gauss伪谱法, 配点选择为Chebyshev-Gauss点. 通过比较非线性规划问题的Kaursh-Kuhn-Tucker条件和伪谱离散化的最优性条件, 导出了协态和Lagrange乘子的估计公式. 在状态逼近中, 采用了重心Lagrange插值公式, 并提出了一种简单有效的计算状态伪谱微分矩阵的方法. 该法的独特优势是具有良好的数值稳定性和计算效率. 仿真结果表明, 该法能够高精度地求解带有约束的复杂最优控制问题.     

The equivalence of the constrained Rayleigh quotient and Newton methods for matrix polynomials expressed in different polynomial bases along with the confluent case

We show that using the constrained Rayleigh quotient method to find the eigenvalues of matrix polynomials in different polynomial bases is equivalent to applying the Newton method to certain functions. We find those functions explicitly for a variety of polynomial bases including monomial, orthogonal, Newton, Lagrange and Bernstein bases. In order to do so, we provide explicit symbolic formulas for the right and left eigenvectors of the generalized companion matrix pencils for matrix polynomials expressed in those bases. Using the properties of the Newton basis, we also find two different formulas for the companion matrix pencil corresponding to the Hermite interpolation. We give pairs of explicit LU factors associated with these pencils. Additionally, we explicitly find the right and left eigenvectors for each of these pencils.     

Simultaneous Surface Approximation and Segmentation of Complex Objects

Deformable models represent a useful approach to approximate objects from collected data points. We propose to augment the basic approaches designed to handle mostly compact objects or objects of known topology.Our approach can fit simultaneously more than one curve or surface to approximate multiple topologically complex objects by using (1) the residual data points, (2) the badly fitting parts of the approximating surface, and (3) appropriate Boolean operations. In 2-D, B-snakes [3] are used to approximate each object (pattern). In 3-D, an analytical surface representation, based on the elements detected, is presented. The global representation of a 3-D object, in terms of elements and their connection, takes the form of B-spline and Bézier surfaces. A Bézier surface is used to connect different elements, and the connecting surface itself conforms to the data points nearby through energy minimization. This way, aG¹continuity surface is achieved for the underlying 3-D object.We present experiments on synthetic and real data in 2-D and 3-D. In these experiments, multiple complex patterns and objects with through holes are segmented. The system proceeds automatically without human interaction or any prior knowledge of the topology of the underlying object.     

Finite element formulation by nested interpolations: Application to the drilling freedom problem

Inclusion of the drilling freedom, that is the in plane rigid body rotation, in membrane elements has proved a formidable problem. There have been few attempts and these have not been particularly successful. As a consequence, though rigorous treatment of this freedom in shell analysis is sometimes desirable, the governing practice at present is to associate arbitrary stiffness with φ in flat shell elements when this is necessary to avoid singularity at points where flat shell elements are coplanar. In the present paper the drilling freedom is defined in the triangular natural coordinate system and the “method of nested interpolations” is then used to derive a nine freedom membrane element with u, v, φ at each vertex. In this method boundary interpolations are used to redefine the element freedoms so that a complete interpolation within the element subdomain is able to follow and the method has already been successfully applied to a nine freedom plate bending element with good results[1].     

Graph Complexity and Slice Functions

Abstract. A graph-theoretic approach to study the complexity of Boolean functions was initiated by Pudlák, Rödl, and Savický [PRS] by defining models of computation on graphs. These models generalize well-known models of Boolean complexity such as circuits, branching programs, and two-party communication complexity. A Boolean function f is called a 2-slice function if it evaluates to zero on inputs with less than two 1's and evaluates to one on inputs with more than two 1's. On inputs with exactly two 1's f may be nontrivially defined. There is a natural correspondence between 2-slice functions and graphs. Using the framework of graph complexity, we show that sufficiently strong superlinear monotone lower bounds for the very special class of {2-slice functions} would imply superpolynomial lower bounds over a complete basis for certain functions derived from them. We prove, for instance, that a lower bound of n ^1+Ω(1) on the (monotone) formula size of an explicit 2-slice function f on n variables would imply a 2 ^Ω(?) lower bound on the formula size over a complete basis of another explicit function g on l variables, where l=Θ( log n) . We also consider lower bound questions for depth-3 bipartite graph complexity. We prove a weak lower bound on this measure using algebraic methods. For instance, our result gives a lower bound of Ω(( log n) ³ / ( log log n) ⁵ ) for bipartite graphs arising from Hadamard matrices, such as the Paley-type bipartite graphs. Lower bounds for depth-3 bipartite graph complexity are motivated by two significant applications: (i) a lower bound of n ^Ω(1) on the depth-3 complexity of an explicit n -vertex bipartite graph would yield superlinear size lower bounds on log-depth Boolean circuits for an explicit function, and (ii) a lower bound of $\exp((\log \log n)^{\omega(1)})$ would give an explicit language outside the class Σ ₂ ^cc of the two-party communication complexity as defined by Babai, Frankl, and Simon [BFS]. Our lower bound proof is based on sign-representing polynomials for DNFs and lower bounds on ranks of ±1 matrices even after being subjected to sign-preserving changes to their entries. For the former, we use a result of Nisan and Szegedy [NS] and an idea from a recent result of Klivans and Servedio [KS]. For the latter, we use a recent remarkable lower bound due to Forster [F1].