The minimum root separation of a polynomial
Authors:
George E. Collins and Ellis Horowitz
Journal:
Math. Comp. 28 (1974), 589597
MSC:
Primary 12D10; Secondary 30A08
MathSciNet review:
0345940
Fulltext PDF Free Access
Abstract 
References 
Similar Articles 
Additional Information
Abstract: The minimum root separation of a complex polynomial A is defined as the minimum of the distances between distinct roots of A. For polynomials with Gaussian integer coefficients and no multiple roots, three lower bounds are derived for the root separation. In each case, the bound is a function of the degree n of A and the sum d of the absolute values of the coefficients of A. The notion of a seminorm for a commutative ring is defined, and it is shown how any seminorm can be extended to polynomial rings and matrix rings, obtaining a very general analogue of Hadamard's determinant theorem.
 [1]
G. E. Collins, "Computing time analyses for some arithmetic and algebraic algorithms," Proc. 1968 Summer Institute on Symbolic Mathematical Computation, IBM Corp., Cambridge, Mass., 1961, pp. 197231.
 [2]
G. E. Collins, "The calculation of multivariate polynomial resultants," J. Assoc. Comput. Mach., v. 18, 1971, pp. 515532. MR 45 #7970. MR 0298921 (45:7970)
 [3]
L. E. Heindel, "Integer arithmetic algorithms for polynomial real zero determination," J. Assoc. Comput. Mach., v. 18, 1971, pp. 533548. MR 45 #9480. MR 0300434 (45:9480)
 [4]
D. E. Knuth, The Art of Computer Programming. Vol. 2: Seminumerical Algorithms, AddisonWesley, Reading, Mass., 1969. MR 44 #3531. MR 0286318 (44:3531)
 [5]
R. G. K. Loos, "A constructive approach to algebraic numbers," Math. of Comp. (submitted.)
 [6]
H. Minc & M. Marcus, Introduction to Linear Algebra, Macmillan, New York, 1965. MR 32 #5660. MR 0188221 (32:5660)
 [7]
M. T. McClellan, "The exact solution of systems of linear equations with polynomial coefficients," J. Assoc. Comput. Mach., v. 20, 1973, pp. 563588. MR 0347068 (49:11788)
 [8]
D. R. Musser, Algorithms for Polynomial Factorization, Univ. of Wisconsin Comp. Sci. Dept. Technical Report No. 134 (Ph.D Thesis), Sept. 1971, 174 pp.
 [9]
J. R. Pinkert, Algebraic Algorithms for Computing the Complex Zeros of Gaussian Polynomials, Univ. of Wisconsin Comp. Sci. Dept. Ph.D. Thesis, May 1973, Technical Report No. 188, July 1973.
 [10]
B. L. van der Waerden, Moderne Algebra. Vol. I, Springer, Berlin, 1930; English transl., Ungar, New York, 1949. MR 10, 587.
 [1]
 G. E. Collins, "Computing time analyses for some arithmetic and algebraic algorithms," Proc. 1968 Summer Institute on Symbolic Mathematical Computation, IBM Corp., Cambridge, Mass., 1961, pp. 197231.
 [2]
 G. E. Collins, "The calculation of multivariate polynomial resultants," J. Assoc. Comput. Mach., v. 18, 1971, pp. 515532. MR 45 #7970. MR 0298921 (45:7970)
 [3]
 L. E. Heindel, "Integer arithmetic algorithms for polynomial real zero determination," J. Assoc. Comput. Mach., v. 18, 1971, pp. 533548. MR 45 #9480. MR 0300434 (45:9480)
 [4]
 D. E. Knuth, The Art of Computer Programming. Vol. 2: Seminumerical Algorithms, AddisonWesley, Reading, Mass., 1969. MR 44 #3531. MR 0286318 (44:3531)
 [5]
 R. G. K. Loos, "A constructive approach to algebraic numbers," Math. of Comp. (submitted.)
 [6]
 H. Minc & M. Marcus, Introduction to Linear Algebra, Macmillan, New York, 1965. MR 32 #5660. MR 0188221 (32:5660)
 [7]
 M. T. McClellan, "The exact solution of systems of linear equations with polynomial coefficients," J. Assoc. Comput. Mach., v. 20, 1973, pp. 563588. MR 0347068 (49:11788)
 [8]
 D. R. Musser, Algorithms for Polynomial Factorization, Univ. of Wisconsin Comp. Sci. Dept. Technical Report No. 134 (Ph.D Thesis), Sept. 1971, 174 pp.
 [9]
 J. R. Pinkert, Algebraic Algorithms for Computing the Complex Zeros of Gaussian Polynomials, Univ. of Wisconsin Comp. Sci. Dept. Ph.D. Thesis, May 1973, Technical Report No. 188, July 1973.
 [10]
 B. L. van der Waerden, Moderne Algebra. Vol. I, Springer, Berlin, 1930; English transl., Ungar, New York, 1949. MR 10, 587.
Similar Articles
Retrieve articles in Mathematics of Computation
with MSC:
12D10,
30A08
Retrieve articles in all journals
with MSC:
12D10,
30A08
Additional Information
DOI:
http://dx.doi.org/10.1090/S0025571819740345940X
PII:
S 00255718(1974)0345940X
Keywords:
Polynomial zeros,
root separation,
Hadamard's theorem,
seminorms
Article copyright:
© Copyright 1974
American Mathematical Society
