NDLI: On the subresultant PRS algorithm

Please wait, while we are loading the content...

On determining the order of a group

Calculating presentations for certain kinds of quotient groups

Collection

Polynomial real root isolation by differentiation

On square-free decomposition algorithms

Algorithms for Gaussian integer arithmetic

A new REDUCE model for algebraic simplification

The definition and use of data structures in REDUCE

A pattern compiler

A draft description of the group theory language Cayley

Recursive programming through table look-up

Symbolic evaluation of programs: a look at loop analysis

Qualitative analysis of mathematical expressions using computer symbolic mathematics

Automatic symbolic solution of differential equations of first order and first degree

Projective representations for energy band calculations

Perturbation calculations for the spin up problem using REDUCE

Practical fast polynomial multiplication

Arithmetic complexity of unordered sparse polynomials

Hashing LEMMAs on time complexities with applications to formula manipulation

Univariate power series expansions in algebraic manipulation

The MACSYMA “big-floating-point” arithmetic system

Interval arithmetic applied to polynomial remainder sequences

Algebraic factoring and rational function integration

Some problems about polynomials

Using basis computation to determine pseudo-multiplicative independence

On the sign of a real algebraic number

Algorithms for symmetrical polynomials

Algebraic algorithms using p-adic constructions

Newton's method: a great algebraic algorithm

On the subresultant PRS algorithm

Polynomial real root isolation using Descarte's rule of signs

The aliquot project: an application of job chaining in number theoretic computing

Generalization of Manin's conditional algorithm

Computers in the study of Lie algebras

Computational techniques and the structure of groups in a certain class

The computation and application of vector congruence classes

Simplification of radical expressions

Canonical representatives for residue classes of a polynomial ideal

Taking advantage of zero entries in the exact inverse of sparse matrices

Completing nth powers of polynomials

A polynomial decomposition algorithm

ASHMEDAI and a large algebraic problem

An approach to automatic asymptotic expansions

A study of alternative methods for the symbolic calculation of elliptic integrals

Symbolic/numeric algorithms for partial differential equations

Use of symbolic and numeric methods in an algorithm for the approximation of multivariate functions

On the subresultant PRS algorithm

Content Provider	ACM Digital Library
Author	Brown, W. S.
Abstract	This paper is a sequel to two earlier papers [1, 2] on the generalization of Euclid's algorithm to domains of polynomials. In attempting such a generalization one easily arrives at the concept of a polynomial remainder sequence (PRS), and then quickly discovers the phenomenon of explosive coefficient growth. Fortunately, this explosive growth is not inherent in the problem, but is only an artifact of various naive solutions. If one removes the content (that is, the greatest common divisor of the coefficients) from each polynomial in a PRS, the coefficient growth in the resulting primitive PRS is relatively modest. However, the cost of computing the content (by applying Euclid's algorithm in the coefficient domain) may be unacceptably or even prohibitively high, especially if the coefficients are themselves polynomials in one or more additional variables. The key to controlling coefficient growth without the costly computation of greatest common divisors (GCD's) of coefficients is the discovery by Collins [3] that every polynomial in a PRS is proportional to some subresultant of the first two. By arranging for the constants of proportionality to be unity, Collins developed the subresultant PRS algorithm, which is the subject of this paper. Unfortunately, Collins' formulation of the algorithm was too complicated for convenient application, and he therefore recommended the simpler reduced PRS algorithm as a practical compromise. Later, Brown and Traub [1] discovered the fundamental theorem of subresultants, and used it to derive a much simpler formulation of the subresultant PRS algorithm. Also, Brown [2] derived essentially linear bounds on the coefficient growth in a subresultant PRS, while showing that the coefficient growth in a reduced PRS can be exponential if the sequence involves degree differences greater than unity. Although such abnormal sequences are a set of measure zero in the space of all PRS's, they are not uncommon in practice, and it is important to deal sensibly with them when they arise. A few months after [1] and [2] were published, I discovered a corollary of the fundamental theorem, which led to a simpler derivation and deeper understanding of the subresultant PRS algorithm. The new approach, which is presented in this paper, reveals the subresultant PRS algorithm as a simple generalization of the reduced PRS algorithm, and converts the conjecture that was mentioned in [1] and [2] into an elementary remark. Although I cannot assert with confidence that the subresultant PRS algorithm is optimal for any important class of problems, it is clearly the best of its kind and deserves to be thoroughly understood. Among its competitors are the modular GCD algorithm, which is shown in [2] to be superior if the given polynomials are sufficiently large and sufficiently dense, and the EZ-GCD algorithm of Moses and Yun [4], which is also modular, but has the advantage of benefiting from sparseness. On the other hand, if one desires only the resultant of the given polynomials, and their degrees are not too large, it may be advantageous to evaluate Sylvester's determinant, or the equivalent but lower-order Bezout's determinant, via expansion by minors. The merits of this approach are explored empirically by Ku and Adler [5], and their important but overstated conclusions are challenged by Collins [6]. In this paper the subresultant PRS algorithm is presented from the new viewpoint, and the outstanding conjecture is proved. The algorithm is then analyzed, and its practical importance is assessed.
File Format	PDF
DOI	10.1145/800205.806345
Language	English
Publisher	Association for Computing Machinery (ACM)
Publisher Date	1976-08-10
Publisher Place	New York
Access Restriction	Subscribed
Content Type	Text
Resource Type	Article

Sl.	Authority	Responsibilities	Communication Details
1	Ministry of Education (GoI), Department of Higher Education	Sanctioning Authority	https://www.education.gov.in/ict-initiatives
2	Indian Institute of Technology Kharagpur	Host Institute of the Project: The host institute of the project is responsible for providing infrastructure support and hosting the project	https://www.iitkgp.ac.in
3	National Digital Library of India Office, Indian Institute of Technology Kharagpur	The administrative and infrastructural headquarters of the project	Dr. B. Sutradhar bsutra@ndl.gov.in
4	Project PI / Joint PI	Principal Investigator and Joint Principal Investigators of the project	Dr. B. Sutradhar bsutra@ndl.gov.in Prof. Saswat Chakrabarti will be added soon
5	Website/Portal (Helpdesk)	Queries regarding NDLI and its services	support@ndl.gov.in
6	Contents and Copyright Issues	Queries related to content curation and copyright issues	content@ndl.gov.in
7	National Digital Library of India Club (NDLI Club)	Queries related to NDLI Club formation, support, user awareness program, seminar/symposium, collaboration, social media, promotion, and outreach	clubsupport@ndl.gov.in
8	Digital Preservation Centre (DPC)	Assistance with digitizing and archiving copyright-free printed books	dpc@ndl.gov.in
9	IDR Setup or Support	Queries related to establishment and support of Institutional Digital Repository (IDR) and IDR workshops	idr@ndl.gov.in

The Subresultant PRS Algorithm

By-prs and an Extension of Subresultant Theory

Various New Methods for Computing Subresultant Polynomial Remainder Sequences ( PRS ’ s )

The Gröbner basis algorithm and subresultant theory

A recursive algorithm for constructing generalized Sturm sequence

An analysis of the subresultant algorithm over an algebraic number field

A subresultant theory for Ore polynomials with applications (1998)

Abstract A Subresultant Theory for Ore Polynomials with Applications

Generalized subresultants and generalized subresultant algorithm (2006).

On the subresultant PRS algorithm

Similar Documents

The Subresultant PRS Algorithm

By-prs and an Extension of Subresultant Theory

Various New Methods for Computing Subresultant Polynomial Remainder Sequences ( PRS ’ s )

The Gröbner basis algorithm and subresultant theory

A recursive algorithm for constructing generalized Sturm sequence

An analysis of the subresultant algorithm over an algebraic number field

A subresultant theory for Ore polynomials with applications (1998)

Abstract A Subresultant Theory for Ore Polynomials with Applications

Generalized subresultants and generalized subresultant algorithm (2006).

On the subresultant PRS algorithm