吉文氏旋轉的韻律演算法與應用

Abstract

摘要 基於吉文氏旋轉,我們提供一個韻律演算法把任意nxn矩陣B化簡成上三角的型式.這計算的模式包含n個線性韻律陣列組成一個二維的陣列,每一個陣列包含有(n-i+1)PEs(處理單元)，第i個線性陣列的目的是讓矩陣B第i行的第(i+1)個到第n個元素為0，對1<=i<=n。每一個PE結構簡單，且相同型式的PEs都在同一時間內執行相同的指令。它非常適合利用VLSI 去完成。 對兩個任意nxn矩陣A、B，我們應用我們的韻律演算法把Ax=^Bx轉換到A'x=^B'x,其中B'是上三角型.

Abstract Based on Givens rotation, we present a systolic algorithm to reduce an arbitrary matrix B into upper triangular form .The computational model consists of n linear systolic arrays. Every array consists of (n-i+1) PEs (process elements). These n linear systolic arrays are connected to form a two-dimensional array . For 1<=i<=n,the i-th linear array is responsible to eliminate the j-th element of the i-th column of the matrix B for i+1<=j<=n. Since the structure of every PE is simple and the same type PE executes the identical instructions in the same time, it is very suitable for VLSI implementation . For two arbitrary nxn matrix A , B , we apply our systolic algorithm to transform Ax=^Bx to A'x=^B'x ,where B' is upper triangular form.