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.
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
REVIEWS:
Math. Rev. 94i:20001 (E.F. Robertson); Zbl. 789.15008 (H. Grassmann)
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
REVIEW: Math. Rev. 95e:68039 (Ricardo Baeza-Yates)
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
REVIEWS:
Math. Rev. 95g:20001 (Sarah E. Rees); Zbl. 822.20001 (J. Neubueser)
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.