skip to main content
10.1145/1277548.1277551acmconferencesArticle/Chapter ViewAbstractPublication PagesissacConference Proceedingsconference-collections
Article

Structured matrix-based methods for polynomial ∈-gcd: analysis and comparisons

Published: 29 July 2007 Publication History

Abstract

The relationship between univariate polynomial ∈-gcd and factorization of resultant matrices is investigated and several stable and effective algorithms for the computation of an ∈-gcd are proposed. The main result is the design of a practically stable algorithm whose arithmetic cost is quadratic in the degrees of the input polynomials. The algorithm relies on the displacement structure properties of Sylvester and Bézout matrices. Its effectiveness is confirmed by numerical experiments.

References

[1]
B. Beckermann and G. Labahn. A fast and numerically stable Euclidean-like algorithm for detecting relatively prime numerical polynomials. J. Symbolic Comput., 26(6):691--714, 1998.
[2]
B. Beckermann and G. Labahn. When are two numerical polynomials relatively prime? J. Symbolic Comput., 26(6):677--689, 1998.
[3]
D. A. Bini and V. Y. Pan. Polynomial and Matrix Computations, vol. I: Fundamental Algorithms. Birkhäuser, Boston, 1994.
[4]
R. M. Corless, P. M. Gianni, B. M. Trager, and S. M. Watt. The singular value decomposition for approximate polynomial systems. In Proc. International Symposium on Symbolic and Algebraic Computation, pages 195--207, 1995.
[5]
R. M. Corless, S. M. Watt, and L. Zhi. QR factoring to compute the GCD of univariate approximate polynomials. IEEE Trans. Signal Processing, 52(12):3394--3402, 2004.
[6]
G. M. Diaz-Toca and L. Gonzalez-Vega. Computing greatest common divisors and squarefree decompositions through matrix methods: The parametric and approximate cases. Linear Algebra Appl., 412(2-3):222--246, 2006.
[7]
I. Z. Emiris, A. Galligo, and H. Lombardi. Certified approximate univariate GCDs. J. Pure Appl. Algebra, 117/118:229--251, 1997.
[8]
I. Gohberg, T. Kailath, and V. Olshevsky. Fast Gaussian elimination with partial pivoting for matrices with displacement structure. Math. Comp., 64(212):1557--1576, 1995.
[9]
M. Gu. Stable and efficient algorithms for structured systems of linear equations. SIAM J. Matrix Anal. Appl., 19(2):279--306, 1998.
[10]
G. Heinig. Inversion of generalized Cauchy matrices and other classes of structured matrices. In IMA volumes in Mathematics and its Applications. Springer, New York, 1995.
[11]
V. Hribernig and H. J. Stetter. Detection and validation of clusters of polynomial zeros. J. Symb. Comp., 24(6):667--681, 1997.
[12]
C.-P. Jeannerod and G. Labahn. SNAP user's guide. Technical Report CS-2002-22, University of Waterloo, 2002.
[13]
E. Kaltofen, Z. Yang, and L. Zhi. Approximate greatest common divisors of several polynomials with linearly constrained coefficients and singular polynomials. In Proc. International Symposium on Symbolic and Algebraic Computations, 2006.
[14]
N. K. Karmarkar and Y. N. Lakshman. On approximate GCDs of univariate polynomials. J. Symbolic Comp., 26(6):653--666, 1998.
[15]
B. Li, Z. Yang, and L. Zhi. Fast low rank approximation of a Sylvester matrix by structure total least norm. Journal of Japan Society for Symbolic and Algebraic Computation, 11:165--174, 2005.
[16]
M.-T. Noda and T. Sasaki. Approximate GCD and its application to ill-conditioned algebraic equations. J. Comput. Appl. Math., 38(1-3):335--351, 1991.
[17]
V. Y. Pan. Computation of approximate polynomial gcds and an extension. Information and Computation, 167(2):71--85, 2001.
[18]
L. B. Rall. Convergence of the Newton process to multiple solutions. Num. Math, 9:23--27, 1966.
[19]
A. Schönhage. Quasi-GCD computations. J. Complexity, 1:118--137, 1985.
[20]
M. Stewart. Stable pivoting for the fast factorization of Cauchy-like matrices. preprint, 1997.
[21]
D. R. Sweet and R. P. Brent. Error analysis of a fast partial pivoting method for structured matrices. In T. Luk, editor, Adv. Signal Proc. Algorithms, Proc. of SPIE, pages 266--280, 1995.
[22]
Z. Zeng. The approximate GCD of inexact polynomials. Part I: a univariate algorithm. To appear.
[23]
L. Zhi. Displacement structure in computing the approximate GCD of univariate polynomials. In W. Sit and Z. Li, editors, Lecture Notes Series on Computing, pages 228--298. World Scientific, 2003.

Cited By

View all
  • (2025)Approximate GCD of several multivariate sparse polynomials based on SLRA interpolationJournal of Symbolic Computation10.1016/j.jsc.2024.102368127:COnline publication date: 1-Mar-2025
  • (2023)Validated Root Enclosures for Interval Polynomials with MultiplicitiesProceedings of the 2023 International Symposium on Symbolic and Algebraic Computation10.1145/3597066.3597122(90-99)Online publication date: 24-Jul-2023
  • (2023)SLRA Interpolation for Approximate GCD of Several Multivariate PolynomialsProceedings of the 2023 International Symposium on Symbolic and Algebraic Computation10.1145/3597066.3597116(470-479)Online publication date: 24-Jul-2023
  • Show More Cited By

Recommendations

Comments

Information & Contributors

Information

Published In

cover image ACM Conferences
ISSAC '07: Proceedings of the 2007 international symposium on Symbolic and algebraic computation
July 2007
406 pages
ISBN:9781595937438
DOI:10.1145/1277548
  • General Chair:
  • Dongming Wang
Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Sponsors

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 29 July 2007

Permissions

Request permissions for this article.

Check for updates

Author Tags

  1. bézout matrix
  2. cauchy matrices
  3. displacement structure
  4. polynomial gcd
  5. sylvester matrix

Qualifiers

  • Article

Conference

ISSAC07
Sponsor:
ISSAC07: International Symposium on Symbolic and Algebraic Computation
July 29 - August 1, 2007
Ontario, Waterloo, Canada

Acceptance Rates

Overall Acceptance Rate 395 of 838 submissions, 47%

Contributors

Other Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

  • Downloads (Last 12 months)5
  • Downloads (Last 6 weeks)0
Reflects downloads up to 14 Feb 2025

Other Metrics

Citations

Cited By

View all
  • (2025)Approximate GCD of several multivariate sparse polynomials based on SLRA interpolationJournal of Symbolic Computation10.1016/j.jsc.2024.102368127:COnline publication date: 1-Mar-2025
  • (2023)Validated Root Enclosures for Interval Polynomials with MultiplicitiesProceedings of the 2023 International Symposium on Symbolic and Algebraic Computation10.1145/3597066.3597122(90-99)Online publication date: 24-Jul-2023
  • (2023)SLRA Interpolation for Approximate GCD of Several Multivariate PolynomialsProceedings of the 2023 International Symposium on Symbolic and Algebraic Computation10.1145/3597066.3597116(470-479)Online publication date: 24-Jul-2023
  • (2022)Simple Algorithm for GCD of PolynomialsWSEAS TRANSACTIONS ON MATHEMATICS10.37394/23206.2022.21.9921(869-871)Online publication date: 31-Dec-2022
  • (2022)A simple algorithm for GCD of polynomialsAnnals of Mathematics and Physics10.17352/amp.0000655:2(193-195)Online publication date: 23-Dec-2022
  • (2021)Relaxed NewtonSLRA for Approximate GCDComputer Algebra in Scientific Computing10.1007/978-3-030-85165-1_16(272-292)Online publication date: 16-Aug-2021
  • (2020)Toward the best algorithm for approximate GCD of univariate polynomialsJournal of Symbolic Computation10.1016/j.jsc.2019.08.004Online publication date: Jun-2020
  • (2019)Computing common factors of matrix polynomials with applications in system and control theory2019 IEEE 58th Conference on Decision and Control (CDC)10.1109/CDC40024.2019.9030137(7721-7726)Online publication date: Dec-2019
  • (2019)The computation of the degree of the greatest common divisor of three Bernstein basis polynomialsJournal of Computational and Applied Mathematics10.1016/j.cam.2019.112373(112373)Online publication date: Aug-2019
  • (2019)An ODE-based method for computing the approximate greatest common divisor of polynomialsNumerical Algorithms10.1007/s11075-018-0569-081:2(719-740)Online publication date: 1-Jun-2019
  • Show More Cited By

View Options

Login options

View options

PDF

View or Download as a PDF file.

PDF

eReader

View online with eReader.

eReader

Figures

Tables

Media

Share

Share

Share this Publication link

Share on social media