TITLE: Groups of deficiency zero
AUTHORS: George Havas, M.F. Newman and E.A. O'Brien
CITATION: Geometric and Computational Perspectives on Infinite Groups, DIMACS Series in Discrete Mathematics and Theoretical Computer Science 25 (1996) 53-67
ABSTRACT: We make a systematic study of groups of deficiency zero, concentrating on groups of prime-power order. We prove that a number of p-groups have deficiency zero and give explicit balanced presentations for them. This significantly increases the number of such groups known. We describe a reasonably general computational approach which leads to these results. We also list some other finite groups of deficiency zero.
TITLE: A new algorithm and refined bounds for extended gcd computation
AUTHORS: David Ford and George Havas
CITATION: Algorithmic Number Theory, Lecture Notes in Computer Science 1122 (1996) 145-150
ABSTRACT: Extended gcd computation is interesting itself. It also plays a fundamental role in other calculations. We present a new algorithm for solving the extended gcd problem. This algorithm has a particularly simple description and is practical. It also provides refined bounds on the size of the multipliers obtained.
TITLE: Central factors of deficiency zero groups
AUTHORS: George Havas and Edmund F. Robertson
CITATION: Communications in Algebra 24 (1996) 3483-3487
ABSTRACT: We answer a question of some twenty years standing: are the central factors of nilpotent groups of deficiency zero 3-generated? We prove a negative answer by giving an explicit presentation for a 3-generator, 3-relator group of order 131072 and class 5 which has central factors which are 4-generated but not 3-generated. We outline the computational techniques which lead to this result.
TITLE: Empirical analysis of distributed depth-first search algorithms
AUTHORS: S.A.M. Makki and George Havas
CITATION: Proc. Eighth IASTED Internat. Conf. Parallel and Distributed Computing and Systems, Acta Press (1996) 292-296
ABSTRACT: We evaluate the practical performance of two improved distributed depth-first search algorithms applied to general and commonly used network structures. In particular we study the behavior of the algorithms in terms of a parameter which depends on the network topology and routing chosen. We deduce that performance is significantly enhanced for smaller networks of sizes which arise in practice. With increasing network size the extended version of the algorithm performs appreciably better than the basic algorithm. We present some unresolved questions about these algorithms.
TITLE: A family of perfect hashing methods
AUTHORS: Bohdan S. Majewski, Nicholas C. Wormald, George Havas and Zbigniew J. Czech
CITATION: Computer Journal 39 (1996) 547-554
ABSTRACT: Minimal perfect hash functions are used for memory efficient storage and fast retrieval of items from static sets. We present an infinite family of efficient and practical algorithms for generating order preserving minimal perfect hash functions. We show that almost all members of the family construct space and time optimal order preserving minimal perfect hash functions, and we identify the one with minimum constants. Members of the family generate a hash function in two steps. First a special kind of function into an r-graph is computed probabilistically. Then this function is refined deterministically to a minimal perfect hash function. We give strong theoretical evidence that the first step uses linear random time. The second step runs in linear deterministic time. The family not only has theoretical importance, but also offers the fastest known method for generating perfect hash functions.
TITLE: Distributed algorithms for depth-first search
AUTHORS: S.A.M. Makki and George Havas
CITATION: Information Processing Letters 60 (1996) 7-12
ABSTRACT: We present distributed algorithms for constructing a depth-first search tree for a communication network which are more efficient than previous methods. Our algorithms require 2|V|-2 messages and units of time in the worst case, where |V| is the number of sites in the network, and as little as |V| messages and time units in the best case. The actual number of messages and time units depends on the network topology and possibly on the routing chosen. We can interpret this to mean that the number of messages and time units is |V|(1+r) in the worst case, where 0<=r<1 and the value of r depends on the topology and the routing. In a best case for the simplest algorithm, for example when the underlying network has a ring topology, r=0 and our basic algorithm requires |V| messages and time units, regardless of routing. We extend the basic algorithm to achieve the same best case bound for other topologies. The worst case bound, which has r=1-2/|V|, applies if the network topology is a tree. The improvement over the best of previous algorithms is achieved by dynamic backtracking, with a minor increase in message length.
TITLE: Integer matrix diagonalization
AUTHORS: George Havas and Bohdan S. Majewski
CITATION: Journal of Symbolic Computation 24 (1997) 399-408 (open archive)
ABSTRACT: We consider algorithms for computing the Smith normal form of integer matrices. Various different strategies have been proposed, primarily trying to avoid the major obstacle that occurs in such computations -- explosive growth in size of intermediate entries. We present a new algorithm with excellent performance. We investigate the complexity of such computations, indicating a relationship with an NP-complete problem. On the other hand we prove that a substantial part of Smith normal form computation can be performed in an optimal way in polynomial time. Based on this we justify our new heuristics which perform well in practice. We present experimental evidence which shows our algorithm outperforming the previous methods.
TITLE: Practical parallel coset enumeration
AUTHORS: Gene Cooperman and George Havas
CITATION: Workshop on High Performance Computing and Gigabit Local Area Networks, Lecture Notes in Control and Information Sciences 226 (1997) 15-27
ABSTRACT: Coset enumeration is a most important procedure for investigating finitely presented groups. We present a practical parallel procedure for coset enumeration on shared memory processors. The shared memory architecture is particularly interesting because such parallel computation is both faster and cheaper. The lower cost comes when the program requires large amounts of memory, and additional CPU's allow us to lower the time that the expensive memory is being used. Rather than report on a suite of test cases, we take a single, typical case, and analyze the performance factors in-depth. The parallelization is achieved through a master-slave architecture. This results in an interesting phenomenon, whereby the CPU time is divided into a sequential and a parallel portion, and the parallel part demonstrates a speedup that is linear in the number of processors. We describe an early version for which only 40% of the program was parallelized, and we describe how this was modified to achieve 90% parallelization while using 15 slave processors and a master.
TITLE: Perfect hashing
AUTHORS: Zbigniew J. Czech, George Havas and Bohdan S. Majewski
CITATION: Theoretical Computer Science 182 (1997) 1-143 (open archive)
AWARD:The authors received awards for this paper from the Polish National Minister for Education
CONTENTS:
TITLE: An efficient method for constructing a distributed depth-first search tree
AUTHORS: S.A.M. Makki and George Havas
CITATION: PDPTA'97 (Proc. Internat. Conf. Parallel and Distributed Processing Techniques and Applications), CSREA Press (1997) 660-666
ABSTRACT: An efficient distributed depth-first search algorithm is presented. The algorithm in the worst case requires (1+r)(|V|-1) messages and (1+r)(|V|-1) units of time, where 0<=r<1 and |V| is the number of sites in the network. The value of r depends on the search path and the graph topology. In the best case when r=0, the algorithm requires only |V|-1 messages and time units. This new algorithm improves over the best of previous algorithms by using a stack-type structure which enables better dynamic backtracking. The improvement in worst case complexity is only minor. However it is much better in practice, manifested by significantly smaller values of r.
TITLE: On the worst-case complexity of integer Gaussian elimination
AUTHORS: Xin Gui Fang and George Havas
CITATION: ISSAC'97 (Proc. 1997 Internat. Sympos. on Symbolic and Algebraic Computation), ACM Press (1997) 28-31
ABSTRACT: Gaussian elimination is the basis for classical algorithms for computing canonical forms of integer matrices. Experimental results have shown that integer Gaussian elimination may lead to rapid growth of intermediate entries. On the other hand various polynomial time algorithms do exist for such computations, but these algorithms are relatively complicated to describe and understand. Gaussian elimination provides the simplest descriptions of algorithms for this purpose. These algorithms have a nice polynomial number of steps, but the steps deal with long operands. Here we show that there is an exponential length lower bound on the operands for a well-defined variant of Gaussian elimination when applied to Smith and Hermite normal form calculation. We present explicit matrices for which this variant produces exponential length entries. Thus, Gaussian elimination has worst-case exponential space and time complexity for such applications. The analysis provides guidance as to how integer matrix algorithms based on Gaussian elimination may be further developed for better performance, which is important since many practical algorithms for computing canonical forms are so based.
TITLE: Counting trees
AUTHORS: George Havas, Dean G. Hoffman and Colin Ramsay
CITATION: Research on Combinatorial Algorithms (Proc. Eighth Australasian Workshop on Combinatorial Algorithms), Queensland University of Technology (1997) 1-10
ABSTRACT: We consider the problem of enumerating particular kinds of spanning trees of a graph. The problem is interesting in its own right and has applications in the analysis of graph algorithms. The general problem seems hard to resolve. We present an algorithm to list depth-first trees for moderate sized graphs. We use this algorithm to count the number of depth-first spanning trees in a variety of graphs, and we give the results for hypercubes, meshes and tori, and complete bipartite graphs. We also give a proof of a theoretical result for complete multipartite graphs.
TITLE: NC approximation algorithms for 2-connectivity augmentation in a graph
AUTHORS: Weifa Liang and George Havas
CITATION: Euro-Par'97 Parallel Processing, Lecture Notes in Computer Science 1300 (1997) 430-439
ABSTRACT: We devise NC approximation algorithms for the optimal 2-edge connectivity and the optimal 2-vertex connectivity augmentation problems. Consequently, we find an approximation solution for the problem of the minimum 2-edge (biconnected) spanning subgraph on a weighted 2-edge connected (biconnected) graph.
TITLE: Parallel approximate edge coloring revisited
AUTHORS: Weifa Liang, George Havas and Anne Street
CITATION: Proceedings of PART'97: The 4th Australasian Conference on Parallel and Real-Time Systems, Springer-Verlag (1998) 95-103.
ABSTRACT: This paper presents a fast NC algorithm for edge coloring a graph with an approximately optimal number of colors.
TITLE: Finding the k most vital edges with respect to minimum spanning trees for k=2 and 3
AUTHORS: Weifa Liang and George Havas
CITATION: Computing Theory '98 (Proc. 4th Australasian Theory Symposium), Springer Verlag (1998) 37-50.
ABSTRACT: Let G(V,E) be a weighted, undirected, connected simple graph with n vertices and m edges. The k most vital edge problem with respect to minimum spanning trees is to find a set S of k edges from E such that the removal of all edges in S results in the greatest increase in the weight of the minimum spanning tree in the remaining graph G(V,E-S). In this paper we present a better algorithm to solve this problem for k=2 and 3. The algorithms can also be implemented on a CREW PRAM.
TITLE: Symmetric presentations and orthogonal groups
AUTHORS: C.M. Campbell, George Havas, S.A. Linton and E.F. Robertson
CITATION: The Atlas of Finite Groups: Ten Years On, London Mathematical Society Lecture Note Series 249, Cambridge University Press (1998) 1-10.
ABSTRACT: We examine series of finite presentations which are invariant under the full symmetric group acting on the set of generators. Evidence from computational experiments reveals a remarkable tendency for the groups in these series to be closely related to the orthogonal groups. We examine cases of finite groups in such series and look in detail at an infinite group with such a presentation. We prove some theoretical results about 3-generator symmetric presentations and make a number of conjectures regarding n-generator symmetric presentations.
TITLE: Extended gcd and Hermite normal form algorithms via lattice basis reduction
AUTHORS: George Havas, Bohdan S. Majewski and Keith R. Matthews
CITATION: Experimental Mathematics 8 (1999) 125-136 (open archive)
Addenda and errata Experimental Mathematics 8 (1999) 205 (open archive)
ABSTRACT: Extended gcd calculation has a long history and plays an important role in computational number theory and linear algebra. Recent results have shown that finding optimal multipliers in extended gcd calculations is difficult. We present an algorithm which uses lattice basis reduction to produce small integer multipliers x1,...,xm for the equation s=gcd(s1,...,sm)= x1s1+...+xmsm, where s1,...,sm are given integers. The method generalises to produce small unimodular transformation matrices for computing the Hermite normal form of an integer matrix.
TITLE: Improved Lightpath (Wavelength) Routing in Large WDM Networks
AUTHORS: Weifa Liang, George Havas and Xiaojun Shen
CITATION: Proc. 18th International Conference on Distributed Computing Systems, IEEE Computer Society (1998) 516-523
ABSTRACT: We address the problem of efficient circuit switching in wide area networks. The solution provided is based on finding optimal routes for lightpaths and semilightpaths. A lightpath is a fully optical transmission path, while a semilightpath is a transmission path constructed by chaining several lightpaths together, using wavelength conversion at their junctions. The problem thus is to find an optimal lightpath/semilightpath in the network in terms of the cost of wavelength conversion and the cost of using the wavelengths on links. We first present fast, efficient algorithms both for the general problem and for a natural restricted version. The new algorithms outperform earlier work, providing time improvements amounting to an almost linear time factor in most cases. Also, all our algorithms can be implemented on the network in a distributed way.
TITLE: Matrix reduction algorithms for Euclidean rings
AUTHORS: George Havas and Clemens Wagner
CITATION: Proc. 1998 Asian Symposium on Computer Mathematics, Lanzhou University Press (1998) 65-70
ABSTRACT: Reduction methods are the basis of algorithms for determining canonical forms of matrices over many computational domains. Experimental results have shown that various methods based on Gaussian elimination (which is a specialized kind of reduction algorithm) in Euclidean rings may lead to rapid growth of intermediate entries. On the other hand polynomial time algorithms do exist for such computations, but these algorithms are relatively complicated to describe and understand. Straightforward reduction methods provide the simplest descriptions of algorithms for this purpose. Such algorithms have a nice polynomial number of steps, but the steps may deal with operands with very large values. Here we show that there is a doubly exponential lower bound on the operands for a well-defined reduction algorithm when applied to Smith and Hermite normal form calculation for certain Euclidean rings. We present explicit matrices for which this variant produces doubly exponential entries. Thus, reduction algorithms have worst-case exponential space and time complexity for such applications. The analysis provides guidance as to how matrix algorithms for Euclidean rings which use reduction algorithms may be further developed for better performance, which is important since many practical algorithms for computing canonical forms are so based.
TITLE: Functional decomposition of a class of wild polynomials
AUTHORS: Robert Coulter, George Havas and Marie Henderson
CITATION: Journal of Combinatorial Mathematics and Combinatorial Computing 28 (1998) 87-94
ABSTRACT: No general algorithm is known for the functional decomposition of wild polynomials over a finite field. However partial solutions exist. In particular, a fast functional decomposition algorithm for linearised polynomials has been developed using factoring methods in skew-polynomial rings. This algorithm is extended to a related class of wild polynomials, which are sub-linearised polynomials.
TITLE: Elementary Algebra Revisited: Randomized Algorithms
AUTHORS: Gene Cooperman and George Havas
CITATION: Randomization Methods in Algorithm Design, DIMACS Series in Discrete Mathematics and Theoretical Computer Science 43 (1999) 37-44
ABSTRACT: We look at some simple algorithms for elementary problems in algebra that yield dramatic efficiency improvements over standard methods through randomization. The randomized algorithms are, in some sense, obvious. Their formal statement was delayed partly by the need for rigorous analysis, but more so by the need to re-think traditional approaches to elementary algorithms. We illustrate this philosophy with some basic problems in computational number theory (GCD of many integers), linear algebra (low-rank Gaussian elimination) and group theory (random subproducts for subgroup construction), along with a brief survey of other areas.
TITLE: Automorphism groups of certain non-quasiprimitive almost simple graphs
AUTHORS: Xin Gui Fang, George Havas and Jie Wang
CITATION: Groups St Andrews 1997 in Bath, I, London Mathematical Society Lecture Note Series 260, Cambridge University Press (1999) 267-274
ABSTRACT: A graph GAMMA is G-quasiprimitive if G is a group of automorphisms of GAMMA such that each nontrivial normal subgroup of G acts transitively on the vertices of GAMMA. We consider GAMMA a finite, connected S-locally-primitive graph with S a nonabelian simple group. We give a set of conditions under which we may guarantee that either the full automorphism group of GAMMA is not quasiprimitive or there is a non-quasiprimitive subgroup Y of Aut(GAMMA) such that C.G is maximal in Y, where C is the centralizer of S in Aut(GAMMA) and G is an almost simple group with socle S. As an application of this result we show that, in certain circumstances, we can specify Aut(GAMMA).
TITLE: GCD of many integers
AUTHORS: Gene Cooperman, Sandra Feisel, Joachim von zur Gathen and George Havas
CITATION: Computing and Combinatorics, Lecture Notes in Computer Science 1627 (1999) 310-317
ABSTRACT: A probabilistic algorithm is exhibited that calculates the gcd of many integers using gcds of pairs of integers; the expected number of pairwise gcds required is less than two.
TITLE: On routing in circulant graphs
AUTHORS: Jin-Yi Cai, George Havas, Bernard Mans, Ajay Nerurkar, Jean-Pierre Seifert and Igor Shparlinski
CITATION: Computing and Combinatorics, Lecture Notes in Computer Science 1627 (1999) 360-369
ABSTRACT: We investigate various problems related to circulant graphs -- finding the shortest path between two vertices, finding the shortest loop, and computing the diameter. These problems are related to shortest vector problems in a special class of lattices. We give matching upper and lower bounds on the length of the shortest loop. We prove NP-hardness results, and establish a worst-case/average-case connection for the shortest loop problem. A pseudo-polynomial time algorithm for these problems is also given. Our main tools are results and methods from the geometry of numbers.
TITLE: Groups with exponent six
AUTHORS: George Havas, M.F. Newman, Alice C. Niemeyer and Charles C. Sims
CITATION: Communications in Algebra 27 (1999) 3619-3638
ABSTRACT: Burnside asked questions about periodic groups in his influential paper of 1902. The study of groups with exponent six is a special case of the study of the Burnside questions on which there has been significant progress. It has contributed a number of worthwhile aspects to the theory of groups and in particular to computation related to groups. Finitely generated groups with exponent six are finite. We investigate the nature of relations required to provide proofs of finiteness for some groups with exponent six. We give upper and lower bounds for the number of sixth powers needed to define the largest two-generator group with exponent six. We solve related questions about other groups with exponent six using substantial computations which we explain.
TITLE: A Family of Non-Quasiprimitive Graphs Admitting a Quasiprimitive 2-Arc Transitive Group Action
AUTHORS: Xin Gui Fang, George Havas and Jie Wang
CITATION: European Journal of Combinatorics 20 (1999) 551-557 (open archive)
ABSTRACT: Let GAMMA be a simple graph and let G be a group of automorphisms of GAMMA. The graph is (G,2)-arc transitive if G is transitive on the set of the 2-arcs of GAMMA. In this paper we construct a new family of PSU(3,q2) 2-arc transitive graphs GAMMA of valency 9 such that Aut(GAMMA)=Z3.G, for some almost simple group G with socle PSU(3,q2). This gives a new infinite family of non-quasiprimitive almost simple graphs.
TITLE: On Sims' presentation for Lyons' simple group
AUTHORS: Holger W. Gollan and George Havas
CITATION: Computational Methods for Representations of Groups and Algebras, Progress in Mathematics 173 (1999) 235-240, Birkhaeuser
ABSTRACT: This paper gives a verification that the corrected Sims presentation is indeed a presentation of Lyons simple group. We prove that Lyons original characterization of his new simple group works inside a permutation group of degree 8,835,156.
TITLE: A presentation for the Lyons simple group
AUTHORS: George Havas and Charles C. Sims
CITATION: Computational Methods for Representations of Groups and Algebras, Progress in Mathematics 173 (1999) 241-249, Birkhaeuser
ABSTRACT: We give a presentation of the Lyons simple group together with information on a complete computational proof that the presentation is correct. This fills a longstanding gap in the literature on the sporadic simple groups. This presentation is a basis for various matrix and permutation representations of the group.
TITLE: Some challenging group presentations
AUTHORS: George Havas, Derek F. Holt, P.E. Kenne and Sarah Rees
CITATION: Journal of the Australian Mathematical Society (Series A) 67 (1999) 206-213 (open archive)
ABSTRACT: We study four challenging presentations which arise as groups of deficiency zero. We show that two presentations are for finite groups while two are for infinite groups. This answers three questions in the literature and provides the first published example of a group of deficiency zero with soluble length seven. The tools we use are coset enumeration and Knuth-Bendix rewriting, which are well-established as methods for proving finiteness or otherwise of a finitely presented group. We briefly comment on their capabilities and compare their performance.
TITLE: The complexity of the extended GCD problem
AUTHORS: George Havas and Jean-Pierre Seifert
CITATION: Mathematical Foundations of Computer Science 1999, Lecture Notes in Computer Science 1672 (1999) 103-113
ABSTRACT: We undertake a thorough complexity study of the following fundamental optimization problem, known as the lp-norm shortest Extended GCD multiplier problem: given a1,...,an in Z, find an lp-norm shortest gcd multiplier for a1,...,an, i.e., a vector x in Zn with minimum sum(|xi|p)1/p satisfying sum(xiai) = gcd(a1,...,an).
First, we prove that the shortest GCD multiplier problem (in its feasibility recognition form) is NP-complete for every lp-norm with p in N. We then strengthen this negative result by ruling out even polynomial-time algorithms which only approximate an lp-norm shortest gcd multiplier within a factor n1/(p logg n), for g an arbitrary small positive constant, under the widely accepted complexity theory assumption NP not in DTIME(npoly(log n)).
For positive results we focus on the l2-norm GCD multiplier problem. We show that approximating this problem within a factor of n1/2 is very unlikely NP-hard by placing it in NP intersection coAM through a simple constant-round interactive proof system. This result is complemented by a polynomial-time algorithm which computes an l2-norm shortest gcd multiplier up to a factor of 2(n-1)/2.
This study is motivated by the importance of extended gcd calculations in applications in computational algebra and number theory. Our results rest upon the close connection between the hardness of approximation and the theory of interactive proof systems.
TITLE: Some Performance Studies in Exact Linear Algebra
AUTHORS: George Havas and Clemens Wagner
CITATION: Workshop on wide area networks and high performance computing, Lecture Notes in Control and Information Sciences 249 (1999) 161-170
ABSTRACT: We consider parallel algorithms for computing the Hermite normal form of matrices over Euclidean rings. We use standard types of reduction methods which are the basis of many algorithms for determining canonical forms of matrices over various computational domains. Our implementations take advantage of well-performing sequential code and give very good performance.
TITLE: On the automorphism groups of quasiprimitive almost simple graphs
AUTHORS: Xin Gui Fang, George Havas and Cheryl E. Praeger
CITATION: Journal of Algebra 222 (1999) 271-283 (open archive)
ABSTRACT: A permutation group is said to be quasiprimitive if each of its nontrivial normal subgroups is transitive. A graph GAMMA is G-quasiprimitive if G is a group of automorphisms of GAMMA such that G acts quasiprimitively on the vertices of GAMMA. In this paper we assume that G is is an almost simple group and investigate the full automorphism group of a G-quasiprimitive graph GAMMA. We show that, for a connected nonbipartite G-quasiprimitive and G-locally-primitive graph GAMMA with G almost simple one of the following three situations holds: Aut(GAMMA) is quasiprimitive; or each intransitive minimal normal subgroup of Aut(GAMMA) centralizes the socle of G; or G is an almost simple group of Lie type of characteristic p, and the socle of Aut(GAMMA) involves an explicitly known faithful GF(p)G-module M, with G, M belonging to a (short) explicit list.
TITLE: Finding a Low-Diameter and Low-Weight k-Connected Subgraph
AUTHORS: Weifa Liang, George Havas and Anne Street
CITATION: Congressus Numerantium 136 (1999) 161-175
ABSTRACT: Low-diameter, low-weight subgraphs have useful applications in networks. The problem is how to find them. Given a weighted undirected k-connected graph G=(V,E), let diam(G) denote the diameter of G and let w(G) the sum of the weights of the edges in G. In this context, the problem is to find a k-connected spanning subgraph G'=(V,E') of G such that the diameter and the weight of G' are minimized simultaneously. Since this problem is NP-hard, it is unlikely that there is a polynomial algorithm for it. We present an approximate solution with a performance guarantee. That is, we find a k-connected spanning subgraph G' in polynomial time such that diam(G')<=a×diam(G) and w(G')<=b×w(G*) for any fixed a>1, where G* is a minimum k-connected spanning subgraph of G and b is a constant depending on a and k.
