Exact Computation in Sparse Linear Algebra

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

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.