Anzeige
Erschienen in:
04.06.2019 | Original Paper
Computing the roots of sparse high–degree polynomials that arise from the study of random simplicial complexes
Erschienen in: Numerical Algorithms | Ausgabe 4/2020
EinloggenAktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
Abstract
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,t^{2},t^{4},\ldots ,t^{2^{n}}\) 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.