×

Computation of approximate polynomial GCDs and an extension. (English) Zbl 1005.12004

Summary: Computation of approximate polynomial greatest common divisors (GCDs) is important both theoretically and due to its applications to control linear systems, network theory, and computer-aided design. We study two approaches to the solution so far omitted by the researchers, despite intensive recent work in this area. Correlation to numerical Padé approximation enabled us to improve computations for both problems (GCDs and Padé). Reduction to the approximation of polynomial zeros enabled us to obtain a new insight into the GCD problem and to devise effective solution algorithms. In particular, unlike the known algorithms, we estimate the degree of approximate GCDs at a low computational cost, and this enables us to obtain certified correct solutions for a large class of input polynomials. We also restate the problem in terms of the norm of the perturbation of the zeros (rather than the coefficients) of the input polynomials, which leads us to the fast certified solution for any pair of input polynomials via the computation of their roots and the maximum matchings or connected components in the associated bipartite graph.

MSC:

12Y05 Computational aspects of field theory and polynomials (MSC2010)
68W30 Symbolic computation and algebraic computation
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Atkinson, K. E., Introduction to Numerical Analysis (1978), Wiley: Wiley New York · Zbl 0402.65001
[2] Barnett, S., Generalized polynomials and linear systems theory, Proc. 3rd IMA Conf. Contr. Theory (1981), p. 3-30
[3] Bini, D., and Pan, V. Y.1991, Parallel complexity of tridiagonal symmetric eigenvalue problem, inProc. 2nd Ann. ACM-SIAM Symposium on Discrete Algorithms, pp. 384-393, ACM Press, New York. Journal version in SIAM J. Comput.27, 1099-11151998.; Bini, D., and Pan, V. Y.1991, Parallel complexity of tridiagonal symmetric eigenvalue problem, inProc. 2nd Ann. ACM-SIAM Symposium on Discrete Algorithms, pp. 384-393, ACM Press, New York. Journal version in SIAM J. Comput.27, 1099-11151998. · Zbl 0800.68501
[4] Bini, D.; Pan, V. Y., Polynomial and Matrix Computations, Vol. 1: Fundamental Algorithms (1994), Birkhaeuser: Birkhaeuser Boston
[5] Bini, D, and, Pan, V. Y. 2001, Polynomial and Matrix Computations, Vol. 2, Fundamental and Practical Algorithms, Birkhaeuser, Boston.; Bini, D, and, Pan, V. Y. 2001, Polynomial and Matrix Computations, Vol. 2, Fundamental and Practical Algorithms, Birkhaeuser, Boston.
[6] Brent, R. B.; Gustavson, F. G.; Yun, D. Y.Y., Fast solution of Toeplitz systems of equations and computation of Padé approximations, J. Algorithms, 1, 259-295 (1980) · Zbl 0475.65018
[7] Cadzow, J. A., Signal enhancement: A composite property mapping algorithm, IEEE Trans. Acoust. Speech Signal Process., 36, 39-62 (1988) · Zbl 0649.93059
[8] Cadzow, J. A.; Wilkes, D. M., Signal enhancement and the SVD, Proceedings of the 2nd International Workshop on SVD and Signal Processing, University of Rhode Island, Kingston, RI (1990), p. 144-151
[9] Chin, P.; Corless, R. M.; Corliss, G. F., Optimization strategies for the approximate gcd problem, Proc. Intern. Symp. on Symb. and Algebraic Comp. (ISSAC98) (1998), ACM Press: ACM Press New York, p. 228-235 · Zbl 0922.65011
[10] Corless, R. M.; Gianni, P. M.; Trager, B. M.; Watt, S. M., The singular value decomposition for polynomial systems, Proc. Intern. Symp. on Symbolic and Algebraic Comp. (ISSAC ’95) (1995), ACM Press: ACM Press New York, p. 195-207 · Zbl 0920.65034
[11] Cormen, T. H.; Leiserson, C. E.; Rivest, R. L., Introduction to Algorithms (1990), MIT Press: MIT Press Cambridge · Zbl 1158.68538
[12] De Moor, B., Total least squares for affinely structured matrices and the noisy realization problem, IEEE Trans. Signal Process., 42, 3104-3113 (1994)
[13] Emiris, I. Z.; Galligo, A.; Lombardi, H., Numerical univariate polynomial GCD, (Renegar, J.; Shub, M.; Smale, S., AMS-SIAM Summer Seminar in Applied Math.: Mathematics of Numerical Analysis, Park City, Utah (1996), Amer. Math. Soc: Amer. Math. Soc Providence), 323-344 · Zbl 0856.65006
[14] Emiris, I. Z.; Galligo, A.; Lombardi, H., Certified approximate polynomial GCDs, J. Pure Appl. Algebra, 117/118, 229-251 (1997) · Zbl 0891.65015
[15] Emiris, I. Z.; Pan, V. Y., The structure of sparse resultant matrices, Proc. of Annual ACM-SIGSAM International Symp. on Symb. and Alg. Comp. (ISSAC’97) (1997), ACM Press: ACM Press New York, p. 189-196 · Zbl 0916.65046
[16] Galil, Z.; Pan, V. Y., Improved processor bounds for combinatorial problems in RNC, Combinatorica, 8, 189-200 (1988) · Zbl 0685.68048
[17] Golub, G. H., and Van Loan, C. F.1996, Matrix Computations, third ed., Johns Hopkins Univ. Press, Baltimore, MD.; Golub, G. H., and Van Loan, C. F.1996, Matrix Computations, third ed., Johns Hopkins Univ. Press, Baltimore, MD. · Zbl 0865.65009
[18] Gragg, W. B., The Padé table and its relation to certain algorithms of numerical analysis, SIAM Rev., 14, 1-62 (1972) · Zbl 0238.30008
[19] Halperin, S.; Zwick, U., Optimal randomized EREW PRAM algorithms for finding spanning forests and for other basic graph connectivity problems, Proceedings of the 7th Ann. ACM-SIAM Symposium on Discrete Algorithms (1996), ACM Press: ACM Press New York, p. 384-393 · Zbl 0847.68077
[20] Hitz, M.; Kaltofen, E., Efficient algorithms for computing the nearest polynomial with constrained roots, Proc. Intern. Symp. on Symb. and Algebraic Comp. (ISSAC’98) (1998), ACM Press: ACM Press New York, p. 236-243 · Zbl 0917.65045
[21] Hopcroft, J. E.; Karp, R. M., SIAM J. Computing, 2, 225-231 (1973)
[22] Hough, D. G., Explaining and Ameliorating the Ill Condition of Zeros of Polynomials (1977), University of CaliforniaComputer Science, Department: University of CaliforniaComputer Science, Department Berkeley
[23] Hribernig, V.; Stetter, H. J., Detection and validation of clusters of polynomial zeros, J. Symb. Comp., 24, 667-681 (1997) · Zbl 0910.65030
[24] Já, J. Já, An Introduction to Parallel Algorithms (1992), Addison-Wesley: Addison-Wesley Reading
[25] Kailath, T., Linear Systems (1980), Prentice-Hall: Prentice-Hall Englewood Cliffs · Zbl 0458.93025
[26] Karcanias, N., Invariance properties and characterisations of the greatest common divisor of a set of polynomials, Int. J. Control, 40, 1751-1760 (1987) · Zbl 0695.12013
[27] Karcanias, N.; Mitrouli, M., A matrix pencil based numerical method for the computation of GCD of polynomials, IEEE Trans. Automatic Control, 39, 977-981 (1994) · Zbl 0807.93021
[28] Karmarkar, N.; Lakshman, Y. N., Approximate polynomial greatest common divisor and nearest singular polynomials, “Proc. Ann. ACM-SIGSAM Intern. Symp. on Symb. and Algebraic Comp”., 35-39 (1996) · Zbl 0928.13017
[29] Lazard, D., Resolution des Systems d’Equations Algebrique, Theoret. Comput. Sci., 15, 77-110 (1981) · Zbl 0459.68013
[30] Noda, M.-T.; Sasaki, T., Approximate GCD and its application to ill-conditioned algebraic equations, J. Comput. Appl. Math., 38, 335-351 (1991) · Zbl 0747.65034
[31] Ostrowski, A. M., Solution of Equations and Systems of Equations (1966), Academic Press: Academic Press New York · Zbl 0222.65070
[32] Pan, V. Y., Complexity of computations with matrices and polynomials, SIAM Rev., 34, 225-262 (1992) · Zbl 0757.65051
[33] Pan, V. Y.1995, Optimal (up to polylog factors) sequential and parallel algorithms for approximating complex polynomial zeros, inProc. 27th Ann. ACM Symposium on Theory of Computing, pp. 741-750, ACM Press, New York.; Pan, V. Y.1995, Optimal (up to polylog factors) sequential and parallel algorithms for approximating complex polynomial zeros, inProc. 27th Ann. ACM Symposium on Theory of Computing, pp. 741-750, ACM Press, New York. · Zbl 0942.68796
[34] Pan, V. Y., Optimal and nearly optimal algorithms for approximating polynomial zeros, Computers Math. (with Appl.), 31, 97-138 (1996) · Zbl 0859.65045
[35] Pan, V. Y. 1996b, Numerical computation of a polynomial GCD and extension, Research Report 2969, INRIA, Sophia-Antipolis, France. [Revised in, 1997.]; Pan, V. Y. 1996b, Numerical computation of a polynomial GCD and extension, Research Report 2969, INRIA, Sophia-Antipolis, France. [Revised in, 1997.]
[36] Pan, V. Y., Solving a polynomial equation: Some history and recent progress, SIAM Rev., 39, 187-220 (1997) · Zbl 0873.65050
[37] Pan, V. Y., Solving polynomials with computers, Amer. Sci., 86, 62-69 (1998)
[38] Pan, V. Y. 2001, Structured Matrices and Polynomials: Unified Superfast Algorithms, Birkhaeuser/Springer.; Pan, V. Y. 2001, Structured Matrices and Polynomials: Unified Superfast Algorithms, Birkhaeuser/Springer. · Zbl 0996.65028
[39] Parlett, B. N. 1980, The Symmetric Eigenvalue Problem, Prentice-Hall, Englewood Cliffs, NJ.; Parlett, B. N. 1980, The Symmetric Eigenvalue Problem, Prentice-Hall, Englewood Cliffs, NJ. · Zbl 0431.65017
[40] Pace, J. S.; Barnett, S., Comparison of algorithms for calculation of GCD of polynomials, Int. J. Systems Sci., 4, 211-223 (1973) · Zbl 0253.93014
[41] Pan, V. Y, Chen, Z, and, Zheng, A. 1998, The complexity of the algebraic eigenproblem, No. 1998-071, Mathematical Sciences Research Institute, Berkeley, California.; Pan, V. Y, Chen, Z, and, Zheng, A. 1998, The complexity of the algebraic eigenproblem, No. 1998-071, Mathematical Sciences Research Institute, Berkeley, California.
[42] Sasaki, T.; Sasaki, M., Polynomial remainder sequence and approximate GCD, ACM SIGSAM Bull., 31, 4-10 (1997)
[43] Schönhage, A. 1982, The fundamental theorem of algebra in terms of computational complexity, Mathematics Department, University of Tübingen, Germany, manuscript.; Schönhage, A. 1982, The fundamental theorem of algebra in terms of computational complexity, Mathematics Department, University of Tübingen, Germany, manuscript.
[44] Schönhage, A., Quasi-GCD computations, J. Complexity, 1, 118-137 (1985) · Zbl 0586.68031
[45] Sederberg, T. W.; Chang, G.-Z., Best linear common divisors for approximate degree reduction, Computer-Aided Design, 25, 163-168 (1993) · Zbl 0772.65010
[46] van der Veen, A., A Schur method for low-rank matrix approximation, SIAM J. Matrix Anal. Appl., 17, 139-160 (1996) · Zbl 0848.47013
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.