Citation
Abstract
Many problems, including matrix-vector multiplication and polynomial evaluation, involve the computation of linear forms. An algorithm is presented here that offers a substantial improvement on the conventional algorithm for this problem when the coefficient set is small. In particular, this implies that every polynomial of degree n with at most s distinct coefficients can be realized with O (n/log,n) operations. It is demonstrated that the algorithm is sharp for some problems.
Details
- Volume
- XIX
- Published
- February 15, 1974
- Pages
- 82–88
- File Size
- 691.9 KB