Integer Linear Algebra, LinBox Applications and Extensions

毕业院校：特拉华大学pi: Saunders， B. DavidTITLE：整数线性代数，LinBox应用与扩展摘要线性代数是科学与工程中计算与建模的核心。今天所做的几乎所有工作都是数值线性代数，其中数据是测量值，结果是近似值，并受到不同程度的误差的影响。本研究解决了精确线性代数计算，其中数据是整数，结果是精确计算的，没有任何误差。在过去的二十年中，出现了重要的新方法，并使以前无法想象的大问题实例得以解决。我们将扩大新方法可解决的问题类型的范围，进一步设计新的和更好的方法，最重要的是，在一个软件库中提供高性能的实现程序，LinBox，随时可供所有人使用。我们将研究(1)极稀疏系统，每个矩阵行只有几个非零条目，(2)对称矩阵：矩阵签名和正定性，(3)Smith范式的混合算法。相应的应用领域是图像绘制、对称研究（李群）和组合学。这一活动的智力核心在于两个主要领域。首先，我们探讨了稀疏线性代数的性能限制，努力创建最优的算法，在计算复杂性的意义上。这需要新颖的算法和关于绝对加速限制的新见解。其次，我们以一种提供高性能和关于矩阵表示和底层算法的许多变体的通用方式对库进行编程。因此，该实现优雅地解决了令人烦恼的软件可重用性问题。我们的项目不只是简单的学术演示，这一点非常重要，这让我们的工作产生了更广泛的影响。数学家和科学家现在可以使用LinBox，并首次对大型问题进行精确的线性代数计算。

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.