Search

This paper presents a discrete-time control design methodology for input-saturating systems using a Lyapunov function with dependence on present and past states. The approach is used to bypass the usual difficulty with full polynomial Lyapunov functions of expressing the problem in a convex way. Also polynomial controllers are allowed to depend on both present and past states. Furthermore, by considering saturation limits on the control action, the information about the relationship between the present and past states is introduced via Positivstellensatz multipliers. Sum-of-squares techniques and available semi-definite programming (SDP) software are used in order to find the controller. [ABSTRACT FROM PUBLISHER]

Finding solutions for fuzzy polynomial systems has recently received much attention and many efforts have been made to make the available algorithms for solving such problems more and more efficient. In the present paper, Wu's algorithm is introduced as a solution procedure to obtain fuzzy polynomial systems solutions. In this approach, the parametric form of the problem is first obtained from the computation of r-cuts of fuzzy polynomials. Wu's algorithm is then applied in order to convert the parametric form of a fuzzy polynomial system into a finite number of characteristic sets. We then have the right relation between solutions of these sets and those of the polynomial system. The most outstanding advantage of the proposed method lies in the fact that it leads to solve triangular sets amenable to easy solution. [ABSTRACT FROM AUTHOR]

In this paper, we consider controllability of discrete-time polynomial systems. First, we present a forward accessibility (local reachability) condition that can be verified in finite time, in contrast to conventional conditions. Second, we give a backward accessibility (local controllability) condition for an invertible system and a condition to verify invertibility. Finally, we derive sufficient conditions to test whether the forward accessible system is reachable and to test the backward accessible system is controllable. [ABSTRACT FROM AUTHOR]

In this work are studied periodic perturbations, depending on two parameters, of quadratic planar polynomial vector fields having an infinite heteroclinic cycle, which is an unbounded solution joining two saddle points at infinity. The global study envolving infinity is performed via the Poincaré compactification. The main result obtained states that for certain types of periodic perturbations, the perturbed system has quadratic heteroclinic tangencies and transverse intersections between the local stable and unstable manifolds of the hyperbolic periodic orbits at infinity. It implies, via the Birkhoff-Smale Theorem, in a complex dynamical behavior of the solutions of the perturbed system, in a finite part of the phase plane.Neste trabalho são estudadas perturbações periódicas, dependendo de dois parâmetros, de campos vetoriais polinomiais planares que possuem um ciclo heteroclínico infinito, que consiste de uma solução ilimitada, que conecta dois pontos de sela no infinito. O estudo global do campo vetorial, envolvendo o infinito, foi elaborado utilizando-se a compactificação de Poincaré. O resultado principal estabelece que, para certo tipo de perturbação periódica, o sistema apresenta tangências heteroclínicas e intersecção transversal das variedades invariantes de órbitas periódicas no infinito, o que implica, via o Teorema de Birkhoff-Smale, em um comportamento dinâmico bastante complexo das soluções do sistema perturbado, em uma região finita do plano de fase.

We introduce the concept of mode-κ generalized eigenvalues and eigenvectors of a tensor and prove some properties of such eigenpairs. In particular, we derive an upper bound for the number of equivalence classes of generalized tensor eigenpairs using mixed volume. Based on this bound and the structures of tensor eigenvalue problems, we propose two homotopy continuation type algorithms to solve tensor eigenproblems. With proper implementation, these methods can find all equivalence classes of isolated generalized eigenpairs and some generalized eigenpairs contained in the positive dimensional components (if there are any). We also introduce an algorithm that combines a heuristic approach and a Newton homotopy method to extract real generalized eigenpairs from the found complex generalized eigenpairs. A MATLAB software package, TenEig, has been developed to implement these methods. Numerical results are presented to illustrate the e ectiveness and efficiency of TenEig for computing complex or real generalized eigenpairs. [ABSTRACT FROM AUTHOR]

We study common composites of triangular polynomial and rational function systems with favorable effects under composition: polynomial degree growth. We construct classes of such systems that do not have common composites. This property makes them suitable for the construction of a recently proposed hash function. We give estimates for the number of collisions of this hash function using these systems. We also mention as future work the study of common composites of systems with sparse representation and pose an open problem related to their usability as hash functions. [ABSTRACT FROM AUTHOR]

We show that certain two-dimensional differential systems can be transformed to a system of Li'{e}nard type. This enables known criteria for the existence of a centre for Li'{e}nard systems to be exploited, so extending the range of techniques which are available for proving that conditions which are known to be necessary for a centre are also sufficient.

The main goal of this paper is to design a compensator able to restore the nominal behavior of a planar system, which is rendered chaotic by an unmeasurable sinusoidal disturbance input. To reach such a goal, some instruments, taken from algebraic geometry, are used to estimate the unmeasurable disturbance from the time derivatives of the output of the system and of the control input. Copyright © 2015 John Wiley & Sons, Ltd. [ABSTRACT FROM AUTHOR]

We describe a general approach to studying bifurcations of critical periods based on a complexification of the system and algorithms of computational algebra. Using this approach we obtain upper bounds on the number of critical periods of several families of cubic systems. In some cases we overcome the problem of nonradicality of a relevant ideal by moving it to a subalgebra generated by invariants of a group of linear transformations. [ABSTRACT FROM AUTHOR]

In this paper, fuzzy polynomial systems in dual form are considered and an algebraic approach for finding their solutions is presented. A dual fuzzy polynomial system in the form $$AX+B=CX+D $$ , where $$A, B, C,$$ and $$D$$ are fuzzy matrices, is converted to a system with real coefficients and variables first. Then, Wu's algorithm is used as a solution procedure for solving this system. This algorithm leads to solving characteristic sets that are amenable to easy solution. Finally, the accuracy of the presented algorithm is shown via some examples. [ABSTRACT FROM AUTHOR]

The paper deals with the problem of finding sparse solutions to systems of polynomial equations possibly perturbed by noise. In particular, we show how these solutions can be recovered from group-sparse solutions of a derived system of linear equations. Then, two approaches are considered to find these group-sparse solutions. The first one is based on a convex relaxation resulting in a second-order cone programming formulation which can benefit from efficient reweighting techniques for sparsity enhancement. For this approach, sufficient conditions for the exact recovery of the sparsest solution to the polynomial system are derived in the noiseless setting, while stable recovery results are obtained for the noisy case. Though lacking a similar analysis, the second approach provides a more computationally efficient algorithm based on a greedy strategy adding the groups one-by-one. With respect to previous work, the proposed methods recover the sparsest solution in a very short computing time while remaining at least as accurate in terms of the probability of success. This probability is empirically analyzed to emphasize the relationship between the ability of the methods to solve the polynomial system and the sparsity of the solution. [ABSTRACT FROM AUTHOR]

A real polynomial system with support W ⊂ Z n is called maximally positive if all its complex solutions are positive solutions. A support W having n + 2 elements is called a circuit. We previously showed that the number of non-degenerate positive solutions of a system supported on a circuit W ⊂ Z n is at most m ( W ) + 1 , where m ( W ) ≤ n is the degeneracy index of W . We prove that if a circuit W ⊂ Z n supports a maximally positive system with the maximal number m ( W ) + 1 of non-degenerate positive solutions, then it is unique up to the obvious action of the group of invertible integer affine transformations of Z n . In the general case, we prove that any maximally positive system supported on a circuit can be obtained from another one having the maximal number of positive solutions by means of some elementary transformations. As a consequence, we get for each n and up to the above action a finite list of circuits W ⊂ Z n which can support maximally positive polynomial systems. We observe that the coefficients of the primitive affine relation of such circuit have absolute value 1 or 2 and make a conjecture in the general case for supports of maximally positive systems. [ABSTRACT FROM AUTHOR]

We improve the local generic position method for isolating the real roots of a zero-dimensional bivariate polynomial system with two polynomials and extend the method to general zero-dimensional polynomial systems. The method mainly involves resultant computation and real root isolation of univariate polynomial equations. The roots of the system have a linear univariate representation. The complexity of the method is O ˜ B ( N 10 ) for the bivariate case, where N = max ⁡ ( d , τ ) , d resp., τ is an upper bound on the degree, resp., the maximal coefficient bitsize of the input polynomials. The algorithm is certified with probability 1 in the multivariate case. The implementation shows that the method is efficient, especially for bivariate polynomial systems. [ABSTRACT FROM AUTHOR]

The main goal of this paper is to compute a class of polynomial vector fields, whose associated dynamical system has a given affine variety as attractive and invariant set, a given point in such an affine variety as invariant and attractive and another given affine variety as invariant set, solving the application of this technique in the robotic area. This objective is reached by using some tools taken from algebraic geometry. Practical examples of how these vector fields can be computed are reported. Moreover, by using these techniques, two feedback control laws, respectively, for a unicycle-like mobile robot and for a car-like mobile robot, which make them move, within the workspace, approaching to a selected algebraic curve, are given. [ABSTRACT FROM PUBLISHER]

We consider a pictorial edge-matching puzzles, in which the goal is to arrange a collection of puzzle pieces with colored edges so that the colors match along the edges of adjacent pieces. We devise an algebraic representation for this problem and provide conditions under which it exactly characterizes a puzzle. Using the new representation, we recast the combinatorial, discrete problem of solving puzzles as a global, polynomial system of equations with continuous variables. We further propose new algorithms for generating approximate solutions to the continuous problem by solving a sequence of convex relaxations. [ABSTRACT FROM AUTHOR]

This paper studies finite- as well as infinite-time horizon nonzero-sum polynomial differential games. In both cases, we explore the so-called state-dependent Riccati equations to find a set of strategies that guarantee an open-loop Nash equilibrium for this particular class of nonlinear games. Such a method presents advantages in simplicity of the design of equilibrium strategies and yields computationally effective solution algorithms. We demonstrate that this solution leads the game to an ε - or quasi-equilibrium- and provide an upper bound for this ε quantity. The proposed solution is given as a set of N coupled polynomial Riccati-like state-dependent differential equations, where each equation includes a p -linear form tensor representation for its polynomial part. We provide an algorithm for finding the solution of the state-dependent algebraic equation in the infinite-time case based on a Hamiltonian approach and give conditions on the existence of such stabilizing solutions for a third order polynomial. A numerical example is presented to illustrate effectiveness of the approach. [ABSTRACT FROM AUTHOR]

We examine several of the normal-form multivariate polynomial rootfinding methods of Telen, Mourrain, and Van Barel and some variants of those methods. We analyze the performance of these variants in terms of their asymptotic temporal complexity as well as speed and accuracy on a wide range of numerical experiments. All variants of the algorithm are problematic for systems in which many roots are very close together. We analyze the performance on one such system in detail, namely the "devastating example" that Noferini and Townsend used to demonstrate instability of resultant-based methods. We demonstrate that the problems with the devastating example arise from having a large number of roots very close to each other. We also show that a small number of clustered roots does not cause numerical problems for these methods. We conjecture that the clustering of many roots is the primary source of problematic examples. [ABSTRACT FROM AUTHOR]

Given a polynomial system f : C N → C n , the methods of numerical algebraic geometry produce numerical approximations of the isolated solutions of f ( z ) = 0 , as well as points on any positive-dimensional components of the solution set, V ( f ) . Some of these methods are guaranteed to find all isolated solutions (nonsingular and singular alike), while others may not find singular solutions. One of the most recent advances in this field is regeneration, an equation-by-equation solver that is often more efficient than other methods. However, the basic form of regeneration will not necessarily find all isolated singular solutions of a polynomial system without the additional cost of using deflation. The aim of this article is two-fold. First, more generally, we consider the use of perturbed homotopies for solving polynomial systems. In particular, we propose first solving a perturbed version of the polynomial system, followed by a parameter homotopy to remove the perturbation. Such perturbed homotopies are sometimes more efficient than regular homotopies, though they can also be less efficient. Second, a useful consequence is that the application of this perturbation to regeneration will yield all isolated solutions, including all singular isolated solutions. This version of regeneration – perturbed regeneration – can decrease the efficiency of regeneration but increases its applicability. [ABSTRACT FROM AUTHOR]

The problem of H∞ filter design for continuous-time nonlinear polynomial systems is addressed in this paper. The aim is to design a full order dynamic filter that depends polynomially on the filter states. The strategy relies on the use of a quadratic Lyapunov function and an inequality condition that assures an H∞ performance bound for the augmented polynomial system, composed by the original system and the filter to be designed, in a regional (local) context. Then, by using Finsler's lemma, an enlarged parameter space is created, where the Lyapunov matrix appears separated from the system matrices in the conditions. Imposing structural constraints to the decision variables and fixing some values for a scalar parameter, design conditions for the H∞ filter can be obtained in terms of linear matrix inequalities. As illustrated by numerical experiments, the proposed conditions can improve the H∞ performance provided by standard linear filtering by including the polynomial terms in the filter dynamics. [ABSTRACT FROM AUTHOR]

In this paper, we generalize the algorithm described by Rump and Graillat, as well as our previous work on verifying breadth-one singular solutions of polynomial systems, to compute verified and narrow error bounds such that a slightly perturbed system is guaranteed to possess an isolated singular solution within computed error bounds. Our verification method is based on deflation techniques using smoothing parameters. We demonstrate the performance of the algorithm for polynomial systems with singular solutions of multiplicity up to hundreds. [ABSTRACT FROM AUTHOR]

The primary goal of this paper is to describe the classes of all polynomial vector fields such that the associated dynamical system admits some polynomial Lyapunov functionv(x). By fixing or constraining the time derivative ofv(x) in different ways, several different cases are studied. Hints are given about how to use the results for stability analysis and for non-polynomial systems. [ABSTRACT FROM PUBLISHER]

We investigate the problem of integrability for a family of three-dimensional autonomous polynomial systems of ODEs. Necessary and sufficient conditions for the existence of two independent analytic first integrals for systems of the family are given. The linearizability of the systems is studied as well. [ABSTRACT FROM AUTHOR]

The problem of designing an optimal filter for a class of nonlinear systems confused with white Gaussian noise over linear time delayed observations is presented in this paper. Output observations may or may not experience sensor delays due to a random variable which is modeled as a Bernoulli distributed one that takes the quantities of zero and one. A closed form of this filter is obtained by expressing the conditional expectation of polynomial terms as a function of its expectation and covariance matrix. As a particular case, finite-dimensional filtering equations are obtained for a third degree polynomial function. Numerical simulations are performed on an induction motor in order to show the effectiveness of proposed filter. [ABSTRACT FROM AUTHOR]

Abstract: We present a certified and complete algorithm to compute arrangements of real planar algebraic curves. It computes the decomposition of the plane induced by a finite number of algebraic curves in terms of a cylindrical algebraic decomposition. From a high-level perspective, the overall method splits into two main subroutines, namely an algorithm denoted Bisolve to isolate the real solutions of a zero-dimensional bivariate system, and an algorithm denoted GeoTop to compute the topology of a single algebraic curve. Compared to existing approaches based on elimination techniques, we considerably improve the corresponding lifting steps in both subroutines. As a result, generic position of the input system is never assumed, and thus our algorithm never demands for any change of coordinates. In addition, we significantly limit the types of symbolic operations involved, that is, we only use resultant and computations as purely symbolic operations. The latter results are achieved by combining techniques from different fields such as (modular) symbolic computation, numerical analysis and algebraic geometry. We have implemented our algorithms as prototypical contributions to the C++-project Cgal. We exploit graphics hardware to expedite the remaining symbolic computations. We have also compared our implementation with the current reference implementations, that is, Lgp and Maple’s Isolate for polynomial system solving, and Cgal’s bivariate algebraic kernel for analyses and arrangement computations of algebraic curves. For various series of challenging instances, our exhaustive experiments show that the new implementations outperform the existing ones. [Copyright &y& Elsevier]

We describe, for the first time, a completely rigorous homotopy (path-following) algorithm (in the Turing machine model) to find approximate zeros of systems of polynomial equations. If the coordinates of the input systems and the initial zero are rational our algorithm involves only rational computations, and if the homotopy is well posed an approximate zero with integer coordinates of the target system is obtained. The total bit complexity is linear in the length of the path in the condition metric, and polynomial in the logarithm of the maximum of the condition number along the path, and in the size of the input. [ABSTRACT FROM AUTHOR]

Abstract: In this paper we describe how to improve the performance of the symbolic–numeric method in [19,20] for computing the multiplicity structure and refining approximate isolated singular solutions in the breadth-one case. By introducing a parameterized deflated system with smoothing parameters, we generalize the algorithm in [33] to compute verified error bounds such that a slightly perturbed polynomial system is guaranteed to have a breadth-one multiple root within the computed bounds. [Copyright &y& Elsevier]

This work presents an approach for estimating the domain of attraction for polynomial systems with state and control-signal constraints, including saturation. In many problems, it is possible to derive global stability properties for such systems, neglecting constraints. Consideration of the constraints usually makes the problem much more complicated. In this paper, the stability analysis performed for the unconstrained case is used for the problem as a whole. For application of the method, there are powerful computational tools that can be employed in cases of polynomial systems. The technique is not only valid for the analysis of equilibrium points, but also for other attractors, such as limit cycles. As examples, the domain of attraction for given control laws is estimated for both a nonlinear DC-DC boost converter and for a boost inverter. [ABSTRACT FROM AUTHOR]

Abstract: In this paper, we consider systems of algebraic and non-linear partial differential equations and inequations. We decompose these systems into so-called simple subsystems and thereby partition the set of solutions. For algebraic systems, simplicity means triangularity, square-freeness and non-vanishing initials. Differential simplicity extends algebraic simplicity with involutivity. We build upon the constructive ideas of J. M. Thomas and develop them into a new algorithm for disjoint decomposition. The present paper is a revised version of and includes the proofs of correctness and termination of our decomposition algorithm. In addition, we illustrate the algorithm with further instructive examples and describe its Maple implementation together with an experimental comparison to some other triangular decomposition algorithms. [Copyright &y& Elsevier]

Abstract: In this paper, we propose a new design strategy for nonlinear systems with input saturation. The resulting nonlinear controllers are locally asymptotically stabilizing the origin. The proposed methodology is based on exact feedback linearization which is used to reformulate the nonlinear system as a linear system having state-dependent input saturation. Linear saturating state feedback controllers and soft variable-structure controllers are developed based on this system formulation. The resulting convex optimization problems can be written in terms of linear matrix inequalities and sum of squares conditions for which efficient solvers exist. Polynomial approximation based on Legendre polynomials is used to extend the methodology to a more general class of nonlinear systems. To demonstrate the benefit of this design method, a stabilizing controller for a single link manipulator with flexible joint is developed. [Copyright &y& Elsevier]

Abstract: This paper is concerned with the filtering problem for polynomial systems. By means of Lyapunov theory and matrix inequality techniques, sufficient conditions are first obtained to ensure that the filtering error system is asymptotically stable and satisfies performance constraint. Then, a sufficient condition for the existence of desired filters is established with a free matrix introduced, which will greatly facilitate the design of filter matrices. By virtue of sum-of-squares (SOS) approaches, a convergent iterative algorithm is developed to tackle the polynomial  filtering problem. Note that the approach can be efficiently implemented by means of recently developed SOS decomposition techniques, and the filter matrices can be designed explicitly. Finally, a numerical example is given to illustrate the main results of this paper. [Copyright &y& Elsevier]

Abstract: We present a method for finding optimal controlled variables, which are polynomial combinations of measurements. Controlling these variables gives optimal steady state operation. Our work extends the concept of self-optimizing control; starting from the first-order necessary optimality conditions, any unknown variables are eliminated using elimination theory for polynomial systems to obtain invariant variable combinations, which contain only known variables (measurements). If a disturbance causes the active constraints to change, the invariants may be used to identify, and switch to the right region. This makes the method applicable over a wide disturbance range with changing active sets. The procedure is applied to two case studies of continuous stirred tank reactors. [Copyright &y& Elsevier]

Abstract: Searching for the roots of (piecewise) polynomial systems of equations is a crucial problem in computer-aided design (CAD), and an efficient solution is in strong demand. Subdivision solvers are frequently used to achieve this goal; however, the subdivision process is expensive, and a vast number of subdivisions is to be expected, especially for higher-dimensional systems. Two blending schemes that efficiently reveal domains that cannot contribute by any root, and therefore significantly reduce the number of subdivisions, are proposed. Using a simple linear blend of functions of the given polynomial system, a function is sought after to be no-root contributing, with all control points of its Bernstein–Bézier representation of the same sign. If such a function exists, the domain is purged away from the subdivision process. The applicability is demonstrated on several CAD benchmark problems, namely surface–surface–surface intersection (SSSI) and surface–curve intersection (SCI) problems, computation of the Hausdorff distance of two planar curves, or some kinematic-inspired tasks. [Copyright &y& Elsevier]

Path tracking is the fundamental computational tool in homotopy continuation and is therefore key in most algorithms in the emerging field of numerical algebraic geometry. Though the basic notions of predictor-corrector methods have been known for years, there is still much to be considered, particularly in the specialized algebraic setting of solving polynomial systems. In this article, the effects of the choice of predictor method on the performance of a tracker is analyzed, and details for using Runge-Kutta methods in conjunction with adaptive precision are provided. These methods have been implemented in the Bertini software package, and several examples are described. [ABSTRACT FROM AUTHOR]

The aim of this paper is to present a symbolic computational algorithm that will allow us to deal with the feedback stabilization problem for continuous non-linear polynomial systems. The overall approach is based on a methodology that checks the positivity of a given polynomial. [ABSTRACT FROM PUBLISHER]

Abstract: Numerical data structures for positive dimensional solution sets of polynomial systems are sets of generic points cut out by random planes of complementary dimension. We may represent the linear spaces defined by those planes either by explicit linear equations or in parametric form. These descriptions are respectively called extrinsic and intrinsic representations. While intrinsic representations lower the cost of the linear algebra operations, we observe worse condition numbers. In this paper we describe the local adaptation of intrinsic coordinates to improve the numerical conditioning of sampling algebraic sets. Local intrinsic coordinates also lead to a better step size control. We illustrate our results with Maple experiments and computations with PHCpack on some benchmark polynomial systems. [Copyright &y& Elsevier]