{"id":{"repo_id":"uiuc","oai_identifier":"oai:www.ideals.illinois.edu:2142/44116"},"canonical_url":"https://search.dev.ndltd.org/etd/uiuc/oai:www.ideals.illinois.edu:2142/44116","repository":{"repo_id":"uiuc","name":"University of Illinois - Urbana-Champaign","base_url":"https://www.ideals.illinois.edu/oai-pmh"},"display":{"title":"A faster FFT in the Mid-West","abstract":"FFT implementations today generally fall into two categories: Library generators (such as FFTW and Spiral) and specialized FFTs (such as prime95). Specialized FFTs have the obvious limitation of being specialized. However they are hand-tuned and generally offer superior performance. Library generators are generic and easier to port. But their performance is generally suboptimal. We describe in this paper an FFT library that was built while paying special attention to locality. The library achieves significantly better performance than FFTW, for long vectors. Unlike FFTW or Spiral, the recursive decomposition of the FFT is not created by a library generator; it is created by macro expansion that has a few selectable parameters. This provides an interface that can be more easily modified by users.","abstract_html":"FFT implementations today generally fall into two categories: Library generators (such as FFTW and Spiral) and specialized FFTs (such as prime95). Specialized FFTs have the obvious limitation of being specialized. However they are hand-tuned and generally offer superior performance. Library generators are generic and easier to port. But their performance is generally suboptimal. We describe in this paper an FFT library that was built while paying special attention to locality. The library achieves significantly better performance than FFTW, for long vectors. Unlike FFTW or Spiral, the recursive decomposition of the FFT is not created by a library generator; it is created by macro expansion that has a few selectable parameters. This provides an interface that can be more easily modified by users.","abstract_has_math":false,"creators":["Yee, Alexander"],"institution":"University of Illinois at Urbana-Champaign","degree_name":"M.S.","degree_level":"Thesis","degree_discipline":"Computer Science","degree_department":null,"school":null,"contributors":["Snir, Marc"],"advisors":[],"committee_chairs":[],"committee_members":[],"year":2013,"date_issued":"2013-05-24T21:51:10Z","date_published":"2013-05-24T21:51:10Z","updated_at":"2026-07-22T22:25:33Z","subjects":["High Performance Computing (HPC)","Fast Fourier Transform (FFT)","Libraries"],"languages":["en"],"rights":["Copyright 2013 Alexander Yee"],"rights_urls":[],"identifier_entries":[]},"links":{"outbound_url":"http://hdl.handle.net/2142/44116","outbound_label":"Handle","outbound_source":"dc:identifier"},"metadata_groups":[{"id":"people","label":"People","entries":[{"key":"dc:contributor","label":"Contributor","values":["Snir, Marc"]},{"key":"dc:creator","label":"Author","values":["Yee, Alexander"]}]},{"id":"academic_context","label":"Academic Context","entries":[{"key":"dc:date","label":"Dc Date","values":["2013-05-24T21:51:10Z","2013-05"]},{"key":"dc:type","label":"Dc Type","values":["text"]},{"key":"thesis:degree_discipline","label":"Discipline","values":["Computer Science"]},{"key":"thesis:degree_level","label":"Degree Level","values":["Thesis"]},{"key":"thesis:degree_name","label":"Degree Name","values":["M.S."]},{"key":"thesis:institution_name","label":"Thesis Institution Name","values":["University of Illinois at Urbana-Champaign"]}]},{"id":"subjects_keywords","label":"Subjects and Keywords","entries":[{"key":"dc:subject","label":"Dc Subject","values":["High Performance Computing (HPC)","Fast Fourier Transform (FFT)","Libraries"]}]},{"id":"language_rights","label":"Language and Rights","entries":[{"key":"dc:language","label":"Dc Language","values":["en"]},{"key":"dc:rights","label":"Dc Rights","values":["Copyright 2013 Alexander Yee"]}]},{"id":"identifiers","label":"Identifiers","entries":[{"key":"dc:identifier","label":"Identifier","values":["http://hdl.handle.net/2142/44116"]}]},{"id":"additional","label":"Additional Metadata","entries":[{"key":"dc:description","label":"Description","values":["FFT implementations today generally fall into two categories: Library generators (such as FFTW and Spiral) and specialized FFTs (such as prime95). Specialized FFTs have the obvious limitation of being specialized. However they are hand-tuned and generally offer superior performance. Library generators are generic and easier to port. But their performance is generally suboptimal. We describe in this paper an FFT library that was built while paying special attention to locality. The library achieves significantly better performance than FFTW, for long vectors. Unlike FFTW or Spiral, the recursive decomposition of the FFT is not created by a library generator; it is created by macro expansion that has a few selectable parameters. This provides an interface that can be more easily modified by users.","Item withdrawn by Mark Zulauf (zulauf@illinois.edu) on 2013-04-24T19:30:15Z Item was in collections: University of Illinois Theses & Dissertations (ID: 1) No. of bitstreams: 1 Yee_Alexander.pdf: 951677 bytes, checksum: 206eb86400149b08d2ae40c5ea5db7ad (MD5)","Made available in DSpace on 2013-05-24T21:51:10Z (GMT). No. of bitstreams: 2 Alexander_Yee.pdf: 938096 bytes, checksum: 3a94b263ad02a41be511e18d1471ef1a (MD5) license.txt: 4060 bytes, checksum: 2e803365be76ce53b2bea07aa1b71dfb (MD5)"]},{"key":"dc:title","label":"Title","values":["A faster FFT in the Mid-West"]}]}],"canonical_facts":{"dc:contributor":["Snir, Marc"],"dc:creator":["Yee, Alexander"],"dc:date":["2013-05-24T21:51:10Z","2013-05"],"dc:description":["FFT implementations today generally fall into two categories: Library generators (such as FFTW and Spiral) and specialized FFTs (such as prime95). Specialized FFTs have the obvious limitation of being specialized. However they are hand-tuned and generally offer superior performance. Library generators are generic and easier to port. But their performance is generally suboptimal. We describe in this paper an FFT library that was built while paying special attention to locality. The library achieves significantly better performance than FFTW, for long vectors. Unlike FFTW or Spiral, the recursive decomposition of the FFT is not created by a library generator; it is created by macro expansion that has a few selectable parameters. This provides an interface that can be more easily modified by users.","Item withdrawn by Mark Zulauf (zulauf@illinois.edu) on 2013-04-24T19:30:15Z Item was in collections: University of Illinois Theses & Dissertations (ID: 1) No. of bitstreams: 1 Yee_Alexander.pdf: 951677 bytes, checksum: 206eb86400149b08d2ae40c5ea5db7ad (MD5)","Made available in DSpace on 2013-05-24T21:51:10Z (GMT). No. of bitstreams: 2 Alexander_Yee.pdf: 938096 bytes, checksum: 3a94b263ad02a41be511e18d1471ef1a (MD5) license.txt: 4060 bytes, checksum: 2e803365be76ce53b2bea07aa1b71dfb (MD5)"],"dc:identifier":["http://hdl.handle.net/2142/44116"],"dc:language":["en"],"dc:rights":["Copyright 2013 Alexander Yee"],"dc:subject":["High Performance Computing (HPC)","Fast Fourier Transform (FFT)","Libraries"],"dc:title":["A faster FFT in the Mid-West"],"dc:type":["text"],"thesis:degree_discipline":["Computer Science"],"thesis:degree_level":["Thesis"],"thesis:degree_name":["M.S."],"thesis:institution_name":["University of Illinois at Urbana-Champaign"]},"updated_at":"2026-07-22T22:25:33Z"}