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

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

  • Author(s): Farouki, Rida T
  • Strom, Jeffrey A
  • et al.

© 2019, Springer Science+Business Media, LLC, part of Springer Nature. The problem of computing the roots of a particular sequence of sparse polynomials pn(t) is considered. Each instance pn(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 pn(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 pn(t) and pn+ 1(t) is used to show that they possess interlaced roots. Closed–form expressions for the Bernstein coefficients of pn(t) on [0,1] are derived and employed to compute the roots in double–precision arithmetic. Despite the severe variation of the graph of pn(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.

Many UC-authored scholarly publications are freely available on this site because of the UC Academic Senate's Open Access Policy. Let us know how this access is important for you.

Main Content
Current View