{"id":9,"date":"2005-03-17T17:24:42","date_gmt":"2005-03-17T17:24:42","guid":{"rendered":"http:\/\/ahay.org\/blog\/?p=9"},"modified":"2015-08-04T23:51:53","modified_gmt":"2015-08-04T23:51:53","slug":"fft","status":"publish","type":"post","link":"https:\/\/ahay.org\/blog\/2005\/03\/17\/fft\/","title":{"rendered":"FFT"},"content":{"rendered":"

How is FFT implemented in RSF? What FFT conventions are used? What choices of array size are efficient?<\/b>
\nThere are two main fft programs: sffft1<\/a> and sffft3<\/a>.
\nsffft1<\/u> takes real input and transforms it to complex by applying real-to-complex FFT on the first axis. It does the inverse transform when inv=y<\/b>.
\nsffft3<\/u> applies complex-to-complex FFT on the specified axis<\/b>. The sign of the transform is determined by the sign<\/b> parameter.
\nsfcosft<\/a> applies real-to-real cosine transform.
\nHere is an example 2-D FFT figure from Jon Claerbout<\/a> reproduced in bei\/ft1\/plane4<\/a>:
\n\"\"
\nRSF utilizes the KISS FFT<\/a> library for applying FFT. There are some faster open-source software solutions available, most notably FFTW<\/a> but KISS (Keep It Simple, Stupid) FFT is attractive because of it simplicity and compactness. The library can handle an arbitrary data size. However, some sizes (prime factor powers) are more efficient than others. For example, here are CPU times for running sffft1<\/b> on files with different sizes:<\/p>\n\n\n\n\n\n
n1<\/th>\nCPU time<\/th>\n<\/tr>\n
999,999 <\/td>\n 0.01 s<\/td>\n<\/tr>\n
1,000,000 <\/td>\n 0.01 s<\/td>\n<\/tr>\n
1,000,001 <\/td>\n 1.64 s<\/td>\n<\/tr>\n<\/table>\n

Update:<\/b> sffft1<\/u>, sffft3<\/u>, and some other programs that use FFT, now pad the data to the nearest optimal size.<\/font><\/p>\n","protected":false},"excerpt":{"rendered":"

How is FFT implemented in RSF? What FFT conventions are used? What choices of array size are efficient? There are two main fft programs: sffft1 and sffft3. sffft1 takes real input and transforms it to complex by applying real-to-complex FFT on the first axis. It does the inverse transform when inv=y. sffft3 applies complex-to-complex FFT […]<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"_import_markdown_pro_load_document_selector":0,"_import_markdown_pro_submit_text_textarea":"","activitypub_content_warning":"","activitypub_content_visibility":"local","activitypub_max_image_attachments":4,"activitypub_interaction_policy_quote":"","footnotes":""},"categories":[4],"tags":[],"class_list":["post-9","post","type-post","status-publish","format-standard","hentry","category-faq"],"_links":{"self":[{"href":"https:\/\/ahay.org\/blog\/wp-json\/wp\/v2\/posts\/9","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/ahay.org\/blog\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/ahay.org\/blog\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/ahay.org\/blog\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/ahay.org\/blog\/wp-json\/wp\/v2\/comments?post=9"}],"version-history":[{"count":1,"href":"https:\/\/ahay.org\/blog\/wp-json\/wp\/v2\/posts\/9\/revisions"}],"predecessor-version":[{"id":906,"href":"https:\/\/ahay.org\/blog\/wp-json\/wp\/v2\/posts\/9\/revisions\/906"}],"wp:attachment":[{"href":"https:\/\/ahay.org\/blog\/wp-json\/wp\/v2\/media?parent=9"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/ahay.org\/blog\/wp-json\/wp\/v2\/categories?post=9"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/ahay.org\/blog\/wp-json\/wp\/v2\/tags?post=9"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}