Ричард Брент

Ричард Брент (англ. Richard Brent; род. 20 апреля 1946, Мельбурн, Австралия) — австралийский математик и специалист в области вычислительной математики, информатики и теории чисел. Наиболее известен своими работами по алгоритмам для вычисления элементарных функций, численному решению уравнений, быстрым алгоритмам для арифметики с плавающей запятой и алгоритмам факторизации целых чисел.

Биография

Ричард Питер Брент родился 20 апреля 1946 года в Мельбурне, Австралия. В 1965 году он поступил в Университет Мельбурна, где в 1968 году получил степень бакалавра с отличием по математике. Затем он продолжил обучение в Стэнфордском университете (США) под руководством Джорджа Форсайта, получив степень магистра в 1970 году и докторскую степень (PhD) в 1971 году. Его диссертация была посвящена алгоритмам минимизации без вычисления производных.

После защиты докторской Брент вернулся в Австралию, где работал в Австралийском национальном университете (АНУ) в Канберре. С 1972 по 1978 год он занимал должность научного сотрудника, а затем профессора в Школе математических наук АНУ. В 1978 году он перешёл в Университет Ньюкасла (Австралия), где стал профессором компьютерных наук и руководителем кафедры. В 1988 году он вернулся в АНУ, где работал до выхода на пенсию в 2011 году, занимая должность профессора в Школе вычислительных наук и Центре математических наук.

Параллельно с академической деятельностью Брент активно участвовал в разработке программного обеспечения и алгоритмов. В 1990-х годах он был одним из ключевых участников проекта по созданию суперкомпьютера Fujitsu AP1000, а также занимался параллельными вычислениями. В 2011 году он стал почётным профессором АНУ.

Научные достижения

Алгоритмы численного анализа

Ричард Брент внёс значительный вклад в численные методы. Он разработал метод Брента (также известный как метод Брента — Деккера) — алгоритм для нахождения корня функции, который сочетает скорость метода секущих и гарантированную сходимость метода бисекции. Этот метод широко применяется в вычислительной математике, в частности, в реализации стандартных библиотек численного анализа (например, в GNU Scientific Library).

В 1973 году Брент опубликовал книгу «Algorithms for Minimization without Derivatives», в которой описал методы оптимизации функций, не требующие вычисления производных. В этой работе он представил алгоритм Брента для минимизации одномерных функций, который также стал стандартным инструментом в численных расчётах.

Вычисление элементарных функций

Брент известен своими работами по быстрому вычислению элементарных функций (синусов, косинусов, логарифмов, экспонент) с высокой точностью. В 1976 году он совместно с Эндрю Яо разработал алгоритм, позволяющий вычислять эти функции с произвольной точностью за время, близкое к линейному относительно числа битов точности. Этот алгоритм основан на использовании модулярной арифметики и быстрого преобразования Фурье.

Теория чисел и факторизация

В области теории чисел Брент внёс вклад в алгоритмы факторизации целых чисел. Он усовершенствовал алгоритм Полларда — «ро»-метод факторизации, предложив вариант, известный как алгоритм Брента — Полларда. Этот метод использует модифицированную последовательность для обнаружения циклов, что позволяет ускорить факторизацию чисел с большими простыми делителями. Алгоритм Брента — Полларда широко применяется в криптографии и при решении задач разложения чисел на множители.

В 1980 году Брент совместно с Джоном Поллардом участвовал в факторизации восьмого числа Ферма (F8 = 2^256 + 1), которое было разложено на множители с использованием алгоритма Брента — Полларда. Это стало одним из ранних примеров успешного применения компьютерных методов для факторизации больших чисел.

Параллельные вычисления и суперкомпьютеры

В 1990-х годах Брент активно занимался параллельными вычислениями. Он участвовал в разработке алгоритмов для суперкомпьютеров, в частности, для системы Fujitsu AP1000. Его работы в этой области включали создание эффективных параллельных алгоритмов для решения линейных систем, умножения матриц и обработки сигналов. Он также исследовал вопросы производительности и масштабируемости параллельных систем.

Основные публикации

Ричард Брент является автором и соавтором более 200 научных статей и нескольких книг. Наиболее значимые из них:

• «Algorithms for Minimization without Derivatives» (1973) — монография, в которой изложены методы оптимизации функций без использования производных, включая алгоритм Брента для минимизации.
• «Fast Algorithms for High-Precision Computation of Elementary Functions» (1976, совместно с Эндрю Яо) — статья, в которой описан метод быстрого вычисления элементарных функций с произвольной точностью.
• «Some Parallel Algorithms for Integer Factorisation» (1990) — работа, посвящённая параллельным алгоритмам факторизации целых чисел.

Награды и признание

За свои достижения Ричард Брент был удостоен ряда наград:

• Премия Ханса Шнайдера (1995) — за вклад в разработку алгоритмов для численного анализа.
• Член Австралийской академии наук (1996) — избран за выдающиеся научные достижения.
• Член Ассоциации вычислительной техники (ACM) (1998) — за вклад в информатику.
• Медаль Института инженеров электротехники и электроники (IEEE) за заслуги в области компьютерных наук (2005) — за разработку алгоритмов, используемых в высокопроизводительных вычислениях.

Интересные факты

• Ричард Брент является одним из пионеров в области использования быстрого преобразования Фурье для вычисления элементарных функций с высокой точностью. Его алгоритмы используются в современных библиотеках произвольной точности, таких как GMP (GNU Multiple Precision Arithmetic Library).
• В 2000-х годах Брент участвовал в проекте по поиску простых чисел Мерсенна, используя распределённые вычисления. Он внёс вклад в разработку алгоритмов, ускоряющих проверку чисел на простоту.
• Брент известен своей работой над алгоритмами для вычисления числа π с рекордной точностью. В 1999 году он совместно с Ясумасой Канадой вычислил π до 206 миллиардов десятичных знаков, используя алгоритм Брента — Саламина (также известный как алгоритм Гаусса — Лежандра).

Источники

• Brent, R. P. (1973). Algorithms for Minimization without Derivatives. Prentice-Hall.
• Brent, R. P., & Yao, A. C. (1976). «Fast Algorithms for High-Precision Computation of Elementary Functions». Journal of the ACM, 23(2), 242–251.
• Brent, R. P. (1980). «An Improved Monte Carlo Factorization Algorithm». BIT Numerical Mathematics, 20(2), 176–184.
• Австралийская академия наук. Профиль Ричарда Брента.
• Ассоциация вычислительной техники (ACM). Список членов ACM.