Publication Details
Title: Approximation of Complex Numbers by Cyclotomic Integers
Author: M. A. Shokrollahi and V. Stemann
Group: ICSI Technical Reports
Date: August 1996
PDF: ftp://ftp.icsi.berkeley.edu/pub/techreports/1996/tr-96-033.pdf
Overview:
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. Keywords: Discrete Fourier tranform, cyclotomic fields, cyclotomic units, complex approximation, integer linear programming
Bibliographic Information:
ICSI Technical Report TR-96-033
Bibliographic Reference:
M. A. Shokrollahi and V. Stemann. Approximation of Complex Numbers by Cyclotomic Integers. ICSI Technical Report TR-96-033, August 1996
Author: M. A. Shokrollahi and V. Stemann
Group: ICSI Technical Reports
Date: August 1996
PDF: ftp://ftp.icsi.berkeley.edu/pub/techreports/1996/tr-96-033.pdf
Overview:
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. Keywords: Discrete Fourier tranform, cyclotomic fields, cyclotomic units, complex approximation, integer linear programming
Bibliographic Information:
ICSI Technical Report TR-96-033
Bibliographic Reference:
M. A. Shokrollahi and V. Stemann. Approximation of Complex Numbers by Cyclotomic Integers. ICSI Technical Report TR-96-033, August 1996