An ODE-based method for computing the approximate greatest common divisor of polynomials. (English) Zbl 1433.65076
Summary: Computing the greatest common divisor of a set of polynomials is a problem which plays an important role in different fields, such as linear system, control, and network theory. In practice, the polynomials are obtained through measurements and computations, so that their coefficients are inexact. This poses the problem of computing an approximate common factor. We propose an improvement and a generalization of the method recently proposed in [N. Guglielmi and I. Markovsky, SIAM J. Numer. Anal. 55, No. 3, 1456–1482 (2017; Zbl 1367.65087)], which restates the problem as a (structured) distance to singularity of the Sylvester matrix. We generalize the algorithm in order to work with more than 2 polynomials and to compute an Approximate GCD (Greatest Common Divisor) of degree \(k \geq 1\); moreover, we show that the algorithm becomes faster by replacing the eigenvalues by the singular values.
MSC:
| 65F45 | Numerical methods for matrix equations |
| 15A24 | Matrix equations and identities |
| 65K10 | Numerical optimization and variational techniques |
| 11R09 | Polynomials (irreducibility, etc.) |
Citations:
Zbl 1367.65087References:
| [1] | Beckermann, B., Labahn, G.: When are two numerical polynomials relatively prime?. J. Symb. Comput. 26, 677-689 (1998) · Zbl 1008.65021 · doi:10.1006/jsco.1998.0234 |
| [2] | Bini, D., Boito, P.: A fast algorithm for approximate polynomial gcd based on structured matrix computations. In: Numerical methods for structured matrices and applications, pp. 155-173. Basel, Birkhäuser (2010) · Zbl 1203.65078 |
| [3] | Bini, D., Boito, P.: Structured matrix-based methods for polynomial 𝜖-GCD: analysis and comparisons. In: ISSAC 2007, pp. 9-16. ACM, New York (2007) · Zbl 1190.65060 |
| [4] | Boito, P.: Structured matrix based methods for approximate polynomial GCD. Edizioni della Normale Pisa (2011) · Zbl 1238.65002 |
| [5] | Chèze, G., Galligo, A., Mourrain, B., Yacoubsohn, J.-C.: A subdivision method for computing nearest gcd with certification. Theor. Comput. Sci. 412, 4493-4503 (2011) · Zbl 1221.68297 · doi:10.1016/j.tcs.2011.04.018 |
| [6] | Chin, P., Corless, R.M., Corliss, G.F.: Optimization strategies for the approximate gcd problem. In: Proceedings of ISSAC’98, pp. 228-235. ACM, New York (1998) · Zbl 0922.65011 |
| [7] | Corless, R.M., Gianni, P.M., Trager, B.M., Watt, S.M.: The singular value decomposition for polynomial systems. In: Proceedings of ISSAC’95, pp. 195-207. ACM, New York (1995) · Zbl 0920.65034 |
| [8] | Dieci, L., Eirola, T.: On smooth decompositions of matrices. SIAM J. Matrix. Anal. and Appl. 20, 800-819 (1999) · Zbl 0930.15014 · doi:10.1137/S0895479897330182 |
| [9] | Duan, X., Zhang, X., Wang, Q.: Computing approximation GCD of several polynomials by structured total least norm. ALAMT 3, 39-46 (2013) · doi:10.4236/alamt.2013.34008 |
| [10] | Golub, G., Pereyra, V.: Separable nonlinear least squares: the variable projection method and its applications. Inverse Prob. 19, 1-26 (2003) · Zbl 1022.65014 · doi:10.1088/0266-5611/19/2/201 |
| [11] | Golub, G., Pereyra, V.: The differentiation of pseudo-inverses and nonlinear least squares problems whose variables separate. SIAM J. Numer. Anal. 10, 413-432 (1973) · Zbl 0258.65045 · doi:10.1137/0710036 |
| [12] | Guglielmi, N., Markovsky, I.: An ODE based method for computing the distance of coprime polynomials. SIAM J. Numer. Anal. 55, 1456-1482 (2017) · Zbl 1367.65087 · doi:10.1137/15M1018265 |
| [13] | Kaltofen, E., Yang, Z., Zhi, L.: Approximate greatest common divisors of several polynomials with linearly constrained coefficients and singular polynomials. In: Proceedings of ISSAC’06, pp. 169-176. ACM, New York (2006) · Zbl 1356.12011 |
| [14] | Karcanias, N., Fatouros, S., Mitrouli, M., Halikias, G.: Approximate greatest common divisor of many polynomials and generalised resultants. Comput. Math. Appl. 51, 1817-1830 (2006) · Zbl 1134.65334 · doi:10.1016/j.camwa.2006.01.010 |
| [15] | Karmarkar, N.K., Lakshman, Y.N.: On approximate GCDs of univariate polynomials. J. Symbolic Comp. 26, 653-666 (1998) · Zbl 0967.12007 · doi:10.1006/jsco.1998.0232 |
| [16] | Li, B., Liu, Z., Zhi, L: A fast algorithm for solving the sylvester structured total least squares problem. Signal Process. 87, 2313-2319 (2007) · Zbl 1186.94202 · doi:10.1016/j.sigpro.2007.03.001 |
| [17] | Li, B., Nie, J., Zhi, L.: Approximate gcds of polynomials and sparse sos relaxations. Theor. Comput. Sci. 409, 200-210 (2008) · Zbl 1156.90424 · doi:10.1016/j.tcs.2008.09.003 |
| [18] | Magnus, J.R.: On differentiating eigenvalues and eigenvectors. Economet. Theor. 1, 179-191 (1985) · doi:10.1017/S0266466600011129 |
| [19] | Markovsky, I.: Structured low-rank approximation and its applications. Automatica 44, 891-909 (2008) · Zbl 1283.93061 · doi:10.1016/j.automatica.2007.09.011 |
| [20] | Markovsky, I., Usevich, K.: Software for weighted structured low-rank approximation. Comput. Appl. Math. 256, 278-292 (2014) · Zbl 1314.65067 · doi:10.1016/j.cam.2013.07.048 |
| [21] | Markovsky, I., Van Huffel, S: An algorithm for approximate common divisor computation. In: Proceedings of MTNS’06, pp. 274-279. Kyoto, Japan (2006) |
| [22] | Maroulas, J., Dascalopoulos, D.: Applications of the generalized Sylvester matrix. Appl. Math. Comput. 8, 121-135 (1981) · Zbl 0461.12014 |
| [23] | Pan, V.Y.: Computation of approximate polynomial GCDs and an extension. Inf. Comput. 167, 71-85 (2001) · Zbl 1005.12004 · doi:10.1006/inco.2001.3032 |
| [24] | Qiu, W., Hua, Y., Abed-Meraim, K.: A subspace method for the computation of the GCD of polynomials. Automatica 33, 741-743 (1997) · Zbl 0922.93016 · doi:10.1016/S0005-1098(96)00244-0 |
| [25] | Schost, E., Spaenlehauer, P.-J.: A quadratically convergent algorithm for structured low-rank approximation. Found. Comput. Math. 16, 457-492 (2016) · Zbl 1347.65080 · doi:10.1007/s10208-015-9256-x |
| [26] | Terui, A.: GPGCD: An iterative method for calculating approximate GCD of univariate polynomials. Theor. Comput. Sci. 479, 127-149 (2013) · Zbl 1291.65162 · doi:10.1016/j.tcs.2012.10.023 |
| [27] | Usevich, K., Markovsky, I.: Variable projection for affinely structured low-rank approximation in weighted 2-norms. J. Comput. Appl. Math. 272, 430-448 (2014) · Zbl 1294.65063 · doi:10.1016/j.cam.2013.04.034 |
| [28] | Usevich, K., Markovsky, I.: Variable projection methods for approximate (greatest) common divisor computations. Theor. Comput. Sci. 681, 176-198 (2017) · Zbl 1375.65062 · doi:10.1016/j.tcs.2017.03.028 |
| [29] | Vardulakis, A.I.G., Stoyle, P.N.R.: Generalized Resultant Theorem. J. Inst. Maths. Applics. 22, 331-335 (1978) · Zbl 0403.12025 · doi:10.1093/imamat/22.3.331 |
| [30] | Zarowsky, C.J., Ma, X., Fairman, F.W.: QR-factorization method for computing the greatest common divisor of polynomials with inexact coefficients. IEEE Trans. Signal Process. 48, 3042-3051 (2000) · Zbl 1002.12011 · doi:10.1109/78.875462 |
| [31] | Zeng, Z.: The approximate GCD of inexact polynomials, Part 1: A univariate algorithm http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.83.645&rep=rep1&type=pdf (2004) · Zbl 1134.13313 |
| [32] | Zeng, Z.: The numerical greatest common divisor of univariate polynomials. Contemp. Math. 556, 187-217 (2011) · Zbl 1236.65051 · doi:10.1090/conm/556/11014 |
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.
