Explicit volume-preserving splitting methods for polynomial divergence-free vector fields

We present new, explicit, volume-preserving splitting methods for polynomial divergence-free vector fields of arbitrary degree (both positive and negative). The main idea is to decompose the divergence polynomial by means of an appropriate basis for polynomials: the monomial basis. For each monomial basis function, the split fields are then identified by collecting the appropriate terms in the vector field so that each split vector field is volume preserving. We show that each split field can be integrated exactly by analytical methods. Thus, the composition yields a volume preserving numerical method. Our numerical tests indicate that the methods compare favorably to standard integrators both in the quality of the numerical solution and the computational effort.     

On the Castelnuovo-Mumford regularity and the arithmetic degree of monomial ideals

In the first part of this paper we show that the Castelnuovo-Mumford regularity of a monomial ideal is bounded above by its arithmetic degree. The second part gives upper bounds for the Castelnuovo-Mumford regularity and the arithmetic degree of a monomial ideal in terms of the degrees of its generators. These bounds can be formulated for an arbitrary homogeneous ideal in terms of any Gröbner basis.     

Bernstein’s theorem in affine space

The stable mixed volume of the Newton polytopes of a polynomial system is defined and shown to equal (genetically) the number of zeros in affine space C_n. This result refines earlier bounds by Rojas, Li, and Wang [5], [7], [8]. The homotopies in [4], [9], and [10] extend naturally to a computation of all isolated zeros in Cⁿ This research was supported by the David and Lucile Packard Foundation and the National Science Foundation.     

A refinement of multivariate value set bounds

Over finite fields, if the image of a polynomial map is not the entire field, then its cardinality can be bounded above by a significantly smaller value. Earlier results bound the cardinality of the value set using the degree of the polynomial, but more recent results make use of the powers of all monomials.In this paper, we explore the geometric properties of the Newton polytope and show how they allow for tighter upper bounds on the cardinality of the multivariate value set. We then explore a method which allows for even stronger upper bounds, regardless of whether one uses the multivariate degree or the Newton polytope to bound the value set. Effectively, this provides improvement of a degree matrix-based result given by Zan and Cao, making our new bound the strongest upper bound thus far.     

Improved algorithms for computing determinants and resultants

Our first contribution is a substantial acceleration of randomized computation of scalar, univariate, and multivariate matrix determinants, in terms of the output-sensitive bit operation complexity bounds, including computation modulo a product of random primes from a fixed range. This acceleration is dramatic in a critical application, namely solving polynomial systems and related studies, via computing the resultant. This is achieved by combining our techniques with the primitive-element method, which leads to an effective implicit representation of the roots. We systematically examine quotient formulae of Sylvester-type resultant matrices, including matrix polynomials and the u-resultant. We reduce the known bit operation complexity bounds by almost an order of magnitude, in terms of the resultant matrix dimension. Our theoretical and practical improvements cover the highly important cases of sparse and degenerate systems.     

Notes on lattice points of zonotopes and lattice-face polytopes

Minkowski’s second theorem on successive minima gives an upper bound on the volume of a convex body in terms of its successive minima. We study the problem to generalize Minkowski’s bound by replacing the volume by the lattice point enumerator of a convex body. In this context we are interested in bounds on the coefficients of Ehrhart polynomials of lattice polytopes via the successive minima. Our results for lattice zonotopes and lattice-face polytopes imply, in particular, that for 0-symmetric lattice-face polytopes and lattice parallelepipeds the volume can be replaced by the lattice point enumerator.     

f-Vectors of Minkowski Additions of Convex Polytopes

The objective of this paper is to present two types of results on Minkowski sums of convex polytopes. The first is about a special class of polytopes we call perfectly centered and the combinatorial properties of the Minkowski sum with their own dual. In particular, we have a characterization of the face lattice of the sum in terms of the face lattice of a given perfectly centered polytope. Exact face counting formulas are then obtained for perfectly centered simplices and hypercubes. The second type of results concerns tight upper bounds for the f-vectors of Minkowski sums of several polytopes.     

Enumerating a subset of the integer points inside a Minkowski sum

Sparse elimination exploits the structure of algebraic equations in order to obtain tighter bounds on the number of roots and better complexity in numerically approximating them. The model of sparsity is of combinatorial nature, thus leading to certain problems in general-dimensional convex geometry. This work addresses one such problem, namely the computation of a certain subset of integer points in the interior of integer convex polytopes. These polytopes are Minkowski sums, but avoiding their explicit construction is precisely one of the main features of the algorithm. Complexity bounds for our algorithm are derived under certain hypotheses, in terms of output-size and the sparsity parameters. A public domain implementation is described and its performance studied. Linear optimization lies at the inner loop of the algorithm, hence we analyze the structure of the linear programs and compare different implementations.     

A lifting and recombination algorithm for rational factorization of sparse polynomials

We propose a new lifting and recombination scheme for rational bivariate polynomial factorization that takes advantage of the Newton polytope geometry. We obtain a deterministic algorithm that can be seen as a sparse version of an algorithm of Lecerf, with a polynomial complexity in the volume of the Newton polytope. We adopt a geometrical point of view, the main tool being derived from some algebraic osculation criterion in toric varieties.     

The Flag Polynomial of the Minkowski Sum of Simplices

For a polytope we define the flag polynomial, a polynomial in commuting variables related to the well-known flag vector and describe how to express the flag polynomial of the Minkowski sum of k standard simplices in a direct and canonical way in terms of the k-th master polytope P(k) where ${k \in \mathbb {N}}$ . The flag polynomial facilitates many direct computations. To demonstrate this we provide two examples; we first derive a formula for the f -polynomial and the maximum number of d-dimensional faces of the Minkowski sum of two simplices. We then compute the maximum discrepancy between the number of (0, d)-chains of faces of a Minkowski sum of two simplices and the number of such chains of faces of a simple polytope of the same dimension and on the same number of vertices.     

Correction to: A scaling algorithm for optimizing arbitrary functions over vertices of polytopes

In this paper we present a scaling algorithm for minimizing arbitrary functions over vertices of polytopes in an oracle model of computation which includes an augmentation oracle. For the binary case, when the vertices are 0–1 vectors, we show that the oracle time is polynomial. Also, this algorithm allows us to generalize some concepts of combinatorial optimization concerning performance bounds of greedy algorithms and leads to new bounds for the complexity of the simplex method.

     

Successive radii and Minkowski addition

In this paper we study the behavior of the so called successive inner and outer radii with respect to the Minkowski addition of convex bodies, generalizing the well-known cases of the diameter, minimal width, circumradius and inradius. We get?all possible upper and lower bounds for the radii of the sum of two convex bodies in terms of the sum of the corresponding radii.     

Successive radii and Minkowski addition

In this paper we study the behavior of the so called successive inner and outer radii with respect to the Minkowski addition of convex bodies, generalizing the well-known cases of the diameter, minimal width, circumradius and inradius. We get all possible upper and lower bounds for the radii of the sum of two convex bodies in terms of the sum of the corresponding radii.     

Separation of variables and the computation of Fourier transforms on finite groups, I

This paper introduces new techniques for the efficient computation of a Fourier transform on a finite group. We present a divide and conquer approach to the computation. The divide aspect uses factorizations of group elements to reduce the matrix sum of products for the Fourier transform to simpler sums of products. This is the separation of variables algorithm. The conquer aspect is the final computation of matrix products which we perform efficiently using a special form of the matrices. This form arises from the use of subgroup-adapted representations and their structure when evaluated at elements which lie in the centralizers of subgroups in a subgroup chain. We present a detailed analysis of the matrix multiplications arising in the calculation and obtain easy-to-use upper bounds for the complexity of our algorithm in terms of representation theoretic data for the group of interest.

Our algorithm encompasses many of the known examples of fast Fourier transforms. We recover the best known fast transforms for some abelian groups, the symmetric groups and their wreath products, and the classical Weyl groups. Beyond this, we obtain greatly improved upper bounds for the general linear and unitary groups over a finite field, and for the classical Chevalley groups over a finite field. We also apply these techniques to obtain analogous results for homogeneous spaces.

This is part I of a two part paper. Part II will present a refinement of these techniques which yields further savings.

     

A bivariate preprocessing paradigm for the Buchberger-Möller algorithm

For the last almost three decades, since the famous Buchberger-Möller (BM) algorithm emerged, there has been wide interest in vanishing ideals of points and associated interpolation polynomials. Our paradigm is based on the theory of bivariate polynomial interpolation on cartesian point sets that gives us a related degree reducing interpolation monomial and Newton bases directly. Since the bases are involved in the computation process as well as contained in the final output of the BM algorithm, our paradigm obviously simplifies the computation and accelerates the BM process. The experiments show that the paradigm is best suited for the computation over finite prime fields that have many applications.     

Sparse effective membership problems via residue currents

We use residue currents on toric varieties to obtain bounds on the degrees of solutions to polynomial ideal membership problems. Our bounds depend on (the volume of) the Newton polytope of the polynomial system and are therefore well adjusted to sparse polynomial systems. We present sparse versions of Max N?ther??s AF?+?BG Theorem, Macaulay??s Theorem, and Kollár??s Effective Nullstellensatz, as well as recent results by Hickel and Andersson?CG?tmark.     

High-Dimensional Adaptive Sparse Polynomial Interpolation and Applications to Parametric PDEs

We consider the problem of Lagrange polynomial interpolation in high or countably infinite dimension, motivated by the fast computation of solutions to partial differential equations (PDEs) depending on a possibly large number of parameters which result from the application of generalised polynomial chaos discretisations to random and stochastic PDEs. In such applications there is a substantial advantage in considering polynomial spaces that are sparse and anisotropic with respect to the different parametric variables. In an adaptive context, the polynomial space is enriched at different stages of the computation. In this paper, we study an interpolation technique in which the sample set is incremented as the polynomial dimension increases, leading therefore to a minimal amount of PDE solving. This construction is based on the standard principle of tensorisation of a one-dimensional interpolation scheme and sparsification. We derive bounds on the Lebesgue constants for this interpolation process in terms of their univariate counterpart. For a class of model elliptic parametric PDE’s, we have shown in Chkifa et al. (Modél. Math. Anal. Numér. 47(1):253–280, 2013) that certain polynomial approximations based on Taylor expansions converge in terms of the polynomial dimension with an algebraic rate that is robust with respect to the parametric dimension. We show that this rate is preserved when using our interpolation algorithm. We also propose a greedy algorithm for the adaptive selection of the polynomial spaces based on our interpolation scheme, and illustrate its performance both on scalar valued functions and on parametric elliptic PDE’s.