Research ArticleOpen AccessGoogle Scholar indexed
Computing Approximation GCD of Several Polynomials by Structured Total Least Norm
College of Mathematics and Computational Science, Guilin University of Electronic Technology, Guilin, China
College of Mathematics and Computational Science, Guilin University of Electronic Technology, Guilin, China
Department of Mathematics, Shanghai University, Shanghai, China
- 1 College of Mathematics and Computational Science, Guilin University of Electronic Technology, Guilin, China
- 2 College of Mathematics and Computational Science, Guilin University of Electronic Technology, Guilin, China
- 3 Department of Mathematics, Shanghai University, Shanghai, China
Advances in Linear Algebra & Matrix Theory·Volume 03 (2013)·Pages 39–46·Published 6 December 2013·DOI10.4236/alamt.2013.34008
Copy link · social · email
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.
KeywordsSylvester MatrixApproximate Greatest Common DivisorLow Rank ApproximationStructured Total Least NormNumerical Method
- 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
- 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
- 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.
- 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.
- 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
- 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
- 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
- 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
- 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
- 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
- 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