| We study numerical algorithms where a system of polynomial equations is solved by converting the problem into an eigenvalue problem. We look at both the case of one polynomial in one variable and the case of two polynomials in two variables. We analyze the numerical accuracy of the algorithms presented for each case.; For a univariate polynomial, we focus on the special case when the leading coefficient is relatively very small. We argue that the companion matrix algorithm (used, for instance, by the Matlab function) is inaccurate in this case. The accuracy problem is addressed by using matrix pencils instead. This improvement can be predicted from the backward error bound of Edelman and Murakami (for companion matrices) versus the bound of Van Dooren and Dewilde (for pencils). We then show how to extend the accurate algorithm to Bezier polynomials and present computational experiments.; For two polynomials in two variables, we present an algorithm based on Macaulay resultant matrices. Our method is similar to that of Macaulay, but we make important modifications to increase the numerical stability of the approach. We analyze the algorithm, both in exact arithmetic and in floating-point arithmetic, the latter analysis being based on the former. The roots are determined from the eigenvector rather than the eigenvalues and the analysis is based on estimating the conditioning of the eigenvector. We argue that if the polynomial system is not ill-conditioned because of a near common factor or because the root being considered is ill-conditioned, then with high probability our algorithm gives an accurate answer.; To our knowledge, this thesis provides the first analysis of an algebraic method for multivariate polynomial root-finding that directly connects the condition of the original polynomial system to the accuracy of the roots computed in floating-point arithmetic. |
