Ritt-Wu Characteristic Set Method for Laurent Partial Differential Polynomial Systems
|
摘要
In this paper, a Ritt-Wu characteristic set method for Laurent partial differential polynomial systems is presented. The concept of Laurent regular differential chain is de?ned and its basic properties are proved. The authors give a partial method to decide whether a Laurent differential chain A is Laurent regular. The decision for whether A is Laurent regular is reduced to the decision of whether a univariate differential chain A1 is Laurent regular. For a univariate differential chain A1,the authors ?rst give a criterion for whether A1 is Laurent regular in terms of its generic zeros and then give partial results on deciding whether A1 is Laurent regular.
In this paper, a Ritt-Wu characteristic set method for Laurent partial differential polynomial systems is presented. The concept of Laurent regular differential chain is de?ned and its basic properties are proved. The authors give a partial method to decide whether a Laurent differential chain A is Laurent regular. The decision for whether A is Laurent regular is reduced to the decision of whether a univariate differential chain A1 is Laurent regular. For a univariate differential chain A1,the authors ?rst give a criterion for whether A1 is Laurent regular in terms of its generic zeros and then give partial results on deciding whether A1 is Laurent regular.
In this paper, a Ritt-Wu characteristic set method for Laurent partial differential polynomial systems is presented. The concept of Laurent regular differential chain is de?ned and its basic properties are proved. The authors give a partial method to decide whether a Laurent differential chain A is Laurent regular. The decision for whether A is Laurent regular is reduced to the decision of whether a univariate differential chain A1 is Laurent regular. For a univariate differential chain A1,the authors ?rst give a criterion for whether A1 is Laurent regular in terms of its generic zeros and then give partial results on deciding whether A1 is Laurent regular.
引文
[1]Ritt J,Differential Algebra,The American Mathematical Society,1950.
[2]Wu W T,On the decision problem and the mechanization of theorem-proving in elementary geometry,Science in China Ser.A,1978,29(2):117-138.
[3]Wu W T,Basic principles of mechanical theorem proving in elementary geometries,Journal of Automated Reasoning,1986,2(3):221-252.
[4]Wu W T,Mathematics Mechanization,Science Press/Kluwer,Beijing,2001.
[5]Aubry P,Lazard D,and Maza M M,On the theories of triangular sets,Journal of Symbolic Computation,1999,28(1-2):105-124.
[6]Chou S C and Gao X S,Ritt-Wu’s decomposition algorithm and geometry theorem proving,Tenth International Conference on Automated Deduction,Springer-Verlag,New York,1990,207-220.
[7]Cheng J S and Gao X S,Multiplicity-preserving triangular set decomposition of two polynomials,Journal of Systems Science and Complexity,2014,27(6):1320-1344.
[8]Li B H,A method to solve algebraic equations up to multiplicities via Ritt-Wu’s characteristic sets,Acta Analysis Functionalis Applicata,2003,5(2):97-109.
[9]Li B H,Hilbert problem 15 and Ritt-Wu method(I),Journal of Systems Science and Complexity,2019,32(1):47-61.
[10]Li X and Maza M M,Fast arithmetic for triangular sets:From theory to practice,International Symposium,2007,269-276.
[11]Wang D,Elimination Methods,Springer,Vienna,2001.
[12]Yang L,Zhang J Z,and Hou X R,Non-Linear Algebraic Equations and Automated Theorem Proving,Shanghai Science and Education Pub.,Shanghai,1996.
[13]Chen C,Davenport J H,May J P,et al.,Triangular decomposition of semi-algebraic systems,Journal of Symbolic Computation,2013,49:3-26.
[14]Chai F,Gao X S,and Yuan C,A characteristic set method for solving boolean equations and applications in cryptanalysis of stream ciphers,Journal of Systems Science and Complexity,2008,21(2):191-208.
[15]Gao X S and Huang Z,Characteristic set algorithms for equation solving in finite fields,Journal of Symbolic Computation,2011,46(6):655-679.
[16]Li X,Mou C,and Wang D,Decomposing polynomial sets into simple sets over finite fields:The zero-dimensional case,Theoretical Computer Science,2010,60(11):2983-2997.
[17]Boulier F,Lemaire F,and Maza M M,Computing differential characteristic sets by change of ordering,Journal of Symbolic Computation,2010,45(1):124-149.
[18]Bouziane D,Rody A K,and Ma arouf H,Unmixed-dimensional decomposition of a finitely generated perfect differential ideal,Journal of Symbolic Computation,2001,31(6):631-649.
[19]Chou S C and Gao X S,Automated reasonning in differential geometry and mechanics using the characteristic set method.Part I.An improved version of Ritt-Wu’s decomposition algorithm,Journal of Automated Reasonning,1993,10:161-172.
[20]Hubert E,Factorization-free decomposition algorithms in differential algebra,Journal of Symbolic Computation,2000,29(4):641-662.
[21]Sit W Y,The Ritt-Kolchin theory for differential polynomials,Differential Algebra and Related Topics,2002,1-70.
[22]Zhu W and Gao X S,A triangular decomposition algorithm for differential polynomial systems with elementary computation complexity,Journal of Systems Science and Complexity,2017,30(2):464-483.
[23]Gao X S,Luo Y,and Yuan C M,A characteristic set method for ordinary difference polynomial systems,Journal of Symbolic Computation,2009,44(3):242-260.
[24]Wu W T and Gao X S,Mathematics mechanization and applications after thirty years,Frontiers of Computer Science in China,2007,1(1):1-8.
[25]Gao X S,Huang Z,and Yuan C M,Binomial difference ideals,Journal of Symbolic Computation,2017,80:665-706.
[26]Gao X S,Huang Z,Wang J,et al.,Toric difference variety,Journal of Systems Science and Complexity,2017,30(1):173-195.
[27]Hu Y and Gao X S,Characteristic set method for Laurent differential polynomial systems,International Workshop on Computer Algebra in Scientific Computing,Springer,2017,183-195.
[28]Cano J,An extension of the Newton-Puiseux polygon construction to give solutions of Pfaffian forms,Annales-Institut Fourier,1993,43(1):125-142.
[29]Fine H B,On the functions defined by differential equations,with an extension of the Puiseux polygon construction to these equations,American Journal of Mathematics,1889,11(4):317-328.
[30]Grigor’ev D Y and Singer M F,Solving ordinary differential equations in terms of series with real exponents,Transactions of the American Mathematical Society,1991,327(1):329-351.
[31]Kolchin E R,Differential Algebra and Algebraic Groups,Academic Press,New York,1973.
[32]Rosenfeld A,Specializations in differential algebra,Transactions of the American Mathematical Society,1959,90(3):394-407.
[33]Li W and Li Y H,Computation of differential chow forms for ordinary prime differential ideals,Advances in Applied Mathematics,2016,72:77-112.
[2]Wu W T,On the decision problem and the mechanization of theorem-proving in elementary geometry,Science in China Ser.A,1978,29(2):117-138.
[3]Wu W T,Basic principles of mechanical theorem proving in elementary geometries,Journal of Automated Reasoning,1986,2(3):221-252.
[4]Wu W T,Mathematics Mechanization,Science Press/Kluwer,Beijing,2001.
[5]Aubry P,Lazard D,and Maza M M,On the theories of triangular sets,Journal of Symbolic Computation,1999,28(1-2):105-124.
[6]Chou S C and Gao X S,Ritt-Wu’s decomposition algorithm and geometry theorem proving,Tenth International Conference on Automated Deduction,Springer-Verlag,New York,1990,207-220.
[7]Cheng J S and Gao X S,Multiplicity-preserving triangular set decomposition of two polynomials,Journal of Systems Science and Complexity,2014,27(6):1320-1344.
[8]Li B H,A method to solve algebraic equations up to multiplicities via Ritt-Wu’s characteristic sets,Acta Analysis Functionalis Applicata,2003,5(2):97-109.
[9]Li B H,Hilbert problem 15 and Ritt-Wu method(I),Journal of Systems Science and Complexity,2019,32(1):47-61.
[10]Li X and Maza M M,Fast arithmetic for triangular sets:From theory to practice,International Symposium,2007,269-276.
[11]Wang D,Elimination Methods,Springer,Vienna,2001.
[12]Yang L,Zhang J Z,and Hou X R,Non-Linear Algebraic Equations and Automated Theorem Proving,Shanghai Science and Education Pub.,Shanghai,1996.
[13]Chen C,Davenport J H,May J P,et al.,Triangular decomposition of semi-algebraic systems,Journal of Symbolic Computation,2013,49:3-26.
[14]Chai F,Gao X S,and Yuan C,A characteristic set method for solving boolean equations and applications in cryptanalysis of stream ciphers,Journal of Systems Science and Complexity,2008,21(2):191-208.
[15]Gao X S and Huang Z,Characteristic set algorithms for equation solving in finite fields,Journal of Symbolic Computation,2011,46(6):655-679.
[16]Li X,Mou C,and Wang D,Decomposing polynomial sets into simple sets over finite fields:The zero-dimensional case,Theoretical Computer Science,2010,60(11):2983-2997.
[17]Boulier F,Lemaire F,and Maza M M,Computing differential characteristic sets by change of ordering,Journal of Symbolic Computation,2010,45(1):124-149.
[18]Bouziane D,Rody A K,and Ma arouf H,Unmixed-dimensional decomposition of a finitely generated perfect differential ideal,Journal of Symbolic Computation,2001,31(6):631-649.
[19]Chou S C and Gao X S,Automated reasonning in differential geometry and mechanics using the characteristic set method.Part I.An improved version of Ritt-Wu’s decomposition algorithm,Journal of Automated Reasonning,1993,10:161-172.
[20]Hubert E,Factorization-free decomposition algorithms in differential algebra,Journal of Symbolic Computation,2000,29(4):641-662.
[21]Sit W Y,The Ritt-Kolchin theory for differential polynomials,Differential Algebra and Related Topics,2002,1-70.
[22]Zhu W and Gao X S,A triangular decomposition algorithm for differential polynomial systems with elementary computation complexity,Journal of Systems Science and Complexity,2017,30(2):464-483.
[23]Gao X S,Luo Y,and Yuan C M,A characteristic set method for ordinary difference polynomial systems,Journal of Symbolic Computation,2009,44(3):242-260.
[24]Wu W T and Gao X S,Mathematics mechanization and applications after thirty years,Frontiers of Computer Science in China,2007,1(1):1-8.
[25]Gao X S,Huang Z,and Yuan C M,Binomial difference ideals,Journal of Symbolic Computation,2017,80:665-706.
[26]Gao X S,Huang Z,Wang J,et al.,Toric difference variety,Journal of Systems Science and Complexity,2017,30(1):173-195.
[27]Hu Y and Gao X S,Characteristic set method for Laurent differential polynomial systems,International Workshop on Computer Algebra in Scientific Computing,Springer,2017,183-195.
[28]Cano J,An extension of the Newton-Puiseux polygon construction to give solutions of Pfaffian forms,Annales-Institut Fourier,1993,43(1):125-142.
[29]Fine H B,On the functions defined by differential equations,with an extension of the Puiseux polygon construction to these equations,American Journal of Mathematics,1889,11(4):317-328.
[30]Grigor’ev D Y and Singer M F,Solving ordinary differential equations in terms of series with real exponents,Transactions of the American Mathematical Society,1991,327(1):329-351.
[31]Kolchin E R,Differential Algebra and Algebraic Groups,Academic Press,New York,1973.
[32]Rosenfeld A,Specializations in differential algebra,Transactions of the American Mathematical Society,1959,90(3):394-407.
[33]Li W and Li Y H,Computation of differential chow forms for ordinary prime differential ideals,Advances in Applied Mathematics,2016,72:77-112.