Search

In this paper, we propose new deterministic and Monte Carlo interpolation algorithms for sparse multivariate polynomials represented by straight-line programs. Let f be an n -variate polynomial given by a straight-line program, which has a total degree bound D and a term bound T. Our deterministic algorithm is quadratic in n , T and cubic in log ⁡ D in the Soft-Oh sense, which has better complexities than existing deterministic interpolation algorithms in most cases. Our Monte Carlo interpolation algorithms have better complexities than existing Monte Carlo interpolation algorithms and are the first algorithms whose complexities are linear in nT and polynomial in log ⁡ D in the Soft-Oh sense. [ABSTRACT FROM AUTHOR]

In this paper, we first introduce the concept of Laurent differentially essential systems and give a criterion for a Laurent differential polynomial system to be Laurent differentially essential in terms of its support matrix. Then, the sparse differential resultant for a Laurent differentially essential system is defined, and its basic properties are proved. In particular, order and degree bounds for the sparse differential resultant are given. Based on these bounds, an algorithm to compute the sparse differential resultant is proposed, which is single exponential in terms of the Jacobi number and the size of the system. [ABSTRACT FROM AUTHOR]

In this paper, an intersection theory for generic differential polynomials is presented. The intersection of an irreducible differential variety of dimension d and order h with a generic differential hypersurface of order s is shown to be an irreducible variety of dimension d - 1 and order h + s. As a consequence, the dimension conjecture for generic differential polynomials is proved. Based on intersection theory, the Chow form for an irreducible differential variety is defined and most of the properties of the Chow form in the algebraic case are established for its differential counterpart. Furthermore, the generalized differential Chow form is defined and its properties are proved. As an application of the generalized differential Chow form, the differential resultant of n+1 generic differential polynomials in n variables is defined and properties similar to that of the Macaulay resultant for multivariate polynomials are proved. [ABSTRACT FROM AUTHOR]

Abstract: In this paper, a linear univariate representation for the roots of a zero-dimensional polynomial equation system is presented, where the complex roots of the polynomial system are represented as linear combinations of the roots of several univariate polynomial equations. An algorithm is proposed to compute such a representation for a given zero-dimensional polynomial equation system based on Gröbner basis computation. The main advantage of this representation is that the precision of the roots of the system can be easily controlled. In fact, based on the linear univariate representation, we can give the exact precisions needed for isolating the roots of the univariate equations in order to obtain roots of the polynomial system with a given precision. As a consequence, a root isolating algorithm for a zero-dimensional polynomial equation system can be easily derived from its linear univariate representation. [Copyright &y& Elsevier]

Abstract: Efficient characteristic set methods for computing zeros of polynomial equation systems in a finite field are proposed. The concept of proper triangular sets is introduced and an explicit formula for the number of zeros of a proper and monic triangular set is given. An improved zero decomposition algorithm is proposed to reduce the zero set of an equation system to the union of zero sets of monic proper triangular sets. The bitsize complexity of this algorithm is shown to be for Boolean polynomials, where is the number of variables and is the number of equations. We also give a multiplication free characteristic set method for Boolean polynomials, where the sizes of the polynomials occurred during the computation do not exceed the sizes of the input polynomials and the bitsize complexity of algorithm is for input polynomials with variables and degree . The algorithms are implemented in the case of Boolean polynomials and extensive experiments show that they are quite efficient for solving certain classes of Boolean equations raising from stream ciphers. [Copyright &y& Elsevier]

Abstract: In this paper, we present an algorithm to decompose ordinary non-linear difference polynomials with rational functions as coefficients. The algorithm provides an effective reduction of the decomposition of difference polynomials to the decomposition of linear difference polynomials over the same coefficient field. The algorithm is implemented in Maple for the constant coefficient case. Experimental results show that the algorithm is quite effective and can be used to decompose difference polynomials with thousands of terms. [Copyright &y& Elsevier]

Abstract: We present a complete numerical algorithm for isolating all the real zeros of a zero-dimensional triangular polynomial system . Our system is general, with no further assumptions. In particular, our algorithm successfully treats multiple zeros directly in such systems. A key idea is to introduce evaluation bounds and sleeve bounds. We also present a much more efficient algorithm for zero-dimensional triangular systems without multiple roots. We implemented our algorithms, and promising experimental results are shown. [Copyright &y& Elsevier]

Abstract: We prove several basic properties for difference ascending chains, including a necessary and sufficient condition for an ascending chain to be the characteristic set of its saturation ideal and a necessary and sufficient condition for an ascending chain to be the characteristic set of a reflexive prime ideal. Based on these properties, we propose an algorithm to decompose the zero set of a finite set of difference polynomials into the union of zero sets of certain ascending chains. This decomposition algorithm is implemented and used to solve the perfect ideal membership problem, and to prove certain difference identities automatically. [Copyright &y& Elsevier]

Abstract: In this paper, we generalize the results of Feng and Gao [Feng, R., Gao, X.S., 2006. A polynomial time algorithm to find rational general solutions of first order autonomous ODEs. J. Symbolic Comput., 41(7), 735–762] to the case of difference equations. We construct two classes of ordinary difference equations () whose solutions are exactly the univariate polynomial and rational functions respectively. On the basis of these and the difference characteristic set method, we give a criterion for an with any order and nonconstant coefficients to have a rational type general solution. For the first-order autonomous (constant coefficient) , we give a polynomial time algorithm for finding the polynomial solutions and an algorithm for finding the rational solutions for a given degree. [Copyright &y& Elsevier]

Abstract: We give a necessary and sufficient condition for an algebraic ODE to have a rational type general solution. For a first order autonomous ODE , we give an exact degree bound for its rational solutions, based on the connection between rational solutions of and rational parametrizations of the plane algebraic curve defined by . For a first order autonomous ODE, we further give a polynomial time algorithm for computing a rational general solution if it exists based on the computation of Laurent series solutions and Padé approximants. Experimental results show that the algorithm is quite efficient. [Copyright &y& Elsevier]

Based on the observation that Q (p − 1) × (p − 1) is isomorphic to a quotient skew polynomial ring, we propose a new deterministic algorithm for (p − 1) × (p − 1) matrix multiplication over Q , where p is a prime number. The algorithm has complexity O (T ω − 2 p 2) , where T ≤ p − 1 is a parameter determined by the skew-polynomial-sparsity of input matrices and ω is the asymptotic exponent of matrix multiplication. Here a matrix is skew-polynomial-sparse if its corresponding skew polynomial is sparse. Moreover, by introducing randomness, we also propose a probabilistic algorithm with complexity O ∼ (t ω − 2 p 2 + p 2 log ⁡ 1 ν) , where t ≤ p − 1 is the skew-polynomial-sparsity of the product and ν is the probability parameter. The main feature of the algorithms is the acceleration for matrix multiplication if the input matrices or their products are skew-polynomial-sparse. [ABSTRACT FROM AUTHOR]

In this paper, the concept of sparse difference resultant for a Laurent transformally essential system of difference polynomials is introduced and a simple criterion for the existence of sparse difference resultant is given. The concept of transformally homogenous polynomial is introduced and the sparse difference resultant is proved to be transformally homogenous. It is shown that the vanishing of the sparse difference resultant gives a necessary condition for the corresponding difference polynomial system to have non-zero solutions. Order and degree bounds for the sparse difference resultant are given. Based on these bounds, an algorithm to compute the sparse difference resultant is proposed, which is single exponential in terms of the number of variables, the Jacobi number, and the size of the Laurent transformally essential system. Furthermore, the precise order and degree, a determinant representation, and a Poisson-type product formula for the difference resultant are given. [ABSTRACT FROM AUTHOR]