Computing Approximation GCD of Several Polynomials by Structured Total Least Norm

Xuefeng Duan, Xinjun Zhang, Qingwen Wang

College of Mathematics and Computational Science, Guilin University of Electronic Technology, Guilin, China.
Department of Mathematics, Shanghai University, Shanghai, China.

DOI: 10.4236/alamt.2013.34008                

Abstract

The task of determining the greatest common divisors (GCD) for several polynomials which arises in image compression, computer algebra and speech encoding can be formulated as a low rank approximation problem with Sylvester matrix. This paper demonstrates a method based on structured total least norm (STLN) algorithm for matrices with Sylvester structure. We demonstrate the algorithm to compute an approximate GCD. Both the theoretical analysis and the computational results show that the method is feasible.

Keywords

Sylvester Matrix; Approximate Greatest Common Divisor; Low Rank Approximation; Structured Total Least Norm; Numerical Method

Conflicts of Interest

The authors declare no conflicts of interest.

References

[1]	B. DeMoor, “Total Least Squares for Affinely Structured Matrices and the Noisy Realization Problem,” IEEE Transactions on Signal Process, Vol. 42, No. 11, 1994, pp. 3104-3113. http://dx.doi.org/10.1109/78.330370
[2]	R. M. Corless, P. M. Gianni, B. M. Tragerm and S. M. Watt, “The Singular Value Decomposition for Polynomial System,” Proceedings of International Symposium on Symbolic and Algebraic Computation, Montreal, 1995, pp. 195-207
[3]	S. R. Khare, H. K. Pillai and M. N. Belur, “Numerical Algorithm for Structured Low Rank Approximation Problem,” Proceeding of the 19th International Symposium on Mathematical Theory of Networks and Systems, Budapest, Hungary, 2010.
[4]	E. Kaltofen, Z. F. Yang and L. H. Zhi, “Approximate Greatest Common Divisors of Several Polynomials with Linearly Constrained Coecients and Simgular Polynomials,” Proceedings of International Symposium on Symbolic and Algebraic Computations, Genova, 2006.
[5]	N. Karkanias, S. Fatouros, M. Mitrouli and G. H. Halikias, “Approximate Greatest Common Divisor of Many Polynomials, Generalised Resultants, and Strength of Approximation,” Computers & Mathematics with Applications, Vol. 51, No. 12, 2006, pp. 1817-1830. http://dx.doi.org/10.1016/j.camwa.2006.01.010
[6]	I. Markovsky, “Structured Low-Rank Approximation and Its Applications,” Automatica, Vol. 44, No. 4, 2007, pp. 891-909. http://dx.doi.org/10.1016/j.automatica.2007.09.011
[7]	D. Rupprecht, “An Algorithm for Computing Certied Approximate GCD of Univariate Polynomials,” Journal of Pure and Applied Algebra, Vol. 139, No. 1-3, 1999, pp. 255-284. http://dx.doi.org/10.1016/S0022-4049(99)00014-6
[8]	J. A. Cadzow, “Signal Enhancement: A Composite Property Mapping Algorithm,” IEEE Transactions on Acoustic Speech Signal Process, Vol. 36, No. 1, 1988, pp. 49- 62. http://dx.doi.org/10.1109/29.1488
[9]	G. Cybenko, “A General Orthogonalization Technique with Applications to Time Series Analysis and Signal Processing,” Mathematics of Computation, Vol. 40, 1983, pp. 323-336. http://dx.doi.org/10.1090/S0025-5718-1983-0679449-6
[10]	J. R. Winkler and J. D. Allan, “Structured Total Least Norm and Approximate GCDs of Inexact Polynomials,” Journal of Computational and Applied Mathematics, Vol. 215, No. 1, 2008, pp. 1-13. http://dx.doi.org/10.1016/j.cam.2007.03.018
[11]	A. Frieze, R. Kannaa and S. Vempala, “Fast Monte-Carlo Algorithm for Finding Low Rank Approximations,” Journal of ACM, Vol. 51, No. 6, 2004, pp. 1025-1041. http://dx.doi.org/10.1145/1039488.1039494
[12]	R. Beer, “Quantitative in Vivo NMR (Nuclear Magnetic Resonance on Living Objects),” University of Technology Delft, 1995.
[13]	B. Paola, “Structured Matrix-Based Methods for Approximate Polynomial GCD,” Edizioni della Normale, 2011.
[14]	M. T. Chu, R. E. Funderlic and R. J. Plemmons, “Structured Low Rank Approximation,” Linear Algebra Applications, Vol. 366, No. 1, 2003, pp. 157-172. http://dx.doi.org/10.1016/S0024-3795(02)00505-0
[15]	B. Beckermann and G. Labahn, “A Fast and Numerically Stable Euclidean-Like Algorithm for Detecting Relative Prime Numerical Polynomials,” IEEE Journal of Symbolic Computation, Vol. 26, No. 6, 1998, pp. 691-714. http://dx.doi.org/10.1006/jsco.1998.0235
[16]	B. Y. Li, Z. F. Yang and L. H. Zhi, “Fast Low Rank Approximation of a Sylvester Matrix by Structured Total Least Norm,” Journal of JSSAC (Japan Society for Symbolic and Algebraic Computation), Vol. 11, No. 34, 2005, pp. 165-174.
[17]	B. Botting, M. Giesbrecht and J. May, “Using Riemannian SVD for Problems in Approximate Algebra,” Proceedings of the 2005 International Workshop on Symbolic-Numeric, 2005, Xi’an.
[18]	E. Kaltofen, Z. F. Yang and L. H. Zhi, “Structured Low Rank Approximation of a Sylvester Matrix,” International Workshop on Symbolic-Numeric Computation, Xi’an, 2005, pp. 19-21.
[19]	H. Park, L. Zhang and J. B. Rosen, “Low Rank Approximation of a Hankel Matrix by Structured Total Least Norm,” BIT Numerical Mathematics, Vol. 39, No. 4, 1999, pp. 757-779. http://dx.doi.org/10.1023/A:1022347425533
[20]	L. H. Zhi and Z. F. Yang, “Computing Approximate GCD of Univariate Polynomials by Structure Total Least Norm,” Mathematics-Mechanization Research Preprints, No. 24, 2004, pp. 375-387.
[21]	Z. Zeng and B. H. Dayton, “The Approximate GCD of Inexact Polynomials Part 2: A Multivariate Algorithm,” Proceedings of the 2004 International Symposium on Symbolic and Algebraic Computation, Santander, 2004.