AF: Small: Algorithms Based on Discrete and Algebraic Methods

点击翻译按钮获取中文摘要

This research is concerned with discrete computational tasks, mainly mathematical decision and optimization problems. Often such problems can be attacked directly by discrete methods. The focus of this research is to study situations where algebraic approaches produce better solutions. Even though the problem formulation can be entirely discrete, significant insight and efficient algorithms might be obtained by applying sophisticated algebraic methods. It is not uncommon that combinatorial problems have simple and elegant formulations, yet the obvious algorithms are too slow for their solutions except for very small instances. In such situation, algebraic methods might provide the decisive insights. The graph isomorphism problem exemplifies a combinatorial problem where algebraic methods have successfully produced efficient algorithms. This research also deals with other foundational mathematical problems having these characteristics, like efficient multiplication of long integers and the monomer dimer problem, and the counting of matchings in grid graphs. Typical algebraic tools used are group theory, the discrete Fourier transform, as well as the zeta transform and its inverse, the Mobius transform. Usually, there is no obvious way of how to apply these tools most effectively. For example, the fastest integer multiplication algorithms are all based on Fourier transforms, but the efficiency heavily depends on the type of Fourier transform applied. This project deals with fundamental combinatorial and algebraic tasks for which efficient algorithms are desirable. This research is significant, because it contributes to a better understanding of the mathematical structures behind these problems and leads to the discovery of more efficient algorithms.An important goal of this project is to contribute to the development of a new generation of graduate students, who appreciate the development of mathematical insight into difficult combinatorial and algebraic problems with the goal of producing efficient algorithms. In particular, integer multiplication is such a fundamental arithmetic task that understanding and improving it is an obvious basic intellectual challenge. Such theoretical goals are foremost in this project. But there is a potential for an impact on the search for Mersenne primes and on general purpose computations with high degree polynomials. Other aspects of this research involve topics with applications in Physics and Chemistry.