An Algorithm for the Computation of Linear Forms
Author:
- John E. SavageJSJohn E. Savage
- 1 June 1974
- journal article
- Published by Society for Industrial & Applied Mathematics (SIAM) in SIAM Journal on Computing
- Vol. 3 (2) , 150-158
Abstract
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.
Keywords
This publication has 4 references indexed in Scilit:
- Computational Work and Time on Finite MachinesJournal of the ACM, 1972
- Bounds on the evaluation time for rational polynomial1971
- On the number of multiplications necessary to compute certain functionsCommunications on Pure and Applied Mathematics, 1970
- Gaussian elimination is not optimalNumerische Mathematik, 1969