Блейхут Р. - Быстрые алгоритмы цифровой обработки сигналов (1044113), страница 58
Текст из файла (страница 58)
и а>, г двумерных таблиц равны тем компонен- там 1,«„и е„„, ииденсы которых определяются выписанными выше падстанов«аии. Рассматриваемое уравнение преобразуется при этом в двумерную циклическую свертку! 1(х, у) =8(х, у)о(х, у)(шобх' 2-- 1)(п!обуз — 1), где 8(х, у) равен обобщенному миагочлеиу Рейдера, 2 2-! 8(х, у) = 3,' ~ иу>-'>Рх'у', Г=.« 1=4 !2а 22 Р а о (х, у) и ! (х, у) представляют собой многочаены от двух вере. мемных, надаваемые входными и выколными данными соожзет. отвеина равенствами 355 5 д 8 2"-.
Эпв ~! (х)~ ~у(х) й (х)~ (,(х)~ ч 4 !5 52 148 0 2 2 0 4 з 2 З 25 10 !8 74 36 50 102 Ш4 258 294 аае аш !370 1464 2994 3146 О 0 4 га 68 !аз мж 1 092 2444 Я16 2 8 !6 32 54 !28 258 5!2 1024 8 18 36 95 2Ы 540 1206 ыаг 5620 1 7 а(х, У) —. дг 2. е!, гх'У', ! !(х, у) —. ~ 2' ,!!, х'уг 7'- С 1=.4 Чтобы задать многочлен а (х, у) по компонентам амм, нужно выполнить толька перестановки. Аналогична, для вычисления компонент !ыы по миогачлепу !(х, у) нужны только перестановки. Структуру легче увидеть, если переписать мноючлевы в виде и (х., у) = о, (х) -1 уо, (х), 1(х, у) =- г,(х) ф уг, (х) 7-4 7=4 -Э 1 глеб(х) = 2, и" х' 7-4 Тогда Если ахадные данные вещественны, то 1; 00 .— !е (х) и вычислять надо только и (х) .=. у (к) а, (х) г у' (х) а, (х) (шоб х" ч — 1).
На следующем шаге носпальзуемся разложением «в'4 — 1 -- (хы — П (х"14 ! 1) и китайской теоремой об остатках. Пусть у!ю (х) = у (Н (шоб х"и — !), у!'1(х) = у(х) (шайх"и —,!), и остальные необходимые мнагочлены опрщеленм аналогичным образом. Так как согласно теореме 4.6.3 йи! (х) —. О, та вычислять чадо только члены, содержа1цнс йп! (х)1 Далее воспользуемся алгоритмам 2-точечной циклической свертки 18 (! ) ' ' 1 )й 1(ного !лен — ' (У!'1(х1 + 81п' (х)) содер- 2 жит только вещественные иоэффипиенты, а многочлен — [у' 1(х) и 2 †8'(хЦ содержит сально чисто мнимые коэффициенты. Следовательно, задача свелась к вычислению четырех произведений по модулю к"л -1- 1 ыногочленов с веществениымн коэффициентами.
Теоретически, каждая из этик задач требует п)4 — 1 вещественных умножений; практически известные алгоритмы требуют несколько большего числа умножений. На рис. 10.5 приведена блок-скема описанного рекурсивного вычисления; на рис. 10.б эатабулированы по. л)'гаеыые при этом характеристики ззт у гшг тг Заа Гл ю Б р ы р , о « « * ! 0.5. 0.5. Быстрая траасиозицяя Во время обработки больших дауне ных табли, аженинм, процессо т~ (шщимер, дл» звполгньгаиия (1024 а миллиона, если табли а к ц та лица запоминаетсн во внешней п тим в онератниную память аропессора.
Как ло, л х л).таблица запоминается па стропам) во внешне й паияти, и в ка па столбцам (влв па ждый иомент времени между й памятью и внешней памя амит ю происхолнт обмен олннм цом. мен двух элементов из двух аэличных , ж~а обмьш л ух целых столбцов. Таким считывать л столбцо, ф м, для формирования одной строки мат р атрицы прихопится ф р р ния всех строк приходится в, а для фо ми ова л' стол пов, так что п имое т трвкспсияроаавие матрицы В н считыванию л столбцов тех приложенинх, в кота ых опе перестаью рых оперативная память мала, для ваться алг вки строк я столбцов во ви б иепьней памяти можно пользор р нспозиции.
Ны рассмотрим случай, аритмам ыст ойт а когда оперативная память дап скает зап кш у~ю~ ыломинание двух столбцов о та лицы. о наиболее инте а вать все основные идеи сл чай. Длн т резания (л х л)-таблицы вс уча . Длн транспони. л (ой, л считываний столбцов в о ицы вс внешней памяти алто нтм ' р 'делает ративн ов в опяративную память. Если а опеую память нельзя записать в х прььхма~ю бли оперэтивнан память дону у лнровать, что снижает его эффекпгвн фф ность; если а.чгоритм можно ул опускает запись более двух столбцов, то ьа улучшить на некоторую констант .
Транспанирование матрипы. з ту. прямого р , записанной в оперативной памяти го доступа, является тривиальной задачей, так нак зуется простым изменением ад есов п и вани б ть, что транспонираванн нию е ю та лицы в оперативн ю л р е малых матриц сводится к считыр у вмять н послед)юаему считыааее во внешнюю память Пусть (2 х2 -мат и на блоки размерности 2"'-' — в виде )-матрица А разбита П редположим, что у нас имеет сн способ вычисления матрицы Тогда дл» вычислеаин матрньгы 10.6. Умножеьгие матриц Произведение матриц размерности два можно вмчислить па правила» г,г = апЬгл , а, Ь „ сы = аыЬы -)-аыЬм, сы . аыЬг, -Ь- олгЬлм сы = аыьы -ь- смЬы, нз кшорых следует, ьто так организованное вычисление содержит зо емь умножений и четыре сложения Алгоритм Шшрассгнл позвотяет так органвзовать вычисление, что оно будет содержать сечь умножений В алгоритме 1Втрассена сначала выполняются следуюане вычисления: ш, = (а, — пгг) (Ь (,„+ „,) (Ьы -1.
Ьы), = (а, — а,) (Ь,г .г. Ьы) (.и 4-;,) Ьы, хьстатоьно переставить матрицы Аьг и Аг Это можно сделать, г , и гывэя и одновремеаяо перегтавляа один столбеп из Ап с одним гтолбнам нз Ап Для полной перестановки матриц потребуетсн перепэвить гь(2 пар столбцов (илв л столбцов). г Теперь примении эту идею рекурсивно к вычислению Аьь. А.',, Аь- н Аг., разбивая каждую нз них на падблокн Так «ак Аьь г а А, расположены в одних н тех же столбцнк таблицм, та входя. ане в них транспозицин выполняются перестановкой одних и тех жс сталбпав. Таким образом, каждый урпвень рекурсии ваграм вает л столбцов, а все~о уровней имеется 1ай, л Следовательно. в противоположность прямому чстаду траяспоннрования катрины, годержааечу л' перестановок столбцов, построенный быстрый алгорнтль транспозиаии содержит л 1ой, п перестановок столбцов ззв Г. Ю Б рзт р .тз и г б.
,аз у зм" рзз т, = ом (Ьм — Ьм), т, = о, (Ьзз — Ьп!. т, — -- (о г .)- ш ) Ьм, Затем элементы произведения матриц зычисляютсз по формулам см = т, -'; т, — т, -(- т„ см = т, -<- та т, з- т,, ам тз та 1- тз — т В матрнчнолг виде алгоритм Шграссена записывается равенством !Ьн обо ~ ~о о; о о ~~!ь,, 'и,'обозе~~!,а, о о з,, о.~с~об а„!-~о~о, о).~ об в катаром элементы стоящей в центре даагональнай матрицы вычисляются по правилу а,( = '~ г о о), „ ,а, ~ о а е <а) '<з а Алгоритм Штрассена содержит сечь умножений и )8 сложений. Если одна из двух перемножаемых матриц являетси постоянной и испол зуется много раз, то некоторые слаженна можно вычислить заранее вне процесса умножения н тогда число сложений становится равным <Э.
По сравнению со стандартным алгоритмом умножения . я матриц р тм трассена даже в лучшем случае меняет адно умножение на девять сложений. Практически этот алгоритм умиажеаин матриц разчернасти два не дает преимуществ. Теперь рассиотрим задачу умножения дауа ьгатриц размености л. П ямой р метод такого вычисления требуе~ л уынаженнй р р меря(л — ! л' ( — ) сложений Предположим, что л равно степени да х: оторого целого т; з противном случае доаолниы аух: матрицу справа таким количеством нулевых столбцов и снизу таким количеством нулевых строк, чтобы л стало равным степенй двух.
Произведение натрии С вЂ”. АВ можно разбить иа блоки гзе каждый блок представляе~ собой матрицу размерности 2 — '. Вычисление блоков слева прямым умножением блоков справа тдержит восемь умвожений мтриц размерности л(2 н четыре глажения матрац размерности л)2. Если все эти еычнслеани провозить стандартнымн способами, та полное число умножений будет равна И(л) =8( — ", )' А (л) = 8 ~ х — !) ( ~ ) + 4 < з ) = (» — )ав Иы получили те же самые величины, чта н раньше, так чта стратегия дублирования не приводит к увеличению эффективности, если не носпользоваться некатарымн другими возможностями.
Такие воэможности дает алгоритм Штрассена. Алгоритм Штрассена можно приьтенить на уровне блоковых матриц, так как он не зависит от свойства коччутатииности умно. жения. Итак, применим сначала алгоритм Штрзссена в следую. шем виде: М, = <Ам — Азз)(В ь В *) м, = (Ам --Ам)(Вм+ Вм)* М, —. (А„- Ам) В,, м, = А„(Вм — Вм) м, = Аз ( — Ва) Ит = <Ам+ Аы) Вм.
Блоки матрицы С вычисляются по правилам сп м,-! М,-м,фма См = м, + ин См=-и,+мо ст =м,-и,-<-м,-ми Если матрица А лвляется матрицей констант, то вместо имев. шихся ранее восьми умножений и четырех сложений матрац раз. мерзости л)2,мы получаем семь умножений и тринаж<ать сложений матриц размерности л)2. Если наждсе нз этих вычислений права. дить стандартным способам, то длз полного числа уьгножений получаем м()=у( — ",) = — ', зб О Г. !О Б р ор, ш и ра .Уа.
и зт Р зина что меньше лй Для полного числа сложений имеем () '(2 — ?( — З) Б< — ) ( л+ Э), гго при л ) 20 также меньше, чем (л - — 1) дк Е ще балынее улучшение ласт рекурсивное использование алгоритма Штрассеяа,основанное на разбиении блоков нз ботеемелкие падблоки н использовании тех же самых уравнений В этом случае число умножений рвано М(л) = 7 .= 7~ з "= н~ их == лт ад у, овлетваряет ре. Число сложений вычисляется сложнее Оно удов курени Число сложений больюе числа умножений, но также р кже Растет как лт .
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
