Approximation of Complex Numbers by Cyclotomic Integers
Title | Approximation of Complex Numbers by Cyclotomic Integers |
Publication Type | Technical Report |
Year of Publication | 1996 |
Authors | M. Shokrollahi, A., & Stemann V. |
Other Numbers | 1043 |
Keywords | complex approximation, cyclotomic fields, cyclotomic units, Discrete Fourier tranform, integer linear programming |
Abstract | We present a new method of approximating complex numbers by cyclotomic integers in Z[e^{2?i/2^n}] whose coefficients with respect to the basis given by powers of e^{2?i/2^n} are bounded in absolute value by a given integer M. It has been suggested by Cozzens and Finkelstein that such approximations reduce the dynamic range requirements of the discrete Fourier transform. For fixed n our algorithm gives approximations with an error of O(1/M^{2^{n-2}-1}). This proves a heuristic formula of Cozzens and Finkelstein. We will also prove a matching lower bound for the worst case error of any approximation algorithm and hence show that our algorithm is essentially optimal. Further, we derive a slightly different and more efficient algorithm for approximation by 16th roots of unity. The basic ingredients of our algorithm are the explicit Galois theory of cyclotomic fields as well as cyclotomic units. We use a deep number theoretic property of these units related to the class number of the field. Various examples and running times for this case and that of approximation by 32nd roots of unity are included. Finally, we derive the algebraic and analytic foundations for the generalization of our results to arbitrary algebraic number fields. |
URL | http://www.icsi.berkeley.edu/ftp/global/pub/techreports/1996/tr-96-033.pdf |
Bibliographic Notes | ICSI Technical Report TR-96-033 |
Abbreviated Authors | M. A. Shokrollahi and V. Stemann |
ICSI Publication Type | Technical Report |