ERCIM News No.25 - April 1996 - SZTAKI

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.

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).

Lajos Rónyai - MTA SZTAKI

Tel: +36-1-2698-270

E-mail: lajos@nyest.ilab.sztaki.hu

return to the contents page