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]

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]