《求解鞍點問題的混合預處理方法》是依託上海交通大學，由王增琦擔任項目負責人的面上項目。
基本介紹
- 中文名：求解鞍點問題的混合預處理方法
- 項目類別：面上項目
- 項目負責人：王增琦
- 依託單位：上海交通大學
項目摘要,結題摘要,
項目摘要
約束型預處理方法是求解鞍點問題的新型預處理方法。通過約束分解和變數代換，鞍點問題被轉化為對稱正定問題，繼而通過具有短遞推格式的疊代算法進行求解，如約束預處理共軛梯度法，約束預處理Chebyshev算法等。這類算法通常具有疊代步數與離散尺度的無關性。該項目擬設計更加準確並且快速近似Schur補矩陣的方法，減少疊代步數的同時，減少單步預處理運行時間。我們採取代數多重格線的思想，依據剛度矩陣與Schur補矩陣在不同格線層上的關係和適當的多項式逼近函式，遞歸得到Schur補矩陣的隱式近似。這一過程將被設計成快速算法加以實現，並通過與約束預處理算法框架相耦合，得到求解鞍點問題的混合預處理方法。新型預處理方法有望在保持疊代步數“最優”性的同時，縮短預處理過程的計算時間、節約存儲空間，達到運行效率上的最優。我們將建立混合預處理的收斂性理論，討論約束預處理矩陣的條件數並給出疊代誤差界的估計。
結題摘要
鞍點問題具有廣泛的套用背景，是科學與工程計算的核心問題之一。該線性系統通常規模巨大，其係數矩陣具有非對稱、不定且壞條件等特點，如何高效數值求解此類問題是本學科及相關領域的熱點問題。本項目結合模型問題的物理背景，利用矩陣分解、矩陣分裂技術等代數學方法，得到了若干高效、穩定的疊代算法和預處理技術，並從理論上闡述了算法的可靠性。主要成果如下：1. 求解帶偏微分方程約束最佳化問題和復對稱線性系統的切比雪夫疊代算法。該算法每疊代步在Krylov子空間上找到與真實解誤差範數最小的疊代解，具有三項遞推格式且無需選取參數，收斂速度與問題參數和格線離散尺度無關且不低於0.42，與其他Krylov子空間類方法相比，由於不含內積運算，更適合於大規模並行計算。2. 求解耦合的分數階復薛丁格方程的快速疊代算法。此類偏微分方程經有限差分離散後，得到類Toeplitz結構的線性系統，快速Fourier變換無法直接套用。我們針對係數矩陣的結構特點，通過代數學手段，設計了收斂性與離散格線尺度無關的快速算法和預處理子，並通過理論分析，獲得了最優參數和最佳收斂速度。3.來源於渦流問題的非埃爾米特鞍點線性系統是電磁場計算中的公認難題。我們發展了求解該問題的分塊交替隱式格式，證明了更一般性問題的收斂性，從而得到了高效的疊代格式和預處理子。4. 對於多因子模型序列最小二乘問題，我們構造了修正約束預處理共軛梯度法，在保留已有結果的前提下，通過少量更新，達到股票市場實時求解的需求。團隊成員在項目執行過程中積極參加國內外學術活動，與國內外著名學者交流合作，主持和參加了多次國際會議和分組討論，多次獲邀作學術會議的邀請報告和大會報告。積極培養研究生，為本方向培養優秀的科研人才。
