A Special Homotopy Continuation Method For A Class of Polynomial Systems

A special homotopy continuation method, as a combination of the polyhedral homotopy and the linear product homotopy, is proposed for computing all the isolated solutions to a special class of polynomial systems. The root number bound of this method is between the total degree bound and the mixed volume bound and can be easily computed. The new algorithm has been implemented as a program called LPH using C++. Our experiments show its efficiency compared to the polyhedral or other homotopies on such systems. As an application, the algorithm can be used to find witness points on each connected component of a real variety.


Similar Publications

We compute the free energy of the planar monomer-dimer model. Unlike the classical planar dimer model, an exact solution is not known in this case. Even the computation of the low-density power series expansion requires heavy and nontrivial computations. Read More


We introduce two new packages, Nemo and Hecke, written in the Julia programming language for computer algebra and number theory. We demonstrate that high performance generic algorithms can be implemented in Julia, without the need to resort to a low-level C implementation. For specialised algorithms, we use Julia's efficient native C interface to wrap existing C/C++ libraries such as Flint, Arb, Antic and Singular. Read More


Let K be a field equipped with a valuation. Tropical varieties over K can be defined with a theory of Gr{\"o}bner bases taking into account the valuation of K. While generalizing the classical theory of Gr{\"o}bner bases, it is not clear how modern algorithms for computing Gr{\"o}bner bases can be adapted to the tropical case. Read More


In this paper, we describe improved algorithms to compute Janet and Pommaret bases. To this end, based on the method proposed by Moller et al., we present a more efficient variant of Gerdt's algorithm (than the algorithm presented by Gerdt-Hashemi-M. Read More


In 2012, Barbulescu, Detrey, Estibals and Zimmermann proposed a new framework to exhaustively search for optimal formulae for evaluating bilinear maps, such as Strassen or Karatsuba formulae. The main contribution of this work is a new criterion to aggressively prune useless branches in the exhaustive search, thus leading to the computation of new optimal formulae, in particular for the short product modulo $X^5$ and the circulant product modulo $(X^5-1)$. Moreover, we are able to prove that there is essentially only one optimal decomposition of the product of $3\times 2$ by $2\times 3$ matrices up to the action of some group of automorphisms. Read More


Analyzing and reasoning about safety properties of software systems becomes an especially challenging task for programs with complex flow and, in particular, with loops or recursion. For such programs one needs additional information, for example in the form of loop invariants, expressing properties to hold at intermediate program points. In this paper we study program loops with non-trivial arithmetic, implementing addition and multiplication among numeric program variables. Read More


We consider several notions of genericity appearing in algebraic geometry and commutative algebra. Special emphasis is put on various stability notions which are defined in a combinatorial manner and for which a number of equivalent algebraic characterisations are provided. It is shown that in characteristic zero the corresponding generic positions can be obtained with a simple deterministic algorithm. Read More


We improve certain degree bounds for Grobner bases of polynomial ideals in generic position. We work exclusively in deterministically verifiable and achievable generic positions of a combinatorial nature, namely either strongly stable position or quasi stable position. Furthermore, we exhibit new dimension- (and depth-)dependent upper bounds for the Castelnuovo-Mumford regularity and the degrees of the elements of the reduced Grobner basis (w. Read More


Template metaprogramming is a popular technique for implementing compile time mechanisms for numerical computing. We demonstrate how expression templates can be used for compile time symbolic differentiation of algebraic expressions in C++ computer programs. Given a positive integer $N$ and an algebraic function of multiple variables, the compiler generates executable code for the $N$th partial derivatives of the function. Read More