Citation
Abstract
Others have shown that the conventional method for computing m X n matrixvector products and Horner's rule for evaluating polynomials are optimal when matrix and vector elements as well as polynomial coefficients and polynomial variables are indeterminate. In this article, the calculation of matrix-vector products and the evaluation of polynomials are treated when the matrix elements and polynomial coefficients are known and drawn from a set of size s. It is shown that the algorithms which are optimal for indeterminate matrix entries and polynomial coefficients are nonoptimal when s is fixed and the entries and coefficients are known. Good algorithms for this case are given and tight bounds are derived on the combinational complexity of the most complex matrix-vector function and the most complex polynomial evaluation function. These are operations used in the Deep Space Station computers for decoding telemetry and interpolating ephemerides for antenna pointing and programmed oscillators.
Details
- Volume
- XIII
- Published
- February 15, 1973
- Pages
- 194–202
- File Size
- 857.6 KB