并行演演算法

適用於并行計算機的數值演演算法。計算機傳統結構的顯著特徵是單指令流單數據流，即每一時刻按一條指令處理一個數據。通常的數值演演算法適於此類計算機，可稱串列演演算法。20世紀60年代開始發展含大量處理機的并行計算機，它分單指令流多數據流與多指令流多數據流兩類，每一時刻分別按一條或多條指令處理多個數據。并行計算機的出現促使了適應其并行這個特點的并行演演算法的發展。

并行演演算法依賴一個簡單事實：獨立的計算可同時執行。所謂獨立計算是指其每個結果元只出現一次的計算。例如中7個乘法不能同時執行，但可分成三個獨立計算組：

第一組

第二組

第三組如每組的運算并行執行，計算，只須三步（乘法），其步驟可用圖中的雙杈計算樹來表示。推廣此例，得到由滿足結合律的任一運算“。”形成的表達式：的最優并行演演算法，稱為結合扇入演演算法。此演演算法提供了建立并行演演算法的一種普遍原則：反覆將每一計算分裂成具有同等複雜性的兩個獨立部份，稱為遞推倍增法。

研究表明，大量數值問題可獲得有效的并行演演算法。一個演演算法是否有效主要看加速

及所需的處理機個數的大小。并行演演算法的複雜性正是通過參數和來描述的。向量運算具有內在并行性（包含大量獨立計算），因而首先是在數值線代數方面，并行演演算法特別富有成果。

串列演演算法與并行演演算法存在固有差別。有效串列演演算法一般不能直接變換為并行演演算法，而且兩者在數值性態方面（例如數值穩定性及迭代演演算法的收斂速度）可以彼此大不相同。