@article{hong_hough_kogan_2017, title={Algorithm for computing mu-bases of univariate polynomials}, volume={80}, ISSN={["0747-7171"]}, url={http://www.scopus.com/inward/record.url?eid=2-s2.0-84995550983&partnerID=MN8TOARS}, DOI={10.1016/j.jsc.2016.08.013}, abstractNote={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 (2d+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(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.}, journal={JOURNAL OF SYMBOLIC COMPUTATION}, publisher={Elsevier BV}, author={Hong, Hoon and Hough, Zachary and Kogan, Irina A.}, year={2017}, pages={844–874} }