×

Roots of bivariate polynomial systems via determinantal representations. (English) Zbl 1376.65056

Summary: We give two determinantal representations for a bivariate polynomial. They may be used to compute the zeros of a system of two of these polynomials via the eigenvalues of a two-parameter eigenvalue problem. The first determinantal representation is suitable for polynomials with scalar or matrix coefficients and consists of matrices with asymptotic order \(n^2/4\), where \(n\) is the degree of the polynomial. The second representation is useful for scalar polynomials and has asymptotic order \(n^2/6\). The resulting method to compute the roots of a system of two bivariate polynomials is very competitive with some existing methods for polynomials up to degree 10, as well as for polynomials with a small number of terms.

MSC:

65F15 Numerical computation of eigenvalues and eigenvectors of matrices
65H10 Numerical computation of solutions to systems of equations
65F50 Computational methods for sparse matrices
13P15 Solving polynomial systems; resultants
PDFBibTeX XMLCite
Full Text: DOI arXiv

References:

[1] F. V. Atkinson, {\it Multiparameter Eigenvalue Problems}, Academic Press, New York, 1972. · Zbl 0555.47001
[2] C. Bajaj, T. Garrity, and J. Warren, {\it On the Applications of Multi-Equational Resultants}, Technical report, Purdue University, 1988.
[3] D. J. Bates, J. H. Husenstein, A. J. Sommese, and C. W. Wampler, {\it Bertini: Software for Numerical Algebraic Geometry}, bertini.nd.edu; doi: dx.doi.org/10.7274/R0H41PB5.
[4] P. Berman, A. Bhattacharyya, K. Makarychev, S. Raskhodnikova, and G. Yaroslavtsev, {\it Approximation algorithms for spanner problems and directed Steiner forest}, Inform. Comput., 222 (2013), pp. 93-107. · Zbl 1267.68317
[5] S. Beyme and C. Leung, {\it A stochastic process model of the hop count distribution in wireless sensor networks}, Ad Hoc Networks, 17 (2014), pp. 60-70.
[6] L. Busé, H. Khalil, and B. Mourrain, {\it Resultant-based methods for plane curves intersection problems}, in Proceedings of the 8th International Conference on Computer Algebra in Scientific Computing, Lecture Notes in Comput. Sci. 3718, Springer-Verlag, Berlin, 2005, pp. 75-92. · Zbl 1169.65316
[7] R. H. Byrd, R. B. Schnabel, and G. A. Schultz, {\it Approximate solution of the trust region problem by minimization over two-dimensional subspaces}, Math. Program., 40, 1 (1988), pp. 247-263. · Zbl 0652.90082
[8] M. Costa, V. Koivunen, and A. Richter, {\it Low complexity azimuth and elevation estimation for arbitrary array configurations}, in Proceedings of Acoustics, Speech and Signal Processing, IEEE, 2009, pp. 2185-2188.
[9] L. E. Dickson, {\it Determination of all general homogeneous polynomials expressible as determinants with linear elements}, Trans. Amer. Math. Soc., 22 (1921), pp. 167-179. · JFM 48.0099.02
[10] A. Dixon, {\it Note on the reduction of a ternary quartic to a symmetrical determinant}, Proc. Camb. Phil. Soc., 11 (1902), pp. 350-351. · JFM 33.0140.04
[11] P. Dreesen, K. Batselier, and B. De Moor, {\it Back to the roots: polynomial system solving, linear algebra, systems theory}, in Proceedings of the 16th IFAC Symposium on System Identification, Brussels, Belgium, 2012 pp. 1203-1208.
[12] Y. Guan and J. Verschelde, {\it PHClab: A MATLAB/Octave Interface to PHCpack}, in Software for Algebraic Geometry, M. Stillman, J. Verschelde, and N. Takayama, eds, IMA Vol. Math. Appl. 148, Springer, New York, 2008, pp. 15-32. · Zbl 1148.68578
[13] B. Hanzon and J. Maciejowski, {\it Constructive algebra methods for the L2-problem for stable linear systems}, Automatica, 32 (1996), pp. 1645-1657. · Zbl 0875.93281
[14] G. F. Hatke, {\it Superresolution source location with planar arrays}, Lincoln Lab. J., 10 (1997).
[15] J. W. Helton, S. A. McCullough, and V. Vinnikov, {\it Noncommutative convexity arises from linear matrix inequalities}, J. Funct. Anal., 240 (2006), pp. 105-191. · Zbl 1135.47005
[16] J. W. Helton and V. Vinnikov, {\it Linear matrix inequality representation of sets}, Comm. Pure Appl. Math., 60 (2007), pp. 654-674. · Zbl 1116.15016
[17] M. E. Hochstenbach, T. Košir, and B. Plestenjak, {\it A Jacobi-Davidson type method for the nonsingular two-parameter eigenvalue problem}, SIAM J. Matrix Anal. Appl., 26 (2005), pp. 477-497. · Zbl 1077.65036
[18] M. E. Hochstenbach, A. Muhič, and B. Plestenjak, {\it On linearizations of the quadratic two-parameter eigenvalue problems}, Linear Algebra Appl., 436 (2012), pp. 2725-2743. · Zbl 1245.65042
[19] M. E. Hochstenbach, A. Muhič, and B. Plestenjak, {\it A Jacobi-Davidson method for polynomial two-parameter eigenvalue problems}, J. Comput. Appl. Math., 288 (2015), pp. 251-263. · Zbl 1503.65075
[20] M. E. Hochstenbach, H. A. van der Vorst, {\it Alternatives to the Rayleigh quotient for the quadratic eigenvalue problem}, SIAM J. Sci. Comput., 25 (2003), pp. 591-603. · Zbl 1042.65028
[21] R. A. Horn and C. R. Johnson, {\it Matrix Analysis}, Cambridge University Press, Cambridge, UK, 1985. · Zbl 0576.15001
[22] E. Jarlebring and M. E. Hochstenbach, {\it Polynomial two-parameter eigenvalue problems and matrix pencil methods for stability of delay-differential equations}, Linear Algebra Appl., 431 (2009), pp. 369-380. · Zbl 1170.65063
[23] G. Jónsson and S. Vavasis, {\it Accurate solution of polynomial equations using Macaulay resultant matrices}, Math. Comp., 74 (2005), pp. 221-262. · Zbl 1083.65052
[24] D. Jungnickel, {\it Graphs, Networks and Algorithms}, 4th ed., Springer, Heidelberg, 2013. · Zbl 1255.68001
[25] V. B. Khazanov, {\it To solving spectral problems for multiparameter polynomial matrices}, J. Math. Sci., 141 (2007), pp. 1690-1700.
[26] K. H. Ko, T. Sakkalis, and N. M. Patrikalakis, {\it Nonlinear polynomial systems: Multiple roots and their multiplicities}, in Proceedings of Shape Modeling Applications, IEEE, 2004, pp. 87-98.
[27] P. Lancaster and P. Psarrakos, {\it A Note on Weak and Strong Linearizations of Regular Matrix Polynomials}, NA Report 470, Manchester Centre for Computational Mathematics, 2005. · Zbl 1095.65032
[28] J. B. Lasserre, M. Laurent, and P. Rostalski, {\it A unified approach to computing real and complex zeros of zero-dimensional ideals}, in {\it Emerging Applications of Algebraic Geometry}, M. Putinar and S. Sullivant, eds., IMA Vol. Math. Appl. 149, Springer-Verlag, New York, 2009, pp. 125-155. · Zbl 1171.12001
[29] C. Lennerz and E. Schömer, {\it Efficient distance computation for quadratic curves and surfaces}, in Proceedings of Geometric Modeling and Processing, IEEE, 2002, pp. 60-69.
[31] A. Muhič, {\it Numerical Methods for Singular Multiparameter Eigenvalue Problems}, Ph.D. thesis, University of Ljubljana, 2011.
[32] A. Muhič and B. Plestenjak, {\it On the singular two-parameter eigenvalue problem}, Electron. J. Linear Algebra, 18 (2009), pp. 420-437. · Zbl 1190.15011
[33] A. Muhič and B. Plestenjak, {\it On the quadratic two-parameter eigenvalue problem and its linearization}, Linear Algebra Appl., 432 (2010), pp. 2529-2542. · Zbl 1189.65070
[34] Y. Nakatsukasa, V. Noferini, and A. Townsend, {\it Computing the common zeros of two bivariate functions via Bézout resultants}, Numer. Math. (2014): pp. 1-29. · Zbl 1308.65076
[36] T. Netzer and A. Thom, {\it Polynomials with and without determinantal representations}, Linear Algebra Appl., 437 (2012), pp. 1579-1595. · Zbl 1259.15016
[37] A. Newell, {\it BertiniLab: Toolbox for solving polynomial systems}, MATLAB Central File Exchange, www.mathworks.com/matlabcentral/fileexchange/48536-bertinilab (2015).
[38] D. Plaumann, R. Sinn, D. E. Speyer, and C. Vinzant, {\it Computing Hermitian Determinantal Representations of Hyperbolic Curves}, arXiv:1504.06023 [math.AG], 2015. · Zbl 1332.14070
[39] B. Plestenjak, MultiParEig: {\it Toolbox for multiparameter eigenvalue problems}, MATLAB Central File Exchange, www.mathworks.com/matlabcentral/fileexchange/47844-multipareig, (2015).
[40] R. Quarez, {\it Symmetric determinantal representation of polynomials}, Linear Algebra Appl., 436 (2012), pp. 3642-3660. · Zbl 1238.47010
[41] A. J. Sommese and C. W. Wampler, {\it The Numerical Solution of Systems of Polynomials Arising in Engineering and Science}, World Scientific, Singapore, 2005. · Zbl 1091.65049
[42] L. Sorber, {\it Data Fusion–Tensor Factorizations by Complex Optimization}, Ph.D. thesis, KU Leuven, 2014.
[43] L. Sorber, M. Van Barel, and L. De Lathauwer, {\it Numerical solution of bivariate and polyanalytic polynomial systems}, SIAM J. Numer. Anal., 52 (2014), pp. 1551-1572. · Zbl 1302.65135
[44] H. J. Stetter, {\it Numerical Polynomial Algebra}, SIAM, Philadelphia, 2004. · Zbl 1058.65054
[45] B. Sturmfels, {\it Solving Systems of Polynomial Equations}, CBMS Reg. Conf. Ser. Math. 97, AMS, Providence, RI, 2002. · Zbl 1101.13040
[46] A. Townsend and L. N. Trefethen, {\it An extension of Chebfun to two dimensions}, SIAM J. Sci. Comput., 35 (2013), pp. 495-518. · Zbl 1300.65010
[47] J. Van der Laar, {\it Mimo Instantaneous Blind Identification and Separation Based on Arbitrary Order Temporal Structure in the Data}, Ph.D. thesis, TU Eindhoven, 2007.
[48] P. van Dooren, {\it The computation of Kronecker’s canonical form of a singular pencil}, Linear Algebra Appl., 27 (1979), pp. 103-141. · Zbl 0416.65026
[49] J. Verschelde, {\it Algorithm 795: PHCpack: A general-purpose solver for polynomial systems by homotopy continuation}, ACM Trans. Math. Software, 25 (1999), pp. 251-276. · Zbl 0961.65047
[50] V. Vinnikov, {\it LMI representations of convex semialgebraic sets and determinantal representations of algebraic ypersurfaces: Past, present, and future}, in {\it Mathematical Methods in Systems, Optimization, and Control: Festschrift in Honor of J. William Helton}, H. Dym. M. C. de Oliveira, and M. Putinar, eds., Oper. Theory Adv. Appl. 222, Birkhäuser, 2012 pp. 325-349. · Zbl 1276.14069
[52] Z. Zeng and T.-Y. Li, {\it NAClab: A Matlab toolbox for numerical algebraic computation}, ACM Commun. Comput. Algebra, 47 (2013), pp. 170-173.
[53] K. Zhou and S. I. Roumeliotis, {\it Multirobot active target tracking with combinations of relative observations}, IEEE J. Robot. Automat., 27 (2011), pp. 678-695.
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.