基于马尔科夫链的线性系统求解问题的高效算法研究

项目名称： 基于马尔科夫链的线性系统求解问题的高效算法研究

项目编号： No.11501085

项目类型： 青年科学基金项目

立项/批准年度： 2016

项目学科： 数理科学和化学

项目作者： 文春

作者单位： 电子科技大学

项目金额： 18万元

中文摘要： 马尔科夫链由于其在生物学、管理学、金融经济学等众多领域的重大应用价值，受到国内外科研工作者的广泛关注。马尔科夫链的优势在于能用马尔科夫性描述和定义如随机漫步、网页排序、动态博弈等实际问题，并将这些问题归结为线性系统的求解问题进行研究。本项目正是以基于马尔科夫链的线性系统求解问题为研究对象，拟研究：(1) 改进和设计新的聚合技术，使辅助矩阵的构造更加合理，使各层系数矩阵的信息在粗网格与细网格的相互转化过程中不会丢失；(2) 提出与问题相适应的迭代法与预处理技术，使Krylov子空间等迭代法的应用得到发展与推广，进一步结合预处理技术，提高算法的性能，并做深入的理论分析和算法比较。

中文关键词： 线性系统；马尔科夫链；Krylov子空间方法；聚合技术；预处理技术

英文摘要： Markov chains are of great practical values in many fields such as biology, management, finance and economics, and therefore have received the wide attention from academic researchers at home and abroad. Its significant advantage is that it is able to use the Markov property to describe and define some practical problems such as random walk, PageRank and dynamic games, and thus they can be boiled down to study the numerical solutions of large-scale linear systems. In this project, we consider studying the numerical solutions of linear systems based on Markov chains and do research from the following aspects. (1) Improving and designing new aggregation techniques of multigrid methods, such that the construction of auxiliary matrices becomes more reasonable, and the information of coefficient matrices in each level cannot be lost when there is a mutual transformation between the coarse grid and the fine grid. (2) Proposing problem-related iterative methods and preconditioning techniques, such that the applications of iterative methods such as Krylov subspace methods can be developed and extended. Furthermore, combining with the use of preconditioning techniques such that the performance of algorithms cannot only be improved, but also the theoretical analysis and algorithmic comparisons can be done deeply.

英文关键词： linear system;Markov chain;Krylov subspace method;aggregation technique;preconditioning technique