《高複雜度矩陣計算問題及其套用》是依託清華大學，由白峰杉擔任項目負責人的面上項目。
基本介紹
- 中文名：高複雜度矩陣計算問題及其套用
- 依託單位：清華大學
- 項目負責人：白峰杉
- 項目類別：面上項目
- 負責人職稱：教授
- 申請代碼：A0502
- 研究期限：2009-01-01 至 2011-12-31
- 批准號：10871115
- 支持經費：28（萬元）
項目摘要
矩陣的積和式、積和多項式是重要的數學問題。它們在很多重要的研究領域有實質性的套用，典型的如統計物理中具有重要理論意義和科學價值的Ising 模型和Monomer-dimer 覆蓋模型。已經證明，這兩個模型的求解與稀疏矩陣積和式的計算有內在和本質的聯繫。與我們熟悉的矩陣計算問題不同，計算矩陣積和式、積和多項式是#P-難問題，也就是說按照複雜性理論的基本猜想，它們不存在多項式時間的算法，所以研究主要集中在近似算法。儘可能有效利用結構性質，是科學計算研究中的基本原則。因此無論確定性算法還是隨機算法，充分有效地利用結構特徵，針對具體問題背景設計更有效的算法，是本問題研究的基本原則。本項目針對幾類重要的物理和套用模型，借鑑傳統矩陣計算中的成功經驗，研究並利用矩陣的特殊結構性質，設計快速有效算法或比較大幅度地提高現有算法的效率，解決有實際意義的科學計算問題。
