Algorithms for Calculating Approximate Greatest Common Divisor of Univariate Polynomials

[1] B. Beckermann and G. Labahn. A fast and numerically stable Euclidean-like algorithm for detecting relatively prime numerical polynomials. J. Symb. Comput., 26(6):691–714, 1998.

[2] Boming Chi and Akira Terui. ct1counter/bezout-gpgcd: Initial release, July 2020. https://doi.org/10.5281/zenodo.3965389.

[3] Boming Chi and Akira Terui. The GPGCD algorithm with the B´ezout matrix. In Computer Algebra in Scientific Computing (CASC 2020), Lecture Notes in Computer Science, volume 12291, pages 170–187. Springer International Publishing, Cham, 2020.

[4] Boming Chi and Akira Terui. The GPGCD algorithm with the B´ezout matrix for multiple univariate polynomials (submitted). 12 pages, 2021.

[5] P. Chin, R. M. Corless, and G. F. Corliss. Optimization strategies for the approximate GCD problem. In Proceedings of the 1998 International Symposium on Symbolic and Algebraic Com- putation, pages 228–235. ACM, New York, NY, USA, 1998.

[6] Eng Wee Chionh, Ming Zhang, and Ronald N. Goldman. Fast computation of the Bezout and Dixon resultant matrices. J. Symb. Comput., 33(1):13–29, 2002.

[7] R. M. Corless, P. M. Gianni, B. M. Trager, and S. M. Watt. The singular value decomposition for polynomial systems. In Proceedings of the 1995 International Symposium on Symbolic and Algebraic Computation, pages 195–207. ACM, New York, NY, USA, 1995.

[8] R. M. Corless, S. M. Watt, and L. Zhi. QR factoring to compute the GCD of univariate approx- imate polynomials. IEEE Trans. Signal Process., 52(12):3394–3402, 2004.

[9] J. W. Demmel. Applied Numerical Linear Algebra. SIAM, USA, 1997.

[10] Gema M. Diaz-Toca and Laureano Gonzalez-Vega. Barnett’s Theorems About the Greatest Common Divisor of Several Univariate Polynomials Through Bezout-like Matrices. J. Symb. Comput., 34(1):59–81, 2002.

[11] I. Z. Emiris, A. Galligo, and H. Lombardi. Certified approximate univariate GCDs. J. Pure Appl. Algebra, 117/118:229–251, 1997.

[12] E. Kaltofen, Z. Yang, and L. Zhi. Approximate greatest common divisors of several polynomials with linearly constrained coefficients and singular polynomials. In Proceedings of the 2006 Inter- national Symposium on Symbolic and Algebraic Computation, pages 169–176. ACM, New York, NY, USA, 2006.

[13] E. Kaltofen, Z. Yang, and L. Zhi. Structured low rank approximation of a Sylvester matrix. In Symbolic-Numeric Computation, Trends in Mathematics, pages 69–83. Birkh¨auser, Basel, Switzer- land, 2007.

[14] N. K. Karmarkar and Y. N. Lakshman. On approximate GCDs of univariate polynomials. J. Symb. Comput., 26(6):653–666, 1998.

[15] Makoto Matsumoto and Takuji Nishimura. Mersenne Twister: A 623-dimensionally equidis- tributed uniform pseudo-random number generator. ACM Transactions on Modeling and Com- puter Simulation, 8(1):3–30, 1998.

[16] Kosaku Nagasaka. Relaxed NewtonSLRA for approximate GCD. In Computer Algebra in Scien- tific Computing (CASC 2021), Lecture Notes in Computer Science, volume 12865, pages 272–292. Springer International Publishing, Cham, 2021.

[17] Jorge Nocedal and Stephen J. Wright. Numerical Optimization. Springer, New York, NY, USA, second edition, 2006.

[18] V. Y. Pan. Computation of approximate polynomial GCDs and an extension. Inform. and Comput., 167(2):71–85, 2001.

[19] J. B. Rosen. The gradient projection method for nonlinear programming. II. Nonlinear con- straints. J. Soc. Indust. Appl. Math., 9:514–532, 1961.

[20] T. Sasaki and M-T. Noda. Approximate square-free decomposition and root-finding of ill- conditioned algebraic equations. J. Inform. Process., 12(2):159–168, 1989.

[21] A. Sch¨onhage. Quasi-GCD computations. J. Complexity, 1(1):118–137, 1985.

[22] E´ric Schost and Pierre-Jean Spaenlehauer. A quadratically convergent algorithm for structured low-rank approximation. Found. Comput. Math., 16(2):457–492, 2016.

[23] Hiroshi Sekigawa. Combining symbolic and numerical computation (in Japanese). IPSJ Magazine, 50(4):342–348, 2009.

[24] Dongxia Sun and Lihong Zhi. Structured low rank approximation of a bezout matrix. Mathematics in Computer Science, 1(2):427–437, Dec 2007.

[25] K. Tanabe. A geometric method in nonlinear programming. J. Optim. Theory Appl., 30(2):181– 210, Feb 1980.

[26] Akira Terui. An iterative method for calculating approximate GCD of univariate polynomials. In Proceedings of the 2009 International Symposium on Symbolic and Algebraic Computation, pages 351–358. ACM Press, New York, New York, USA, 2009.

[27] Akira Terui. GPGCD, an iterative method for calculating approximate GCD, for multiple univari- ate polynomials. In Computer Algebra in Scientific Computing (CASC 2010), Lecture Notes in Computer Science, volume 6244, pages 238–249. Springer Berlin Heidelberg, Berlin, Heidelberg, 2010.

[28] Akira Terui. GPGCD: An iterative method for calculating approximate GCD of univariate poly- nomials. Theor. Comput. Sci., 479:127–149, 2013.

[29] C. J. Zarowski, X. Ma, and F. W. Fairman. QR-factorization method for computing the great- est common divisor of polynomials with inexact coefficients. IEEE Trans. Signal Process., 48(11):3042–3051, 2000.

[30] Zhonggang Zeng. The numerical greatest common divisor of univariate polynomials. In Random- ization, Relaxation, and Complexity in Polynomial Equation Solving, volume 556 of Contemporary Mathematics, pages 187–217. AMS, Providence, RI, USA, 2011.

[31] L. Zhi. Displacement structure in computing approximate GCD of univariate polynomials. In Computer mathematics: Proc. Six Asian Symposium on Computer Mathematics (ASCM 2003), volume 10 of Lecture Notes Ser. Comput., pages 288–298. World Sci. Publ., River Edge, NJ, 2003.