Triangular decomposition with different properties has been used for various types of problem solving.In this paper,the concepts of pure chains and square-free pure triangular decomposition(SFPTD)of zero-dimensional p...Triangular decomposition with different properties has been used for various types of problem solving.In this paper,the concepts of pure chains and square-free pure triangular decomposition(SFPTD)of zero-dimensional polynomial systems are defined.Because of its good properties,SFPTD may be a key way to many problems related to zero-dimensional polynomial systems.Inspired by the work of Wang(2016)and of Dong and Mou(2019),the authors propose an algorithm for computing SFPTD based on Gr¨obner bases computation.The novelty of the algorithm is that the authors make use of saturated ideals and separant to ensure that the zero sets of any two pure chains are disjoint and every pure chain is square-free,respectively.On one hand,the authors prove the arithmetic complexity of the new algorithm can be single exponential in the square of the number of variables,which seems to be among the rare complexity analysis results for triangular-decomposition methods.On the other hand,the authors show experimentally that,on a large number of examples in the literature,the new algorithm is far more efficient than a popular triangular-decomposition method based on pseudodivision,and the methods based on SFPTD for real solution isolation and for computing radicals of zero-dimensional ideals are very efficient.展开更多
A generalization of the Householder transformation,renamed as elementary matrix by A.S.Householder:Unitary transformation of a nonsymmetric matrix,J.ACM,5(4),339–342,1958,was introduced by LaBudde(Math Comput 17(84):...A generalization of the Householder transformation,renamed as elementary matrix by A.S.Householder:Unitary transformation of a nonsymmetric matrix,J.ACM,5(4),339–342,1958,was introduced by LaBudde(Math Comput 17(84):433–437,1963)as a tool to obtain a tridiagonal matrix similar to a given square matrix.Some of the free parameters of the transformation can be chosen to attain better numerical properties.In this work,we study the spectral properties of the transformation.We also propose a special choice for free coefficients of that transformation to minimize its condition number.The transformation with such suitable choice of parameters is called optimal.展开更多
基金supported by National Key R&D Program of China under Grant No.2022YFA1005102the National Natural Science Foundation of China under Grant No.61732001。
文摘Triangular decomposition with different properties has been used for various types of problem solving.In this paper,the concepts of pure chains and square-free pure triangular decomposition(SFPTD)of zero-dimensional polynomial systems are defined.Because of its good properties,SFPTD may be a key way to many problems related to zero-dimensional polynomial systems.Inspired by the work of Wang(2016)and of Dong and Mou(2019),the authors propose an algorithm for computing SFPTD based on Gr¨obner bases computation.The novelty of the algorithm is that the authors make use of saturated ideals and separant to ensure that the zero sets of any two pure chains are disjoint and every pure chain is square-free,respectively.On one hand,the authors prove the arithmetic complexity of the new algorithm can be single exponential in the square of the number of variables,which seems to be among the rare complexity analysis results for triangular-decomposition methods.On the other hand,the authors show experimentally that,on a large number of examples in the literature,the new algorithm is far more efficient than a popular triangular-decomposition method based on pseudodivision,and the methods based on SFPTD for real solution isolation and for computing radicals of zero-dimensional ideals are very efficient.
基金The work of the first and third authors was partially supported by National Council for Scientific and Technological Development(CNPq),Brazil.
文摘A generalization of the Householder transformation,renamed as elementary matrix by A.S.Householder:Unitary transformation of a nonsymmetric matrix,J.ACM,5(4),339–342,1958,was introduced by LaBudde(Math Comput 17(84):433–437,1963)as a tool to obtain a tridiagonal matrix similar to a given square matrix.Some of the free parameters of the transformation can be chosen to attain better numerical properties.In this work,we study the spectral properties of the transformation.We also propose a special choice for free coefficients of that transformation to minimize its condition number.The transformation with such suitable choice of parameters is called optimal.
