An Algorithm for the Computation of Linear Forms

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 ₛ n) operations. It is demonstrated that the algorithm is sharp for some problems.