A heuristic verification of the degree of the approximate GCD of two univariate polynomials. (English) Zbl 1302.68333
Summary: We consider the problem of computing verified real interval perturbations of the coefficients of two univariate polynomials such that there exist corresponding perturbed polynomials which have an exact greatest common divisor (GCD) of a given degree \(k\). Based on the certification of the rank deficiency of a submatrix of the Bezout matrix of two univariate polynomials, we propose an algorithm to compute verified real perturbations. Numerical experiments show the performance of our algorithm.
MSC:
| 68W30 | Symbolic computation and algebraic computation |
| 65H04 | Numerical computation of roots of polynomial equations |
| 13P05 | Polynomials, factorization in commutative rings |
| 11A05 | Multiplicative structure; Euclidean algorithm; greatest common divisors |
References:
| [1] | Barnett, S.: Greatest common divisor of two polynomials. Linear Algebra Appl. 3, 7-9 (1970) · Zbl 0191.32503 · doi:10.1016/0024-3795(70)90023-6 |
| [2] | Barnett, S.: Greatest common divisor of several polynomials. Proc. Camb. Philos. Soc. 70, 263-268 (1971) · Zbl 0224.15018 · doi:10.1017/S0305004100049860 |
| [3] | Barnett, S.: A note on the Bezoutian matrix. SIAM J. Appl. Math. 22, 84-86 (1972) · Zbl 0245.15011 · doi:10.1137/0122009 |
| [4] | Beckermann, B., Labahn, G.: When are two polynomials relatively prime. J. Symb. Comput. 26, 677-689 (1998) · Zbl 1008.65021 · doi:10.1006/jsco.1998.0234 |
| [5] | Bini, D., Gemignani, L.: Fast parallel computation of the polynomial remainder sequence via Bezout and Hankel matrices. SIAM J. Comput. 22(3), 63-77 (1993) · Zbl 0779.68048 · doi:10.1137/0222041 |
| [6] | Bini, D., Pan, V.Y.: Polynomial and Matrix Computations, vol. 1 of Fundamental Algorithm. Birkhüser, Boston (1994) · Zbl 0809.65012 · doi:10.1007/978-1-4612-0265-3 |
| [7] | Bini, D.A., Boito, P.: Structured matrix-based methods for polynomial ε \(\varepsilon \)-gcd: analysis and comparisons. In: Brown, C.W. (ed.) International Symposium Symbolic Algebraic Computation, pp. 9-16. ACM Press, New York (2007) · Zbl 1190.65060 |
| [8] | Chen, X., Womersley, R.S.: Existence of solutions to systems of underdetermined equations and spherical designs. SIAM J. Numer. Anal. 24(6), 2326-2341 (2006) · Zbl 1129.65035 · doi:10.1137/050626636 |
| [9] | Chéze, G., Galligo, A., Mourrain, B., Yakoubsohna, J.: 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 |
| [10] | Corless, R.M., Gianni, P.M., Trager, B.M., Watt, S.M.: The singular value decomposition for polynomial systems. In: Levelt, A.H.M. (ed.) International Symposium Symbolic Algebraic Computation, pp. 195-207. ACM Press, New York (1995) · Zbl 0920.65034 |
| [11] | Corless, R., Watt, S., Zhi, L.: QR factoring to compute the GCD of univariate approximate polynomials. IEEE Trans. Signal Process. 52, 3394-3402 (2004) · Zbl 1372.65120 · doi:10.1109/TSP.2004.837413 |
| [12] | Diaz-Toca, G.M., Gonzalez-Vega, L.: Computing greatest common divisors and squarefree decompositions through matrix methods: the parametric and approximate cases. Linear Algebra Appl. 412, 222-246 (2006) · Zbl 1084.65037 · doi:10.1016/j.laa.2005.06.028 |
| [13] | Emiris, I.Z., Galligo, A., Lombardi, H.: Certified approximate univariate GCDs. J. Pure Appl. Algebra Spec. Issue Algoritm. Algebra 117, 229-251 (1997) · Zbl 0891.65015 · doi:10.1016/S0022-4049(97)00013-3 |
| [14] | Gemignani, L.: Gcd of polynomials and bezout matrices. J. Inf. Comput. Sci. 3(3), 453-461 (2006) |
| [15] | Golub, G.H., Van Loan, Ch.: Matrix Computations, 3rd edn. Johns Hopkins University Press, Baltimore (1996) · Zbl 0865.65009 |
| [16] | Govaerts, W.: Bordered matrices and singularities of large nonlinear systems. Int. J. Bifurcation Chaos 5(1), 243-250 (1995) · Zbl 0887.65053 · doi:10.1142/S0218127495000181 |
| [17] | Griewank, A., Reddien, G.W.: Characterisation and computation of generalised turning points. SIAM J. Numer. Anal. 21, 176-185 (1984) · Zbl 0536.65031 · doi:10.1137/0721012 |
| [18] | Griewank, A., Reddien, G.W.: The approximation of generalized turning points by projection methods with superconvergence to the critical parameter. Numer. Math. 48, 591-606 (1986) · Zbl 0596.65040 · doi:10.1007/BF01389452 |
| [19] | Griewank, A., Reddien, G.W.: The approximate solution of defining equations for generalized turning points. SIAM J. Numer. Anal. 33, 1912-1920 (1996) · Zbl 0876.65030 · doi:10.1137/S003614299325866X |
| [20] | Higham, N.J.: Accuracy and Stability of Numerical Algorithms, 2nd edn. SIAM Publications, Philadelphia (2002) · Zbl 1011.65010 · doi:10.1137/1.9780898718027 |
| [21] | Hribernig, V., Stetter, H.: Detection and validation of clusters of polynomials zeros. J. Symb. Comput. 24, 667-681 (1997) · Zbl 0910.65030 · doi:10.1006/jsco.1997.0160 |
| [22] | Kaltofen, E., Yang, Z., Zhi, L.: Approximate greatest common divisors of several polynomials with linearly constrained coefficients and singular polynomials. In: Dumas, J.G. (ed.) International Symposium Symbolic Algebraic Computation, pp. 169-176. ACM Press, New York (2006) · Zbl 1356.12011 |
| [23] | Kaltofen, E., Yang, Z., Zhi, L.: Structured low rank approximation of a Sylvester matrix. In: Wang,D., Zhi, L. (eds.) Symbolic-Numeric Computation, pp. 69-83. Birkhäuser Verlag, Switzerland (2007) · Zbl 1117.65060 |
| [24] | Karmarkar, N., Lakshman, Y.N.: Approximate polynomial greatest common divisors and nearest singular polynomials. In: Lakshman, Y.N. (ed.) International Symposium Symbolic Algebraic Computation, pp. 35-42. ACM Press, New York (1996) · Zbl 0928.13017 |
| [25] | Krawczyk, R.: Newton-algorithmen zur bestimmung von nullstellen mit fehlerschranken. Computing 4, 187-201 (1969) · Zbl 0187.10001 · doi:10.1007/BF02234767 |
| [26] | Li, B., Nie, J., Zhi, L.: Approximate gcds of polynomials and sparse sos relaxations. Theor. Comput. Sci. 409(2), 200-210 (2008) · Zbl 1156.90424 · doi:10.1016/j.tcs.2008.09.003 |
| [27] | Li, B., Liu, Z., Zhi, L.: A structured rank-revealing method for sylvester matrix. J. Comput. Appl. Math. 213(1), 212-223 (2008) · Zbl 1140.65035 · doi:10.1016/j.cam.2007.01.032 |
| [28] | Li, B., Yang, Z., Zhi, L.: Fast low rank approximation of a Sylvester matrix by structured total least norm. Jpn. Soc. Symb. Algebraic Comput. 11, 3-4 (2005) · Zbl 1098.70010 |
| [29] | Li, Z.; Yang, Z.; Zhi, L., Blind image deconvolution via fast approximate GCD. In, 155-162 (2010), New York · Zbl 1321.68442 |
| [30] | Markovsky, I., Huffel, S.V.: An Algorithm for Approximate Common Divisor Computation. Internal Report 205-248, ESAT-SISTA. K.U.Leuven, Leuven (2005) · Zbl 1070.65025 |
| [31] | Miyajima, S.: Fast enclosure for solutions in underdetermined systems. J. Comput. Appl. Math. 234, 3436-3444 (2010) · Zbl 1201.65064 · doi:10.1016/j.cam.2010.05.005 |
| [32] | Miyajima, S.: Componentwise enclosure for solutions in least squares problems and underdetermined linear systems. In: SCAN Conference Novosibirsk (2012) · Zbl 1372.65120 |
| [33] | Moore, R.E.: A test for existence of solutions to nonlinear system. SIAM J. Numer. Anal. 14(4), 611-615 (1977) · Zbl 0365.65034 · doi:10.1137/0714040 |
| [34] | Nie, J., Demmel, J., Gu, M.: Global minimization of rational functions and the nearest gcds. J. Glob. Optim. 40(4), 697-718 (2008) · Zbl 1138.90030 · doi:10.1007/s10898-006-9119-8 |
| [35] | Noda, M., Sasaki, T.: Approximate GCD and its application to ill-conditioned algebraic equations. J. Comput. Appl. Math. 38, 335-351 (1991) · Zbl 0747.65034 · doi:10.1016/0377-0427(91)90180-R |
| [36] | Pan, V.: Numerical computation of a polynomial GCD and extensions. Inf. Comput. 167, 71-85 (2001) · Zbl 1005.12004 · doi:10.1006/inco.2001.3032 |
| [37] | Rabier, P.J., Reddien, G.W.: Characterization and computation of singular points with maximum rank deficiency. SIAM J. Numer. Anal. 23, 1040-1051 (1986) · Zbl 0627.65057 · doi:10.1137/0723072 |
| [38] | Rump, S.M.: Kleine fehlerschranken bei matrixproblemen. Ph.D. thesis. Universit Karlsruhe (1980) · Zbl 0437.65036 |
| [39] | Rump, S.M.: Solving algebraic problems with high accuracy. In: Kulisch, W.L., Miranker, W.L. (eds.) A New Approach to Scientific Computation, pp. 51-120. Academic, New York (1983) · Zbl 1132.68073 |
| [40] | Rump, S.M.: Verification methods: rigorous results using floating-point arithmetic. Acta Numer. 19, 287-449 (2010) · Zbl 1323.65046 · doi:10.1017/S096249291000005X |
| [41] | Rump, S.M.: Verified bounds for singular values, in particular for the spectral norm of a matrix and its inverse. BIT Numer. Math. 51(2), 367-384 (2011) · Zbl 1226.65028 · doi:10.1007/s10543-010-0294-0 |
| [42] | Rump, S.M.: Verified bounds for least squares problems and underdetermined linear systems. SIAM J. Matrix Anal. Appl. 33(1), 130-148 (2012) · Zbl 1255.65082 · doi:10.1137/110840248 |
| [43] | Rump, S.M.: Improved componentwise verified error bounds for least squares problems and underdetermined linear systems. Numer. Algorithm. (2013). doi:10.1007/s11075-013-9735-6 · Zbl 1293.65062 |
| [44] | Schönhage, A.: Quasi-gcd computations. J. Complex. 1(1), 118-137 (1985) · Zbl 0586.68031 · doi:10.1016/0885-064X(85)90024-X |
| [45] | Spence, A., Poulton, C.: Photonic band structure calculations using nonlinear eigenvalue techniques. J. Comput. Phys. 204, 65-81 (2005) · Zbl 1143.82336 · doi:10.1016/j.jcp.2004.09.016 |
| [46] | Sun, D., Zhi, L.: Structured low rank approximation of a bezout matrix. MM Res. Prepr. 25, 207-218 (2006) |
| [47] | Sun, D., Zhi, L.: Structured low rank approximation of a bezout matrix. Math. Comput. Sci. 1, 427-437 (2007) · Zbl 1132.68073 · doi:10.1007/s11786-007-0014-6 |
| [48] | Terui, A.: An iterative method for calculating approximate GCD of univariate polynomials. In: May (ed.) International Symposium on Symbolic Algebraic Computation, pp. 351-358. ACM Press, New York (2009) · Zbl 1237.65024 |
| [49] | Zeng, Z., Dayton, B.H.: The approximate gcd of inexact polynomials. In: International Symposium on Symbolic and Algebraic Computation, pp. 320-327. ACM Press, New York (2004) · Zbl 1134.13313 |
| [50] | Zarowski, C.J., Ma, X., Fairman, F.W.: A QR-factorization method for computing the greatest common divisor of polynomials with real-valued coefficients. IEEE Trans. Signal Process. 48, 3042-3051 (2000) · Zbl 1002.12011 · doi:10.1109/78.875462 |
| [51] | Zhi, L.; Li, Z. (ed.); Sit, W. (ed.), Displacement structure in computing approximate GCD of univariate polynomials, 288-298 (2003), Singapore · Zbl 1092.12003 |
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.
