循環最小平方法在各類超級電腦上的平行計算

Abstract

在訊號及影像處理的工程應用領域裡,循環 最小平方法是最常被用來處理這些動態環境下 的電子訊號的計算方法,但在實際的處理過程 中,將受制於記憶容量有限的濾波器.在此,我們 採用Sliding data window method的方法,探討以 Computationalcomplexity O(n/sup 2/)的計算方式去計算 並且修正Normal equation中的Cholesky factor來解決其 中的最小平方法方程式,而此法有良好的穩定 性.我們也將深入研究所謂的快速循環最小平 方法,此法在最近才被提出且受到廣泛的重視. 原因是其Lowcomputational cost,因為在訊號及影像 處理中所產生的Data matrix絕大多數具有Toeplitz matrix的結構,因此能夠發展出Computationalcomplexity為O(n)的計算方法,但此法的穩定性備受 爭議,而這也將是深入研究的重點.將全力研究 的另一個重點是一個剛有謅議的最新方法,此 法利用Preconditioned conjugate gradient slover及sliding window的方法,來解最小平方方程式,其 Computationalcomplexity為O(plogn),但能夠同時修正數 個Updating及Downdating的資料,因此具有最佳的訊 號追蹤能力.本研究計畫,是要深入探討循環最 小平方法的Mathematical aspects及Numerical aspects中 的Efficiency□Robustness□Stability等問題,而在近代 高速電腦上,如何利用平行計算的概念來發展 出最佳的計算軟體來解最小平方法的問題,便 是所要研究的重點.