{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2022,4,2]],"date-time":"2022-04-02T18:44:37Z","timestamp":1648925077571},"reference-count":51,"publisher":"Springer Science and Business Media LLC","issue":"2","license":[{"start":{"date-parts":[[2013,11,6]],"date-time":"2013-11-06T00:00:00Z","timestamp":1383696000000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Numer Algor"],"published-print":{"date-parts":[[2014,10]]},"DOI":"10.1007\/s11075-013-9793-9","type":"journal-article","created":{"date-parts":[[2013,11,5]],"date-time":"2013-11-05T05:12:00Z","timestamp":1383628320000},"page":"319-334","source":"Crossref","is-referenced-by-count":0,"title":["A heuristic verification of the degree of the approximate GCD of two univariate polynomials"],"prefix":"10.1007","volume":"67","author":[{"given":"Zhe","family":"Li","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Qi","family":"Liu","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2013,11,6]]},"reference":[{"key":"9793_CR1","doi-asserted-by":"crossref","first-page":"7","DOI":"10.1016\/0024-3795(70)90023-6","volume":"3","author":"S Barnett","year":"1970","unstructured":"Barnett, S.: Greatest common divisor of two polynomials. Linear Algebra Appl. 3, 7\u20139 (1970)","journal-title":"Linear Algebra Appl."},{"key":"9793_CR2","doi-asserted-by":"crossref","first-page":"263","DOI":"10.1017\/S0305004100049860","volume":"70","author":"S Barnett","year":"1971","unstructured":"Barnett, S.: Greatest common divisor of several polynomials. Proc. Camb. Philos. Soc. 70, 263\u2013268 (1971)","journal-title":"Proc. Camb. Philos. Soc."},{"key":"9793_CR3","doi-asserted-by":"crossref","first-page":"84","DOI":"10.1137\/0122009","volume":"22","author":"S Barnett","year":"1972","unstructured":"Barnett, S.: A note on the Bezoutian matrix. SIAM J. Appl. Math. 22, 84\u201386 (1972)","journal-title":"SIAM J. Appl. Math."},{"key":"9793_CR4","doi-asserted-by":"crossref","first-page":"677","DOI":"10.1006\/jsco.1998.0234","volume":"26","author":"B Beckermann","year":"1998","unstructured":"Beckermann, B., Labahn, G.: When are two polynomials relatively prime. J. Symb. Comput. 26, 677\u2013689 (1998)","journal-title":"J. Symb. Comput."},{"issue":"3","key":"9793_CR5","doi-asserted-by":"crossref","first-page":"63","DOI":"10.1137\/0222041","volume":"22","author":"D Bini","year":"1993","unstructured":"Bini, D., Gemignani, L.: Fast parallel computation of the polynomial remainder sequence via Bezout and Hankel matrices. SIAM J. Comput. 22(3), 63\u201377 (1993)","journal-title":"SIAM J. Comput."},{"key":"9793_CR6","doi-asserted-by":"crossref","DOI":"10.1007\/978-1-4612-0265-3","volume-title":"Polynomial and Matrix Computations, vol. 1 of Fundamental Algorithm","author":"D Bini","year":"1994","unstructured":"Bini, D., Pan, V.Y.: Polynomial and Matrix Computations, vol. 1 of Fundamental Algorithm. Birkh\u00fcser, Boston (1994)"},{"key":"9793_CR7","doi-asserted-by":"crossref","unstructured":"Bini, D.A., Boito, P.: Structured matrix-based methods for polynomial \u03b5 $\\varepsilon $ -gcd: analysis and comparisons. In: Brown, C.W. (ed.) International Symposium Symbolic Algebraic Computation, pp. 9\u201316. ACM Press, New York (2007)","DOI":"10.1145\/1277548.1277551"},{"issue":"6","key":"9793_CR8","doi-asserted-by":"crossref","first-page":"2326","DOI":"10.1137\/050626636","volume":"24","author":"X Chen","year":"2006","unstructured":"Chen, X., Womersley, R.S.: Existence of solutions to systems of underdetermined equations and spherical designs. SIAM J. Numer. Anal. 24(6), 2326\u20132341 (2006)","journal-title":"SIAM J. Numer. Anal."},{"key":"9793_CR9","doi-asserted-by":"crossref","first-page":"4493","DOI":"10.1016\/j.tcs.2011.04.018","volume":"412","author":"G Ch\u00e9ze","year":"2011","unstructured":"Ch\u00e9ze, G., Galligo, A., Mourrain, B., Yakoubsohna, J.: A subdivision method for computing nearest gcd with certification. Theor. Comput. Sci. 412, 4493\u20134503 (2011)","journal-title":"Theor. Comput. Sci."},{"key":"9793_CR10","doi-asserted-by":"crossref","unstructured":"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\u2013207. ACM Press, New York (1995)","DOI":"10.1145\/220346.220371"},{"key":"9793_CR11","doi-asserted-by":"crossref","first-page":"3394","DOI":"10.1109\/TSP.2004.837413","volume":"52","author":"R Corless","year":"2004","unstructured":"Corless, R., Watt, S., Zhi, L.: QR factoring to compute the GCD of univariate approximate polynomials. IEEE Trans. Signal Process. 52, 3394\u20133402 (2004)","journal-title":"IEEE Trans. Signal Process."},{"key":"9793_CR12","doi-asserted-by":"crossref","first-page":"222","DOI":"10.1016\/j.laa.2005.06.028","volume":"412","author":"GM Diaz-Toca","year":"2006","unstructured":"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\u2013246 (2006)","journal-title":"Linear Algebra Appl."},{"key":"9793_CR13","doi-asserted-by":"crossref","first-page":"229","DOI":"10.1016\/S0022-4049(97)00013-3","volume":"117","author":"IZ Emiris","year":"1997","unstructured":"Emiris, I.Z., Galligo, A., Lombardi, H.: Certified approximate univariate GCDs. J. Pure Appl. Algebra Spec. Issue Algoritm. Algebra 117, 229\u2013251 (1997)","journal-title":"J. Pure Appl. Algebra Spec. Issue Algoritm. Algebra"},{"issue":"3","key":"9793_CR14","first-page":"453","volume":"3","author":"L Gemignani","year":"2006","unstructured":"Gemignani, L.: Gcd of polynomials and bezout matrices. J. Inf. Comput. Sci. 3(3), 453\u2013461 (2006)","journal-title":"J. Inf. Comput. Sci."},{"key":"9793_CR15","volume-title":"Matrix Computations, 3rd edn","author":"GH Golub","year":"1996","unstructured":"Golub, G.H., Van Loan, Ch.: Matrix Computations, 3rd edn. Johns Hopkins University Press, Baltimore (1996)"},{"issue":"1","key":"9793_CR16","doi-asserted-by":"crossref","first-page":"243","DOI":"10.1142\/S0218127495000181","volume":"5","author":"W Govaerts","year":"1995","unstructured":"Govaerts, W.: Bordered matrices and singularities of large nonlinear systems. Int. J. Bifurcation Chaos 5(1), 243\u2013250 (1995)","journal-title":"Int. J. Bifurcation Chaos"},{"key":"9793_CR17","doi-asserted-by":"crossref","first-page":"176","DOI":"10.1137\/0721012","volume":"21","author":"A Griewank","year":"1984","unstructured":"Griewank, A., Reddien, G.W.: Characterisation and computation of generalised turning points. SIAM J. Numer. Anal. 21, 176\u2013185 (1984)","journal-title":"SIAM J. Numer. Anal."},{"key":"9793_CR18","doi-asserted-by":"crossref","first-page":"591","DOI":"10.1007\/BF01389452","volume":"48","author":"A Griewank","year":"1986","unstructured":"Griewank, A., Reddien, G.W.: The approximation of generalized turning points by projection methods with superconvergence to the critical parameter. Numer. Math. 48, 591\u2013606 (1986)","journal-title":"Numer. Math."},{"key":"9793_CR19","doi-asserted-by":"crossref","first-page":"1912","DOI":"10.1137\/S003614299325866X","volume":"33","author":"A Griewank","year":"1996","unstructured":"Griewank, A., Reddien, G.W.: The approximate solution of defining equations for generalized turning points. SIAM J. Numer. Anal. 33, 1912\u20131920 (1996)","journal-title":"SIAM J. Numer. Anal."},{"key":"9793_CR20","doi-asserted-by":"crossref","DOI":"10.1137\/1.9780898718027","volume-title":"Accuracy and Stability of Numerical Algorithms","author":"NJ Higham","year":"2002","unstructured":"Higham, N.J.: Accuracy and Stability of Numerical Algorithms, 2nd edn. SIAM Publications, Philadelphia (2002)","edition":"2"},{"key":"9793_CR21","doi-asserted-by":"crossref","first-page":"667","DOI":"10.1006\/jsco.1997.0160","volume":"24","author":"V Hribernig","year":"1997","unstructured":"Hribernig, V., Stetter, H.: Detection and validation of clusters of polynomials zeros. J. Symb. Comput. 24, 667\u2013681 (1997)","journal-title":"J. Symb. Comput."},{"key":"9793_CR22","doi-asserted-by":"crossref","unstructured":"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\u2013176. ACM Press, New York (2006)","DOI":"10.1145\/1145768.1145799"},{"key":"9793_CR23","doi-asserted-by":"crossref","unstructured":"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\u00e4user Verlag, Switzerland (2007)","DOI":"10.1007\/978-3-7643-7984-1_5"},{"key":"9793_CR24","doi-asserted-by":"crossref","unstructured":"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\u201342. ACM Press, New York (1996)","DOI":"10.1145\/236869.236892"},{"key":"9793_CR25","doi-asserted-by":"crossref","first-page":"187","DOI":"10.1007\/BF02234767","volume":"4","author":"R Krawczyk","year":"1969","unstructured":"Krawczyk, R.: Newton-algorithmen zur bestimmung von nullstellen mit fehlerschranken. Computing 4, 187\u2013201 (1969)","journal-title":"Computing"},{"issue":"2","key":"9793_CR26","doi-asserted-by":"crossref","first-page":"200","DOI":"10.1016\/j.tcs.2008.09.003","volume":"409","author":"B Li","year":"2008","unstructured":"Li, B., Nie, J., Zhi, L.: Approximate gcds of polynomials and sparse sos relaxations. Theor. Comput. Sci. 409(2), 200\u2013210 (2008)","journal-title":"Theor. Comput. Sci."},{"issue":"1","key":"9793_CR27","doi-asserted-by":"crossref","first-page":"212","DOI":"10.1016\/j.cam.2007.01.032","volume":"213","author":"B Li","year":"2008","unstructured":"Li, B., Liu, Z., Zhi, L.: A structured rank-revealing method for sylvester matrix. J. Comput. Appl. Math. 213(1), 212\u2013223 (2008)","journal-title":"J. Comput. Appl. Math."},{"key":"9793_CR28","first-page":"3","volume":"11","author":"B Li","year":"2005","unstructured":"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\u20134 (2005)","journal-title":"Jpn. Soc. Symb. Algebraic Comput."},{"key":"9793_CR29","first-page":"155","volume-title":"International Symposium on Symbolic Algebraic Computation","author":"Z Li","year":"2010","unstructured":"Li, Z., Yang, Z., Zhi, L.: Blind image deconvolution via fast approximate GCD. In: International Symposium on Symbolic Algebraic Computation, pp. 155\u2013162. ACM Press, New York (2010)"},{"key":"9793_CR30","volume-title":"An Algorithm for Approximate Common Divisor Computation. Internal Report 205\u2013248, ESAT-SISTA","author":"I Markovsky","year":"2005","unstructured":"Markovsky, I., Huffel, S.V.: An Algorithm for Approximate Common Divisor Computation. Internal Report 205\u2013248, ESAT-SISTA. K.U.Leuven, Leuven (2005)"},{"key":"9793_CR31","doi-asserted-by":"crossref","first-page":"3436","DOI":"10.1016\/j.cam.2010.05.005","volume":"234","author":"S Miyajima","year":"2010","unstructured":"Miyajima, S.: Fast enclosure for solutions in underdetermined systems. J. Comput. Appl. Math. 234, 3436\u20133444 (2010)","journal-title":"J. Comput. Appl. Math."},{"key":"9793_CR32","unstructured":"Miyajima, S.: Componentwise enclosure for solutions in least squares problems and underdetermined linear systems. In: SCAN Conference Novosibirsk (2012)"},{"issue":"4","key":"9793_CR33","doi-asserted-by":"crossref","first-page":"611","DOI":"10.1137\/0714040","volume":"14","author":"RE Moore","year":"1977","unstructured":"Moore, R.E.: A test for existence of solutions to nonlinear system. SIAM J. Numer. Anal. 14(4), 611\u2013615 (1977)","journal-title":"SIAM J. Numer. Anal."},{"issue":"4","key":"9793_CR34","doi-asserted-by":"crossref","first-page":"697","DOI":"10.1007\/s10898-006-9119-8","volume":"40","author":"J Nie","year":"2008","unstructured":"Nie, J., Demmel, J., Gu, M.: Global minimization of rational functions and the nearest gcds. J. Glob. Optim. 40(4), 697\u2013718 (2008)","journal-title":"J. Glob. Optim."},{"key":"9793_CR35","doi-asserted-by":"crossref","first-page":"335","DOI":"10.1016\/0377-0427(91)90180-R","volume":"38","author":"M Noda","year":"1991","unstructured":"Noda, M., Sasaki, T.: Approximate GCD and its application to ill-conditioned algebraic equations. J. Comput. Appl. Math. 38, 335\u2013351 (1991)","journal-title":"J. Comput. Appl. Math."},{"key":"9793_CR36","doi-asserted-by":"crossref","first-page":"71","DOI":"10.1006\/inco.2001.3032","volume":"167","author":"V Pan","year":"2001","unstructured":"Pan, V.: Numerical computation of a polynomial GCD and extensions. Inf. Comput. 167, 71\u201385 (2001)","journal-title":"Inf. Comput."},{"key":"9793_CR37","doi-asserted-by":"crossref","first-page":"1040","DOI":"10.1137\/0723072","volume":"23","author":"PJ Rabier","year":"1986","unstructured":"Rabier, P.J., Reddien, G.W.: Characterization and computation of singular points with maximum rank deficiency. SIAM J. Numer. Anal. 23, 1040\u20131051 (1986)","journal-title":"SIAM J. Numer. Anal."},{"key":"9793_CR38","unstructured":"Rump, S.M.: Kleine fehlerschranken bei matrixproblemen. Ph.D. thesis. Universit Karlsruhe (1980)"},{"key":"9793_CR39","doi-asserted-by":"crossref","unstructured":"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\u2013120. Academic, New York (1983)","DOI":"10.1016\/B978-0-12-428660-3.50010-0"},{"key":"9793_CR40","doi-asserted-by":"crossref","first-page":"287","DOI":"10.1017\/S096249291000005X","volume":"19","author":"SM Rump","year":"2010","unstructured":"Rump, S.M.: Verification methods: rigorous results using floating-point arithmetic. Acta Numer. 19, 287\u2013449 (2010)","journal-title":"Acta Numer."},{"issue":"2","key":"9793_CR41","doi-asserted-by":"crossref","first-page":"367","DOI":"10.1007\/s10543-010-0294-0","volume":"51","author":"SM Rump","year":"2011","unstructured":"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\u2013384 (2011)","journal-title":"BIT Numer. Math."},{"issue":"1","key":"9793_CR42","doi-asserted-by":"crossref","first-page":"130","DOI":"10.1137\/110840248","volume":"33","author":"SM Rump","year":"2012","unstructured":"Rump, S.M.: Verified bounds for least squares problems and underdetermined linear systems. SIAM J. Matrix Anal. Appl. 33(1), 130\u2013148 (2012)","journal-title":"SIAM J. Matrix Anal. Appl."},{"key":"9793_CR43","doi-asserted-by":"crossref","unstructured":"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","DOI":"10.1007\/s11075-013-9735-6"},{"issue":"1","key":"9793_CR44","doi-asserted-by":"crossref","first-page":"118","DOI":"10.1016\/0885-064X(85)90024-X","volume":"1","author":"A Sch\u00f6nhage","year":"1985","unstructured":"Sch\u00f6nhage, A.: Quasi-gcd computations. J. Complex. 1(1), 118\u2013137 (1985)","journal-title":"J. Complex."},{"key":"9793_CR45","doi-asserted-by":"crossref","first-page":"65","DOI":"10.1016\/j.jcp.2004.09.016","volume":"204","author":"A Spence","year":"2005","unstructured":"Spence, A., Poulton, C.: Photonic band structure calculations using nonlinear eigenvalue techniques. J. Comput. Phys. 204, 65\u201381 (2005)","journal-title":"J. Comput. Phys."},{"key":"9793_CR46","first-page":"207","volume":"25","author":"D Sun","year":"2006","unstructured":"Sun, D., Zhi, L.: Structured low rank approximation of a bezout matrix. MM Res. Prepr. 25, 207\u2013218 (2006)","journal-title":"MM Res. Prepr."},{"key":"9793_CR47","doi-asserted-by":"crossref","first-page":"427","DOI":"10.1007\/s11786-007-0014-6","volume":"1","author":"D Sun","year":"2007","unstructured":"Sun, D., Zhi, L.: Structured low rank approximation of a bezout matrix. Math. Comput. Sci. 1, 427\u2013437 (2007)","journal-title":"Math. Comput. Sci."},{"key":"9793_CR48","doi-asserted-by":"crossref","unstructured":"Terui, A.: An iterative method for calculating approximate GCD of univariate polynomials. In: May (ed.) International Symposium on Symbolic Algebraic Computation, pp. 351\u2013358. ACM Press, New York (2009)","DOI":"10.1145\/1576702.1576750"},{"key":"9793_CR49","first-page":"320","volume-title":"The approximate gcd of inexact polynomials. In: International Symposium on Symbolic and Algebraic Computation","author":"Z Zeng","year":"2004","unstructured":"Zeng, Z., Dayton, B.H.: The approximate gcd of inexact polynomials. In: International Symposium on Symbolic and Algebraic Computation, pp. 320\u2013327. ACM Press, New York (2004)"},{"key":"9793_CR50","doi-asserted-by":"crossref","first-page":"3042","DOI":"10.1109\/78.875462","volume":"48","author":"CJ Zarowski","year":"2000","unstructured":"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\u20133051 (2000)","journal-title":"IEEE Trans. Signal Process."},{"key":"9793_CR51","first-page":"288","volume-title":"Sixth Asian Symposium on Computer Mathematics (ASCM 2003), vol. 10 of Lecture Notes Series on Computing","author":"L Zhi","year":"2003","unstructured":"Zhi, L.: Displacement structure in computing approximate GCD of univariate polynomials. In: Li, Z., Sit, W. (eds.) Sixth Asian Symposium on Computer Mathematics (ASCM 2003), vol. 10 of Lecture Notes Series on Computing, pp. 288-298. World Scientific, Singapore (2003)"}],"container-title":["Numerical Algorithms"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s11075-013-9793-9.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s11075-013-9793-9\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s11075-013-9793-9","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,7,31]],"date-time":"2019-07-31T21:03:55Z","timestamp":1564607035000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s11075-013-9793-9"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2013,11,6]]},"references-count":51,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2014,10]]}},"alternative-id":["9793"],"URL":"https:\/\/doi.org\/10.1007\/s11075-013-9793-9","relation":{},"ISSN":["1017-1398","1572-9265"],"issn-type":[{"value":"1017-1398","type":"print"},{"value":"1572-9265","type":"electronic"}],"subject":[],"published":{"date-parts":[[2013,11,6]]}}}