Given a field extension K/k of degree n we are interested in finding the subfields of K containing k. There can be more than polynomially many subfields. We introduce the notion of generating subfields, a set of up to n subfields whose intersections ...

A generalized criterion for signature related algorithms to compute Gröbner basis is proposed in this paper. Signature related algorithms are a popular kind of algorithms for computing Gröbner basis, including the famous F5 algorithm, the F5C algorithm, ...

We present the application of real quantifier elimination to formal verification and synthesis of continuous and switched dynamical systems. Through a series of case studies, we show how first-order formulas over the reals arise when formally analyzing ...

We present algorithmic, complexity and implementation results for the problem of isolating the real roots of a univariate polynomial in B_α ∈ L[y], where L=Qα is a simple algebraic extension of the rational numbers. We revisit two approaches for the ...

In this paper we propose a mechanisable technique for asymptotic stability analysis of continuous dynamical systems. We start from linearizing a continuous dynamical system, solving the Lyapunov matrix equation and then check whether the solution is ...

An iterative refinement approach is taken to rational linear system solving. Such methods produce, for each entry of the solution vector, a rational approximation with denominator a power of 2. From this the correct rational entry can be reconstructed. ...

We present a new algebraic algorithm for computing the discrete Fourier transform over arbitrary fields. It computes DFTs of infinitely many orders n in O(n log n) algebraic operations, while the complexity of a straightforward application of the known ...

There are several preliminary definitions for a Gröbner basis with inexact input since computing such a basis is one of the challenging problems in symbolic-numeric computations for several decades. A structured Gröbner basis is such a basis defined ...

In this paper we find division polynomials for Jacobi quartics. These curves are an alternate model for elliptic curves to the more common Weierstrass equation. Division polynomials for Weierstrass curves are well known, and the division polynomials we ...

The computation of a Gröbner basis of a polynomial ideal is known to be exponential space complete. We revisit the algorithm by Kühnle and Mayr using recent improvements of various degree bounds. The result is an algorithm which is exponential in the ...

We develop a new symbolic-numeric algorithm for the certification of singular isolated points, using their associated local ring structure and certified numerical computations. An improvement of an existing method to compute inverse systems is presented,...

The problem of computing a representation for a real polynomial as a sum of minimum number of squares of polynomials can be casted as finding a symmetric positive semidefinite real matrix of minimum rank subject to linear equality constraints. In this ...

This paper proposes a non-intrusive automatic parallelization framework for typeful and property-aware computer algebra systems. Automatic parallelization remains a promising computer program transformation for exploiting ubiquitous concurrency ...

In this paper, the concept of sparse differential resultant for a differentially essential system of differential polynomials is introduced and its properties are proved. In particular, a degree bound for the sparse differential resultant is given. ...

We continue to investigate which polynomials can possibly occur as factors in the denominators of rational solutions of a given partial linear difference equation. In an earlier article we have introduced the distinction between periodic and aperiodic ...

In Kapur et al (ISSAC, 2010), a new method for computing a comprehensive Grobner system of a parameterized polynomial system was proposed and its efficiency over other known methods was effectively demonstrated. Based on those insights, a new approach ...

We study how an irreducible smooth and closed algebraic surface X embedded in CP⁴, can be recovered using its projections from two points onto embedded projective hyperplanes. The different embeddings are unknown. The only input is the defining equation ...

We present a method for interpolating a supersparse blackbox rational function with rational coefficients, for example, a ratio of binomials or trinomials with very high degree. We input a blackbox rational function, as well as an upper bound on the ...

We present certificates for the positive semidefiniteness of an n by n matrix A, whose entries are integers of binary length log ||A||, that can be verified in O(n^(2+µ) (log ||A||)^(1+µ) binary operations for any µ > 0. The question arises in Hilbert/...

State of the art factoring in Q[x] is dominated in theory by a combinatorial reconstruction problem while, excluding some rare polynomials, performance tends to be dominated by Hensel lifting. We present an algorithm which gives a practical improvement (...