Фо́лькер Штра́ссен ( нем. Volker Strassen ; род. 29 апреля 1936 , Дюссельдорф , Германия ) — немецкий математик , почетный профессор кафедры математики и статистики Констанцского университета .

Биография

Штрассен родился 29 апреля 1936 года в дюссельдорфском районе Герресхайм. Изучал музыку, философию, физику и математику в нескольких немецких университетах . Докторскую степень по математике он получил в 1962 году в Гёттингенском университете под руководством Конрада Якобса. Затем, занимая должность на кафедре статистики Калифорнийского университета в Беркли он подготовил свою хабилитацию для университета Эрлангена — Нюрнберга , куда переехал Якобс. В 1968 году, Штрассен перешел в Институт Прикладной Математики Цюрихского университета , где проработал двадцать лет. В 1988 году он перешел в Констанцский университет. В 1998 году ушел на пенсию.

Вклад в науку

Свои исследования Штрассен начал как вероятностник. В статье 1964 года «Принцип инвариантности для закона повторного логарифма» он дал функциональную форму закона повторного логарифма , демонстрирующую масштабную инвариантность случайного блуждания . Этот результат, известный сегодня как принцип инвариантности Штрассена или закон повторного логарифма Штрассена , обильно цитировался и был представлен в 1966 году на Международном конгрессе математиков .

В 1969, Штрассен сосредоточил свои усилия на анализе сложности алгоритмов и разработке быстрых алгоритмов. В статье о неоптимальности метода Гаусса он доказал, что для перемножения двух матриц 2 X 2 над некоммутативным кольцом достаточно семи умножений и, используя рекурсию, предложил быстрый алгоритм Штрассена для умножения больших матриц. Это первый алгоритм, который позволяет перемножать большие матрицы за время меньше, чем O( n ³ ) . В той же статье он предложил асимптотически быстрый алгоритм обращения матрицы , основанный на алгоритме быстрого умножения матриц. Этот результат был важным теоретическим прорывом, повлёкшим многочисленные дальнейшие исследования проблемы быстрого умножения матриц. Несмотря на последующие улучшения алгоритм Штрассена остаётся практическим методом умножения больших плотных матриц. Поставленная Штрассеном проблема быстрого умножения матриц по сей день (2015 год) не решена ни в теоретическом , ни в практическом плане.

В 1971 году Штрассен совместно с предложил метод асимптотически быстрого умножения больших целых чисел , основанный на быстром преобразовании Фурье .

В 1977 году он вместе с Робертом Соловеем предложил тест Соловея — Штрассена для определения простоты числа . Это был первый полиномиальный вероятностный алгоритм с ограниченной односторонней ошибкой для определения простоты числа — класс сложности RP . И один из первых результатов, привлекший внимание к возможностям вероятностных алгоритмов.

Был одним из основных создателей теории алгебраической сложности , в которой ему принадлежат многие классические теоремы .

Награды

В 1999 году Штрассен был награждён медалью Кантора , . В 2003 году Фолькер Штрассен, Роберт Соловей , Гари Миллер и Михаэль Рабин получили премию Париса Канеллакиса за вклад в разработку вероятностного тестирования простоты чисел. В 2008 году он получил премию Кнута за «выдающийся вклад в разработку и анализ эффективных алгоритмов.» В 2011 году он получил от .

Примечания

Ссылки

• от 23 июля 2013 на Wayback Machine
• Weisstein, Eric W. (англ.) на сайте Wolfram MathWorld . Формулы для быстрого умножения и обращения матриц.