13 results on '"Xiao, Shan"'
Search Results
2. INTERSECTION THEORY IN DIFFERENTIAL ALGEBRAIC GEOMETRY: GENERIC INTERSECTIONS AND THE DIFFERENTIAL CHOW FORM.
- Author
-
GAO, XIAO-SHAN, WEI LI, and YUAN, CHUN-MING
- Subjects
- *
ALGEBRAIC geometry , *DIFFERENTIAL geometry , *INTERSECTION theory , *INTERSECTION numbers , *HYPERSURFACES , *POLYNOMIALS , *MULTIVARIATE analysis - Abstract
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]
- Published
- 2013
- Full Text
- View/download PDF
3. Root isolation of zero-dimensional polynomial systems with linear univariate representation
- Author
-
Cheng, Jin-San, Gao, Xiao-Shan, and Guo, Leilei
- Subjects
- *
POLYNOMIALS , *UNIVARIATE analysis , *LINEAR algebra , *ALGORITHMS , *ACCURACY , *SYMBOLIC computation - Abstract
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]
- Published
- 2012
- Full Text
- View/download PDF
4. Characteristic set algorithms for equation solving in finite fields
- Author
-
Gao, Xiao-Shan and Huang, Zhenyu
- Subjects
- *
SET theory , *ALGORITHMS , *FINITE fields , *POLYNOMIALS , *MATHEMATICAL decomposition , *MATHEMATICAL variables , *STREAM ciphers - Abstract
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]
- Published
- 2012
- Full Text
- View/download PDF
5. Decomposition of ordinary difference polynomials
- Author
-
Zhang, Mingbo and Gao, Xiao-Shan
- Subjects
- *
MATHEMATICAL decomposition , *DIFFERENCE operators , *POLYNOMIALS , *ALGORITHMS , *MATHEMATICAL analysis , *DIFFERENCE algebra - Abstract
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]
- Published
- 2009
- Full Text
- View/download PDF
6. Complete numerical isolation of real roots in zero-dimensional triangular systems
- Author
-
Cheng, Jin-San, Gao, Xiao-Shan, and Yap, Chee-Keng
- Subjects
- *
ALGORITHMS , *NUMERICAL analysis , *POLYNOMIALS , *SYSTEMS theory , *ZERO (The number) , *DIMENSIONAL analysis - Abstract
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]
- Published
- 2009
- Full Text
- View/download PDF
7. A characteristic set method for ordinary difference polynomial systems
- Author
-
Gao, Xiao-Shan, Luo, Yong, and Yuan, Chunming
- Subjects
- *
POLYNOMIALS , *ALGORITHMS , *ALGEBRA , *FOUNDATIONS of arithmetic - Abstract
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]
- Published
- 2009
- Full Text
- View/download PDF
8. Rational solutions of ordinary difference equations
- Author
-
Feng, Ruyong, Gao, Xiao-Shan, and Huang, Zhenyu
- Subjects
- *
DIFFERENTIAL equations , *POLYNOMIALS , *NEWTON diagrams , *DIFFERENCE equations - Abstract
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]
- Published
- 2008
- Full Text
- View/download PDF
9. Decomposition of ordinary differential polynomials.
- Author
-
Xiao-Shan Gao and Mingbo Zhang
- Subjects
- *
MATHEMATICS , *ALGORITHMS , *ALGEBRA , *POLYNOMIALS - Abstract
Abstract  In this paper, we present a complete algorithm to decompose nonlinear differential polynomials in one variable and with coefficients in a computable differential field $${\mathcal K}$$ of characteristic zero. The algorithm provides an efficient reduction of the problem to the factorization of LODOs over the same coefficient field. Besides arithmetic operations, the algorithm needs decomposition of algebraic polynomials, factorization of multi-variable polynomials, and solution of algebraic linear equation systems. The algorithm is implemented in Maple for the constant field case. The program can be used to decompose differential polynomials with thousands of terms effectively. [ABSTRACT FROM AUTHOR]
- Published
- 2008
- Full Text
- View/download PDF
10. A polynomial time algorithm for finding rational general solutions of first order autonomous ODEs
- Author
-
Feng, Ruyong and Gao, Xiao-Shan
- Subjects
- *
POLYNOMIALS , *ALGEBRA , *LAURENT series , *ALGORITHMS - Abstract
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]
- Published
- 2006
- Full Text
- View/download PDF
11. Skew-polynomial-sparse matrix multiplication.
- Author
-
Huang, Qiao-Long, Ye, Ke, and Gao, Xiao-Shan
- Subjects
- *
MATRIX multiplications , *PRIME numbers , *POLYNOMIAL rings , *DETERMINISTIC algorithms , *EXPONENTS , *POLYNOMIALS - Abstract
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]
- Published
- 2024
- Full Text
- View/download PDF
12. Sparse difference resultant.
- Author
-
Li, Wei, Yuan, Chun-Ming, and Gao, Xiao-Shan
- Subjects
- *
POLYNOMIALS , *EXISTENCE theorems , *MATHEMATICAL bounds , *ALGORITHMS , *JACOBI method , *POISSON processes - Abstract
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]
- Published
- 2015
- Full Text
- View/download PDF
13. Sparse Differential Resultant for Laurent Differential Polynomials.
- Author
-
Li, Wei, Yuan, Chun-Ming, and Gao, Xiao-Shan
- Subjects
- *
DIFFERENTIAL dimension polynomials , *POLYNOMIALS , *ALGORITHMS , *DIFFERENTIAL algebra , *MATRICES (Mathematics) - Abstract
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]
- Published
- 2015
- Full Text
- View/download PDF
Catalog
Discovery Service for Jio Institute Digital Library
For full access to our library's resources, please sign in.