Algorithm for computing μ-bases of univariate polynomials. (May 2017)

• Record Type: Journal Article
• Authors: Hong, Hoon; Hough, Zachary; Kogan, Irina A.
• Is Part Of: Journal of symbolic computation. Volume 80:Part 3(2017)
• Page Start: 844
• Page End: 874
• Publication Date: 2017-05
• Subjects: 12Y05 -- 13P10 -- 14Q05 -- 68W30; μ-basis -- Syzygy module -- Polynomial vectors -- Rational curves; Mathematics -- Data processing -- Periodicals; Numerical analysis -- Data processing -- Periodicals; Automatic programming (Computer science) -- Periodicals; Mathématiques -- Informatique -- Périodiques; Analyse numérique -- Informatique -- Périodiques; Programmation automatique -- Périodiques; Automatic programming (Computer science); Mathematics -- Data processing; Numerical analysis -- Data processing; Periodicals; Electronic journals; 510.285
• DOI: 10.1016/j.jsc.2016.08.013
• Languages: English
• ISSNs: 0747-7171

Abstract

Abstract: We present a new algorithm for computing a μ -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 ( 2 d + 1 ) × n ( d + 1 ) matrix over K, 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 ( 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 .