LAUSR

The problem of computing the roots of a particular sequence of sparse polynomials p n ( t ) is considered. Each instance p n ( t ) incorporates only the n + 1 monomial terms t , t 2 , t 4 , … , t 2 n $t,t^{2},t^{4},\ldots ,t^{2^{n}}$ associated with the binomial coefficients of order n and alternating signs. It is shown that p n ( 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 n ( t ) and p n + 1 ( t ) is used to show that they possess interlaced roots. Closed–form expressions for the Bernstein coefficients of p n ( 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 n ( 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.