Algorithm for computing mu-bases of univariate polynomials

作者：Hong Hoon^*; Hough Zachary; Kogan Irina A

来源：Journal of Symbolic Computation, 2017, 80: 844-874.

DOI：10.1016/j.jsc.2016.08.013

• mu-basis
• Syzygy module
• Polynomial vectors
• Rational curves

We present a new algorithm for computing a mu-basis of the syzygy module of n polynomials in one variable over an arbitrary field K. The algorithm is conceptually different from the previously developed algorithms by Cox, Sederberg, Chen, Zheng, and Wang for n = 3, and by Song and Goldman for an arbitrary n. The algorithm involves computing a "partial" reduced row-echelon form of a (2d + 1) x n(d + 1) matrix over 1K, 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 mu-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(d(2)n + d(3) + n(2)). 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.

• 出版日期2017-6