TITLE: A nilpotent
quotient algorithm for graded Lie rings
AUTHORS: George Havas, M. F. Newman and M. R.
Vaughan-Lee
CITATION: Journal
of Symbolic Computation 9 (1990) 655-664 (open
archive)
ABSTRACT: A nilpotent quotient algorithm for graded
Lie rings of prime characteristic is described. The algorithm
has been implemented and applications have been made to the
investigation of the associated Lie rings of Burnside groups.
New results about Lie rings and Burnside groups are
presented. These include detailed information on groups of
exponent 5 and 7 and their associated Lie rings.
TITLE: Coset enumeration
strategies
AUTHOR: George Havas
CITATION: ISSAC'91
(Proc. 1991 International Symposium on Symbolic and Algebraic
Computation), ACM Press (1991) 191-199
ABSTRACT: A primary reference on computer
implementation of coset enumeration procedures is a 1973
paper of Cannon, Dimino, Havas and Watson. Programs and
techniques described there are updated in this paper.
Improved coset definition strategies, space saving techniques
and advice for obtaining improved performance are included.
New coset definition strategies for Felsch-type methods give
substantial reductions in total cosets defined for some
pathological enumerations. Significant time savings are
achieved for coset enumeration procedures in general.
Statistics on performance are presented, both in terms of
time and in terms of maximum and total cosets defined for
selected enumerations.
TITLE: An optimal
algorithm for generating minimal perfect hash functions
AUTHORS: Zbigniew J. Czech, George Havas and Bohdan S.
Majewski
CITATION: Information
Processing Letters 43 (1992) 257-264
ABSTRACT: A new algorithm for generating order
preserving minimal perfect hash functions is presented. The
algorithm is probabilistic, involving generation of random
graphs. It uses expected linear time and requires a linear
number words to represent the hash function, and thus is
optimal up to constant factors. It runs very fast in
practice.
TITLE: Algorithms for
groups
AUTHORS: John Cannon and George Havas
CITATION: Australian Computer Journal 24
(1992) 51-60
ABSTRACT: Group theory is a particularly fertile field
for the design of practical algorithms. Algorithms have been
developed across the various branches of the subject and they
find wide application. Because of its relative maturity,
computational group theory may be used to gain insight into
the general structure of algebraic algorithms. This paper
examines the basic ideas behind some of the more important
algorithms for finitely presented groups and permutation
groups, and surveys recent developments in these
fields.
[Reprint: 822K]
TITLE: Optimal
Algorithms for Minimal Perfect Hashing
AUTHORS: George Havas and Bohdan S. Majewski
CITATION: Technical Report 234, The University of
Queensland (1992)
ABSTRACT: We review previous methods for finding
minimal perfect hash functions, showing that the earlier ones
have no serious practical value for large sets. Then we
present optimal time solutions to the problem, which generate
minimal perfect hash functions for arbitrary sets in expected
linear time and use almost linear space. The hash functions
are fast computable. We give examples of performance for
large sets.
TITLE: Application of
substring searching methods to group presentations
AUTHORS: George Havas and Mark Ollila
CITATION: Australian Computer Science
Communications 15 (1993) 587-593
ABSTRACT: An important way for describing groups is by
finite presentations. Large presentations arise in practice
which are poorly suited for either human or computer use.
Presentation simplification processes which take bad
presentations and produce good presentations have been
developed. Substantial use is made of substring searching and
appropriate techniques for this context are described.
Effective use is made of signatures and change flags. Change
flags are shown to be the most beneficial of the methods
tested here, with very significant performance improvement.
Experimental performance figures are given.
TITLE: Recognizing
badly presented Z-modules
AUTHORS: George Havas, Derek F. Holt and Sarah
Rees
CITATION: Linear
Algebra and its Applications 192 (1993) 137-164
(open archive)
ABSTRACT: Finitely generated Z-modules have canonical
decompositions. When such modules are given in a finitely
presented form there is a classical algorithm for computing a
canonical decomposition. This is the algorithm for computing
the Smith normal form of an integer matrix. We discuss
algorithms for Smith normal form computation, and present
practical algorithms which give excellent performance for
modules arising from badly presented abelian groups. We
investigate such issues as congruential techniques, sparsity
considerations, pivoting strategies for Gauss-Jordan
elimination, lattice basis reduction and computational
complexity. Our results, which are primarily empirical, show
dramatically improved performance on previous methods.
TITLE: Graph theoretic
obstacles to perfect hashing
AUTHORS: George Havas and Bohdan S. Majewski
CITATION: Congressus Numerantium 98
(1993) 81-93
ABSTRACT: A number of algorithms based on quasi-random
graphs for generating perfect hash functions have been
published. These include Sager's mincycle algorithm, a
modification by Fox et al. of it and finally probabilistic
methods due to Czech, Havas and Majewski. Each of these
algorithms exploits different properties of graphs, such as
being bipartite or being acyclic. In this paper we formally
justify the significance of these properties. Also we
indicate causes of failure for some methods. In particular we
show that acyclicity of a graph plays a crucial role in
finding order preserving perfect hash functions. It is a
sufficient, but not necessary, condition for algorithms to
actually find a perfect hash function. We provide some
examples for which various published methods methods fail,
taking exponential time to do so. Finally, based on our
considerations of graph properties, we propose yet another
method for generating perfect hash functions.
TITLE: Graphs,
hypergraphs and hashing
AUTHORS: George Havas, Bohdan S. Majewski, Nicholas C.
Wormald and Zbigniew J. Czech
CITATION: Graph-Theoretic
Concepts in Computer Science, Lecture Notes in Computer
Science 790 (1994), 153-165
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 minimal perfect hash
functions which allow an arbitrary order to be specified for
the keys. We show that almost all members of the family are
space and time optimal, and we identify the one with minimum
constants. Members of the family generate a minimal perfect
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 practical and 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: Application of
computational tools for finitely presented groups
AUTHORS: George Havas and Edmund F. Robertson
CITATION: Computational Support for Discrete
Mathematics, DIMACS Series in Discrete Mathematics and
Theoretical Computer Science 15 (1994), 29-39
ABSTRACT: Computer based techniques for recognizing
finitely presented groups are quite powerful. Tools available
for this purpose are outlined. They are available both in
stand-alone programs and in more comprehensive systems. A
general computational approach for investigating finitely
presented groups by way of quotients and subgroups is
described and examples are presented. The techniques can
provide detailed information about group structure. Under
suitable circumstances a finitely presented group can be
shown to be soluble and its complete derived series can be
determined, using what is in effect a soluble quotient
algorithm.
TITLE: Hermite normal
form computation for integer matrices
AUTHORS: George Havas and Bohdan S. Majewski
CITATION: Congressus Numerantium 105
(1994) 87-96
ABSTRACT: We consider algorithms for computing the
Hermite 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 analyze some
methods for computing the Hermite normal form and we show the
intractability of associated problems. We investigate in
detail a method based on an algorithm due to Blankinship and
show how improved performance is achieved.
TITLE: The complexity
of greatest common divisor computations
AUTHORS: Bohdan S. Majewski and George Havas
CITATION: Algorithmic
Number Theory, Lecture Notes in Computer Science
877 (1994) 184-193
ABSTRACT: We consider the complexity of expressing the
greatest common divisor of n positive numbers as a linear
combination of the numbers. We prove the NP-completeness of
finding optimal sets of multipliers with respect to both the
L0 metric and Linfinity norm. We
present and analyze a new method for expressing the gcd of n
numbers as their linear combination and give an upper bound
on the size of the largest multiplier produced by this
method, which is optimal.
TITLE: A new problem in
string searching
AUTHORS: George Havas and Jin Xian Lian
CITATION: Algorithms
and Computation, Lecture Notes in Computer Science
834 (1994) 660-668
ABSTRACT: We describe a substring search problem that
arises in group presentation simplification processes. We
suggest a two-level searching model: skip and match levels.
We give two timestamp algorithms which skip searching parts
of the text where there are no matches at all and prove their
correctness. At the match level, we consider Harrison
signature, Karp-Rabin fingerprint, Bloom filter and automata
based matching algorithms and present experimental
performance figures.
TITLE: Reconstructing a
distributed depth-first-search tree after network topology
changes
AUTHORS: S.A.M. Makki and George Havas
CITATION: Proc. Sixth IASTED/ISMM Internat. Conf.
Parallel and Distributed Computing and Systems, Acta
Press (1994) 335-337
ABSTRACT: We consider the problem of reconstructing a
distributed depth-first-search (DFS) tree in an
interconnected communication network in the presence of link
failures or deletions and/or recoveries or additions. We
describe an algorithm which efficiently reconstructs a
distributed DFS tree after several links are deleted, with
link additions also properly handled. Under standard
assumptions, the required number of messages and time units
in the worst case is bounded by k(h+|V|(1+r)), where k is the
number of link failures, h is the length of the longest
simple path in the network, |V| is the number of nodes in the
network and 0<=r<1.
TITLE: Extended gcd
algorithms
AUTHORS: George Havas, B.S. Majewski and K.R.
Matthews
CITATION: Technical Report 302, The University of
Queensland (1995)
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 study algorithms for finding good multipliers
and present new algorithms with improved performance. We
present a well-performing algorithm which is based on lattice
basis reduction methods and may be formally analyzed. We also
give a relatively fast algorithm with moderate performance.
TITLE: A solution to
the extended gcd problem
AUTHORS: Bohdan S. Majewski and George Havas
CITATION: ISSAC'95
(Proc. 1995 Internat. Sympos. on Symbolic and Algebraic
Computation), ACM Press (1995) 248-253
ABSTRACT: An improved method for expressing the
greatest common divisor of n numbers as an integer linear
combination of the numbers is presented and analyzed, both
theoretically and practically. The performance of this
algorithm is compared with other methods, indicating
substantial improvements in the size of the solution. The
results are given in the light of the current knowledge about
the complexity of extended gcd computations. Thus, finding
optimal sets of multipliers has been proved to be an
NP-complete problem. We present a relatively efficient
approximation algorithm with excellent performance. This
problem is interesting in its own right. Furthermore, it has
important applications, for example in computing canonical
normal forms of integer matrices.
TITLE: Extended gcd
calculation
AUTHORS: George Havas and Bohdan S. Majewski
CITATION: Congressus Numerantium 111
(1995) 104-114
ABSTRACT: Given an integer vector a of n
positive numbers the extended gcd problem asks for an integer
vector x of length n such that
x.aT = gcd(ai). For many
applications it is vital that some measure of x is
small. We have proved, however, that if we choose either the
max norm or the zero metric the question of finding x
such that these are smaller than some positive constant K is
NP-complete. We conjecture that the question remains
NP-complete for other norms. In the light of these results we
have proposed two approximation algorithms. Their respective
complexities are O(n2log(max{ai})) and
O(n4log(max{ai})). Theoretical analysis
of the algorithms leads to unsatisfactory bounds on the
quality of the solution. Thus here we undertake a practical
study of the methods, where their performance is matched
against optimal solutions.
TITLE: A hard problem
that is almost always easy
AUTHORS: George Havas and B.S. Majewski
CITATION: Algorithms and
Computation, Lecture Notes in Computer Science
1004 (1995) 216-223
ABSTRACT: NP-completeness is, in a well-defined sense,
a worst case notion. Thus, 3-colorability of a graph, for a
randomly generated graph, can be determined in constant
expected time even though the general problem is NP-complete.
The reason for this is that some hard problems exhibit a
structure where only a small (perhaps exponentially small)
fraction of all possible instances is intractable, while the
remaining large fraction has a polynomial time solution
algorithm. We add a new problem to the list of NP-complete
problems that are solvable in average polynomial time.
