Asymptotic purity for very general hypersurfaces of PnxPn of bidegree (k, k) Central European Journal of Mathematics 10(2) (2012) 530-542
ABSTRACT: For a complex irreducible projective variety, the volume function and the higher asymptotic cohomological functions have proven to be useful in understanding the positivity of divisors as well as other geometric properties of the variety. In this paper, we study the vanishing properties of these functions on hypersurfaces of PnxPn. In particular, we show that very general hypersurfaces of bidegree (k, k) obey a very strong vanishing property, which we define as asymptotic purity: at most one asymptotic cohomological function is nonzero for each divisor. This provides evidence for the truth of a conjecture of Bogomolov and also suggests some general conditions for asymptotic purity.
SqFreeEVAL: An (Almost) Optimal Real-Root Isolation Algorithm. (with F. Krahmer) Journal of Symbolic Computation 47(2) (2012) 131-152
ABSTRACT: Let f be a univariate polynomial with real coefficients, f in R[X]. Subdivision algorithms based on algebraic techniques (e.g., Sturm or Descartes methods) are widely used for isolating the real roots of f in a given interval. In this paper, we consider a simple subdivision algorithm whose primitives are purely numerical (e.g., function evaluation). The complexity of this algorithm is adaptive because the algorithm makes decisions based on local data. The complexity analysis of adaptive algorithms (and this algorithm in particular) is a new challenge for computer science. In this paper, we compute the size of the subdivision tree for the SqFreeEVAL algorithm. The SqFreeEVAL algorithm is an evaluation-based numerical algorithm which is well-known in several communities. The algorithm itself is simple, but prior attempts to compute its complexity have proven to be quite technical and have yielded sub-optimal results. Our main result is a simple O(d(L+lnd)) bound on the size of the subdivision tree for the SqFreeEVAL algorithm on the benchmark problem of isolating all real roots of an integer polynomial f of degree d and whose coefficients can be written with at most L bits. Our proof uses two amortization-based techniques: first, we use the algebraic amortization technique of the standard Mahler-Davenport root bounds to interpret the integral in terms of d and L. Second, we use a continuous amortization technique based on an integral to bound the size of the subdivision tree. This paper is the first to use the novel analysis technique of continuous amortization to derive state of the art complexity bounds. [DOI]
Complete Subdivision Algorithms II: Isotopic Meshing of General Algebraic Curves (with S. Choi, B. Galehouse, and C. Yap) Journal of Symbolic Computation 47(2) (2012) 153-166
ABSTRACT: 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.
We generalize their algorithm to any (possibly non-simply connected) region B that does not contain singularities of C. With this generalization as subroutine, we provide a method to detect isolated algebraic singularities and their branching degree. This appears to be the first complete numerical method to treat implicit algebraic curves with isolated singularities.
MATH 9860 - Introduction to Manifolds
The main topic is the basic theory of smooth manifolds. Manifolds are a basic object in geometry and appear in a wide variety of subjects in the mathematical sciences.