Search

The notions of equivalence and strict equivalence for order one differential equations are introduced. The more explicit notion of strict equivalence is applied to examples and questions concerning autonomous equations and equations having the Painleve property. The order one equation determines an algebraic curve. If this curve has genus zero or one, then it is difficult to verify strict equivalence. However, for higher genus strict equivalence can be tested by an algorithm sketched in the text. For autonomous equations, testing strict equivalence and the existence of algebraic solutions are shown to be algorithmic., 19 pages

Let K be a field of characteristic zero, alpha algebraic of degree n over K. Given a proper parametrization psi of a rational curve C, we present a new algorithm to compute the hypercircle associated to the parametrization psi. As a consequence, we can decide if the curve C is defined over K and, if not, to compute the minimum field of definition of C containing K. The algorithm exploits the conjugate curves of C but avoids computation in the normal closure of K(alpha) over K., 16 pages

We give a uniform method for the two problems of counting the connected and irreducible components of complex algebraic varieties. Our algorithms are purely algebraic, i.e., they use only the field structure of C. They work in parallel polynomial time, i.e., they can be implemented by algebraic circuits of polynomial depth. The design of our algorithms relies on the concept of algebraic differential forms. A further important building block is an algorithm of Szántó computing a variant of characteristic sets. Furthermore, we use these methods to obtain a parallel polynomial time algorithm for computing the Hilbert polynomial of a projective variety which is arithmetically Cohen–Macaulay.

Cylindrical algebraic decomposition requires many very time consuming operations, including resultant computation, polynomial factorization, algebraic polynomial gcd computation and polynomial real root isolation. We show how the time for algebraic polynomial real root isolation can be greatly reduced by using interval arithmetic instead of exact computation. This substantially reduces the overall time for cylindrical algebraic decomposition.

By means of Gröbner basis techniques algorithms for solving various problems concerning subfields K(g):=K(g1, …,gm) of a rational function field K(x):=K(x1, …,xn) are derived: computing canonical generating sets, deciding field membership, computing the degree and separability degree resp. the transcendence degree and a transcendence basis of K(x)/K(g), deciding whetherf∈K(x) is algebraic or transcendental over K(g), computing minimal polynomials, and deciding whether K(g) contains elements of a “particular structure”, e.g. monic univariate polynomials of fixed degree. The essential idea is to reduce these problems to questions concerning an ideal of a polynomial ring; connections between minimal primary decompositions over K(x) of this ideal and intermediate fields of K(g) and K(x) are given. In the last section some practical considerations concerning the use of the algorithms are discussed.

With the exception of a finite set of finite differential Galois groups, if an irreducible linear differential equation L(y) = 0 of prime order with unimodular differential Galois group has a Liouvillian solution, then all algebraic solutions of smallest degree of the associated Riccati equation are solutions of a unique minimal polynomial. If the coefficients of L (y) = 0 are in Q (α)(x) ⊂ Q(x) this unique minimal polynomial is also defined over Q(α)(x). In the finite number of exceptions all solutions of L(y) = 0 are algebraic and in each case one can apriori give an extension Q(β)(x) over which the minimal polynomial of an algebraic solution of L(y) = 0 can be computed.

Let L(y) = b be a linear differential equation with coefficients in a differential field K. We discuss the problem of deciding if such an equation has a non-zero solution in K and give a decision procedure in case K is an elementary extension of the field of rational functions or is an algebraic extension of a transcendental liouvillian extension of the field of rational functions. We show how one can use this result to give a procedure to find a basis for the space of solutions, liouvillian over K, of L(y) = 0 where K is such a field and L(y) has coefficients in K.

It was proved over a century ago that an algebraic curve C in the real projective plane, of degree n, has at most (n-1)(n-2)2+1 connected components. If C is nonslngular, then each of its commponents is a topological circle. A circle in the projectlve plane either separates it into a disk (the interior of the circle) and a Mobius band (the circle's exterior), or does not separate it. In the former case, the circle is an oval. If C is nonsingular, then all its components are ovals if n is even, and all except one are ovals if n is odd. An oval is included in another if it lies in the other's interior. The topological type of (a nonsingular) C is completely determined by (1) the parity of n, (2) how many ovals it has, and (3) the partial ordering of its ovals by inclusion. We present an algorithm which, given a homogeneous polinomial f(x,y,z) of degree n with integer coefficients, checks whether tlte curve defined hy f = 0 is nonsingular and if so, computes its topological type. The algorithm's maximum computing time is O(n^2^7L(d)^3), where d is the sum of the absolute values of the integer coofficients of f, and L(d) is the length of d.

We present a modular algorithm for computing the greatest common divisor of two polynomials over an algebraic number field. Our algorithm is an application of ideas of Brown and Collins. We use the Weinberger-Rothschild homomorphic scheme with the important change that we avoid factoring the modular image of the minimal polynomial. We perform a computing time analysis and report some empirical computing times.

Let F(x,y) be a polynomial over a field K and m a nonnegative integer. We call a polynomial g over K an m-near solution of F(x,y) if there exists a [email protected]?K such that F(x,g)=cx^m, and the number c is called an m-value of F(x,y) corresponding to g. In particular, c can be 0. Hence, by viewing F(x,y)=0 as a polynomial equation over K[x] with variable y, every solution of the equation F(x,y)=0 in K[x] is also an m-near solution. We provide an algorithm that gives all m-near solutions of a given polynomial F(x,y) over K, and this algorithm is polynomial time reducible to solving one variable equations over K. We introduce approximate solutions to analyze the algorithm. We also give some interesting properties of approximate solutions.

In this paper we investigate the problem of determining rational parametrizations of plane algebraic curves over an algebraic extension of least degree over the field of definition. This problem reduces to the problem of finding simple points with coordinates in the field of definition on algebraic curves of genus 0. Consequently we are also able to decide parametrizability over the reals. We generalize a classical theorem of Hilbert and Hurwitz about birational transformations. An efficient algorithm for computing such optimal parametrizations is presented.

Let K be a characteristic zero field, let ϕ(t) be a birational parametrization ϕ(t) of a K-definable curve C with coefficients in an algebraic extension K(α) over K. We propose an algorithm to solve the optimization problem of computing the affine reparametrization t→at+b such that ϕ(at+b) has coefficients over an extension of K with algebraic degree as small as possible.