{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
6#6
by Tihonov regularization in Maple gives7#7
which is correct unless a=1, when the Moore-Penrose inverse is8#8
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.
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.
{ugoktas,whereman}@mines.edu
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.
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.
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.
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
park@oakland.edu
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.
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.
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.
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.
{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.
eowmob@exp-math.uni-essen.de
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.