Research Report - 2001
Algorithm Design
Academic Staff
A/Prof George Havas Dr Kevin Gates |
Research Staff
Dr Robert Coulter Dr Greg Gamble Dr Colin Ramsay |
Research Students
Ms Julie Lawrence Mr Andrew Janke |
Contact Details
A/Prof George Havas Email: havas@csee.uq.edu.au Tel: 3365 2904 Dr Kevin Gates Email: keg@csee.uq.edu.au Tel: 3365 3261 |
The Algorithm Design Group is part of the Centre for Discrete Mathematics and Computing at The University of Queensland. It has active international collaborations with research groups in Canada, China, Germany, UK and USA, and has received substantial support from the Australian Research Council.
Abstract Algebraic Algorithms
Algebraic computation research includes the design, development, implementation, application and analysis of algorithms for computer use in abstract algebraic problem solving. Work is being undertaken on various procedures for computations in groups and related structures: coset enumeration; p-quotient calculation; subgroup presentation; and presentation manipulation. Programs implementing these algorithms have been incorporated into coherent packages of machine implementations for the study of algebraic structures, including Gap (Germany), Magma (Australia) and Quotpic (UK).
C M Campbell, George Havas, S A Linton and E F Robertson, "Symmetric presentations and orthogonal groups", The Atlas of Finite Groups: Ten Years On, London Mathematical Society Lecture Note Series 249, Cambridge University Press (1998) 1-10.
Gene Cooperman and George Havas, "Elementary Algebra Revisited: Randomized Algorithms", Randomization Methods in Algorithm Design, DIMACS Series in Discrete Mathematics & Theoretical Computer Science, 43 (1999) 37-44
Xin Gui Fang, George Havas and Jie Wang, "Automorphism groups of certain non-quasiprimitive simple graphs", Groups St Andrews 1997 in Bath, I, London Mathematical Society Lecture Notes Series 260, Cambridge University Press (1999) 267-274.
Gene Cooperman, Sandra Feisel, Joachim von zur Gathen and George Havas, "GCD of many integers", Computing and Combinatorics, Lecture Notes in Computer Science 1627 (1999) 310-317.
George Havas, M.F. Newman, Alice C. Niemeyer and Charles C. Sims, "Groups with exponent six", Communications in Algebra 27 (1999) 3619-3638.
Exact Linear Algebra and Extended Greatest Common Divisor (GCD) Algorithms
The existence of canonical forms for integer matrices (and for matrices over other rings) has been known since the middle of the last century. The computation of canonical forms for matrices have important applications in both theoretical and practical areas of mathematics, science and engineering. This project aims to design, implement, test and analyze effective computer algorithms and data structures for computing canonical forms of matrices over various rings and fields, with a view to application to research problems in the areas associated with the matrices. Algorithms developed in this project are incorporated into leading systems for computational algebra and number theory, including Gap (Germany), Magma (Australia), Magnus (USA), Lidia (Germany), Quotpic (UK) and Pari (France).
A fundamental building block for canonical matrix algorithms is provided by extended gcd algorithms. Extended gcd calculation has a long history and plays an important role in computational number theory and linear algebra. Extended gcd algorithms are studied both in theory and in practice.
George Havas, B.S. Majewski and K.R. Matthews, "Extended gcd and Hermite normal form algorithms via lattice basis reduction", Experimental Mathematics 7 (1998) 125-135. Addenda and errata: Experimental Mathematics 8 (1999) 205.
George Havas and Clemens Wagner, "Some Performance Studies in Exact Linear Algebra", Distributed High Performance Computing and Gigabit Wide Area Networks, Lecture Notes in Control and Information Sciences 249 (1999) 161-170.
George Havas and Jean-Pierre Seifert, "The complexity of the extended GCD problem", Mathematical Foundations of Computer Science 1999, Lecture Notes in Computer Science 1672 (1999) 103-113.
Perfect Hashing
A classic problem in computer science is how to store information so that it can be searched and retrieved efficiently. Minimal perfect hash functions are used for memory efficient storage and fast retrieval of items from static sets. The aim of the project is to investigate, both from theoretical and practical points of view, algorithms for generating perfect hash functions. Algorithms developed here are used in systems for data management, and also are available in the Linux software library.
Zbigniew J. Czech, George Havas and Bohdan S. Majewski, "Perfect hashing", Theoretical Computer Science 182 (1997) 1-143. (The authors received awards for this paper from the Polish National Minister for Education.)
Fundamental Algorithms
For Parallel and Distributed Systems With the increasing availability of parallel and distributed systems, investigation of appropriate algorithms for the basic graph procedures are most important. The aim of this project is to design, develop, implement, analyze and apply algorithms which improve on previous work.
Weifa Liang, George Havas and Anne Street, "Parallel approximate edge coloring revisited", Proceedings of PART'97: The 4th Australasian Conference on Parallel and Real-Time Systems, Springer-Verlag (1998) 95-103.
Weifa Liang and George Havas, "Finding the k most Vital Edges with Respect to Minimum Spanning Trees for k=2 and 3", Computing Theory `98, Proc 4th Australasian Theory Symposium, Springer Verlag (1998) 37-50.
Algorithms and Application in Finite Fields
One of the most important properties of a finite field is that any function defined on it can be represented as a polynomial. Different classes of polynomials which have special types of behaviour are important because of their applications in areas such as cryptography, combinatorics and finite geometries. A major aim of this project is to study the behaviour of classes of polynomials by computational and theoretical methods and to develop applications of the results obtained. One problem this project has considered at length deals with decomposing wild polynomials into indecomposables. In general, wild polynomials do not decompose uniquely. However, some subsets do have unique decomposition within their own set. For example, it has long been known that any linearised polynomial decomposes uniquely into indecomposable linearised polynomails. We have now established that the sub-linearised also exhibit this behaviour, in a very specific way. An algorithm exploiting this has since been developed.
Presently, the project is considering just how many indecomposable sub-linearised polynomials exist in a fixed finite field.
R.S. Coulter, "On the evaluation of a class of Weil sums in characteristic 2", New Zealand J. Math. 28 (1999), 171-184.
R.S. Coulter and M. Henderson, "A class of functions and their application in constructing semi-biplanes and association schemes", Discrete Math. 202 (1999), 21-31.
Combinatorial Computation
Combinatorial computation is basic to pure research, new technologies and product development. Work is being done to design, implement, test, analyse and apply effective fundamental combinatorial algorithms on high performance com- puters. This means designing new algorithms, redesigning old ones, and using such algorithms to solve problems where current techniques are inadequate. Brenton D. Gray and Colin Ramsay, "Some results on defining sets of t-designs", Bulletin of the Australian Mathematical Society, 59 (1999) 203-215.
Brenton D. Gray and Colin Ramsay, "On the index of simple trades", Australian Journal of Combinatorics, 20 (1999) 207-221
Iterative Subspace
Techniques in Chemical Reaction Dynamics The work in this area concentrates on the development of new linear algebra algorithms for the solution of problems in chemical reaction dynamics. Of particular interest are iterative algorithms with high relative accuracy resolution of eigenvalues and eigenvectors. This project has just received a new Large ARC grant.
Rasmussen, A.J.; Gates, K.E.; Smith, S.C.; "A pseudo-spectral algorithm for the computation of transitional-mode eigenfunctions in loose transition states. II. Optimized primary and grid representations", J. Chem. Phys., 1999, 110, 3, 1354-1364.
Gates, K.E.; Robertson, S.H.: Smith, S.C.; Pilling, M.J.; Beasley, M.S.; Maschhoff, K.J.; "Multiple-Well Isomerization Diffusion Equation Solutions with a Shift and Invert Lanczos Algorithm", J.Phys.Chem., 1997, 101, 5765-5769.
Simulation of Electron Paramagnetic Resonance Spectra
This work is involved in the production of a commercia[l program for the numerical simulation of electron paramagnetic resonance spectra. The development involves work on numerical and optimisation algorithms for the actual simulation, as well as CORBA interface work for the connection of the suite of programs and the development of state of the art visual interfaces to the program in both Java and X11. Commercial product available for resale by Bruker Analytik Germany.
Gates, K.E.; Griffin, M.; Hanson, G.R.; Burrage, K.; "Computer Simulation of Randomly Oriented EPR Spectra Employing Homotopy", Magnetic Resonance and Related Phemomena, Proceedings of the Joint 29th AMPERE & 13th ISMAR International Conference, Technische University Berlin, Aug. 2-7, 1998, pp. 1212-1213.
Gates, K.E.; Griffin, M.; Hanson, G.R.; Burrage, K.; "Computer Simulation of Magnetic Resonance Spectra Employing Homotopy", J. Magn. Reson., 1998, 135, 104-112.
Image Processing for Magnetic Resonance Images
This aim of this research is the development of image processing techniques to aid in the understanding and analysis of magnetic resonance images. By studying the image deformations and changes it is hoped a better understanding of the disease process. This work involves the construction of new algorithms for processing and comparing images taken over a span of time.
<%-- end content --%>
<%@ include file="/include/footer.inc.jsp" %>