We study a partial correspondence between two previously-studied analogues of Gröbner bases in the setting of algebras: namely subalgebra bases for quotients of polynomial rings and Khovanskii bases for valued algebras and domains. Our main motivation is to apply the concrete and computational aspects of subalgebra bases for quotient rings to the abstract theory of Khovanskii bases. Our perspective is that most interesting examples of Khovanskii bases can also be realized as subalgebra bases and vice-versa. As part of this correspondence, we extend the theory of subalgebra bases for quotients of polynomial rings to infinitely generated polynomial algebras and study conditions which make this theory effective. We also provide a computation of Newton-Okounkov bodies from the data of subalgebra bases for quotient rings, which illustrates how interpreting Khovanskii bases as subalgebra bases makes them amenable to existing computer algebra tools.

We present a certified algorithm that takes a smooth algebraic curve in \(\mathbb {R}^n\) and computes an isotopic approximation for a generic projection of the curve into \(\mathbb {R}^2\). Our algorithm is designed for curves given implicitly by the zeros of n − 1 polynomials, but it can be partially extended to parametrically defined curves. The main challenge in correctly computing the projection is to guarantee the topological correctness of crossings in the projection. Our approach combines certified path tracking and interval arithmetic in a two-step procedure: first, we construct an approximation to the curve in \(\mathbb {R}^n\), and, second, we refine the approximation until the topological correctness of the projection can be guaranteed. We provide a proof-of-concept implementation illustrating the algorithm.

The main results of this paper establish a partial correspondence between two previously-studied analogues of Gröbner bases in the setting of algebras: namely, subalgebra (aka SAGBI) bases for quotients of polynomial rings and Khovanskii bases for valued algebras. We aim to bridge the gap between the concrete, computational aspects of the former and the more abstract theory of the latter. Our philosophy is that most interesting examples of Khovanskii bases can also be realized as subalgebra bases and vice-versa. We also discuss the computation of Newton-Okounkov bodies, illustrating how interpreting Khovanskii bases as subalgebra bases makes them more amenable to the existing tools of computer algebra.

We present a certified algorithm based on subdivision for computing an isotopic approximation to a pair of curves in the plane. Our algorithm is based on the certified curve approximation algorithm of Plantinga and Vegter. The main challenge in this computation is to correctly and efficiently compute the intersections of the curves. To address this issue, we introduce a new, but simple test that guarantees the global correctness of our output.

Given a system of analytic functions and an approximation to a cluster of zeros, we wish to construct two regions containing the cluster and no other zeros of the system. The smaller region tightly contains the cluster while the larger region separates it from the other zeros of the system. We achieve this using the method of inflation which, counterintuitively, relates it to another system that is more amenable to our task but whose associated cluster of zeros is larger.

We develop algorithms for certifying an approximation to a nonsingular solution of a square system of equations built from univariate analytic functions. These algorithms are based on the existence of oracles for evaluating basic data about the input analytic functions. One approach for certification is based on α-theory while the other is based on the Krawczyk generalization of Newton's iteration. We show that the necessary oracles exist for \Dfinite\ functions and compare the two algorithmic approaches for this case using our software implementation in \sage.

Homotopy continuation is a well-known method in numerical root-finding. Recently, certified algorithms for homotopy continuation based on Smale's alpha-theory have been developed. This approach enforces very strong requirements at each step, leading to small step sizes. In this paper, we propose an approach that is independent of alpha-theory. It is based on the weaker notion of well-isolated approximations to the roots. We apply it to univariate polynomials and provide experimental evidence of its feasibility.

In 1984, Johnson and Lindenstrauss proved that any finite set of data in a high-dimensional space can be projected to a lower-dimensional space while preserving the pairwise Euclidean distances between points up to a bounded relative error. If the desired dimension of the image is too small, however, Kane, Meka, and Nelson (2011) and Jayram and Woodruff (2013) proved that such a projection does not exist. In this paper, we provide a precise asymptotic threshold for the dimension of the image, above which, there exists a projection preserving the Euclidean distance, but, below which, there does not exist such a projection.

We present the first complexity analysis of the algorithm by Plantinga and Vegter for approximating real implicit curves and surfaces. This approximation algorithm certifies the topological correctness of the output using both subdivision and interval arithmetic. In practice, it has been seen to be quite efficient; our goal is to quantify this efficiency. We focus on the subdivision step (and not the approximation step) of the Plantinga and Vegter algorithm. We begin by extending the subdivision step to arbitrary dimensions. We provide a priori worst-case bounds on the complexity of this algorithm both in terms of the number of subregions constructed and the bit complexity for the construction. Then, we use continuous amortization to derive adaptive bounds on the complexity of the subdivided region. We also provide examples showing our bounds are tight.

Given a real function f(X,Y), a box region B and ε>0, we want to compute an ε-isotopic polygonal approximation to the curve C: f(X,Y)=0 within B. We focus on subdivision algorithms because of their adaptive complexity. Plantinga & Vegter (2004) gave a numerical subdivision algorithm that is exact when the curve C is non-singular. They used a computational model that relies only on function evaluation and interval arithmetic.