平行演算法

作者:(晝伏夜出的研究生) 資料來源:http://bbs.ee.ntu.edu.tw/boards/Math/4/2/7.html Q: 一般計算兩個 n*n matrix 的乘積的 complexity 為 O(n^3),這邊假設有兩個Boolean Matrix, 其entry為0 or 1,為 random 產生, 機率各為 1/2 . 試求一演算法, 使得其相乘之 complexity 為 O(n^2) 1. 利用平行演算法 2. 假設在 boolean addition 1 1 = 1 0 = 0 1 = 1 下計算和 (所得積矩陣仍為 Boolean matrix) 此題乍看之下, 似乎不可行, 好似要求計算向量內積在常數完成, 但... 此題可直接問成要 A x 在 O(n) 內完成, 因 B.i 和 B.j 的值不會互相影響 AB. where x 為 0,1 n-column vector. Ax = A.1 x1 A.2 x2 ... A.n xn. where A.i 為 A 的第 i 行. xi 為 x 第 i 元素. 從 A.1 x1 開始算起, 若 x1 = 0 則不須計算, 需時 1 否則 計算 A.1 x1 需時 n 從假設 entry 出現 1 的機率為 1/2 可見約有 一半 的 entry 為 1, 一半為 0 若某 entry 已為 1, 則不需計算後往. 於是 只須挑出 entry 為 0 者之列往後計算. 挑出需時 n. (最好挑出循序存剩下的列, 另加一欄存 列 index) 現在計算 A.2 x2, A.2 x2 只算那些計算 Ax 過程中仍為 0 的列. 照理 只需計算 n/2 個,..... 依照獨利分配特性, 算完後仍為 0 者將僅剩 n/2/2 = n/4,... 如此算到 A.n xn 或是 entry 已全為 1 所以 假設 xi 皆為 1 , worst case, 則 計算 A.1 x1 , A.2 x2 , A.3 x3 , A.4 x4 , ... 耗時 2( n n/2 n/4 n/8 ...) <= 4 n ^ 包含挑出 entry 為 0 的費時 故 計算 Ax 需時 O(n). 網路志工聯盟----Visita網站http://www.vista.org.tw ---[ 發問前請先找找舊文章 ]---