Challenges in Linear and Polynomial Algebra in Symbolic Computation Software (05w5039)

Objectives

Our workshop brings together algorithm designers and symbolic computation software builders from industry and academia. Our first objective is to review the status of the problems in the core area whose solution has the greatest impact in systems for symbolic mathematical computation. Our second objective is to design an approach that can achieve fast transfer of new mathematical algorithmic advances and new computer science concepts into the available software. We plan to invite for discussion those who make the new mathematics for the discipline and those who make the computer programs, in particular those who are engaged in both activities.

The software builder is faced with a mammoth task: the involved mathematical analysis in current algorithms can be highly sophisticated, using deep mathematical ideas. We give as an example the computation of sparse resultant formulas via exterior algebras and Chow forms. The underlying system for programming these algorithms is highly complex, combining techniques from reusable object-oriented design with entirely original data structures and standards. For example, the LinBox group, which is developing a symbolic linear algebra library in analogy to numerical libraries such as LinPack and MatLab, had to revise the basic generic archetype for a black box matrix three times, thus requiring a re-programming of the entire library. The revisions were necessitated when new concepts such as non-native garbage collection and BLAS (basic linear algebra subprograms) were introduced. In general, our experience is that efficient delivery of effective symbolic computation software requires ongoing and often original computer science research.

Clearly, given the proliferation of algorithmic ideas and the complexity of a modern computer environment, innovative design principles and linkages are required to bring the new breakthroughs quickly into the software that the users, including our own community, need.

This workshop provides a forum for focused discussion among the experts in industry and academia, and among algorithm designers and algorithm implementors. The goal is to understand a framework which will foster the evolution of new algorithmic ideas into usable software in a timely fashion. The pressures on being able to faster compute more are great. In some cases, the difference can be the disproval of a mathematical conjecture. In others, the yield can be a better FFT (fast Fourier transform) algorithm. If our workshop results in a commonly understood methodolgy for quickly moving new algorithmic ideas into mainstream software, all of the users will benefit for the gained efficiency.