Integer Linear Algebra, LinBox Applications and Extensions

University Of Delaware, Newark DE

Investigators

Abstract

PROPOSAL: 0515197 INSTITUTION: U of Delaware PI: Saunders, B. David TITLE: Integer Linear Algebra, LinBox Applications and Extensions ABSTRACT Linear 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.