ERCIM News No.25 - April 1996 - SZTAKI
Symbolic Computation
by Lajos Rónyai
Within the Informatics Laboratory at SZTAKI, a group works on problems
with strong links to theoretical computer science. One of these research
directions is Symbolic Computation in various algebraic structures.
With the widespread use of high performance electronic computers, several
new research directions have emerged on the common frontiers of mathematics
and computer science: the study of algorithmic aspects of mathe-matical
structures and theories. The results of these efforts find applications
in symbolic computational systems. Symbolic computational tools perform
exact (as opposed to approximate) calcu-lations with a rich variety of mathematical
objects. The importance of such systems is rapidly growing, as they are
being intensively used in engineering, scientific research and education.
Typical examples are such commercial products as Mathematica, MAPLE, and
Cayley; there are also a number of freeware systems available now (GAP,
Macaulay, etc.).
Our research group at the Informatics Laboratory, SZTAKI, has been active
in developing new algorithms for handling algebraic structures. Our principal
aim is to develop algorithms which have strong theoretical guarantees for
their performance.
Results and objectives
Associative algebras play a paramount role in both the theoretical and the
applied side of representation theory. We have established that over certain
tractable fields (algebraic number fields, finite fields) the basic structural
ingredients of associative algebras (radical, Wedderburn decomposition)
can be determined efficiently. Building on these results, we work on algorithms
which reveal the fine-structure of algebras. We intend to develop algorithms
with good running times, both in practical and in asymptotic sense.
From the perspective of practical applications, algorithmic questions related
to linear representations of finite groups look very promising. There are
several practically useful methods here. We think, nevertheless, that significant
further developments are possible on the basis of a rigorous complexity-analysis
of some fundamental subtasks. Little is known in this direction. Our aim
is to develop polynomial time methods, or to clarify the class of problems
tractable in this sense.
We have an ongoing cooperation with the Research Institute for the Applications
of Computer Algebra (RIACA), The Netherlands, and the University of Eindhoven.
The main objective of the joint work is to develop efficient algorithms
for computations in Lie algebras. Lie algebras emerge in many problems of
physics and analysis. For this reason several algorithms have been developed
and implemented all round the world. These are, however, scattered results,
mostly with only experimental observations about the performance of the
methods. We started to study Lie algebra-algorithms from the perspective
of polynomial time computations. Our long term goal is to develop and implement
(most likely in GAP) a coherent collection of symbolic algorithms for handling
Lie algebras over various ground fields. So far we have focused on Cartan
subalgebras, which are known to be extremely useful, both in theory and
practice, to explore the structure of a Lie algebra. We have succeeded in
turning some known existence arguments into efficient algorithms. Our methods
work over ground fields which support efficient symbolic arithmetic.
Support
Our research has been supported in part by the Hungarian National Fund for
Scientific Research (OTKA). Grant numbers are 2581, T016503. We also received
support from EC Cooperative Action IC 1000, Algorithms for Future Technologies
(ALTEC).
Please contact:
Lajos Rónyai - MTA SZTAKI
Tel: +36-1-2698-270
E-mail: lajos@nyest.ilab.sztaki.hu
return to the contents page