Т. Кормен, Ч. Лейзерсон, Р. Ривест, К. Штайн - Алгоритмы - Построение и анализ (2 изд.) (1123758), страница 189
Текст из файла (страница 189)
Использование эллипсоидного алгоритма для решения разнообразных задач комбинаторной оптимизации описано в работе Гретшеля (ОгбгзсЬе!), Ловаса (Еочазх) и Шрайвера [134]. Однако на сегодняшний день эллипсоидный алгоритм в практическом применении не может конкурировать с симплекс-алгоритмом. В работе Кармаркара (Каггпагкаг) [172] содержится описание предложенного им алгоритма внутренней точки.
Многие его последователи разработали свои алгоритмы внутренней точки. Хороший обзор этих алгоритмов можно найти в статье Гольдфарба (Оо!б(агЬ) и Тодда (То<Ы) [122] и в книге Е (Уе) [319]. Анализ симплекс-алгоритма относится к сфере активных исследований. Кли (К1ее) и Минти (Мш1у) построили пример, в котором симплекс-алгоритм выполняет 2" — 1 итераций. На практике симплекс-алгоритм работает очень эффективно, и многие исследователи пытались найти теоретическое обоснование этому эмпирическому наблюдению. Исследования, начатые Боргвардтом (Вогнан!!) и продолженные многими другими, показывают, что при определенных вероятностных предположениях об исходных данных симплекс-алгоритм сходится за ожидаемое полиномиальное время. Последних результатов в этой области добились Спилмен (Бр!е1шап) и Тенг (Тепй) [284], которые ввели понятие "сглаженного анализа алгоритмов" и применили его к симплекс-алгоритму.
Известно, что симплекс-алгоритм работает более эффективно в определенных специальных случаях. В частности, заслуживает внимания сетевой симплекс-алгоритм — разновидность симплекс-алгоритма, приспособленная для решения задач сетевых потоков. Для некоторых сетевых задач, включая задачи поиска кратчайшего пути, максимального потока и потока с минимальными затратами, варианты сетевого симплекс-алгоритма достигают результата за полиномиальное время. Обратитесь, например, к статье Орлина [234] и ее ссылкам. ГЛАВА 30 Полиномы и быстрое преобразование Фурье Для выполнения непосредственного сложения двух полиномов степени и требуется время 6 (и), однако для их непосредственного умножения требуется время О (из).
В данной главе мы покажем, как с помощью быстрого преобразования Фурье (БПФ) (газг гоиг(ег Тгапз(опп, РРТ) можно сократить время умножения полиномов до 9 (и 1к и). Наиболее часто преобразования Фурье (а следовательно, и БПФ) используются в обработке сигналов. Сигнал задается во временной области (пше боша(п) как функция, отображающая время в амплитуду. Анализ Фурье позволяет выразить сигнал как взвешенную сумму сдвинутых по фазе синусоид различных частот.
Веса и фазы связаны с частотными характеристиками сигнала в частотной ойласн1и ((гес(оепсу боша1п). Обработка сигналов — обширная область исследований, которой посвящено несколько отличных книг; в примечаниях к данной главе приводятся ссылки на некоторые из них. Полииомы Полиномом (ро1упоппа1) относительно переменной х над алгебраическим полем Е называется представление функции А (х) в виде суммы А(х) = ~ а-ху . Глава 30. Полиномы и быстрое преобразование Фурье 927 значения а1, аз,..., а„1 называются коэффициентами данного полинома.
коэффициенты принадлежат некоторому полю Е, как правило, это множество комплексных чисел С. Говорят, что полипом А (х) имеет степень й, если его старшим ненулевым коэффициентом является аь. Любое целое число, строго большее степени полинома, называется границей степени (бейтса-Ьоцп41) данного полинома. Следовательно, степенью полинома с границей степени и может быть любое целое число от 0 до и — 1 включительно. Для полиномов можно определить множество разнообразных операций.
Например, сложение полиномов (ро1упощ1а! а4Ы111оп): если А (х) и В (х) — поли- номы степени не выше п, то их суммой (зшп) является полинам С (х) степени не выше и, такой что С (х) = А (х) + В(х) для всех х из соответствующего поля. Таким образом, если п-1 В(х) = ~> Ь хз, и-1 С(х) = ~> с хз где с = ау+6 для всех з = 0,1,...,и — 1. Например, если А(х) = бхз+ 7хз— — 10х + 9 и В (х) = — 2х + 4х — 5, то С (х) = 4х + 7хз — бх + 4. Умножение полиномов (ро1упопца1 шц111р!1сабоп): если А (х) и В (х) — полиномы степени не выше и, их произведением (ргобцс1) С (х) является полипом степени не выше 2п — 1, таюй что С (х) = А (х) В (х) для всех х из соответствующего поля.
Вероятно, вам уже доводилось перемножать полиномы, умножая каждый член полинома А (х) на каждый член полинома В (х) и выполняя приведение членов с одинаювыми степенями. Например, умножение полиномов А (х) = бхз+ 7хз -10х+ 9 и В (х) = -2хз+4х-5 можно выполнить следующим образом: бхз + 7хз — 10х + 9 — 2х + 4х — 5 — 30хз — 35хз + 50х — 45 24х4 + 28хз — 40хз + Збх — 12ха — 14хз + 20х4 — 18хз — 12хв — 14хз + 44х4 — 20хз — 75хз + 8бх — 45 Часть ЧП.
Избранные темы 928 По-другому произведение С (х) можно записать как зи-2 С(х)= ~схз, 3=о (30.1) где с =~) аьЬ (30.2) Заметим„что с1ебгее(С) = с1ебгее(А) + с1екгее(В), откуда вытекает, что если А — полипом степени не выше иА, а  — полипом степени не выше ин, то С— полипом степени не выше ил + ил — 1. Тем не менее, поскольку полипом степени не выше к является также полиномом степени не выше /с+ 1, мы будем говорить, что произведение С является полиномом степени не выше иА + ин. Краткое содержание главы 30.1 Представление полиномов Представления полиномов в форме коэффициентов и в форме значений в точках в определенном смысле эквивалентны: полиному, заданному в форме точек- значений, соответствует единственный полипом в коэффициентной форме.
В данном разделе мы познакомимся с обоими представлениями и покажем, как их можно скомбинировать, чтобы выполнить умножение двух полиномов степени не выше п за время тт (и 18 и). В разделе 30.1 описаны два способа представления полиномов: представление, основанное на коэффициентах, и представление, основанное на значениях в точках. Для непосредственного умножения полиномов — уравнения (30.1) и (30.2)— требуется время Э (из), если полиномы представлены при помощи коэффициентов, и только 6 (и), когда они представлены в форме, основанной на значениях в точках. Однако с помощью преобразования представлений можно умножить заданные с помощью коэффициентов полиномы за время О (и 18 и).
Чтобы понять, как это происходит, необходимо сначала изучить свойства комплексных корней из единицы, что и предлагается сделать в разделе 30.2. Затем также описанные в разделе 30.2 прямое и обратное быстрое преобразование Фурье используются для выполнения указанных преобразований представлений. В разделе 30.3 показано, как быстро реализовать БПФ в последовательных и параллельных моделях. В данной главе широко используются комплексные числа, поэтому символ 1 будет использоваться исключительно для обозначения ~/ — Т.
Глава 30. Полиномы и быстрое преобразование Фурье 929 Представление, основанное на коэффициентах Основанным на коэффициентах представлением (сое1йс!епг гергезеп!а!!оп) полинома А (х) = ~ ":о а хз степени не выше п является вектор коэффициентов а = (ао, ам..., а„1). В матричных уравнениях данной главы мы будем считать векторы векторами-столбцами. Основанное на коэффициентах представление удобно при выполнении определенных операций над полиномами. Например, операция вычисления (еча!па!- !ля) полинома А (х) в некой заданной точке хо заключается в вычислении значения А (хо). Если использовать схему Горнери (Ногпег'з гп1е), вычисление требует О (и) времени: А(хо) = И ((а„1)хо+а„з)хо+ +аз)хо+а1)хо+по. Аналогично, сложение двух полиномов, представленных векторами коэффициентов а = (ао,ам...,а„1) и 6 = (Ьо,Ьп...,Ь„|), занимает время О(п): мы просто создаем вектор коэффициентов с = (со, см..., с„1), где с = а + Ь, 3' = О, 1,..., и — 1.
Рассмотрим теперь умножение двух полиномов степени не выше и, А(х) и В (х), представленных в коэффициентной форме. Если использовать метод, описанный уравнениями (30.1) и (30.2), умножение данных полиномов займет время 6 (пз), поскольку каждый коэффициент из вектора а необходимо умножить на каждый коэффициент из вектора Ь. Операция умножения полиномов в коэффициентной форме оказывается гораздо более сложной, чем операции вычисления полинома или сложения двух полиномов.
Результирующий вектор коэффициентов с, заданный формулой (30.2), также называется сверткой (сопчо!щюп) исходных векторов а и 6, и обозначается он как с = а ЗЬ. Поскольку умножение полиномов и вычисление сверток являются фундаментальными вычислительными задачами, имеющими важное практическое значение, данная глава посвящена эффективным алгоритмам их решения. Представление, основанное на значениях в точках Основанным ни значениях в точках представлением (рошьча!пе гергезепгабоп) полинома А (х) степени не выше и является множество, состоящее из и пар точка-значение (ро!пг-ча!пе ра1гз): ((хо,ро),(хырг), ",(х -ыр -1)), таких что все хя различны и уь = А(хь) (30.3) Часть Ч!!.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
