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.
Published Web Locationhttps://doi.org/10.1007/s11075-019-00745-3
© 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.