✦ LIBER ✦

Practical Algorithms for Polycyclic Matrix Groups

✍ Scribed by Gretchen Ostheimer

Publisher: Elsevier Science
Year: 1999
Tongue: English
Weight: 322 KB
Volume: 28
Category: Article
ISSN: 0747-7171
DOI: 10.1006/jsco.1999.0287

No coin nor oath required. For personal study only.

✦ Synopsis

In this paper we describe a suite of new algorithms for studying polycyclic matrix groups-algorithms for testing membership and for uncovering the polycyclic structure of the group. We also describe an algorithm for deciding whether or not a group is solvable, which, in the important context of subgroups of GL(n, Z), is equivalent to deciding whether or not a group is polycyclic. Algorithms were developed in Baumslag et al. (1991. The algorithmic theory of polycyclic-by-finite groups. J. Algebra, 142, 118-149) for all of these problems, but the algorithms in this paper represent a first step toward finding practical algorithms: experiments show that they are fast enough to be useful in studying some reasonably complex examples using current technology.

📜 SIMILAR VOLUMES

A Practical Algorithm for Finding Matrix

A Practical Algorithm for Finding Matrix Representations for Polycyclic Groups

✍ Eddie H. Lo; Gretchen Ostheimer 📂 Article 📅 1999 🏛 Elsevier Science 🌐 English ⚖ 365 KB

In this paper we describe a new algorithm for constructing a representation by integer matrices for a polycyclic group given by a finite presentation. This is a first step toward finding a practical algorithm for this problem. We used our algorithm to construct representations for various polycyclic

A practical algorithm for faster matrix

A practical algorithm for faster matrix multiplication

✍ Igor Kaporin 📂 Article 📅 1999 🏛 John Wiley and Sons 🌐 English ⚖ 69 KB

The purpose of this paper is to present an algorithm for matrix multiplication based on a formula discovered by Pan [7]. For matrices of order up to 10 000, the nearly optimum tuning of the algorithm results in a rather clear non-recursive one-or two-level structure with the operation count comparab

Algorithms for Matrix Groups and the Tit

Algorithms for Matrix Groups and the Tits Alternative

✍ Robert Beals 📂 Article 📅 1999 🏛 Elsevier Science 🌐 English ⚖ 224 KB

Tits has shown that a finitely generated matrix group either contains a nonabelian free group or has a solvable subgroup of finite index. We give a polynomial time algorithm for deciding which of these two conditions holds for a given finitely generated matrix group over an algebraic number field. N

Selecting Base Points for the Schreier-S

Selecting Base Points for the Schreier-Sims Algorithm for Matrix Groups

✍ Scott H. Murray; E.A. O'Brien 📂 Article 📅 1995 🏛 Elsevier Science 🌐 English ⚖ 282 KB

Preconditioners for distance matrix algo

Preconditioners for distance matrix algorithms

✍ W. Glunt; T. L. Hayden; M. Raydan 📂 Article 📅 1994 🏛 John Wiley and Sons 🌐 English ⚖ 410 KB

A recent gradient algorithm in nonlinear optimization uses a novel idea that avoids line searches. This so-called spectral gradient algorithm works well when the spectrum of the Hessian of the function to be minimized has a small range or is clustered. In this article, we find a general precondition

Testing Matrix Groups for Primitivity

✍ Derek F. Holt; C.R. Leedham-Green; E.A. O'Brien; Sarah Rees 📂 Article 📅 1996 🏛 Elsevier Science 🌐 English ⚖ 206 KB

We describe an algorithm which seeks to decide whether or not a matrix group defined over a finite field acts to preserve blocks of imprimitivity and, if so, to find a block system. Implementations of the algorithm are publicly available.