Work is just beginning on a variety of approaches which use computational logic to support these systems in practical applications. Things are not always easy: for example systems such as Maple implement continuous mathematics by means of differential algebra, which is not the same as classical continuous mathematics.
In this tutorial we
Dr Steve Linton
University of St Andrews
sal@dcs.st-and.ac.uk
Slides:
The GAP system for computational discrete mathematics
Professor Ursula Martin
University of St Andrews
um@dcs.st-and.ac.uk
Slides:
Computational mathematics: opportunities and challenges for computational
logic
Professor James Davenport
University of Bath
jhd@maths.bath.ac.uk
What is numerical computation?
Numerical methods have formed the standard, and almost universal, approach
to computation for continuous mathematics for almost fifty years, and fast
effective implementations lie at the heart of COTS systems such as MATLAB
(1 million users) and NAG (500K users), and stand alone systems such as
those used in weather forecasting or intensive graphics. Numerical systems
do continuous mathematics "numerically": that is to say the query "integrate
tan(a*x) between 0 and b" only returns a value for specific floating point
values of a and b, when it will return either a floating point value, or
"undefined". The theory of numerical analysis deals with the accuracy of
the answer. Numerical systems nearly always return a result, and with sufficient
user expertise are accepted as doing so accurately, with established protocols
for testing and error analysis. They also accommodate other inputs, for
example from sensors or measuring devices, or other outputs, for example
to visualisation systems: and they scale to systems as complex as weather
forecasting or large engineering designs. However they can be wrong, or
unacceptably slow, particularly in the hands of inexpert users, and do
not offer scope for reasoning about the systems they model.
The NAG library comprises high quality implementations of large numbers of basic routines, in versions optimized for many different architectures and languages, which users then incorporate into their own systems.
By contrast MATLAB provides a stand-alone environment for numerical analysis augmented by additional packages for specialised applications like DSP or control systems. MATLAB/Simulink provides a graphical user interface: users can build up Simulink blocks representing a dynamical system from primitive blocks representing mathematical functions, matrix transforms and so on: these blocks are composed using a Data Flow semantics and can be used to drive simulations. MATLAB/Stateflow adds FSMs, so an automotive component like a braking system can be modelled by representing the control system as a state machine, and the environment as the differential equations governing the engine, road surface and so on. Running simulations of the model predicts performance: it is then used to synthesise code for the component.
Background :
Textbook:
Numerical
Analysis: An Introduction, W. Gautschi, Purdue University, Indiana,
Birkhauser Boston.
Sample Systems: MATLAB, NAG Library
Survey of current challenges: L N Trefethen, Predictions for scientific
computing 50 years from now, Mathematics Today, 2000
What is symbolic computation?
Computer algebra systems like Maple (1 million users) incorporate a
wide variety of symbolic techniques, for example for factoring polynomials
or computing Grobner bases, and increasingly some numerical elements also.
They can in principle do continuous mathematics "symbolically", that is
to say the query "integrate tan(a*x) between 0 and b" should return a symbolic
answer in a and b and side conditions on a and b to indicate where it is
valid. They also provide a mathematical programming environment and
facilities such as graphics and document generation. They have enjoyed
some outstanding successes: for example 't Hooft and Veltman received the
1999 Nobel Prize in Physics, Veltman for using computer algebra to verify
't Hooft's results on quantum field theory.
In practice current computer algebra systems are not reliable for continuous mathematics: they do not handle side conditions well, their semantics is not that of standard continuous mathematics, and even if these problems were solved many continuous mathematics problems do not have a symbolic solution. Even the right way to implement complex numbers in computer algebra systems is still a subject of active research. Specialised techniques for different aspects of computational continuous mathematics include quantifier elimination, real algebraic geometry, particularly algorithms based on semi-algebraic sets, and exact real arithmetic: all are the subject of active research rather than, as yet, components of main-stream applications.
Background :
Textbook:
Computer
Algebra Systems: A Practical Guide, M.J. Wester (Ed.), J. Wiley.
Sample Systems: Maple, Mathematica
Survey of current challenges: E Kaltofen, Challenges of symbolic computation,
my favorite open problems, J Symbolic Comp 29 (2000) 891-919
Computation in research mathematics
In many of the major achievements of 20th century mathematics,
such as the recent proof of Fermat's theorem or the developments in topology
and geometry, the role of computation has been slight. Computation
has transformed biology, chemistry, neuroscience and physics: without
computational mathematics we would have no Mars pathfinder robot, no human
genome project and no CAT scans. We might still have the proof
of Fermat's theorem.
Yet in some areas computation has been significant: computational investigations of groups lie behind some of the most significant discoveries in algebra this century. On the one hand are stand-alone programs to solve particular problems such as the construction of individual sporadic simple groups; on the other the development of packages such as GAP which incorporate libraries as well as containing configurable implementations of many of the standard algorithms which have been developed over the years. Computation may be used not only to construct and solve problems in a specific group of interest, but also to suggest results, conjectures and lines of argument which may then be proved more generally.
Background :
Textbook:
Sample Systems: GAP, Weyl
Survey of current challenges: Ursula Martin, Computers, reasoning and
mathematical practice, in Proceedings of the 1997 NATO ASI Summer School
Summer School on Logic and Computation, Springer Verlag 1999 .ps