• ### Open Weak CAD and its Applications(1507.03834)

March 27, 2019 cs.SC
The concept of open weak CAD is introduced. Every open CAD is an open weak CAD. On the contrary, an open weak CAD is not necessarily an open CAD. An algorithm for computing projection polynomials of open weak CADs is proposed. The key idea is to compute the intersection of projection factor sets produced by different projection orders. The resulting open weak CAD often has smaller number of sample points than open CADs. The algorithm can be used for computing sample points for all open connected components of $f\neq0$ for a given polynomial $f$. It can also be used for many other applications, such as testing semi-definiteness of polynomials and copositive problems. In fact, we solved several difficult semi-definiteness problems efficiently by using the algorithm. Furthermore, applying the algorithm to copositive problems, we find an explicit expression of the polynomials producing open weak CADs under some conditions, which significantly improves the efficiency of solving copositive problems.
• ### Object-Image Correspondence for Algebraic Curves under Projections(1303.3358)

March 10, 2019 math.DG, math.AG, cs.CG
We present a novel algorithm for deciding whether a given planar curve is an image of a given spatial curve, obtained by a central or a parallel projection with unknown parameters. The motivation comes from the problem of establishing a correspondence between an object and an image, taken by a camera with unknown position and parameters. A straightforward approach to this problem consists of setting up a system of conditions on the projection parameters and then checking whether or not this system has a solution. The computational advantage of the algorithm presented here, in comparison to algorithms based on the straightforward approach, lies in a significant reduction of a number of real parameters that need to be eliminated in order to establish existence or non-existence of a projection that maps a given spatial curve to a given planar curve. Our algorithm is based on projection criteria that reduce the projection problem to a certain modification of the equivalence problem of planar curves under affine and projective transformations. To solve the latter problem we make an algebraic adaptation of signature construction that has been used to solve the equivalence problems for smooth curves. We introduce a notion of a classifying set of rational differential invariants and produce explicit formulas for such invariants for the actions of the projective and the affine groups on the plane.
• ### Positive Solutions of Systems of Signed Parametric Polynomial Inequalities(1804.09705)

April 25, 2018 cs.LO, cs.SC
We consider systems of strict multivariate polynomial inequalities over the reals. All polynomial coefficients are parameters ranging over the reals, where for each coefficient we prescribe its sign. We are interested in the existence of positive real solutions of our system for all choices of coefficients subject to our sign conditions. We give a decision procedure for the existence of such solutions. In the positive case our procedure yields a parametric positive solution as a rational function in the coefficients. Our framework allows to reformulate heuristic subtropical approaches for non-parametric systems of polynomial inequalities that have been recently used in qualitative biological network analysis and, independently, in satisfiability modulo theory solving. We apply our results to characterize the incompleteness of those methods.
• ### Global Identifiability of Differential Models(1801.08112)

April 3, 2018 math.CA, math.AG, math.AC, math.OC
Many real-world processes and phenomena are modeled using systems of ordinary differential equations with parameters. Given such a system, we say that a parameter is globally identifiable if it can be uniquely recovered from input and output data. The main contribution of this paper is to provide theory, an algorithm, and software for deciding global identifiability. First, we rigorously derive an algebraic criterion for global identifiability (this is an analytic property), which yields a deterministic algorithm. Second, we improve the efficiency by randomizing the algorithm while guaranteeing probability of correctness. With our new algorithm, we can tackle problems that could not be tackled before.
• ### Degree-optimal moving frames for rational curves(1703.03014)

Feb. 9, 2018 math.AG, math.AC
A $\mathit{\text{moving frame}}$ at a rational curve is a basis of vectors moving along the curve. When the rational curve is given parametrically by a row vector $\mathbf{a}$ of univariate polynomials, a moving frame with important algebraic properties can be defined by the columns of an invertible polynomial matrix $P$, such that $\mathbf{a} P=[\gcd(\mathbf{a}),0\ldots,0]$. A $\mathit{\text{degree-optimal moving frame}}$ has column-wise minimal degree, where the degree of a column is defined to be the maximum of the degrees of its components. Algebraic moving frames are closely related to the univariate versions of the celebrated Quillen-Suslin problem, effective Nullstellensatz problem, and syzygy module problem. However, this paper appears to be the first devoted to finding an efficient algorithm for constructing a degree-optimal moving frame, a property desirable in various applications. We compare our algorithm with other possible approaches, based on already available algorithms, and show that it is more efficient. We also establish several new theoretical results concerning the degrees of an optimal moving frame and its components. In addition, we show that any deterministic algorithm for computing a degree-optimal algebraic moving frame can be augmented so that it assigns a degree-optimal moving frame in a $GL_n(\mathbb{K})$-equivariant manner. This crucial property of classical geometric moving frames, in combination with the algebraic properties, can be exploited in various problems.
• ### Explicit expression for a family of ternary cyclotomic polynomials(1801.01186)

Jan. 16, 2018 math.NT
In this paper, we give an explicit expression for a certain family of ternary cyclotomic polynomials: specifically $\Phi_{p_{1}p_{2}p_{3}}$, where $p_{1}<p_{2}<p_{3}$ are odd primes such that $p_{2} \equiv1 \mod p_{1}$ and $p_{3} \equiv1 \mod {p_{1}p_{2}}$. As an application of the explicit expressions, we give an exact formula for the number of nonzero terms in the polynomials in the family, which in turn immediately shows that the density (number of non-zeros terms / degree) is roughly inversely proportional to $p_{2}$, when $p_{1}$ is sufficiently large.
• ### Number of common roots and resultant of two tropical univariate polynomials(1608.02394)

Oct. 9, 2017 math.AG
It is well known that for two univariate polynomials over complex number field the number of their common roots is equal to the order of their resultant. In this paper, we show that this fundamental relationship still holds for the tropical polynomials under suitable adaptation of the notion of order, if the roots are simple and non-zero.
• ### Locating and counting equilibria of the Kuramoto model with rank one coupling(1705.06568)

April 28, 2017 math.AG, math.DS, math.OC
The Kuramoto model describes synchronization behavior among coupled oscillators and enjoys successful application in a wide variety of fields. Many of these applications seek phase-coherent solutions, i.e., equilibria of the model. Historically, research has focused on situations where the number of oscillators, n, is extremely large and can be treated as being infinite. More recently, however, applications have arisen in areas such as electrical engineering with more modest values of n. For these, the equilibria can be located by solving a system of polynomial equations utilizing techniques from algebraic geometry. Typical methods for solving such systems locate all complex solutions even though only the real solutions, corresponding to equilibria of the model, are of physical interest. In this paper, we develop an algorithm to locate only all equilibria of the model, thereby shortening computation time by several orders of magnitude in certain situations. This is accomplished by choosing specific equilibria representatives and the consequent algebraic decoupling of the system. We compare this solving approach to other computational algebraic geometric methods. Furthermore, analyzing this approach allows us to prove, asymptotically, that the maximum number of equilibria grows at the same rate as the number of complex solutions of a corresponding polynomial system. Finally, we conjecture an upper bound on the maximum number of equilibria for any number of oscillators which generalizes the known cases and is obtained on a range of explicitly provided natural frequencies.
• ### Block Structure of Cyclotomic Polynomials(1704.04051)

April 20, 2017 math.NT
In this paper, we list several interesting structures of cyclotomic polynomials: specifically relations among blocks obtained by suitable partition of cyclotomic polynomials. We present explicit and self-contained proof for all of them, using a uniform terminology and technique.
• ### Algorithm for computing $\mu$-bases of univariate polynomials(1603.04813)

March 8, 2017 math.AG, cs.SC, math.AC
We present a new algorithm for computing a $\mu$-basis of the syzygy module of $n$ polynomials in one variable over an arbitrary field $\mathbb{K}$. The algorithm is conceptually different from the previously-developed algorithms by Cox, Sederberg, Chen, Zheng, and Wang for $n=3$, and by Song and Goldman for an arbitrary $n$. It involves computing a "partial" reduced row-echelon form of a $(2d+1)\times n(d+1)$ matrix over $\mathbb{K}$, where $d$ is the maximum degree of the input polynomials. The proof of the algorithm is based on standard linear algebra and is completely self-contained. It includes a proof of the existence of the $\mu$-basis and as a consequence provides an alternative proof of the freeness of the syzygy module. The theoretical (worst case asymptotic) computational complexity of the algorithm is $O(d^2n+d^3+n^2)$. We have implemented this algorithm (HHK) and the one developed by Song and Goldman (SG). Experiments on random inputs indicate that SG gets faster than HHK when $d$ gets sufficiently large for a fixed $n$, and that HHK gets faster than SG when $n$ gets sufficiently large for a fixed $d$.
• ### Lower Bounds for Maximum Gap in (Inverse) Cyclotomic Polynomials(1702.07650)

Feb. 24, 2017 math.NT
The maximum gap $g(f)$ of a polynomial $f$ is the maximum of the differences (gaps) between two consecutive exponents that appear in $f$. Let $\Phi_{n}$ and $\Psi_{n}$ denote the $n$-th cyclotomic and $n$-th inverse cyclotomic polynomial, respectively. In this paper, we give several lower bounds for $g(\Phi_{n})$ and $g(\Psi_{n})$, where $n$ is the product of odd primes. We observe that they are very often exact. We also give an exact expression for $g(\Psi_{n})$ under a certain condition. Finally we conjecture an exact expression for $g(\Phi_{n})$ under a certain condition.
• ### Algorithm for computing semi-Fourier sequences of expressions involving exponentiations and integrations(1702.07060)

Feb. 23, 2017 cs.SC
We provide an algorithm for computing semi-Fourier sequences for expressions constructed from arithmetic operations, exponentiations and integrations. The semi-Fourier sequence is a relaxed version of Fourier sequence for polynomials (expressions made of additions and multiplications).
• ### Resultants over Commutative Idempotent Semirings(1505.06470)

May 24, 2015 math.RA
The resultant plays a crucial role in (computational) algebra and algebraic geometry. One of the most important and well known properties of the resultant is that it is equal to the determinant of the Sylvester matrix. In 2008, Odagiri proved that a similar property holds over the tropical semiring if one replaces subtraction with addition. The tropical semiring belongs to a large family of algebraic structures called commutative idempotent semiring. In this paper, we prove that the same property (with subtraction replaced with addition) holds over an \emph{arbitrary\/} commutative idempotent semiring.
• ### On Lazard's Valuation and CAD Construction(1501.06563)

Feb. 9, 2015 math.AG
In 1990 Lazard proposed an improved projection operation for cylindrical algebraic decomposition (CAD). For the proof he introduced a certain notion of valuation of a multivariate Puiseux series at a point. However a gap in one of the key supporting results for the improved projection was subsequently noticed. In this report we study a more limited but rigorous concept of Lazard's valuation: namely, we study Lazard's valuation of a multivariate polynomial at a point. We prove some basic properties of the limited Lazard valuation and identify some relationships between valuation-invariance and order-invariance.
• ### An algebraic method for constructing stable and consistent autoregressive filters(1412.1392)

Dec. 2, 2014 math.NA, math.AG, stat.ME
In this paper, we introduce an algebraic method to construct stable and consistent univariate autoregressive (AR) models of low order for filtering and predicting nonlinear turbulent signals with memory depth. By stable, we refer to the classical stability condition for the AR model. By consistent, we refer to the classical consistency constraints of Adams-Bashforth methods of order-two. One attractive feature of this algebraic method is that the model parameters can be obtained without directly knowing any training data set as opposed to many standard, regression-based parameterization methods. It takes only long-time average statistics as inputs. The proposed method provides a discretization time step interval which guarantees the existence of stable and consistent AR model and simultaneously produces the parameters for the AR models. In our numerical examples with two chaotic time series with different characteristics of decaying time scales, we find that the proposed AR models produce significantly more accurate short-term predictive skill and comparable filtering skill relative to the linear regression-based AR models. These encouraging results are robust across wide ranges of discretization times, observation times, and observation noise variances. Finally, we also find that the proposed model produces an improved short-time prediction relative to the linear regression-based AR-models in forecasting a data set that characterizes the variability of the Madden-Julian Oscillation, a dominant tropical atmospheric wave pattern.
• ### The Secant-Newton Map is Optimal Among Contracting $n^{th}$ Degree Maps for $n^{th}$ Root Computation(1404.2371)

April 9, 2014 cs.SC
Consider the problem: given a real number $x$ and an error bound $\epsilon$, find an interval such that it contains the $\sqrt[n]{x}$ and its width is less than $\epsilon$. One way to solve the problem is to start with an initial interval and to repeatedly update it by applying an interval refinement map on it until it becomes narrow enough. In this paper, we prove that the well known Secant-Newton map is optimal among a certain family of natural generalizations.
• ### Special Algorithm for Stability Analysis of Multistable Biological Regulatory Systems(1312.1780)

Dec. 26, 2013 cs.SC
We consider the problem of counting (stable) equilibriums of an important family of algebraic differential equations modeling multistable biological regulatory systems. The problem can be solved, in principle, using real quantifier elimination algorithms, in particular real root classification algorithms. However, it is well known that they can handle only very small cases due to the enormous computing time requirements. In this paper, we present a special algorithm which is much more efficient than the general methods. Its efficiency comes from the exploitation of certain interesting structures of the family of differential equations.
• ### Maximum Gap in (Inverse) Cyclotomic Polynomial(1101.4255)

Jan. 22, 2011 math.NT
Let $g(f)$ denote the maximum of the differences (gaps) between two consecutive exponents occurring in a polynomial $f$. Let $\Phi_n$ denote the $n$-th cyclotomic polynomial and let $\Psi_n$ denote the $n$-th inverse cyclotomic polynomial. In this note, we study $g(\Phi_n)$ and $g(\Psi_n)$ where $n$ is a product of odd primes, say $p_1 < p_2 < p_3$, etc. It is trivial to determine $g(\Phi_{p_1})$, $g(\Psi_{p_1})$ and $g(\Psi_{p_1p_2})$. Hence the simplest non-trivial cases are $g(\Phi_{p_1p_2})$ and $g(\Psi_{p_1p_2p_3})$. We provide an exact expression for $g(\Phi_{p_1p_2}).$ We also provide an exact expression for $g(\Psi_{p_1p_2p_3})$ under a mild condition. The condition is almost always satisfied (only finite exceptions for each $p_1$). We also provide a lower bound and an upper bound for $g(\Psi_{p_1p_2p_3})$.
• ### Sylvester's Double Sums: the general case(math/0701721)

March 27, 2008 math.AG, math.AC
In 1853 Sylvester introduced a family of double sum expressions for two finite sets of indeterminates and showed that some members of the family are essentially the polynomial subresultants of the monic polynomials associated with these sets. A question naturally arises: What are the other members of the family? This paper provides a complete answer to this question. The technique that we developed to answer the question turns out to be general enough to charactise all members of the family, providing a uniform method.
• ### An Elementary Proof of Sylvester's Double Sums for Subresultants(math/0604418)

Sept. 14, 2006 math.AG, math.AC
In 1853 Sylvester stated and proved an elegant formula that expresses the polynomial subresultants in terms of the roots of the input polynomials. Sylvester's formula was also recently proved by Lascoux and Pragacz by using multi-Schur functions and divided differences. In this paper, we provide an elementary proof that uses only basic properties of matrix multiplication and Vandermonde determinants.