Abstracts of the Posters

The symbolic Moore-Penrose inverse with provisos
Robert M. Corless and David J. Jeffrey
Department of Applied Mathematics University of Western Ontario London, Canada N6A 5B7 {rmc,djj}@apmaths.uwo.ca

Some standard computations with continuous families of matrices may produce discontinuous results. These discontinuities cause specialization problems in computer algebra. In this poster we reconsider the reduced row echelon form, LU factoring, and the Moore-Penrose inverse. For example, computing the Moore-Penrose inverse of


by Tihonov regularization in Maple gives


which is correct unless a=1, when the Moore-Penrose inverse is


The problem is discontinuity: lim_{a->1} A(a)^\dagger \ne lim_{a->1} A(a). We here show how to deal effectively with this discontinuity using provisos.

FoxBox: A System for Manipulating Symbolic Objects in Black Box Representation
Angel Díaz & Erich Kaltofen Angel Diaz Research Staff Member IBM T.J. Watson Research Center Yorktown Heights, NY 10598 diaz@watson.ibm.com and kaltofen@eos.ncsu.edu

The black box representation of a symbolic object is a function that takes as input a value for each variable and then produces the value of that object. In this presentation we introduce FOXBOX, a software package that puts in practice the black box representation of symbolic objects and provides algorithms for performing the symbolic calculus with such representations. Improved versions of the algorithms found in Kaltofen and Trager [J. Symbolic Comput., vol.9, nr.3, p.311 (1990)] and Kaltofen and Díaz [ISSAC '95, p.232] are discussed. Also we describe an interpolation scheme based on a Zippel's [J. Symbolic Comput., vol.9, nr.3, p.375 (1990)] algorithm that optimizes the number of required black box evaluations. The design of FOXBOX is intended to demonstrate how plug-in software components can be employed for generally used symbolic systems. Our implementation incorporates data types parameterized by arbitrary coefficient domains and generic algorithms. By providing a mechanism for interfacing to general purpose computer algebra systems, we broaden FOXBOX's applicability. Furthermore we provide a distribution mechanism that allows for parallel and distributed execution of FOXBOX programs independent of the underlying parallel architecture. Finally, we present the results of several challenge problems which exercise our FOXBOX library and represent the first symbolic solutions of such problems.

Symbolic Computation of Conserved Densities for Nonlinear Evolution and Differential-Difference Equations
Ünal Göktas and Willy Hereman Department of Mathematical and Computer Sciences Colorado School of Mines Golden, CO 80401-1887, USA {ugoktas,whereman}@mines.edu
Two programs in Mathematica are presented. The first program automatically computes conserved densities and associated fluxes for systems of nonlinear evolution equations. The second program is the extension of the first one towards systems of nonlinear differential-difference equations. For systems with parameters, the programs can be used to determine the conditions on these parameters so that a sequence of conservation laws will exist. Mainly, these programs can be used as tools to test integrability of a given system.

Software Demonstration: CONDENS.M: Symbolic Computation of Conservation Laws for Systems of Nonlinear Evolution Equations with Mathematica DIFFDENS.M: Symbolic Computation of Conservation Laws for Systems of Nonlinear Differential-Difference Equations with Mathematica The programs condens.m and diffdens.m will be demonstrated with several examples, including equations with parameters, for which the compatibility conditions for the existence of conserved densities will be computed.

Exact solution of a nonlinear equation by approximate arithmetic
David J. Jeffrey, D. E. G. Hare, and Robert M. Corless Department of Applied Mathematics University of Western Ontario London, Canada N6A 5B7 {djj,rmc}@apmaths.uwo.ca

The equations xn bx = c and xy = yx are considered. First an explicit solution is found in terms of the Lambert W function. Simple rational cases of that solution imply simplification rules for the Lambert W function. A computational strategy using approximations for W is given for obtaining exactly these simplifications. Euler's parametric solution of xy = yx leads to further simplification rules for W and connects with a known parametric representation for W.

Polynomial Real Root Isolation using Approximate Arithmetic
Jeremy R. Johnson Drexel University Philadelphia, PA jjohnson@mcs.drexel.edu Werner Krandick Universität-GH Paderborn, Germany

A method is presented for isolating and refining the real roots of polynomials with either integer or real algebraic number coefficients. For root isolation the method uses a well-known algorithm that is based on Descartes' rule of signs. However, exact arithmetic is replaced as far as possible by validated double precision floating point arithmetic. The resulting method is powerful and very fast.

While we do not sacrifice correctness, our methods are not always able to locate all real roots. We perform experiments with polynomials from various classes to find the limits of applicability of our methods.

There are inputs for which the computing times of our validated methods are comparable to library quality numeric routines using unvalidated floating-point arithmetic. Of course, in general, numeric algorithms cannot be used when guaranteed results are needed.

We also compare the computing time of our algorithms to current implementations of exact methods. These implementations are from the computer algebra system Maple and from the SACLIB library of computer algebra programs. The main reason for considering Maple is to show that the SACLIB implementation is highly optimized. Compared to SACLIB we achieve speed-ups by factors of more than 1000.

Fraction-Free Algorithms for Linear and Polynomial Equations
George C. Nakos, Peter R. Turner Mathematics Department U.S. Naval Academy Annapolis, MD 21402-5002 {gcn,prt}@sma.usna.navy.mil Robert M. Williams Naval Air Warfare Center Aircraft Division Patuxent River Naval Air Station, MD bobw@nadc.nadc.navy.mil
This report extends the ideas behind Bareiss's fraction-free Gauss elimination algorithm in a number of directions. First, in the realm of linear algebra, algorithms are presented for fraction-free LU ``factorization'' of a matrix and for fraction-free algorithms for both forward and back substitution. These algorithms are valid not just for integer computation but also for any matrix system where the entries are taken from a unique factorization domain such as a polynomial ring. The second part of the paper applies a fraction-free formulation to resultant algorithms for solving systems of polynomial equations. In particular, the use of fraction-free polynomial arithmetic and triangularization algorithm in computing the Dixon resultant of a polynomial system is discussed in detail.

A Computational Algebraic Approach to Signal Processing
Hyungju Alan Park Department of Mathematical Sciences Oakland University Rochester, MI 48309 park@oakland.edu
Many problems in digital signal processing can be converted to algebraic problems over polynomial and Laurent polynomial rings, and can be solved using the existing methods of algebraic and symbolic computation. For example, the difficult problem of determining the perfect reconstructibility of a multidimensional multi-input-multi-output (MIMO) system cab be solved by determining the unimodularity of a Laurent polynomial matrix.

This presentation aims to establish this connection in a systematic manner, and makes use of it to solve a few important problems arising in multidimensional signal processing.

T. Kalker, H. Park, and M. Vetterli.
Groebner Bases Techniques in Multidimensional Multirate Systems.
Proceedings of ICASSP 95, 1995.

A. Logar and B. Sturmfels.
Algorithms for the Quillen-Suslin theorem.
Journal of Algebra, 145:231-239, 1992.

H. Park and C. Woodburn.
An algorithmic proof of Suslin's stability theorem for polynomial rings.
Journal of Algebra, 178:277-298, 1995.

M. Vetterli and J. Kovacevic.
Wavelets and Subband Coding.
Prentice Hall Signal Processing Series. Prentice Hall, 1995.

The Schmidt-Kolchin Conjecture
Georg Reinhart Department of Mathematics Wellesley College Wellesley, MA 02181 greinhart@wellesley.edu

A differential polynomial P(y,z) is called differentially homogeneous (DHDP) if P(ty,tz)=tdP(y,z), where t,y,z are differential indeterminates. These polynomials have a natural vector space structure over the base field. The following results concerning this vector space will be presented: (a) a DHDP of degree d can have order at most d-1. (b) The dimension of the vector space is 2d in the case for small d (conjectured by E. Kolchin) (c) there are efficient algorithms and shortcuts to compute bases. These algorithms have important applications for computer algebra systems.

Extended Chow Forms and their Applications
J. Maurice Rojas rojas@math.mit.edu

We illustrate two refinements of the classical Chow form: Twisted Chow forms and Semi-mixed Chow forms. The first extension leads to a variant of the u-resultant with far fewer degeneracy problems, thus giving a more reliable resultant-based method to solve large systems of polynomial equations. The latter refinement gives a unification of the Dixon resultant, the Bezoutian, and the sparse resultant. We present various examples of these new Chow forms. In particular, we detail an image recognition problem which can be greatly simplified with an effective theory of semi-mixed Chow forms.

By making use of the toric (or sparse) resultant, we thus obtain an alternative (and more combinatorial) approach to Gröbner-basis methods for polynomial system solving. Of particular interest are the new, more intrinsic complexity bounds one obtains.

Parameter <> Indeterminate
B. David Saunders Department of Computer and Information Sciences University of Delaware Newark, DE 19716 saunders@louie.udel.edu

Computer algebra systems provide computation over specific domains, most often assuming that variables in expressions are independent indeterminates, sometimes providing mechanisms to arrange that computation is with respect to user pre-specified dependencies among the variables.

Computer algebra users often want another thing altogether, "Under what conditions do my equations have interesting special-case solutions?" That is, the underlying domain of computation is not given. It is a large part of the question.

We illustrate this conflict between what is provided by systems and what users want (and often expect) with an interesting real life example. We then offer a way to solve parametric systems in one very specific case: one parameter systems of linear equations. While straightforward to solve, this case illustrates some of the design issues that arise when dealing with parameters and is a base case of the important (multi)parametric linear systems problem.

IBM techexplorer: Scientific and Technical Electronic Publishing
Robert S. Sutor, Samuel S. Dooley, Angel L. Diaz Angel Diaz Research Staff Member IBM T.J. Watson Research Center Yorktown Heights, NY 10598 {diaz,sutor,dooley}@watson.ibm.com

The IBM techexplorer HyperMedia Browser(tm) is an application supporting interactive publishing of scientific and technical documents. It is available in several versions, including a stand-alone application and a Netscape Navigator plug-in. In this demo we will provide an overview of techexplorer

and detail how it can be used to deliver mathematical articles, books, and course materials via the World Wide Web. We will also discuss our use of the OpenMath standard to allow documents to contain semantically attributed math objects for reuse in computer algebra systems and other mathematical software. Future directions regarding our plans for opening the architecture of techexplorer and how that relates to TeX, SGML, and Java will be presented.

Constructing Large Permutation Representations of Matrix Groups
Michael Weller Institute for Experimental Mathematics University of Essen D-45326 Essen, Germany eowmob@exp-math.uni-essen.de
In group theory a certain kind of examples for groups, the 26 sporadic simple groups comes up.

Those which one is able to represent on a computer at all are usually given by matrices which generate the group as a subgroup of a general linear group over a finite field. Unfortunately many algorithms require the knowledge of a permutation representation and a base and strong generating set.

Because of the size of the groups and the permutations involved several special techniques and the use of parallel computers are required.

An implementation of these for Janko's group J4 of order 86,775,571,046,077,562,880 and its permutation representation of degree 173,067,389 is presented.

Gene Cooperman