Roots Multiplicity without Companion Matrices

• Autorzy: Koprowski P.

Identyfikatory

DOI

10.3233/FI-2017-1540

• Języki publikacji: EN

Abstrakty

EN

We show a method for constructing a polynomial interpolating roots' multiplicities of another polynomial, that does not use companion matrices. This leads to a modification to Guersenzvaig-Szechtman square-free decomposition algorithm that is more efficient both in theory and in practice.

Słowa kluczowe

EN

companion matrix; square-free factorization

• Wydawca: IOS Press
• Czasopismo: Fundamenta Informaticae
• Rocznik: 2017
• Tom: Vol. 153, nr 3
• Strony: 265--270
• Opis fizyczny: Bibliogr. 8 poz., tab.

Twórcy

autor

Koprowski P.

• Faculty of Mathematics, University of Silesia, ul. Bankowa 14, PL-40-007 Katowice, Poland

Bibliografia

• [1] Tobey RG. Algorithms for antidifferentiation of rational functions. Ph.D. thesis, Harvard, 1967.
• [2] Horowitz E. Algorithms for symbolic integration of rational functions. Ph.D. thesis, University of Wisconsin, 1969.
• [3] Musser DR. Algorithms for polynomial factorization. Ph.D. thesis, University of Wisconsin, 1971.
• [4] Yun DY. On Square-free Decomposition Algorithms. In: Proceedings of the Third ACM Symposium on Symbolic and Algebraic Computation, SYMSAC ’76. ACM, New York, NY, USA, 1976 pp. 26–35. doi:10.1145/800205.806320. URL http://doi.acm.org/10.1145/800205.806320.
• [5] Guersenzvaig NH, Szechtman F. Roots multiplicity and square-free factorization of polynomials using companion matrices. Linear Algebra Appl., 2012. 436(9):3160–3164. doi:10.1016/j.laa.2011.10.018. URL http://dx.doi.org/10.1016/j.laa.2011.10.018.
• [6] Le Gall F. Powers of tensors and fast matrix multiplication. In: ISSAC 2014−Proceedings of the 39th International Symposium on Symbolic and Algebraic Computation, pp. 296–303. ACM, New York, 2014. doi:10.1145/2608628.2608664. URL http://dx.doi.org/10.1145/2608628.2608664.
• [7] Zhdanovich DV. Exponent of complexity of matrix multiplication. Fundam. Prikl. Mat., 2011/12. 17(2):107–166. doi:10.1007/s10958-012-1009-7. URL http://dx.doi.org/10.1007/s10958-012-1009-7.
• [8] Bosma W, Cannon J, Playoust C. The Magma algebra system. I. The user language. J. Symbolic Comput., 1997. 24(3-4):235–265. doi:10.1006/jsco.1996.0125. Computational algebra and number theory (London, 1993), URL http://dx.doi.org/10.1006/jsco.1996.0125.