Uniform Bounds for a Class of Algebraic Mappings
David Y. Y. Yun · SIAM Journal on Computing · 1979
The computation of residues with respect to a set of given moduli and the Chinese remainder algorithm can be considered a pair of general invertible algebraic mappings. This class of algebraic mappings include the more familiar mappings of evaluation and interpolation as well as forward and inverse fast Fourier transform (FFT). The utility and significance of these mappings are fully recognized in such fields as symbolic and algebraic computation and signal processing. The importance of the more general pair of mappings as algebraic techniques is just beginning to be appreciated. All these mapping techniques are presented in this paper from a unifying perspective. Then, a uniform upper bound for these pairs of invertible mappings in terms of computational cost or time is established. Hopefully, this effort alleviates concerns of applicability of these mapping techniques and encourages their use in numerous other potential application areas.