Skip to main content
eScholarship
Open Access Publications from the University of California

UC Davis

UC Davis Previously Published Works bannerUC Davis

Computing the roots of sparse high–degree polynomials that arise from the study of random simplicial complexes

  • Author(s): Farouki, RT
  • Strom, JA
  • et al.
Abstract

The problem of computing the roots of a particular sequence of sparse polynomials p (t) is considered. Each instance p (t) incorporates only the n + 1 monomial terms t,t2,t4,…,t2n associated with the binomial coefficients of order n and alternating signs. It is shown that p (t) has (in addition to the obvious roots t = 0 and 1) precisely n − 1 simple roots on the interval (0,1) with no roots greater than 1, and a recursion relating p (t) and p (t) is used to show that they possess interlaced roots. Closed–form expressions for the Bernstein coefficients of p (t) on [0,1] are derived and employed to compute the roots in double–precision arithmetic. Despite the severe variation of the graph of p (t), and tight clustering of roots near t = 1, it is shown that for n ≤ 10, the roots on (0,1) are remarkably well–conditioned and can be computed to high accuracy using both the power and Bernstein forms. n n n n n+ 1 n n

Many UC-authored scholarly publications are freely available on this site because of the UC's open access policies. Let us know how this access is important for you.

Main Content
Current View