Algebraic transformation of differential characteristic decompositions from one ranking to another

We propose an algorithm for transforming a characteristic decomposition of a radical differential ideal from one ranking into another. The algorithm is based on a new bound: we show that, in the ordinary case, for any ranking, the order of each element of the canonical characteristic set of a characterizable differential ideal is bounded by the order of the ideal. Applying this bound, the algorithm determines the number of times one needs to differentiate the given differential polynomials, so that a characteristic decomposition w.r.t. the target ranking could be computed by a purely algebraic algorithm (that is, without further differentiations). We also propose a factorization-free algorithm for computing the canonical characteristic set of a characterizable differential ideal represented as a radical ideal by a set of generators. This algorithm is not restricted to the ordinary case and is applicable for an arbitrary ranking.     

Gröbner fan and universal characteristic sets of prime differential ideals

The concepts of Gröbner cone, Gröbner fan, and universal Gröbner basis are generalized to the case of characteristic sets of prime differential ideals. It is shown that for each cone there exists a set of polynomials which is characteristic for every ranking from this cone; this set is called a strong characteristic set, and an algorithm for its construction is given. Next, it is shown that the set of all differential Gröbner cones is finite for any differential ideal. A subset of the ideal is called its universal characteristic set, if it contains a characteristic set of the ideal w.r.t. any ranking. It is shown that every prime differential ideal has a finite universal characteristic set, and an algorithm for its construction is given. The question of minimality of this set is addressed in an example. The example also suggests that construction of a universal characteristic set can help in solving a system of nonlinear PDE’s, as well as maybe providing a means for more efficient parallel computation of characteristic sets.     

Triviality and Dimension of a System of Algebraic Differential Equations

We present an algorithm that tests the triviality and computes the differential dimension and a parametric set for an ordinary differential polynomial ideal. No factorization is needed. The basic operation in our algorithm is the test of invertibility of an algebraic polynomial with respect to a finite set of algebraic polynomials. The algorithm has been implemented in the computer algebra system MAPLE and has been tested successfully on many examples.     

Computing differential characteristic sets by change of ordering

We describe an algorithm for converting a characteristic set of a prime differential ideal from one ranking into another. This algorithm was implemented in many different languages and has been applied within various software and projects. It permitted to solve formerly unsolved problems.     

Characteristic set method for differential–difference polynomial systems

In this paper, we present a characteristic set method for mixed differential and difference polynomial systems. We introduce the concepts of coherent, regular, proper irreducible, and strongly irreducible ascending chains and study their properties. We give an algorithm which can be used to decompose the zero set for a finitely generated differential and difference polynomial sets into the union of the zero sets of regular and consistent ascending chains. As a consequence, we solve the perfect ideal membership problem for differential and difference polynomials.     

A bound for the Rosenfeld–Gröbner algorithm

We consider the Rosenfeld–Gröbner algorithm for computing a regular decomposition of a radical differential ideal generated by a set of ordinary differential polynomials in n$n$ indeterminates. For a set of ordinary differential polynomials F$F$, let M(F)$M\left(F\right)$ be the sum of maximal orders of differential indeterminates occurring in F$F$. We propose a modification of the Rosenfeld–Gröbner algorithm, in which for every intermediate polynomial system F$F$, the bound M(F)?(n−1)!M(_F0)$M\left(F\right)?(n-1)!M\left(F_0\right)$ holds, where _F0$F_0$ is the initial set of generators of the radical ideal. In particular, the resulting regular systems satisfy the bound. Since regular ideals can be decomposed into characterizable components algebraically, the bound also holds for the orders of derivatives occurring in a characteristic decomposition of a radical differential ideal.     

Unmixed-dimensional Decomposition of a Finitely Generated Perfect Differential Ideal

We present an algorithm that computes an unmixed-dimensional decomposition of a finitely generated perfect differential ideal I. Each I_iin the decompositionI  = I₁ ∩   ∩ I_kis given by its characteristic set. This decomposition is a generalization of the differential case of Kalkbrener’s decomposition. We use a different approach. The basic operation in our algorithm is the computation of the inverse of an algebraic polynomial with respect to a finite set of algebraic polynomials. No factorization is needed. Some of the main problems in polynomial ideal theory can be solved by means of this decomposition: we show how the radical membership can be decided, a characteristic set of a prime differential ideal can be selected, and the differential dimension with a parametric set of a differential ideal can be read. The algorithm has been implemented in the computer algebra system MAPLE and has been tested successfully on many examples.     

On computing absolutely irreducible components of algebraic varieties with parameters

This paper presents a new algorithm for computing absolutely irreducible components of n-dimensional algebraic varieties defined implicitly by parametric homogeneous polynomial equations over ${\mathbb{Q}}$ , the field of rational numbers. The algorithm computes a finite partition of the parameters space into constructible sets such that the absolutely irreducible components are given uniformly in each constructible set. Each component will be represented by two items: first by a parametric representative system, i.e., the equations that define the component and second by a parametric effective generic point which gives a parametric rational univariate representation of the elements of the component. The number of absolutely irreducible components is constant in each constructible set. The complexity bound of this algorithm is ${\delta^{O(r^4)}d^{r^4d^{O(n^3)}}}$ , being double exponential in n, where d (resp. δ) is an upper bound on the degrees of the input parametric polynomials w.r.t. the main n variables (resp. w.r.t. r parameters).     

Parameter identifiability of nonlinear systems: the role of initial conditions

Identifiability is a fundamental prerequisite for model identification; it concerns uniqueness of the model parameters determined from the input-output data, under ideal conditions of noise-free observations and error-free model structure. In the late 1980s concepts of differential algebra have been introduced in control and system theory. Recently, differential algebra tools have been applied to study the identifiability of dynamic systems described by polynomial equations. These methods all exploit the characteristic set of the differential ideal generated by the polynomials defining the system. In this paper, it will be shown that the identifiability test procedures based on differential algebra may fail for systems which are started at specific initial conditions and that this problem is strictly related to the accessibility of the system from the given initial conditions. In particular, when the system is not accessible from the given initial conditions, the ideal I having as generators the polynomials defining the dynamic system may not correctly describe the manifold of the solution. In this case a new ideal that includes all differential polynomials vanishing at the solution of the dynamic system started from the initial conditions should be calculated. An identifiability test is proposed which works, under certain technical hypothesis, also for systems with specific initial conditions.     

Linear complete differential resultants and the implicitization of linear DPPEs

The linear complete differential resultant of a finite set of linear ordinary differential polynomials is defined. We study the computation by linear complete differential resultants of the implicit equation of a system of n$n$ linear differential polynomial parametric equations in n−1$n-1$ differential parameters. We give necessary conditions to ensure properness of the system of differential polynomial parametric equations.     

Some results on the stabilization of switched systems

This paper deals with the stabilization of switched systems with respect to (w.r.t.) compact sets. We show that the switched system is stabilizable w.r.t. a compact set by means of a family of switched signals if and only if a certain control affine system whose admissible controls take values in a polytope is asymptotically controllable to that set. In addition we present a control algorithm that based on a family of open-loop controls which stabilizes the aforementioned control system, a model of the system and the states of the switched system, generates switching signals which stabilize the switched system in a practical sense. We also give results about the convergence and the robustness of the algorithm.     

A characteristic set method for ordinary difference polynomial systems

We prove several basic properties for difference ascending chains, including a necessary and sufficient condition for an ascending chain to be the characteristic set of its saturation ideal and a necessary and sufficient condition for an ascending chain to be the characteristic set of a reflexive prime ideal. Based on these properties, we propose an algorithm to decompose the zero set of a finite set of difference polynomials into the union of zero sets of certain ascending chains. This decomposition algorithm is implemented and used to solve the perfect ideal membership problem, and to prove certain difference identities automatically.     

Characterizable Radical Differential Ideals and Some Properties of Characteristic Sets

In this paper, the characterizability of radical differential ideals is discussed and the characterizability criterion for them is proved. This criterion is based on the known algorithm for decomposing a radical differential ideal into characterizable components. The inclusion problem is also considered, in the light of which the algorithm for minimal characteristic decomposition of principal ideals is discussed. This algorithm is improved by using the proven characterizability criterion. Differential and algebraic properties of autoreduced sets are discussed, and the structure of differential chains and characteristic sets of radical differential ideals is revealed. The corresponding algorithms are constructed and discussed.     

Identification of partial differential equation models for a class of multiscale spatio-temporal dynamical systems

In this article, the identification of a class of multiscale spatio-temporal dynamical systems, which incorporate multiple spatial scales, from observations is studied. The proposed approach is a combination of Adams integration and an orthogonal least squares algorithm, in which the multiscale operators are expanded, using polynomials as basis functions, and the spatial derivatives are estimated by finite difference methods. The coefficients of the polynomials can vary with respect to the space domain to represent the feature of multiple scales involved in the system dynamics and are approximated using a B-spline wavelet multi-resolution analysis. The resulting identified models of the spatio-temporal evolution form a system of partial differential equations with different spatial scales. Examples are provided to demonstrate the efficiency of the proposed method.     

Zeros of equivariant vector fields: Algorithms for an invariant approach

We present a symbolic algorithm to solve for the zeros of a polynomial vector field equivariant with respect to a finite subgroup of O (n). We prove that the module of equivariant. polynomial maps for a finite matrix group is Cohen-Macaulay and give an algorithm to compute a fundamental basis. Equivariant normal forms are easily computed from this basis. We use this basis to transform the problem of finding the zeros of an equivariant map to the problem of finding zeros of a set of invariant polynomials. Solving for the values of fundamental polynomial invariants at the zeros effectively reduces each group orbit of solutions to a single point. Our emphasis is on a computationally effective algorithm and we present our techniques applied to two examples.     

Standard Bases in Power Series Rings: Uniqueness and Superfluous Critical Pairs

We show that w.r.t. fixed admissible term order, every ideal in a ring of power series over a field has a unique reduced standard basis. Furthermore, we show that a finite set of power series whose lowest terms are pairwise relatively prime is a standard basis. Finally, a second criterion for detecting superfluous critical pairs is discussed. As a spinoff, we obtain a Gröbner basis criterion that does not seem to have been stated before.     

A DESCRIPTION OF A SET OF HYPOTHESES FOR SYSTEM IDENTIFICATION PROBLEM*

This paper concerns the system identification process which is a specific form of the hypothetico-deductive process. More specifically, this paper deals with the inductive inference, i.e., with the process of generating a set of hypotheses σ(E) that explain a given finite set of input-output experiments performed on a finite sequential system being identified. It is shown that Sεσ(E) if and only if there exists a homomorphism of a basic hypothesis explaining E, into S. Next, a set of hypotheses σ¹(E). defined as follows: Sεσ¹(E) if E is structure-complete w.r.t. S, is considered. Then it is proved that Sεσ¹(E) if and only if there exists a full homomorphism of a basic hypothesis onto S. Some important methodological consequences of obtained results are derived. Finally, relationship linking the properties of a system identification algorithm is investigated.     

Simple robust stability tests for polynomials with real parameter uncertainty

In this paper we consider several problems related to the robust stability of polynomials whose coefficients depend on real parameters. We first show that if these parameters appear linearly in the coefficients, the computation of the largest stability hypercube with a fixed centre does not require a frequency ‘sweep’. Its size can be determined by considering a finite set of frequencies. We also demonstrate that for some polynomials where the coefficients themselves are polynomials in the parameters, the determination of stability can be made in a manner that involves a single frequency sweep and where at each frequency a finite number of simple tests are carried out. The methods are based on the Nyquist theorem and ‘value set’ ideas, and the approach provides analytical solutions.     

First-order logic characterization of program properties

A program is first-order reducible (FO-reducible) w.r.t. a set IC of integrity constraints if there exists a first-order theory T such that the set of models for T is exactly the set of intended models for the program w.r.t. all possible EDBs. In this case, we say that P is FO-reducible to T w.r.t. IC. For FO-reducible programs, it is possible to characterize, using first-order logic implications, properties of programs that are related to all possible EDBs as in the database context. These properties include, among others, containment of programs, independence of updates w.r.t. queries and integrity constraints, and characterization and implication of integrity constraints in programs, all of which have no known proof procedures. Therefore, many important problems formalized in a nonstandard logic can be dealt with by using the rich reservoir of first-order theorem-proving tools, provided that the program is FO-reducible. The following classes of programs are shown to be FO-reducible: (1) a stratified acyclic program P is FO-reducible to comp(P)∪IC w.r.t. IC for any set IC of constraints; (2) a general chained program P is FO-reducible to comp(P')∪IC w.r.t. certain acyclicity constraints IC; and (3) a bounded program P is FO-reducible to comp(P')∪IC w.r.t. any set IC of constraints, where P' is a nonrecursive program equivalent to P. Some heuristics for constructing FO-reducible programs are described     

Termination of the F5 algorithm

The F5 algorithm, which calculates the Gröbner basis of an ideal generated by homogeneous polynomials, was proposed by Faugère in 2002; simultaneously, the correctness of this algorithm was proved under the condition of termination. However, termination itself was demonstrated only for a regular sequence of polynomials. In this paper, it is proved that the algorithm terminates for any input data. First, it is shown that if the algorithm does not terminate, it eventually generates two polynomials where the first is a reductor for the second. However, it is not argued that such a reduction is permitted by all the criteria introduced in F5. Next, it is shown that if such a pair exists, then there exists another pair for which the reduction is permitted by all the criteria, which is impossible.