An efficient algorithm is presented that returns the exactly rounded sum of two multiprecision floating point numbers. Depending on the input signs and exponents the algorithm distinguishes five cases. In each case, the method minimizes the number of computer words that are subject to de-normalization, addition or subtraction, and normalization. The method achieves further efficiency by trying to combine these three steps into one single pass over the mantissas. To do this, the method guesses the shift amount of the normalizing shift before the sum is known.

Let a rectangle be given which contains exactly one complex root of a given univariate polynomial. Let the edges of the rectangle be parallel to the coordinate axes. We present a hybrid symbolic-numeric method for constructing a small subrectangle which contains the root. The subrectangle is chosen such that it contains the intersection of two triangles. The triangles are constructed so as to contain segments of certain algebraic curves that pass through the given rectangle; the intersection of these segments is precisely the complex root. 1 Introduction Any univariate polynomial A 2 C[z] can be represented canonically as a pair of bivariate real polynomials: A(z) 7\\Gamma! A(x + iy) = AU (x; y) + iAV (x; y) The complex roots of A are precisely the intersection points of the plane algebraic curves U and V defined by the two bivariate polynomials; U = f(x; y) 2 R 2 jAU (x; y) = 0g, V = f(x; y) 2 R 2 jAV (x; y) = 0g. Let R be a rectangle in the complex plane with edges parallel to...

A straightforward implementation of Newton's method for polynomial real root calculation using exact arithmetic is inefficient. In each step the length of the iterate multiplies by the degree of the polynomial while its accuracy merely doubles. We present an exact algorithm which keeps the length of each iterate proportional to its accuracy. The resulting speed-up is dramatic. The average computing time can be further reduced by trying floating point computations. Several floating point Newton steps are executed; interval arithmetic is used to check whether the result is sufficiently close to the root; if this condition cannot be verified the exact algorithm is invoked. 1 Introduction Real roots of a univariate integral polynomial A can be calculated in two steps, called "root isolation" and "root refinement". Root isolation computes isolating intervals for the roots of A; those are intervals which contain exactly one polynomial root each. Root refinement refines an isolating interva...

Applying the principle of the argument to rectangles provides an efficient algorithm for polynomial complex root isolation. For example, the roots of a real integral polynomial of degree 10 (with 10-bit coefficients) can be isolated in about 1 second. Furthermore, although the algorithm is not designed for efficient refinement of isolating rectangles, it does nevertheless refine all of these rectangles to width 10 \\Gamma50 in less than 4 minutes. 1 Introduction Let A(z) be a non-zero squarefree univariate polynomial with Gaussian integer coefficients. This paper presents an algorithm which produces disjoint isolating rectangles for all the roots of A(z) in the complex plane, i.e. each such rectangle will contain exactly one root of A, and each root of A will be contained in one of the rectangles. The sides of the rectangles will be parallel to the axes. Given any rational number e ? 0, the algorithm will deliver isolating rectangles with sidelengths ! e. Unlike numerical methods t...

Article Free Access Share on Quantifier elimination and the sign variation method for real root isolation Authors: G. E. Collins Ohio State Univ., Columbus Ohio State Univ., ColumbusView Profile , J. R. Johnson Ohio State Univ., Columbus Ohio State Univ., ColumbusView Profile Authors Info & Claims ISSAC '89: Proceedings of the ACM-SIGSAM 1989 international symposium on Symbolic and algebraic computationJuly 1989 Pages 264–271https://doi.org/10.1145/74540.74574Online:17 July 1989Publication History 9citation342DownloadsMetricsTotal Citations9Total Downloads342Last 12 Months7Last 6 weeks4 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my Alerts New Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteeReaderPDF

Given a set of r-variate integral polynomials, a cylindrical algebraic decomposition (cad) of euclidean r-space $E^r $ partitions $E^r $ into connected subsets compatible with the zeros of the polynomials. Each subset is a cell Collins gave a cad construction algorithm in 1975, as part of a quantifier elimination procedure for real closed fields. The cad algorithm has found diverse applications (optimization, curve display); new applications have been proposed (term rewriting systems, motion planning). In the present two-part paper, we give an algorithm which determines the pairs of adjacent cells as it constructs a cad of $E^2 $. Such information is often useful in applications. In Part I we describe the essential features of the r-space cad algorithm, to provide a framework for the adjacency algorithm in Part II.

Given a set of r-variate integral polynomials, a cylindrical algebraic decomposition (cad) of euclidean r-space $E^r $ partitions $E^r $ into connected subsets compatible with the zeros of the polynomials. Each subset is a cell. Informally, two cells of a cad are adjacent if they touch each other; formally, they are adjacent if their union is connected. In applications of cad’s one often wishes to know the adjacent pairs of cells. Previous algorithms for cad construction (such as that given in Part I of this paper) have not actually determined them. We give here in Part II an algorithm which determines the pairs of adjacent cells as it constructs a cad of $E^2 $.

Two algorithms for the solution of linear Diophantine systems, which well restrain intermediate expression swell, are presented. One is an extension and improvement of Kannan and Bachem’s algorithm for the Smith and the Hermite normal forms of a nonsingular square integral matrix. The complexity of this algorithm is investigated and a polynomial time bound is derived. Also a much better coefficient bound is obtained compared to Kannan and Bachem’s analysis. The other is based on ideas of Rosser, which were originally used in finding a general solution with smaller coefficients to a linear Diophantine equation and in computing the exact inverse of a nonsingular square integral matrix. These algorithms are implemented by using the infinite precision integer arithmetic capabilities of the SAC-2 system. Their performances are compared. Finally future studies are mentioned.

The minimum, maximum and average computing times of the classical Euclidean algorithm are derived. With positive integer inputs of lengths m and n, and with output (greatest common divisor) of length k, $m \geqq n \geqq k$, the minimum is shown to be codominant with $n(m - n + 1) + k(n - k + 1)$, while both the maximum and the average are shown to be codominant with $n(m - k + 1)$.

This paper describes a graduate course curriculum, currently being taught, in the area of symbolic mathematical computation. The subject area is described and is then followed by a description of the courses. A bibliography for each course is also given. The relationship of the symbolic mathematical computation curriculum to an overall Computer Science curriculum is discussed. Ph.D. theses which have been written are listed and some topics for future research are outlined. The paper ends with a summary of the strengths and weakensses of the curriculum.

An efficient algorithm is presented for the exact calculation of resultants of multivariate polynomials with integer coefficients.The algorithm applies modular homomorphisms and the Chinese remainder theorem, evaluation homomorphisms and interpolation, in reducing the problem to resultant calculation for univariate polynomials over GF(p), whereupon a polynomial remainder sequence algorithm is used.The computing time of the algorithm is analyzed theoretically as a function of the degrees and coefficient sizes of its inputs.As a very special case, it is shown that when all degrees are equal and the coefficient size is fixed, its computing time is approximately proportional to V r+*, where X is the common degree and r is the number of variables.Empirically observed computing times of the algorithm are tabulated for a large number of examples, and other algorithms are compared.Potential application of the algorithm to the solution of systems of polynomial equations is briefly discussed.

Let @@@@ be an integral domain, P(@@@@) the integral domain of polynomials over @@@@. Let P , Q ∈ P(@@@@) with m @@@@ deg ( P ) ≥ n = deg ( Q ) > 0. Let M be the matrix whose determinant defines the resultant of P and Q . Let M ij be the submatrix of M obtained by deleting the last j rows of P coefficients, the last j rows of Q coefficients and the last 2 j +1 columns, excepting column m — n — i — j (0 ≤ i ≤ j < n ). The polynomial R j ( x ) = ∑ i i =0 det ( M ij ) x i is the j-t subresultant of P and Q , R 0 being the resultant. If b = £( Q ), the leading coefficient of Q , then exist uniquely R , S ∈ P(@@@@) such that b m-n +1 P = QS + R with deg ( R ) < n ; define R( P , Q ) = R . Define P i ∈ P( F ), F the quotient field of @@@@, inductively: P 1 = P , P 2 = Q , P 3 = R P 1 , P 2 P i -2 = R( P i , P i +1 )/ c δ i -1 +1 i for i ≥ 2 and n i +1 > 0, where c i = £( P i ), n i = deg ( P i ) and δ i = n i — n i +1 . P 1 , P 2 , …, P k , for k ≥ 3, is called a reduced polynomial remainder sequence . Some of the main results are: (1) P i ∈ P(@@@@) for 1 ≤ i ≤ k ; (2) P k = ± A k R n k -1 -1 , when A k = Π k -2 i -2 c δ i -1 (δ i -1) i ; (3) c δ k -1 -1 k P k = ± A k +1 R n k ; (4) R j = 0 for n k < j < n k -1 — 1. Taking @@@@ to be the integers I , or P r ( I ), these results provi

In this paper a theorem will be established which states that a particular axiom of choice is equivalent to complete distributivity of union and intersection. The theorem will be formulated and proved in the system of logic of [4]. In addition to definitions of [4], the following will be used. In terms of these definitions, the theorem can be formulated as follows. The dual of this statement, obtained by interchanging I and U, is also a theorem and has a similar proof.