Exact Computation in Sparse Linear Algebra

稀疏线性代数中的精确计算

• 批准号: 0098284
• 负责人: B. David Saunders
• 金额: $ 25.5万
• 依托单位: University of Delaware
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2001
• 资助国家: 美国
• 起止时间: 2001-08-15 至 2005-07-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=0098284&HistoricalAwards=false
• 关键词: Exact; Computation; Sparse; Linear; Algebra

ABSTRACTProposal #0098284Saunders, B. DavidUniversity of DelawareThis is a program of research in the area of exact solution of systems of linear equations and related problems. There will be an emphasis on Diophantine problems, wherein the input data (coefficients) are integers and the solutions sought must also have integer coefficients. There will also be an emphasis on parametric linear systems, wherein the input data contain symbolic parameters and the solutions must be expressed in terms of these parameters, including all special cases (ranges of values of the parameters for which the solutions have form different from the general case). New efficient algorithms are sought and high performance software is to be developed based on both new and previously described methods.The work will be largely carried out in the context of the LINBOX collaboration. LINBOX is a group of twelve researchers in three countries (USA, France, Canada) who are conducting research in the design of efficient algorithms for linear algebra, in their implementation in a software library, and in how to interface the library to widely-used scientific computing software. such as Maple and Mathematica.There are two basic approaches to sparse matrix problems, iterative and direct. Both approaches have been significantly developed by the numeric linear algebra community. Iterative methods involve finding recurrence relations in a series of vectors resulting from matrix-vector products. In LINBOX these have been called "black box" methods, and the adaptation of such methods to symbolic problems has been the emphasis to date. There has been substantial theoretical work in the past two decades in this area. The emphasis of LINBOX is to find and to demonstrate in software the variants and extensions and improvements to these methods which will work in practice. The here proposed research will continue in this direction but will also work to develop the direct methods for solution of sparse symbolic linear systems, again basing on prior work in numerical linear algebra.

sanders， B. david特拉华大学这是一个线性方程组精确解及相关问题领域的研究项目。将重点放在丢芬图问题上，其中输入数据（系数）是整数，所寻求的解也必须具有整数系数。还将强调参数线性系统，其中输入数据包含符号参数，解必须用这些参数表示，包括所有特殊情况（解的形式与一般情况不同的参数值范围）。新的高效算法正在寻求和高性能的软件是基于新的和以前描述的方法开发。这项工作将主要在LINBOX合作的背景下进行。LINBOX是一个由来自三个国家（美国、法国、加拿大）的12名研究人员组成的小组，他们正在进行线性代数有效算法的设计、在软件库中的实现以及如何将该库与广泛使用的科学计算软件接口的研究。比如Maple和Mathematica。求解稀疏矩阵问题有两种基本方法：迭代法和直接法。这两种方法都得到了数值线性代数界的显著发展。迭代方法涉及在矩阵-向量乘积的一系列向量中找到递归关系。在LINBOX中，这些方法被称为“黑盒”方法，将这些方法应用于符号问题一直是迄今为止的重点。在过去的二十年里，这一领域进行了大量的理论工作。LINBOX的重点是发现并在软件中演示这些方法的变体、扩展和改进，这些方法将在实践中起作用。这里提出的研究将继续朝这个方向发展，但也将致力于发展稀疏符号线性系统的直接解决方法，再次基于先前在数值线性代数方面的工作。