Tag Archives: 分治

Strassen 演算法──分治矩陣乘法

本文的閱讀等級:初級 令 和 為 階矩陣。矩陣乘積 需要使用多少乘法與加法運算?根據矩陣乘法定義, 。 因為 階矩陣 有 個元,計算每一元需要 個乘法和 個加法,故知 階矩陣乘積共使用了 個乘法和 個加法。長久以來,人們普遍認為矩陣乘法定義本身即為最佳的算法,這個迷思直到1969年才被施特拉森[1](Volker Strassen) 打破──他提出了一個更快捷的分治 (divide-and-conquer) 矩陣乘法,稱為 Strassen 演算法。 Advertisements

Posted in 線性代數專欄, 數值線性代數 | Tagged , , | 5 Comments

快速傅立葉轉換

本文的閱讀等級:中級 給定一序列 ,離散傅立葉轉換的計算公式為 (見“離散傅立葉轉換”) 。 令 。離散傅立葉轉換可表示成矩陣形式 ,如下: , 其中 階 稱為傅立葉矩陣。若採用一般矩陣乘法運算,離散傅立葉轉換的計算複雜度為 。公元1965年,美國學者庫利 (James Cooley) 與圖基 (John Tukey) 提出了一個複雜度為 的演算法,稱為快速傅立葉轉換 (fast Fourier transform,簡稱 FFT),後來人們發現原來高斯 (Carl Friedrich Gauss) 早在1805年就已經提出同樣的演算法。本文採用別於傳統訊號處理的推導方法[1],我們先檢視傅立葉矩陣 擁有的特殊性質,然後運用分塊矩陣技巧推導 Cooley-Tukey 演算法。除了本文介紹的 Cooley-Tukey 演算法,還有其他多種形式的快速傅立葉轉換演算法,請讀者參閱維基百科[2]。

Posted in 線性代數專欄, 應用之道 | Tagged , , , , | 6 Comments