快速傳立葉轉換向量化之研究

Abstract

傳立葉轉換在科學應用上是一種重要的分析工具，然而用一般循序性電腦(sequentia l computer) 執行傳立葉轉換卻是非常耗費時間。但是自從超級電腦(super compute r)問世以後，許多本來在一般電腦上無法處理的大型問題卻都得到了解決；而需具備 的條件就是對任何要在超級電腦上執行的程序而言，必需經過向量化之後，才能得到 快速的計算。因此在本論文中，我們就針對快速傳立葉轉換(FFT) 向量化的問題作為 研究。 文中快速傳立葉轉換演算法的推導將作簡單的介紹，接著我們也將對一些已存在的演 算法探討其特性及其在超級電腦上之製作。同時，我們針對資料長度是二的次方及因 數互質演算法(the prime factor algorithm)此兩種情況分別提出了我們自己的方法 。在資料長度是二的次方這種情形下，我們所提的方法除了可以使向量長度(vector length) 維持固定外，也可以使計算中的向量置放於連續之位置中；而對於因數互質 這種演算法，我們採用了Ruritanian索引對應，如此便可使整個演算法得以向量化。 而論文的最後，我們將這些演算法做了比較和分析。