Martin Furer [A legend in Multiplication?]

Martin Furer is a Computer Scientist and Mathematician who is known for creating one of the fastest Integer Multiplication algorithm which held the record of the fastest multiplication algorithm for 12 years (2007 to 2019).

Martin Furer is a legend in Computing.
Currently, he is a Computer Science professor at Pennsylvania State University. He is on the editorial board of international journals namely: Journal of Graph Algorithms and Applications and Information and Computation (by MIT).

Known for:

  • Furer's Algorithm for Multiplication (2007)

Education

  • PhD in Mathematics from ETH Zurich (1967 to 1978)

Work

  • Computer Science professor at Pennsylvania State University from August 1978 just after completing his PhD (43 years and counting)

Location: State College, Pennsylvania, United States
Research impact: As of 2021: 2997 citations, 22 h-index and 94 publications (One of the best in the industry).

Martin Furer

Furer's algorithm

Furer's algorithm is one of the fastest Integer Multiplication algorithm known to humanity. It was discovered by Martin Furer in 2007. Previously, this record was held by Schonhage Strassen algorithm for nearly 36 years (from 1971 to 2007).

Furer's algorithm is significant as:

  • It was the first theoretical breakthrough in a problem where nothing happened for last 36 years since 1971.
  • The improvement by Furer's algorithm was the basis of several other algorithms but no major theoretical improvement was acheived till 2019.
  • For 12 years (2007 to 2019), Furer's algorithm was the theoretically the best algorithm for the multiplication problem.
  • It is a Galactic Algorithm which is an active area of research.

Currently, Furer's algorithm is not used for practical applications

The naive algorithm to multiply two N bit numbers take O(N^2) time complexity.

In 1971, Schonhage Strassen algorithm was developed which acheived a time complexity of O(N logN loglogN). Everyone was stuck at this point and was unable to improve the time complexity. It was widely believed that the minimum time complexity possible should be O(N logN) but it was not theoretically proved.

The breakthrough came after 36 years with Furer's algorithm which improved the time complexity further. It improved the loglogN factor.

Furer's algorithm had a time complexity of O(N logN 2^(O(log* N))) where:

  • log* is iterative logarithm and is smaller than logN in complexity notation.

This is a major theoretical result.
From practical point of view, this is not used as Schonhage Strassen algorithm performs better for real data.

Furer's algorithm is expected to perform significantly better than Schonhage Strassen algorithm for integers greater than 2^(2^64).

In 2008, another algorithm was proposed by another scientist which resulted in the same complexity and is expected to perform better than Schonhage Strassen algorithm for integers greater than 10^(10^4796).
This could not improve over Furer's algorithm.

Furer's algorithm held its record till 2019.

In 2015, Harvey, Joris van der Hoeven and Lecerf came up with a new algorithm which preceded log* N factor with an actual constant. The time complexity of the new algorithm is O(N logN 2^(3 log* N).

Later in 2016 and 2018, the time complexity was improved to O(N logN 2^(2 log* N). There was no actual improvement over Furer's algorithm.

In May 2019, finally, an algorithm was developed by Harvey and van der Hoeven which acheived the time complexity of O(N logN).

Research by Martin Furer

Research interests of Martin Furer are:

  • Graph Algorithms and Algebraic Graph Theory
  • Width Parameters and Fixed Parameter Tractability
  • Combinatorial and Algebraic Algorithms
  • Approximation Algorithms to Combinatorial Optimization Problems
  • Computational Complexity
  • The Graph Isomorphism Problem

Some of the other major breakthroughs by Martin Furer are as follows:

  • Proved that there exists a polynomial time approximation algorithm for finding a spanning tree with degree is at most 1 more than the minimal degree. Previous results had a logN factor and this algorithm is optimal if P=NP.

  • Proved that there are non isomorphic graphs of degree 3 with N vertices such that WL[k] (Weisfeiler Lehman method) does not detect that they are non isomorphic for any K = O(N). Previously, it was not known if the algorithm detected all graphs.

Two Most recent research papers by Furer:

February 2021: An Improvement of Reed’s Treewidth Approximation
Belbasi, M. & Fürer, M., 2021, WALCOM: Algorithms and Computation - 15th International Conference and Workshops, WALCOM 2021, Proceedings.

October 2020: Efficient diagonalization of symmetric matrices associated with graphs of small treewidth
Fürer, M., Hoppen, C. & Trevisan, V., Jun 1 2020, 47th International Colloquium on Automata, Languages, and Programming, ICALP 2020. Czumaj, A., Dawar, A. & Merelli, E. (eds.). Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing.

With this article at OpenGenus, you must have a good idea of Martin Furer and the importance of his work. He is definitely, a legend in Computing.