Approximate greatest common divisors of several polynomials with linearly constrained coefficients and singular polynomials

ABSTRACT

We consider the problem of computing minimal real or complex deformations to the coefficients in a list of relatively prime real or complex multivariate polynomials such that the deformed polynomials have a greatest common divisor (GCD) of at least a given degree k. In addition, we restrict the deformed coefficients by a given set of linear constraints, thus introducing the linearly constrained approximate GCD problem. We present an algorithm based on a version of the structured total least norm (STLN) method and demonstrate on a diverse set of benchmark polynomials that the algorithm in practice computes globally minimal approximations. As an application of the linearly constrained approximate GCD problem we present an STLN-based method that computes a real or complex polynomial the nearest real or complex polynomial that has a root of multiplicity at least k. We demonstrate that the algorithm in practice computes on the benchmark polynomials given in the literature the known globally optimal nearest singular polynomials. Our algorithms can handle, via randomized preconditioning, the difficult case when the nearest solution to a list of real input polynomials actually has non-real complex coefficients.

REFERENCES

• 1: Andrew A. Anda , Haesun Park, Fast Plane Rotations with Dynamic Scaling, SIAM Journal on Matrix Analysis and Applications, v.15 n.1, p.162-174, Jan. 1994 [doi>10.1137/S0895479890193017]
• 2: Anda, A. A., and Park, H. Self-scaling fast rotations for stiff and equality-constrained linear least squares problems. Linear Algebra and Applications 234 (1996), 137--161.
• 3: Bernhard Beckermann , George Labahn, A fast and numerically stable Euclidean-like algorithm for detecting relatively prime numerical polynomials, Journal of Symbolic Computation, v.26 n.6, p.691-714, Dec. 1998 [doi>10.1006/jsco.1998.0235]
• 4: Botting, B., Giesbrecht, M., and May, J. Using Riemannian SVD for problems in approximate algebra. In Wang and Zhi {33}, pp. 209--219.
• 5: Chu, M. T., Funderlic, R. E., and Plemmons, R. J. Structured low rank approximation. Linear Algebra and Applications 366 (2003), 157--172.
• 6: Robert M. Corless , Patrizia M. Gianni , Barry M. Trager , Stephen M. Watt, The singular value decomposition for polynomial systems, Proceedings of the 1995 international symposium on Symbolic and algebraic computation, p.195-207, July 10-12, 1995, Montreal, Quebec, Canada [doi>10.1145/220346.220371]
• 7: Corless, R. M., Watt, S. M., and Zhi, L. QR factoring to compute the GCD of univariate approximate polynomials. IEEE Transactions on Signal Processing 52 (Dec. 2004), 3394--3402.
• 8: Dunaway, D. K. Calculation of zeros of a real polynomial through factorization using Euclid's algorithm. SIAM J. Numer. Anal. 11, 6 (1974), 1087--1104.
• 9: Eckart, C., and Young, G. The approximation of one matrix by another of lower rank. Psychometrika 1, 3 (Sept. 1936), 211--218.
• 10: Shuhong Gao , Erich Kaltofen , John May , Zhengfeng Yang , Lihong Zhi, Approximate factorization of multivariate polynomials via differential equations, Proceedings of the 2004 international symposium on Symbolic and algebraic computation, p.167-174, July 04-07, 2004, Santander, Spain [doi>10.1145/1005285.1005311]
• 11: Joachim von zur Gathen , Jürgen Gerhard, Modern computer algebra, Cambridge University Press, New York, NY, 1999
• 12: Gutierrez, J., Ed. ISSAC 2004 Proc. 2004 Internat. Symp. Symbolic Algebraic Comput. (New York, N. Y., 2004), ACM Press.
• 13: Markus A. Hitz , Erich Kaltofen, Efficient algorithms for computing the nearest polynomial with constrained roots, Proceedings of the 1998 international symposium on Symbolic and algebraic computation, p.236-243, August 13-15, 1998, Rostock, Germany [doi>10.1145/281508.281624]
• 14: Kahan, W. Numerical linear algebra. Canadian Math. Bull. 9 (1966), 757--801.
• 15: Erich Kaltofen , John May, On approximate irreducibility of polynomials in several variables, Proceedings of the 2003 international symposium on Symbolic and algebraic computation, p.161-168, August 03-06, 2003, Philadelphia, PA, USA [doi>10.1145/860854.860893]
• 16: Kaltofen, E., May, J., Yang, Z., and Zhi, L. Approximate factorization of multivariate polynomials using singular value decomposition. Manuscript, 22 pages. Submitted, Jan. 2006.
• 17: Kaltofen, E., Yang, Z., and Zhi, L. Structured low rank approximation of a Sylvester matrix. Manuscript, 15 pages, Oct. 2005. Preliminary version in SNC 2005 Proceedings, Dongming Wang and Lihong Zhi eds., pp. 188--201, distributed at the International Workshop on Symbolic-Numeric Computation in Xi'an, China, July 19--21, 2005.
• 18: Kaltofen, E., Yang, Z., and Zhi, L. Structured low rank approximation of a generalized Sylvester matrix. In Proc. of the Seventh Asian Symposium on Computer Mathematics (Seoul, South Korea, 2005), S. Pae and H. Park, Eds., Korea Institute for Advanced Study, pp. 219--222. Extended abstract.
• 19: Kaltofen, E., Yang, Z., and Zhi, L. Approximate greatest common divisors of several polynomials with linearly constrained coefficients and singular polynomials. Manuscript, 16 pages, Apr. 2006.
• 20: N. K. Karmarkar , Y. N. Lakshman, On approximate GCDs of univariate polynomials, Journal of Symbolic Computation, v.26 n.6, p.653-666, Dec. 1998 [doi>10.1006/jsco.1998.0232]
• 21: Lemmerling, P. Structured total least squares: analysis, algorithms and applications. Dissertation, Katholieke Universiteit Leuven, Belgium, 1999.
• 22: Lemmerling, P., Mastronardi, N., and Van Huffel, S. Fast algorithm for solving the Hankel/Toeplitz Structured Total Least Squares problem. Numerical Algorithms 23 (2000), 371--392.
• 23: Li, B., Liu, Z., and Zhi, L. Fast low rank approximation of a Sylvester matrix. In Wang and Zhi {33}, pp. 202--208.
• 24: Li, B., Yang, Z., and Zhi, L. Fast low rank approximation of a Sylvester matrix by structured total least norm. J. JSSAC (Japan Society for Symbolic and Algebraic Computation) 11, 3,4 (2005), 165--174.
• 25: Nicola Mastronardi , Philippe Lemmerling , Sabine Van Huffel, Fast Structured Total Least Squares Algorithm for Solving the Basic Deconvolution Problem, SIAM Journal on Matrix Analysis and Applications, v.22 n.2, p.533-553, 2000 [doi>10.1137/S0895479898345813]
• 26: May, J. P. Approximate factorization of polynomials in many variables and other problems in approximate algebra via singular value decomposition methods. PhD thesis, North Carolina State Univ., Raleigh, North Carolina, Aug. 2005.
• 27: Park, H., Zhang, L., and Rosen, J. B. Low rank approximation of a Hankel matrix by structured total least norm. BIT 39, 4 (1999), 757--779.
• 28: Pope, S., and Szanto, A. Nearest multivariate system with given root multiplicities. Manuscript available at http://www.math.ncsu.edu/~aszanto/papers.html, 2005.
• 29: Siegfried M. Rump, Structured Perturbations Part I: Normwise Distances, SIAM Journal on Matrix Analysis and Applications, v.25 n.1, p.1-30, 2003 [doi>10.1137/S0895479802405732]
• 30: T. Sasaki , M. Noda, Approximate square-free decomposition and root-finding of lll-conditioned algebraic equations, Journal of Information Processing, v.12 n.2, p.159-168, Jan. 1989
• 31: Schönhage, A. Quasi-gcd computations. Journal of Complexity 1 (1985), 118--137.
• 32: Stewart, G. W. Introduction to Matrix Computations. Academic Press, Inc., New York, 1973.
• 33: Wang, D., and Zhi, L., Eds. Proc. 2005 International Workshop on Symbolic-Numeric (July 2005). Distributed at the Workshop in Xi'an, China.
• 34: Zhonggang Zeng , Barry H. Dayton, The approximate GCD of inexact polynomials, Proceedings of the 2004 international symposium on Symbolic and algebraic computation, p.320-327, July 04-07, 2004, Santander, Spain [doi>10.1145/1005285.1005331]
• 35: Zhi, L. Displacement structure in computing approximate GCD of univariate polynomials. In Proc. Sixth Asian Symposium on Computer Mathematics (ASCM 2003) (Singapore, 2003), Z. Li and W. Sit, Eds., vol. 10 of Lecture Notes Series on Computing, World Scientific, pp. 288--298.
• 36: Zhi, L., Noda, M.-T., Kai, H., and Wu, W. Hybrid method for computing the nearest singular polynomials. Japan J. Industrial and Applied Math. 21, 2 (June 2004), 149--162.
• 37: Zhi Lihong , Wu Wenda, Nearest singular polynomials, Journal of Symbolic Computation, v.26 n.6, p.667-675, Dec. 1998 [doi>10.1006/jsco.1998.0233]

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
      I.2.1 Applications and Expert Systems

Additional Classification:
  G. Mathematics of Computing
  G.1 NUMERICAL ANALYSIS
      G.1.2 Approximation

General Terms:
Algorithms, Experimentation

Keywords:
approximate multiple root, approximate polynomial gcd, linear constraint, multivariate polynomial gcd, singular polynomial, symbolic/numeric hybrid method