Source author record

John Abbott

Explore this author’s publications, collaborators and research topics. This catalog record has not been claimed by its author.

ResearcherUnclaimed source record

math.AC math.NT math.GR math.NA

Catalog footprint

Research overview

6works

4topics

3close collaborators

Actions

Is this your work?

Open graph Browse papers

preprint2020arXiv

Certifying Irreducibility in Z[x]

We consider the question of certifying that a polynomial in ${\mathbb Z}[x]$ or ${\mathbb Q}[x]$ is irreducible. Knowing that a polynomial is irreducible lets us recognise that a quotient ring is actually a field extension (equiv.~that a polynomial ideal is maximal). Checking that a polynomial is irreducible by factorizing it is unsatisfactory because it requires trusting a relatively large and complicated program (whose correctness cannot easily be verified). We present a practical method for generating certificates of irreducibility which can be verified by relatively simple computations; we assume that primes and irreducibles in ${\mathbb F}_p[x]$ are self-certifying.

preprint2016arXiv

Implicitization of Hypersurfaces

We present new, practical algorithms for the hypersurface implicitization problem: namely, given a parametric description (in terms of polynomials or rational functions) of the hypersurface, find its implicit equation. Two of them are for polynomial parametrizations: one algorithm, "ElimTH", has as main step the computation of an elimination ideal via a \textit{truncated, homogeneous} Gröbner basis. The other algorithm, "Direct", computes the implicitization directly using an approach inspired by the generalized Buchberger-Möller algorithm. Either may be used inside the third algorithm, "RatPar", to deal with parametrizations by rational functions. Finally we show how these algorithms can be used in a modular approach, algorithm "ModImplicit", for avoiding the high costs of arithmetic with rational numbers. We exhibit experimental timings to show the practical efficiency of our new algorithms.

preprint2015arXiv

Deciding if a variety forms an algebraic group

Let $n$ be a positive integer and let $f_1, \ldots, f_r$ be polynomials in $n^2$ indeterminates over an algebraically closed field $K$ . We describe an algorithm to decide if the invertible matrices contained in the variety of $f_1, \ldots, f_r$ form a subgroup of $GL(n,K)$ ; that is, we show how to decide if the polynomials $f_1, \ldots, f_r$ define a linear algebraic group.

preprint2015arXiv

Fault-Tolerant Modular Reconstruction of Rational Numbers

In this paper we present two efficient methods for reconstructing a rational number from several residue-modulus pairs, some of which may be incorrect. One method is a natural generalization of that presented by Wang, Guy and Davenport in \cite{WGD1982} (for reconstructing a rational number from \textit{correct} modular images), and also of an algorithm presented in \cite{Abb1991} for reconstructing an \textit{integer} value from several residue-modulus pairs, some of which may be incorrect.

preprint2012arXiv

Quadratic Interval Refinement for Real Roots

We present a new algorithm for refining a real interval containing a single real root: the new method combines characteristics of the classical Bisection algorithm and Newton's Iteration. Our method exhibits quadratic convergence when refining isolating intervals of simple roots of polynomials (and other well-behaved functions). We assume the use of arbitrary precision rational arithmetic. Unlike Newton's Iteration our method does not need to evaluate the derivative.

preprint2009arXiv

Bounds on Factors in Z[x]

We gather together several bounds on the sizes of coefficients which can appear in factors of polynomials in Z[x]; we include a new bound which was latent in a paper by Mignotte, and a few minor improvements to some existing bounds. We compare these bounds and show that none is universally better than the others. In the second part of the paper we give several concrete examples of factorizations where the factors have "unexpectedly" large coefficients. These examples help us understand why the bounds must be larger than you might expect, and greatly extend the collection published by Collins.

Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.