An Algorithm for the Computation of Linear Forms
John E. Savage · SIAM Journal on Computing · 1974
Many problems, including matrix-vector multiplication and polynomial evaluation, involve the computation of linear forms. An algorithm is presented here which 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 _s n)$ operations. It is demonstrated that the algorithm is sharp for some problems.