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.


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

return to the contents page