請問關於帶狀矩陣求解

Question

由於最近使用到一些大的矩陣運算, 而矩陣剛好有帶狀性質, 也就是對角中心附近有值, 其他位置均為零, 原本矩陣為 A * B = C , 其中 A 為 n*n 方陣, B 是 n*1 矩陣, C 也是 n*1 矩陣, 已知 A, C, 要求 B, 本來這種問題直接用高斯法就可以找到答案, 但因有需求, n 的數值要約 160000, 如此一來, 160000*160000 的陣列根本無法宣告, 如果考慮將矩陣變成帶狀矩陣, 則應該可以將矩陣變成 160000*800, 這樣宣告應該就還可以, 可是帶狀矩陣的填值及運算我忘記了, 手上也沒有書, 網路上也沒找到比較詳細的算法介紹, 請問有人知道這要怎麼算嗎?

Answer 1

上帶寬 = q (即 A(i,j) = 0 當 j > i+q)下帶寬 = p (即 A(i,j) = 0 當 i > j+p)總帶寬 = p+q+1可令 A.band 為 (p+q+1)×n 的陣列，並將 A(i,j) 存入 A.band(i-j+q+1,j).這樣一來，可將演算法裡的 A(i,j) 改成 A.band(i-j+q+1,j)
例：LU 分解+forward substitution+back substitutionLU 分解:for k = 1 to n-1for i = k+1 to min(k+p,n)A(i,k) = A(i,k)/A(k,k)endfor j = k+1 to min(k+q,n)for i = k+1 to min(k+p,n)A(i,j) = A(i,j) - A(i,k)A(k,j)endendendforward substitution:for i = 2 to nC(i) = C(i) - A(i,i-p:i-1)C(i-p:i-1)endback substitution:C(n) = C(n)/A(n,n)for i = n-1 down to 1
C(i) = (C(i) - A(i,i+1:i+q)C(i+1:i+q))/A(i,i)

end