Stochastically-inspired methods for solving systems of linear equations

求解线性方程组的随机方法

• 批准号: 0634802
• 负责人: Sachin Sapatnekar
• 金额: $ 25万
• 依托单位: University of Minnesota-Twin Cities
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2006
• 资助国家: 美国
• 起止时间: 2006-09-15 至 2011-08-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=0634802&HistoricalAwards=false
• 关键词: Stochastically; inspired; methods; solving; systems

Many applications in engineering and science require the solution of systems oflinear algebraic equations, or partial differential equations (PDEs) that are solved using linear equation solvers. Conventionally, these have been solved using direct and iterative approaches. This project explores a third way, through the use of stochastic methods for the solution of linear equations, using random walks on a Markov chain. Although the basis for these methods has been well known for many years, they have not found widespread application as they were not considered scalable or accurate. This project develops novel techniques that show how these methods can be viable alternatives to conventional methods, and researches this approach to expand its theoretical and practical horizons, including hybridizations with existing methods.The application of these techniques on a variety of practical engineering applications is under investigation, ranging from problems that require the solution of linear equations or PDEs, to a set of domain-specific applications, drawn from a range of fields. This effort has parallel research thrusts, of which one develops new theory to enhance the accuracy and efficiency of these methods, while the other applies the theory to specific applications, using problem-specific knowledge for further performance gains. The research is expected to have a broader impact beyond its immediate scope through its applicability to a range of problems in science and engineering, and its potential for wider application to fields beyond those considered in this project. In addition, the educational aspects of this work involve includingfacets of this work in the classroom, and in helping train the next generation of scientists and engineers.

在工程和科学中的许多应用都需要求解线性代数方程组，或者使用线性方程求解器求解偏微分方程（PDE）。 传统上，这些已经解决了使用直接和迭代的方法。 这个项目探索了第三种方法，通过使用随机方法来解决线性方程组，使用马尔可夫链上的随机行走。虽然这些方法的基础已经众所周知多年，但它们没有得到广泛的应用，因为它们被认为不具有可扩展性或准确性。 本项目开发新技术，展示这些方法如何成为传统方法的可行替代品，并研究这种方法，以扩大其理论和实践视野，包括与现有方法的杂交。这些技术在各种实际工程应用中的应用正在调查中，范围从需要解决线性方程或PDE的问题，到一组特定于领域的应用程序，从一系列领域中提取。 这项工作有平行的研究重点，其中一个开发新的理论，以提高这些方法的准确性和效率，而另一个将理论应用于具体的应用，使用特定于问题的知识，以进一步提高性能。 预计这项研究将通过其对科学和工程中一系列问题的适用性，以及其在本项目所考虑的领域之外的更广泛应用的潜力，产生超出其直接范围的更广泛影响。 此外，这项工作的教育方面涉及将这项工作的各个方面纳入课堂，并帮助培训下一代科学家和工程师。