×

The ERES method for computing the approximate GCD of several polynomials. (English) Zbl 1185.12005

Summary: The computation of the greatest common divisor (GCD) of a set of polynomials has interested the mathematicians for a long time and has attracted a lot of attention in recent years. A challenging problem that arises from several applications, such as control or image and signal processing, is to develop a numerical GCD method that inherently has the potential to work efficiently with sets of several polynomials with inexactly known coefficients. The presented work focuses on: (i) the use of the basic principles of the ERES methodology for calculating the GCD of a set of several polynomials and defining approximate solutions by developing the hybrid implementation of this methodology. (ii) the use of the developed framework for defining the approximate notions for the GCD as a distance problem in a projective space to develop an optimization algorithm for evaluating the strength of different ad-hoc approximations derived from different algorithms. The presented new implementation of ERES is based on the effective combination of symbolic-numeric arithmetic (hybrid arithmetic) and shows interesting computational properties for the approximate GCD problem. Additionally, an efficient implementation of the strength of an approximate GCD is given by exploiting some of the special aspects of the respective distance problem. Finally, the overall performance of the ERES algorithm for computing approximate solutions is discussed.

MSC:

12Y05 Computational aspects of field theory and polynomials (MSC2010)
65H99 Nonlinear algebraic or transcendental equations
68W30 Symbolic computation and algebraic computation

Software:

MultRoot
PDFBibTeX XMLCite
Full Text: DOI Link

References:

[1] Barlow, J. L., More accurate bidiagonal reduction for computing the singular value decomposition, SIAM J. Matrix Anal. Appl., 23, 3, 761-798 (2002) · Zbl 1007.65026
[2] Barnett, S., Greatest common divisor of several polynomials, (Proc. Cambridge Philos. Soc. (1971)), 263-268 · Zbl 0224.15018
[3] Barnett, S., Greatest common divisor from generalized Sylvester matrices, Proc. Cambridge Philos. Soc., 8, 271-279 (1980) · Zbl 0438.12012
[4] Blankiship, W., A new version of Euclid algorithm, American Mathematics Monthly, 70, 742-744 (1963)
[5] Brown, W. S., On Euclid’s algorithm and the computation of polynomials greatest common divisors, Journal of the Association for Computer Machinery, 18, 4, 478-504 (1971) · Zbl 0226.65040
[6] Chan, T. F., An improved algorithm for computing the singular value decomposition, ACM Trans. Math. Soft., 8, 72-83 (1982) · Zbl 0477.65032
[8] Datta, B. N., Numerical Linear Algebra and Applications (1995), Brooks/Cole Publishing Company - ITP
[9] Diaz-Toca, G. M.; Gonzalez-Vega, L., Computing greatest common divisors and squarefree decompositions through matrix methods: The parametric and approximate cases, Linear Algebra and its Applications, 412, 222-246 (2006) · Zbl 1084.65037
[10] Emiris, I. Z.; Galligo, A.; Lombardi, H., Certified approximate univariate gcds, Journ. Pure and Applied Algebra, 117-118, 229-251 (1997) · Zbl 0891.65015
[11] Fatouros, S.; Karcanias, N., Resultant properties of the gcd of many polynomials and a factorisation representation of gcd, Int. Journ. Control, 76, 16, 1666-1683 (2003) · Zbl 1043.93017
[12] Foster, L., Rank and null space calculations using matrix decomposition without column interchanges, Linear Algebra and its Applications, 74, 47-71 (1986) · Zbl 0589.65031
[13] Golub, G.; Kahan, W., Calculating the singular values and pseudo-inverse of a matrix, SIAM J. Num. Anal. Ser. B, 2, 205-224 (1965) · Zbl 0194.18201
[14] Golub, G.; Loan, C. V., Matrix Computations (1989), The John Hopkins University Press: The John Hopkins University Press Baltimore, London
[15] Hirsch, M.; Smale, S., Differential Equations, Dynamical Systems and Linear Algebra (1974), Academic Press: Academic Press New York
[16] Kailath, T., Linear Systems (1980), Prentice Hall, Inc.: Prentice Hall, Inc. Englewood Cliffs, NJ · Zbl 0458.93025
[17] Karcanias, N., Invariance properties and characterisation of the greatest common divisor of a set of polynomials, Int. Journ. Control, 46, 1751-1760 (1987) · Zbl 0695.12013
[18] Karcanias, N.; Fatouros, S.; Mitrouli, M.; Halikias, G., Approximate greatest common divisor of many polynomials, generalised resultants and strength of approximation, Computers & Mathematics with Applications, 51, 12, 1817-1830 (2006) · Zbl 1134.65334
[19] Karcanias, N.; Giannakopoulos, G.; Hubbard, M., Almost zeros of a set of polynomials, Int. Journ. Control, 40, 439-457 (1984)
[20] Karcanias, N.; Mitrouli, M., A matrix pencil based numerical method for the computation of the gcd of polynomials, IEEE Trans. Autom. Cont., 39, 977-981 (1994) · Zbl 0807.93021
[21] Karcanias, N.; Mitrouli, M., Approximate algebraic computations of algebraic invariants, (Symbolic Methods in Control Systems Analysis and Design. Symbolic Methods in Control Systems Analysis and Design, IEE Control Engin. Series, vol. 56 (1999)), 162-168
[22] Karmarkar, N.; Lakshman, Y. N., On approximate gcds of univariate polynomials, J. Symbolic Computation, 26, 6, 653-666 (1998) · Zbl 0967.12007
[24] Marcus, M.; Minc, M., A Survey of Matrix Theory and Matrix Inequalities (1964), Allyn and Bacon: Allyn and Bacon Boston · Zbl 0126.02404
[25] Mitrouli, M.; Karcanias, N., Computation of the gcd of polynomials using Gaussian transformation and shifting, Int. Journ. Control, 58, 211-228 (1993) · Zbl 0777.93053
[26] Noda, M.; Sasaki, T., Approximate gcd and its applications to ill-conditioned algebraic equations, Journ. of Comp. and Appl. Math., 38, 335-351 (1991) · Zbl 0747.65034
[27] Pace, I. S.; Barnett, S., Comparison of algorithms for calculation of g.c.d. of polynomials, Int. Journ. Control, 4, 2, 211-216 (1973) · Zbl 0253.93014
[28] Rupprecht, D., An algorithm for computing certified approximate gcd of \(n\) univariate polynomials, Journ. of Pure and Applied Algebra, 139, 255-284 (1999) · Zbl 0964.12007
[29] Van Huffel, S., Partial singular value decomposition algorithm, Journ. of Comp. and Appl. Math., 33, 105-112 (1990) · Zbl 0721.65016
[30] Van Huffel, S.; Vandewalle, J., An efficient and reliable algorithm for computing the singular subspace of a matrix, associated with its smallest singular values, Journ. of Comp. and Appl. Math., 19, 313-330 (1987) · Zbl 0632.65041
[31] Vardulakis, A. I.G.; Stoyle, P. N.R., Generalized resultant theorem, IMA Journal of Applied Mathematics, 22, 3, 331-335 (1978) · Zbl 0403.12025
[32] Wonham, W. M., Linear Multivariable Control: A Geometric Approach (1984), Springer-Verlag: Springer-Verlag New York · Zbl 0393.93024
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.