冪等半環(huán)上矩陣正閉包的一個計算方法.pdf

1、求矩陣的逆、最短路徑問題和求二元關(guān)系的傳遞閉包是科學(xué)計算領(lǐng)域中的三個基本問題，它們在計算機科學(xué)與工程中有著重要的實踐意義。Gaussian消元法、Floyd算法和Warshall算法分別是這三個問題的經(jīng)典算法。1971年，Carré發(fā)現(xiàn)這三個算法在結(jié)構(gòu)上非常相似，并基于半環(huán)代數(shù)理論提出了它們的統(tǒng)一形式——Gauβ-Jordan消元法。1977年，Carré和Lehmann等抽象出求矩陣的逆、最短路徑問題、求二元關(guān)系的傳遞閉包和正則語言的

2、有理表示問題的本質(zhì)特征，正式提出了代數(shù)距離問題。
　　代數(shù)距離問題可以轉(zhuǎn)化為計算半環(huán)上的矩陣的正閉包（即其所有正數(shù)次冪的和）的問題。本文的主要內(nèi)容是考慮一類矩陣的正閉包的計算方法。本文首先引入了矩陣圈非負的概念，接著給出了冪等半環(huán)上的矩陣圈非負的充分與必要條件以及計算圈非負矩陣的正閉包的方法，再依據(jù)該方法設(shè)計了時間復(fù)雜度為O(n3)的Plus_Closure_ of_ Matrix算法（其中n為矩陣的階數(shù)）。最后，本文還考察了Pl