Dynamics solution of n-DOF global machinery model

Automated model generation and solution for motion planning and re-planning of automated systems will play an important role in future reconfigurable manufacturing systems (RMS). An n-DOF Global Kinematic Model (n-GKM) was previously developed for any combination of either rotational or translational type of joints. In this paper, the automatic generation of the dynamic equations for the n-GKM is presented. For the symbolic calculation of the n-GKM dynamic equations, the recursive Newton–Euler algorithm is employed using the symbolic algebra package MAPLE 12. The dynamic model is named Global Dynamic Model (n-GDM). The significance of the n-GDM is that it automatically generates each element of the inertia matrix A, Coriolis torque matrix B, centrifugal torque matrix C, and the gravity torque vector G, using Automatic Separation Method (ASM). The n-GDM is a dynamic solver for the n-GKM which includes predefined reconfigurable parameters. These parameters are used to control the joint's positive directions and its type (rotational and/or translational). Instead of solving the dynamics of different kinematic structures, the n-GDM can be used to auto-generate the solution by only defining these reconfigurable parameters. Using n-DOF Global Dynamic Model equations, a 3-DOF Global Dynamic Model (GDM) is derived. The 3-GDM has been validated using five selected cases (RR, RT, TR, TT planar and SCARA configurations). The results show the model ability to automatically generate different dynamic realizations for any required configuration.     

Towards the classification of scalar nonpolynomial evolution equations: Quasilinearity

We prove that, for m ≥ 7, scalar evolution equations of the form u_t = F(x, t, u, …, u_m) which admit a nontrivial conserved density of order m + 1 are linear in u_m. The existence of such conserved densities is a necessary condition for integrability in the sense of admitting a formal symmetry, hence, integrable scalar evolution equations of order m ≥ 7, admitting nontrivial conserved densities are quasilinear.     

Extended Jacobian elliptic function algorithm with symbolic computation to construct new doubly-periodic solutions of nonlinear differential equations

With the aid of computerized symbolic computation, the extended Jacobian elliptic function expansion method and its algorithm are presented by using some relations among ten Jacobian elliptic functions and are very powerful to construct more new exact doubly-periodic solutions of nonlinear differential equations in mathematical physics. The new (2+1)-dimensional complex nonlinear evolution equations is chosen to illustrate our algorithm such that sixteen families of new doubly-periodic solutions are obtained. When the modulus m→1 or 0, these doubly-periodic solutions degenerate as solitonic solutions including bright solitons, dark solitons, new solitons as well as trigonometric function solutions.     

A symbolic algorithm for computing recursion operators of nonlinear partial differential equations

A recursion operator is an integro-differential operator which maps a generalized symmetry of a nonlinear partial differential equation (PDE) to a new symmetry. Therefore, the existence of a recursion operator guarantees that the PDE has infinitely many higher-order symmetries, which is a key feature of complete integrability. Completely integrable nonlinear PDEs have a bi-Hamiltonian structure and a Lax pair; they can also be solved with the inverse scattering transform and admit soliton solutions of any order.

A straightforward method for the symbolic computation of polynomial recursion operators of nonlinear PDEs in (1+1) dimensions is presented. Based on conserved densities and generalized symmetries, a candidate recursion operator is built from a linear combination of scaling invariant terms with undetermined coefficients. The candidate recursion operator is substituted into its defining equation and the resulting linear system for the undetermined coefficients is solved.

The method is algorithmic and is implemented in Mathematica. The resulting symbolic package PDERecursionOperator.m can be used to test the complete integrability of polynomial PDEs that can be written as nonlinear evolution equations. With PDERecursionOperator.m, recursion operators were obtained for several well-known nonlinear PDEs from mathematical physics and soliton theory.     

Post-quantum signature algorithms on noncommutative algebras,using difficulty of solving systems of quadratic equations

A recently proposed new concept for constructing algebraic signature schemes with a hidden group is used to develop two new post-quantum signature algorithms on four-dimensional and six-dimensional finite noncommutative associative algebras. As in the case of the post-quantum signature schemes of multivariate cryptography, the security of the introduced algorithms is based on the computational difficulty of solving systems of many quadratic equations (44 and 42) with many unknowns (40 and 36). The signature represents a pair of a natural number e and a vector S. The latter enters three times in the verification equation used, providing resistance to the forging signature attacks by using the value S as a fitting parameter. A public key is generated in the form of a set of vectors, each of which is calculated as the product of triples of secret vectors. With a special choice of these triples, a signer has the possibility of calculating a signature that satisfies the verification equation. The developed post-quantum signature algorithms are practical, having sufficiently small signatures (97 and 109 bytes), public keys (387 and 291 bytes), and secret keys (315 and 451 bytes). A significant difference from the public-key algorithms of multivariate cryptography is that in the developed signature schemes, the system of quadratic equations is derived from the formulas for generating the public-key elements in the form of a set of vectors of m-dimensional finite noncommutative algebra with an associative vector multiplication operation. The formulas define the system of n quadratic vector equations, which reduces to the system of m quadratic equations over a finite field.     

A REDUCE package for finding conserved densities of systems of nonlinear difference-difference equations

A computer algebra program for finding polynomial conserved densities of nonlinear difference-difference equations is presented. The algorithm is based on scaling properties and implemented in computer algebra system REDUCE. The package is applicable to systems of any number of nonlinear difference-difference equations.     

Application of Computer Algebra Systems for Stability Analysis of Difference Schemes on Curvilinear Grids

The paper deals with problems arising in the application of the computer algebra systems for the symbolic–numeric stability analysis of difference schemes and schemes of the finite-volume method approximating the two-dimensional Euler equations for compressible fluid flows on curvilinear spatial grids. We carry out a detailed comparison of the REDUCE 3.6 and Mathematica(Versions 2.2 and 3.0) from the point of view of their applicability to the solution of the above problems. We draw a conclusion that a preference should be given for Mathematica from the viewpoint of the execution of symbolic–numeric computations. We also describe in detail our new symbolic–numeric algorithm for stability investigation, which was implemented with the aid of Mathematica. The proposed method enables us to reduce the needed computer storage at the symbolic stages by a factor of about 20 as compared with the previous algorithms. A feature of the numerical stages is the use of the arithmetic of rational numbers, which enables us to avoid the accumulation of the roundoff errors. We present the examples of the application of the proposed symbolic–numeric method for stability analysis of very complex schemes of the finite-volume method on curvilinear grids, which are widely used in computational fluid dynamics.     

Symbolic computation of hyperbolic tangent solutions for nonlinear differential-difference equations

A new algorithm is presented to find exact traveling wave solutions of differential-difference equations in terms of tanh functions. For systems with parameters, the algorithm determines the conditions on the parameters so that the equations might admit polynomial solutions in tanh. Examples illustrate the key steps of the algorithm. Through discussion and example, parallels are drawn to the tanh-method for partial differential equations. The new algorithm is implemented in Mathematica. The package DDESpecialSolutions.m can be used to automatically compute traveling wave solutions of nonlinear polynomial differential-difference equations. Use of the package, implementation issues, scope, and limitations of the software are addressed.

Program summary

Title of program: DDESpecialSolutions.mCatalogue identifier:ADUJProgram summary URL:http://cpc.cs.qub.ac.uk/summaries/ADUJProgram obtainable from:CPC Program Library, Queen's University of Belfast, N. IrelandDistribution format: tar.gzComputers: Created using a PC, but can be run on UNIX and Apple machinesOperating systems under which the program has been tested: Windows 2000 and Windows XPProgramming language used: Mathematica, version 3.0 or higherMemory required to execute with typical data: 9 MBNumber of processors used: 1Has the code been vectorised or parallelized?: NoNumber of lines in distributed program, including test data, etc.: 3221Number of bytes in distributed program, including test data, etc.: 23 745Nature of physical problem: The program computes exact solutions to differential-difference equations in terms of the tanh function. Such solutions describe particle vibrations in lattices, currents in electrical networks, pulses in biological chains, etc.Method of solution: After the differential-difference equation is put in a traveling frame of reference, the coefficients of a candidate polynomial solution in tanh are solved for. The resulting traveling wave solutions are tested by substitution into the original differential-difference equation.Restrictions on the complexity of the program: The system of differential-difference equations must be polynomial. Solutions are polynomial in tanh.Typical running time: The average run time of 16 cases (including the Toda, Volterra, and Ablowitz-Ladik lattices) is 0.228 seconds with a standard deviation of 0.165 seconds on a 2.4 GHz Pentium 4 with 512 MB RAM running Mathematica 4.1. The running time may vary considerably, depending on the complexity of the problem.     

New exact solutions for modified nonlinear dispersive equations mK(m,n) in higher dimensions spaces

With the use of some proper transformations and symbolic computation, we present a general and unified method for investigating the general modified nonlinear dispersive equations mK(m,n) in higher dimensions spaces. The work formally shows how to construct the general solutions and some special exact-solutions for mK(m,n) equations in higher dimensional spatial domains. The general solutions not only contain the solutions by Wazwaz [Math. Comput. Simulation 59 (2002) 519] but also contain many new compact and noncompact solutions.     

Symbolic algorithms for qualitative analysis of Markov decision processes with Büchi objectives

We consider Markov decision processes (MDPs) with Büchi (liveness) objectives. We consider the problem of computing the set of almost-sure winning states from where the objective can be ensured with probability 1. Our contributions are as follows: First, we present the first subquadratic symbolic algorithm to compute the almost-sure winning set for MDPs with Büchi objectives; our algorithm takes $O(n \cdot\sqrt{m})$ symbolic steps as compared to the previous known algorithm that takes O(n ²) symbolic steps, where n is the number of states and m is the number of edges of the MDP. In practice MDPs have constant out-degree, and then our symbolic algorithm takes $O(n \cdot\sqrt{n})$ symbolic steps, as compared to the previous known O(n ²) symbolic steps algorithm. Second, we present a new algorithm, namely win-lose algorithm, with the following two properties: (a) the algorithm iteratively computes subsets of the almost-sure winning set and its complement, as compared to all previous algorithms that discover the almost-sure winning set upon termination; and (b) requires $O(n \cdot\sqrt{K})$ symbolic steps, where K is the maximal number of edges of strongly connected components (scc’s) of the MDP. The win-lose algorithm requires symbolic computation of scc’s. Third, we improve the algorithm for symbolic scc computation; the previous known algorithm takes linear symbolic steps, and our new algorithm improves the constants associated with the linear number of steps. In the worst case the previous known algorithm takes 5?n symbolic steps, whereas our new algorithm takes 4?n symbolic steps.     

Connecting the 3D DGS Calques3D with the CAS Maple

Many (2D) Dynamic Geometry Systems (DGSs) are able to export numeric coordinates and equations with numeric coefficients to Computer Algebra Systems (CASs). Moreover, different approaches and systems that link (2D) DGSs with CASs, so that symbolic coordinates and equations with symbolic coefficients can be exported from the DGS to the CAS, already exist. Although the 3D DGS Calques3D can export numeric coordinates and equations with numeric coefficients to Maple and Mathematica, it cannot export symbolic coordinates and equations with symbolic coefficients. A connection between the 3D DGS Calques3D and the CAS Maple, that can handle symbolic coordinates and equations with symbolic coefficients, is presented here. Its main interest is to provide a convenient time-saving way to explore problems and directly obtain both algebraic and numeric data when dealing with a 3D extension of “ruler and compass geometry”. This link has not only educational purposes but mathematical ones, like mechanical theorem proving in geometry, geometric discovery (hypotheses completion), geometric loci finding… As far as we know, there is no comparable “symbolic” link in the 3D case, except the prototype 3D-LD (restricted to determining algebraic surfaces as geometric loci).     

Symbolic computation of exact solutions expressible in hyperbolic and elliptic functions for nonlinear PDEs

Algorithms are presented for the tanh- and sech-methods, which lead to closed-form solutions of nonlinear ordinary and partial differential equations (ODEs and PDEs). New algorithms are given to find exact polynomial solutions of ODEs and PDEs in terms of Jacobi’s elliptic functions.For systems with parameters, the algorithms determine the conditions on the parameters so that the differential equations admit polynomial solutions in tanh, sech, combinations thereof, Jacobi’s sn or cn functions. Examples illustrate key steps of the algorithms.The new algorithms are implemented in Mathematica. The package PDESpecialSolutions.m can be used to automatically compute new special solutions of nonlinear PDEs. Use of the package, implementation issues, scope, limitations, and future extensions of the software are addressed.A survey is given of related algorithms and symbolic software to compute exact solutions of nonlinear differential equations.     

Symbolic computation in studying stability of solutions of linear differential equations with periodic coefficients

An algorithm for symbolic computation of characteristic exponents of a linear system of differential equations with a periodic matrix represented by a power series in terms of a small parameter is discussed. The algorithm is based on the infinite determinant method. The corresponding procedures implemented in the Mathematica system and computation results related to the elliptic restricted four-body problem are presented.     

Succinct representation of regular languages by boolean automata

Boolean automata are a generalization of finite automata in the sense that the ‘next state’, i.e. the result of the transition function given a state and a letter, is not just a single state (deterministic automata) or a union of states (nondeterministic automata) but a boolean function of states. Boolean automata accept precisely regular languages; furthermore they correspond in a natural way to certain language equations as well as to sequential networks. We investigate the succinctness of representing regular languages by boolean automata. In particular, we show that for every deterministic automaton A with m states there exists a boolean automaton with [log₂m] states which accepts the reverse of the language accepted by A (m≥1). We also show that for every n≥1 there exists a boolean automation with n states such that the smallest deterministic automaton accepting the same language has 2⁽²ⁿ⁾ states; moreover this holds for an alphabet with only two letters.     

Time step integration algorithms with predetermined coefficients for second order equations

In this paper, the effect of using the predetermined coefficients in constructing time step integration algorithms suitable for linear second order differential equations based on the weighted residual method is investigated. The second order equations are manipulated directly. The displacement approximation is assumed to be in a form of polynomial in the time domain and some of the coefficients can be predetermined from the known initial conditions. The algorithms are constructed so that the approximate solutions are equivalent to the solutions given by the transformed first order equations. If there are m predetermined coefficients (in addition to the two initial conditions) and r unknown coefficients in the displacement approximation, it is shown that the formulation is consistent with a minimum order of accuracy m+r. The maximum order of accuracy achievable is m+2r. This can be related to the Padé approximations for the second order equations. Unconditionally stable algorithms equivalent to the generalized Padé approximations for the second order equations are presented. The order of accuracy is 2r−1 or 2r and it is required that m+1⩽r. The corresponding weighting parameters, weighting functions and additional weighting parameters for the Padé and generalized Padé approximations are given explicitly.     

Computing Stochastic Completion Fields in Linear-Time Using a Resolution Pyramid

We describe a linear-time algorithm for computing the likelihood that a completion joining two contour fragments passes through any given position and orientation in the image plane. Our algorithm is a resolution-pyramid-based method for solving a partial differential equation (PDE) characterizing a distribution of short, smooth completion shapes. The PDE consists of a set of independent advection equations in (x, y) coupled in the θ dimension by the diffusion equation. A previously described algorithm used a first-order, explicit finite difference scheme implemented on a rectangular grid. This algorithm required O(n³m) time for a grid of size n×n with m discrete orientations. Unfortunately, systematic error in solving the advection equations produced unwanted anisotropic smoothing in the (x, y) dimension. This resulted in visible artifacts in the completion fields. The amount of error and its dependence on θ have been previously characterized. We observe that by careful addition of extra spatial smoothing, the error can be made totally isotropic. The combined effect of this error and of intrinsic smoothness due to diffusion in the θ dimension is that the solution becomes smoother with increasing time, i.e., the high spatial frequencies drop out. By increasing Δx and Δt on a regular schedule, and using a second-order, implicit scheme for the diffusion term, it is possible to solve the modified PDE in O(n²m) time, i.e., time linear in the problem size. Using current hardware and for problems of typical size, this means that a solution which previously took 1 h to compute can now be computed in about 2 min.     

Galois Action on Solutions of a Differential Equation

Consider a second-order differential equation of the form y″ + ay ′ + by = 0 with a, b ϵ Q(x). Kovacic's algorithm tries to compute a solution of the associated Riccati equation that is algebraic and of minimal degree over Q̄ (x). The coefficients of the monic irreducible polynomial of this solution are in C(x), where C is a finite algebraic extension of Q. In this paper we give a bound for the degree of the extension C ⊃ Q. Similar results are obtained for third-order differential equations.     

Efficient decomposition of separable algebras

We present new, efficient algorithms for computations on separable matrix algebras over infinite fields. We provide a probabilistic method of the Monte Carlo type to find a generator for the center of a given algebra $\text{A}\text{⊆}\text{F}{}^{\mathrm{m\times m}}$ over an infinite field $\text{F}$. The number of operations used is within a logarithmic factor of the cost of solving m×m systems of linear equations. A Las Vegas algorithm is also provided under the assumption that a basis and set of generators for the given algebra are available. These new techniques yield a partial factorization of the minimal polynomial of the generator that is computed, which may reduce the cost of computing simple components of the algebra in some cases.     

Deadline-based scheduling of periodic task systems on multiprocessors

We consider the problem of scheduling periodic task systems on multiprocessors and present a deadline-based scheduling algorithm for solving this problem. We show that our algorithm successfully schedules on m processors any periodic task system with utilization at most m²/(2m−1).