Abstract
用內點法解角型線性規劃時, 在每一次的迭代（iteration ）最費時間的是在解一個最小平方和問題（1.s.P.）, 可經由解其normal equation 來解此1.S.P.O 這也就等於在解一個正定的線性系統: Ax＝b....（*）, 而Cholesky分解常被用來解（* ）;即先將正定矩陣A cholesky分解: A＝LL,再解兩個三角系統: Ly＝b, L x=y, 其中L L ＝A, K =B （L ）,L L =C=（K K ＋K K ＋...K K ）因矩陣A 的結構特殊, 隱含有強烈的平行性, 因此我們提出了一個解（* ）的平行解法。因為我們所用的平行電腦NCUBE 是一種local-memory的機器, 所以我們在考慮每一個處理器（processor ）工作量的平均及減少資料傳輸的情況下, 將A,B 及b 放置在第map?i?個處理器將C 的第j 行, b 的第j 個元素放在第map?j?個處理器（假設使用的處理器有P 個，若｜i 則map?i?≡P,否則map?i?≡i（mod P）)。此平行演算法共分五個步聚:步驟1:每一個處理器對其所包含的A,B 做Cholesky分解, 不須要資料傳輸。步聚2:計算C,並利用ring communication傳輸資料。步聚3:利用Geist 和Heath 的平行演算法對C 做Cholesky分解。步聚4:解下三角系統L y =b（i＝1,...,N）,L y =b （K y ＋k y ＋…＋K y ）, 平行處理。步聚5:解上三角系統L X=y,L X＝y -K X （i＝1,...,N）,平行處理。我們也對此平行演算法做Time complexity 的分析, 發現我們所預測的現象與實際在NCUBE 平行電腦上執行的結果相吻合, 並且對近乎全部的我們所測試的中型及大型題目, 本法得到超過80％的效率（efficiency）。