Browse Prior Art Database

AN EXACT METHOD FOR FINDING THE ROOTS OF A COMPLEX POLYNOMIAL

IP.com Disclosure Number: IPCOM000128692D
Original Publication Date: 1975-Dec-31
Included in the Prior Art Database: 2005-Sep-16
Document File: 29 page(s) / 61K

Publishing Venue

Software Patent Institute

Related People

James R. Pinkert: AUTHOR [+3]

Abstract

Let G be a univariate polynomial with rational complex coefficients. This paper describes a new SAC-1 module which uses algebraic algorithms based on the classical theorems of Sturm and Routh to isolate the unique roots of G into disjoint squares in the complex plane. These squares can then be refined to any prespecified rational width. Furthermore, the algorithms can associate with each square the multiplicity of the unique root of G contained in that square.

This text was extracted from a PDF file.
This is the abbreviated version, containing approximately 9% of the total text.

Page 1 of 29

THIS DOCUMENT IS AN APPROXIMATE REPRESENTATION OF THE ORIGINAL.

AN EXACT METHOD FOR FINDING THE ROOTS OF A COMPLEX POLYNOMIAL*

James R. Pinkert

CS-75-4 March 1975

* Research supported by National Science Foundation, I

Grant GJ-30125X

Abstract

Let G be a univariate polynomial with rational complex coefficients. This paper describes a new SAC-1 module which uses algebraic algorithms based on the classical theorems of Sturm and Routh to isolate the unique roots of G into disjoint squares in the complex plane. These squares can then be refined to any prespecified rational width. Furthermore, the algorithms can associate with each square the multiplicity of the unique root of G contained in that square.

Exact arithmatic is used so that all computational errors are eliminated. The system is self- sufficient in the sense that no starting approximations are needed, and no user interaction during computation is required. The methods used insure termination of the algorithms with the desired squares regardless of such aspects as multiple roots, roots which are distinct but very close together, or polynomials with high condition numbers.

Theoretical computing times are analyzed and compared to empirical results.

Keywords

Polynomials, SAC-1, Zeros, Roots, Root-Finding, Algebraic Algorithms, Computational Algebra, Analysis of Algorithms, Sturm's Theorem, Routh's Theorem, FORTRAN, List Processing, Modular Arithmetic, Algebra n some instances, the SAC-1 root-finding modules have not been used because the polynomial in question had "real" coefficients. The quotes are used because what was often meant was not real in the mathematical sense, but rather real in the sense of being represented as "floating point" on a computer. With present-day binary computers, these floating point numbers are actually rationals. Hence the polynomial can be rewritten with coefficients in a rational form acceptable to the SAC-1 modules.

This is certainly not meant to imply that these algebraic systems should be used in every case. For example, a given application might not require the exact arithmetic, with its corresponding increase in computing time, to obtain sufficiently accurate results. Rather, what is meant here is that floating point coefficients should not immediately exclude algebraic systems.

Polynomials, SAC-1, Zeros, Roots, Root-Finding, Algebraic Algorithms, Computational Algebra, Analysis of Algorithms, Sturm's Theorem, Routh's Theorem, FORTRAN, List Processing, Modular Arithmetic, Algebra

University of Tennessee Page 1 Dec 31, 1975

Page 2 of 29

AN EXACT METHOD FOR FINDING THE ROOTS OF A COMPLEX POLYNOMIAL

1. Introduction

Systems for finding the roots of polynomials are an important part of mathematical software, having many applications in a variety of areas. Closed form expressions for the roots of arbitrary polynomials with degree n>4 do not exist, and hence some sort of search technique most be employed.

One important reason for the number and dive...