Algorithm for computing μ-bases of univariate polynomials

详细信息    查看全文

• 作者：Hoon Hong ^{hong@ncsu.edu} ; Zachary Hough ^{zchough@ncsu.edu} ; Irina A. Kogan ^{iakogan@ncsu.edu}
• 关键词：12Y05 ; 13P10 ; 14Q05 ; 68W30
• 刊名：Journal of Symbolic Computation
• 出版年：2017
• 出版时间：May-June 2017
• 年：2017
• 卷：80
• 期：part_P3
• 页码：844-874
• 全文大小：1140 K
• 卷排序：80

文摘

We present a new algorithm for computing a μ-basis of the syzygy module of n   polynomials in one variable over an arbitrary field KK. The algorithm is conceptually different from the previously-developed algorithms by Cox, Sederberg, Chen, Zheng, and Wang for n=3n=3, and by Song and Goldman for an arbitrary n  . The algorithm involves computing a “partial” reduced row-echelon form of a (2d+1)×n(d+1)(2d+1)×n(d+1) matrix over KK, where d is the maximum degree of the input polynomials. The proof of the algorithm is based on standard linear algebra and is completely self-contained. The proof includes a proof of the existence of the μ  -basis and as a consequence provides an alternative proof of the freeness of the syzygy module. The theoretical (worst case asymptotic) computational complexity of the algorithm is O(d2n+d3+n2)O(d2n+d3+n2). We have implemented this algorithm (HHK) and the one developed by Song and Goldman (SG). Experiments on random inputs indicate that SG is faster than HHK when d is sufficiently large for a fixed n, and that HHK is faster than SG when n is sufficiently large for a fixed d.