Organizer:
Michael Wester (wester@math.unm.edu)
Abstract:
This session will consider both proposed and actual implementations of mathematical algorithms/heuristics in computer algebra systems.
Talks:
David J. Jeffrey
Department of Applied Mathematics
University of Western Ontario
London, Ontario, Canada
A new treatment is given of the elementary inverse functions. The new approach addresses the difference between the single-valued inverse function defined by computer systems and the multi-valued function which represents the multiple solutions of the defining equation. The approach takes an idea from complex analysis, namely the branch of an inverse function, and defines an index for each branch. The branch index then becomes an additional argument to the (new) function. A benefit of the new approach is that it helps with the general problem of correctly simplifying expressions containing inverse func tions, which has always been difficult both for humans and for computer algebra systems. The new approach also can be extended to non-elementary inverse functions such a s the Lambert W function, which otherwise cannot be handled. The difference between this approach and that of Riemann surfaces lies in the fa ct that Riemann surfaces distinguish between branches by dividing the domain of the function into sheets, whereas here the range of the function is indexed.
Adam Strzebonski
Wolfram Research, Inc.
Champaign, Illinois, USA
I will present a function for solving (possibly quantified) systems of equations and inequalities with domain restrictions on the variables. I will show some examples, discuss what we can and what we can't solve, and what algorithms we use.
The domains currently supported are Complexes, Reals, Algebraics, Rationals, Integers, and Primes. The classes of systems that we can solve in full generality include quantified systems of polynomial equations and inequations in complex variables (using Groebner bases), quantified systems of polynomial equations and inequalities with real or complex variables (using cylindrical algebraic decomposition), and systems of linear equations and inequalities in integer, real, or complex variables (using several algorithms depending on the domain of variables and on whether inequalities are present). With certain restrictions, we can also solve quantified real or complex systems containing algebraic functions. We can also solve several classes of transcendental systems, using various heuristics in order to reduce the problem to solving algebraic systems and simple transcendental equations and inequalities.
Polynomial systems in integer variables are not solvable in general (by Matiyasevich's solution of Hilbert's 10th problem), however we have implemented algorithms for solving certain classes of such systems, including systems of linear or univariate Diophantine equations and inequalities, binary quadratic Diophantine equations (with some inequality restrictions allowed), Thue equations, and systems for which the set of real solutions is bounded. We have also implemented several heursitics allowing to solve various other classes of Diophantine systems.
The function has been implemented as a part of a development version of Mathematica.
Igor Gachkov
Sweden
Igor.Gachkov@kau.se
Under almost 30 years long history of continuous efforts to describe optimal codes of small length as well as codes of fixed weight, theoretical research has been integrated in practice. As early as 1966 T. J. Wagner suggested an algorithm of finding quasi-perfect codes, which was implemented on computer. The results were summarised in a table of quasi-perfect codes correcting two errors [1]. Successful application of computers is proved by a whole list of codes obtained 1974 by A. A. Hashim and A. G. Constantinides [2]. A great development and improvement of computational techniques increased opportunities of finding new codes. 1987 a group of Finish mathematicians obtained a number of codes of constant weight [3]. The results of code searching's used to be put in tables of optimal codes. One of the examples of such work is [4]. At the same time, the research was not limited to just binary codes. There is a number of codes on field GF(3) and consequently tables of corresponding optimal codes [5]. However, there was no opportunity of checking and correcting the results, because there was no appropriate softwares, which in turn did not allow full application of the information about optimal codes. Under a period of time the author used MATHEMATICA in the theory of error correcting codes. The results presented simple descriptions of already known codes. The research showed some falsifications, for instance in [2] the code with parameters [71,58,5] has the parameters [71,58,4]. Weight polynomial of the codes were obtained as well. In other words, simple description of codes with constant weight (for example, A[23,8,8], A[23,8,7], A[22,8,8]) were found. The package enclosed by the author allows to check and correct most of the results in the tables in [4], [5]. This work was performed in co-operation with V. M. Sidelnikov and supported by Swedish Royal Science Academy.
References
Go to: ACA'2002 main page, Conferences on Applications of Computer Algebra main page.