Volker Strassen
Encyclopedia
Volker Strassen is a German
mathematician
, a professor emeritus in the department of mathematics and statistics at the University of Konstanz
.
.
After studying music, philosophy, physics, and mathematics at several German universities, he received his Ph.D. in mathematics in 1962 from the University of Göttingen under the supervision of Konrad Jacobs. He then took a position in the department of statistics
at the University of California, Berkeley
while performing his habilitation
at the University of Erlangen-Nuremberg, where Jacobs had since moved. In 1968, Strassen moved to the Institute of Applied Mathematics at the University of Zurich
, where he remained for twenty years before moving to the University of Konstanz in 1988. He retired in 1998.
, showing a form of scale invariance
in random walk
s. This result, now known as Strassen's invariance principle or as Strassen's law of the iterated logarithm, has been highly cited and led to a 1966 presentation at the International Congress of Mathematicians
.
In 1969, Strassen shifted his research efforts towards the analysis of algorithms
with a paper on Gaussian elimination
, introducing Strassen's algorithm, the first algorithm for performing matrix multiplication
faster than the O(n3) time bound that would result from a naive algorithm. In the same paper he also presented an asymptotically-fast algorithm to perform matrix inversion, based on the fast matrix multiplication algorithm. This result was an important theoretical breakthrough, leading to much additional research on fast matrix multiplication, and despite later theoretical improvements it remains a practical method for multiplication of dense matrices of moderate to large sizes. In 1971 Strassen published another paper together with Arnold Schönhage
on asymptotically-fast
integer multiplication based on the fast Fourier transform
; see the Schönhage–Strassen algorithm. Strassen is also known for his 1977 work with Robert M. Solovay
on the Solovay–Strassen primality test, the first method to show that testing whether a number is prime
can be performed in randomized polynomial time and one of the first results to show the power of randomized algorithms more generally.
, and in 2003 he was co-recipient of the Paris Kanellakis Award
with Robert Solovay
, Gary Miller
, and Michael Rabin
for their work on randomized primality testing. In 2008 he was awarded the Knuth Prize
for "seminal and influential contributions to the design and analysis of efficient algorithms."
Germany
Germany , officially the Federal Republic of Germany , is a federal parliamentary republic in Europe. The country consists of 16 states while the capital and largest city is Berlin. Germany covers an area of 357,021 km2 and has a largely temperate seasonal climate...
mathematician
Mathematician
A mathematician is a person whose primary area of study is the field of mathematics. Mathematicians are concerned with quantity, structure, space, and change....
, a professor emeritus in the department of mathematics and statistics at the University of Konstanz
University of Konstanz
The University of Konstanz is a university in the city of Konstanz in Baden-Württemberg, Germany. It was founded in 1966, and the main campus on the Gießberg was opened in 1972. As one of nine German Excellence Universities today University of Konstanz is counted among Germany's most prestigious...
.
Biography
Strassen was born on April 29, 1936, in Düsseldorf-GerresheimDüsseldorf-Gerresheim
Gerresheim is one of the City of Düsseldorf, Germany's forty-nine boroughs. It is located in the eastern part of the municipality. Gerresheim is much older than Düsseldorf itself, having been an independent city with a rich history for over 1,000 years...
.
After studying music, philosophy, physics, and mathematics at several German universities, he received his Ph.D. in mathematics in 1962 from the University of Göttingen under the supervision of Konrad Jacobs. He then took a position in the department of statistics
Statistics
Statistics is the study of the collection, organization, analysis, and interpretation of data. It deals with all aspects of this, including the planning of data collection in terms of the design of surveys and experiments....
at the University of California, Berkeley
University of California, Berkeley
The University of California, Berkeley , is a teaching and research university established in 1868 and located in Berkeley, California, USA...
while performing his habilitation
Habilitation
Habilitation is the highest academic qualification a scholar can achieve by his or her own pursuit in several European and Asian countries. Earned after obtaining a research doctorate, such as a PhD, habilitation requires the candidate to write a professorial thesis based on independent...
at the University of Erlangen-Nuremberg, where Jacobs had since moved. In 1968, Strassen moved to the Institute of Applied Mathematics at the University of Zurich
University of Zurich
The University of Zurich , located in the city of Zurich, is the largest university in Switzerland, with over 25,000 students. It was founded in 1833 from the existing colleges of theology, law, medicine and a new faculty of philosophy....
, where he remained for twenty years before moving to the University of Konstanz in 1988. He retired in 1998.
Research
Strassen began his researches as a probabilist; his 1964 paper An Invariance Principle for the Law of the Iterated Logarithm defined a functional form of the law of the iterated logarithmLaw of the iterated logarithm
In probability theory, the law of the iterated logarithm describes the magnitude of the fluctuations of a random walk. The original statement of the law of the iterated logarithm is due to A. Y. Khinchin . Another statement was given by A.N...
, showing a form of scale invariance
Scale invariance
In physics and mathematics, scale invariance is a feature of objects or laws that do not change if scales of length, energy, or other variables, are multiplied by a common factor...
in random walk
Random walk
A random walk, sometimes denoted RW, is a mathematical formalisation of a trajectory that consists of taking successive random steps. For example, the path traced by a molecule as it travels in a liquid or a gas, the search path of a foraging animal, the price of a fluctuating stock and the...
s. This result, now known as Strassen's invariance principle or as Strassen's law of the iterated logarithm, has been highly cited and led to a 1966 presentation at the International Congress of Mathematicians
International Congress of Mathematicians
The International Congress of Mathematicians is the largest conference for the topic of mathematics. It meets once every four years, hosted by the International Mathematical Union ....
.
In 1969, Strassen shifted his research efforts towards the analysis of algorithms
Analysis of algorithms
To analyze an algorithm is to determine the amount of resources necessary to execute it. Most algorithms are designed to work with inputs of arbitrary length...
with a paper on Gaussian elimination
Gaussian elimination
In linear algebra, Gaussian elimination is an algorithm for solving systems of linear equations. It can also be used to find the rank of a matrix, to calculate the determinant of a matrix, and to calculate the inverse of an invertible square matrix...
, introducing Strassen's algorithm, the first algorithm for performing matrix multiplication
Matrix multiplication
In mathematics, matrix multiplication is a binary operation that takes a pair of matrices, and produces another matrix. If A is an n-by-m matrix and B is an m-by-p matrix, the result AB of their multiplication is an n-by-p matrix defined only if the number of columns m of the left matrix A is the...
faster than the O(n3) time bound that would result from a naive algorithm. In the same paper he also presented an asymptotically-fast algorithm to perform matrix inversion, based on the fast matrix multiplication algorithm. This result was an important theoretical breakthrough, leading to much additional research on fast matrix multiplication, and despite later theoretical improvements it remains a practical method for multiplication of dense matrices of moderate to large sizes. In 1971 Strassen published another paper together with Arnold Schönhage
Arnold Schönhage
Arnold Schönhage is a mathematician and computer scientist and Professor Emeritus at Rheinische Friedrich-Wilhelms-Universität, Bonn. He was also professor in Tübingen and Konstanz...
on asymptotically-fast
Big O notation
In mathematics, big O notation is used to describe the limiting behavior of a function when the argument tends towards a particular value or infinity, usually in terms of simpler functions. It is a member of a larger family of notations that is called Landau notation, Bachmann-Landau notation, or...
integer multiplication based on the fast Fourier transform
Fast Fourier transform
A fast Fourier transform is an efficient algorithm to compute the discrete Fourier transform and its inverse. "The FFT has been called the most important numerical algorithm of our lifetime ." There are many distinct FFT algorithms involving a wide range of mathematics, from simple...
; see the Schönhage–Strassen algorithm. Strassen is also known for his 1977 work with Robert M. Solovay
Robert M. Solovay
Robert Martin Solovay is an American mathematician specializing in set theory.Solovay earned his Ph.D. from the University of Chicago in 1964 under the direction of Saunders Mac Lane, with a dissertation on A Functorial Form of the Differentiable Riemann–Roch theorem...
on the Solovay–Strassen primality test, the first method to show that testing whether a number is prime
Prime number
A prime number is a natural number greater than 1 that has no positive divisors other than 1 and itself. A natural number greater than 1 that is not a prime number is called a composite number. For example 5 is prime, as only 1 and 5 divide it, whereas 6 is composite, since it has the divisors 2...
can be performed in randomized polynomial time and one of the first results to show the power of randomized algorithms more generally.
Awards and honors
In 1999 Strassen was awarded the Cantor medalCantor medal
The Cantor medal of the Deutsche Mathematiker-Vereinigung is named in honor of Georg Cantor. It is awarded at most every second year during the yearly meetings of the society...
, and in 2003 he was co-recipient of the Paris Kanellakis Award
Paris Kanellakis Award
The Paris Kanellakis Theory and Practice Award is granted yearly by the Association for Computing Machinery to honor specific theoretical accomplishments that have had a significant and demonstrable effect on the practice of computing...
with Robert Solovay
Robert M. Solovay
Robert Martin Solovay is an American mathematician specializing in set theory.Solovay earned his Ph.D. from the University of Chicago in 1964 under the direction of Saunders Mac Lane, with a dissertation on A Functorial Form of the Differentiable Riemann–Roch theorem...
, Gary Miller
Gary Miller (professor)
Gary Lee Miller is a professor of Computer Science at Carnegie Mellon University, Pittsburgh, United States. In 2003, he won the ACM Paris Kanellakis Award for the Miller–Rabin primality test. He was also made an ACM Fellow in 2002....
, and Michael Rabin
Michael O. Rabin
Michael Oser Rabin , is an Israeli computer scientist and a recipient of the Turing Award.- Biography :Rabin was born in 1931 in Breslau, Germany, , the son of a rabbi. In 1935, he emigrated with his family to Mandate Palestine...
for their work on randomized primality testing. In 2008 he was awarded the Knuth Prize
Knuth Prize
The Donald E. Knuth Prize is a prize for outstanding contributions to the foundations of computer science, named after Donald E. Knuth.-History:...
for "seminal and influential contributions to the design and analysis of efficient algorithms."
External links
- Home page of Dr. Volker Strassen Formulas for fast(er) matrix multiplication and inversion.