Integer Linear Algebra, LinBox Applications and Extensions

整数线性代数、LinBox 应用和扩展

• 批准号: 0515197
• 负责人: B. David Saunders
• 金额: --
• 依托单位: University of Delaware
• 依托单位国家: 美国
• 项目类别: Continuing Grant
• 财政年份: 2005
• 资助国家: 美国
• 起止时间: 2005-08-01 至 2010-01-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=0515197&HistoricalAwards=false
• 关键词: Integer; Linear; Algebra; LinBox; Applications

PROPOSAL: 0515197INSTITUTION: U of DelawarePI: Saunders, B. DavidTITLE: Integer Linear Algebra, LinBox Applications and ExtensionsABSTRACTLinear algebra lies at the core of computation and modeling in science and engineering. Almost all of it done today is numeric linear algebra in which the data are measured values and the results are approximate and subject to varying amounts of error. This research addresses EXACT linear algebra computation in which the data are whole numbers and the results are exact - computed without any error whatsoever. In the past two decades, significant new methods have arisen and are enabling solution of large problem instances where it could not before be dreamed of. We will broaden the range of problem types solvable by the new methods, devise further new and better methods, and, above all, provide high performance implemented programs in a software library, LinBox, readily available to all. We will study (1) extremely sparse systems, with just a few nonzero entries per matrix row, (2) symmetric matrices: matrix signature and positive definiteness, (3) hybrid algorithms for Smith normal forms. The corresponding application areas are image rendering, study of symmetry (Lie groups), and combinatorics. The intellectual heart of the activity lies in two major areas. First, we probe the performance limits for sparse linear algebra, striving to create algorithms which are optimal, in the sense of computational complexity. This requires both novel algorithms and new insights concerning the absolute limits to speedup. Secondly, we program the library in a way providing for both high performance and genericity with respect to the many variants of matrix representation and underlying arithmetic. Thus the implementation elegantly solves the vexing problem of software reusability. The fact that our programs are not simply academic demonstrations is very important, giving the work much broader impact. Mathematicians and scientists may now use LinBox and for the first time perform exact linear algebra computations on large problems.

提案：0515197机构：特拉华大学PI：Saunders，B. David标题：线性代数，LinBox应用程序和扩展摘要线性代数是科学和工程中计算和建模的核心。今天所做的几乎都是数值线性代数，其中的数据是测量值，结果是近似的，并受到不同数量的误差。该研究解决了精确线性代数计算，其中数据是整数，结果是精确计算，没有任何错误。在过去的二十年中，出现了重要的新方法，并使解决大型问题的情况下，它以前不能梦想。我们将扩大新方法可解决的问题类型的范围，进一步设计新的和更好的方法，最重要的是，在软件库LinBox中提供高性能的实现程序，随时提供给所有人。我们将研究（1）极稀疏系统，每个矩阵行只有几个非零元素，（2）对称矩阵：矩阵签名和正定性，（3）Smith标准形的混合算法。相应的应用领域是图像渲染，对称性研究（李群）和组合学。活动的智力核心在于两个主要领域。首先，我们探索稀疏线性代数的性能限制，努力创建算法是最佳的，在这个意义上的计算复杂性。这需要新的算法和新的见解有关的绝对限制加速。其次，我们的程序库的方式提供了高性能和通用性方面的矩阵表示和底层算法的许多变种。因此，该实现优雅地解决了软件可重用性的烦恼问题。我们的项目不仅仅是学术演示，这一事实非常重要，使这项工作产生了更广泛的影响。数学家和科学家现在可以使用LinBox，并首次在大型问题上执行精确的线性代数计算。