PhD candidate Stavros Birmpilis, co-supervised by Cheriton School of Computer Science Professors George Labahn and Arne Storjohann, has won one of two Distinguished Student Author Awards at ISSAC 2020, the 45th International Symposium on Symbolic and Algebraic Computation.
Stavros’s paper, titled “A Las Vegas algorithm for computing the Smith form of a nonsingular integer matrix,” continues work that began in 1979. Since then, computer scientists in the field of symbolic computation — a research area in which algorithms and software are developed to manipulate mathematical expressions and other mathematical objects — have made considerable progress by developing faster deterministic algorithms to compute the Smith normal form of a nonsingular integer matrix. More recently, researchers have employed randomized techniques, what are known as Monte Carlo and Vas Vegas types, to improve the running time of algorithms.
The algorithm that Stavros and his co-supervisors have developed is probabilistic of Las Vegas type. This means it returns the correct Smith form or it will return failure with a probability of less than 1/2. The algorithm has significantly improved time complexity compared with previous algorithms. In particular, it can compute the Smith form of an integer matrix in a comparable number of bit operations as multiplying two integer matrices of the same dimensions and size.
Watch Stavros’s virtual award-winning presentation at ISSAC 2020.
“Arne and I are thrilled that Stavros has won a Distinguished Student Award at ISSAC 2020,” said Professor Labahn. “His paper represents significant progress on computing Smith forms and it has important implications on future work on fast algorithms for integer matrix arithmetic.”
ISSAC is the premier conference for research in symbolic computation and computer algebra. ISSAC began in 1966 and has been held annually since 1981.
To learn more about this research, please see Stavros Birmpilis, George Labahn and Arne Storjohann. A Las Vegas Algorithm for Computing the Smith Form of a Nonsingular Integer Matrix. Proceedings of the 2020 International Symposium on Symbolic and Algebraic Computation (ISSAC ’20), July 20–23, 2020.
