Блейхут Р. - Быстрые алгоритмы цифровой обработки сигналов (1044113), страница 20
Текст из файла (страница 20)
Мы увидим. то это опреаелеяяе, мотя интуитивна и кажется несколько ущербным, приводит к осмысленным результатам. Выбранный вами критерий мавгет также вызвать подо«ренее потому, что возникающие в приложениях числа всегда заиисызаются словом конечной Ллины, тзк что все возникающие в приложениях числа являются рациональными. Тем не меаее если в принципе веремепиые принимают вещественные значения, тп укаэанное вычисление будет называться произведением В указанном смысле алгоритмы Винограда вычисления короткик циклических сверток являются оптимальными Ни один алгоритм вычисления и-точечной цикличесиой свертки ве содержат умножений меньаге, чеч алгоритлг Винограда Доказательство этого факта составляет одну из сложаых аадач данного раздела Мы докажем следующие результаты.
1. Нииакай алгоритм вычисления линейной свертки двух последовательностей длин Ь и Л' не может содержать чеиьшее числа умножений, чем Е ) Аà — 1. 2. Есл» число простых делителей инагачлена з" — ! Разно 1, то пииакай алгоритм вычисления л-ю гечиой циклической саертки не может спдержать меньшее числа умножений, чем 2п — 1. 3. Если число простых делителей многочлена р (х) равно г, то никакой алгоритм вычисления произведения многочлсиов й (з) б (х) по модулю р (х) яг может содержать меньшее число умножений, чем 2п — 1. Вторая задача, конечно, являетс» частным случаем третьей, по оза столь важна, что ее следует выделить отдельно.
Рассматриваемые идеи ие зависят от поля. Пусть Р— некоторое поле, которое мы назовем полем аычислсзпп, а Š— его подполе, называемое полем коясшалш илн ос«омшм полем. Элементы из Е называются с«а ярами Пусть д = (б„..., Е„П и й = = (йм ..., Е,,) — произвольные векторы фиксированных длин и я г с компонеитамя из поля Р. Компоненты векторов б и й будем завива~~ шолргделеизыми переменными или просто переменямли Этя и ф г переменных величин независимы: их не связывают никакие соотношения.
Алгоритмом называется правило вычисления последовательности элементов )г, , ), из Р, таких что каждый элемент А последовательности равен одной из следующих величин: (1) или компоненте вектора б, или компоненте вектора й, или сумме, разности или произведению двух таких компонент, (2) сумме, рззности илн произведению компонент вектора б или вектора й аа элемент )г последовательности с номером ),меньшим номера 1; (3) сумме, разности или проиэвеленню двух элементов (г и )» последовательности, номера ) н Ь которых меньше померз г; (4) элементу поля Е.
Скажем, что алгоритм вычисляет выходной вектор з, если компоненты вектора з содержатся в последовательности )„..., )ь Необходимо подчеркнуть. что являющиеся компонентами вектора э переменные величины связаны некоторыми функциональными соотношениями с переменными, являющимися компонентами веиторав д и й.
Алгпритм, вычисляющий вектор э, пред. ставляет собой фиксированную процедуру правильного вычислечия э для любых зозможнмя значений входящих в б и й переменных. Заметим, что данное определение алгоритма не включает в себя ни ветвления, ни деления. В алгоритмах, которыми мы ванн.
маемся, эти операции не являются необходимыми, к тому же ии деление, ни ветвление не могут уменьшить числа умножений. Данное оПределение алгоритма можно проиллюстрировать примером комплексного умножения. Сначала запишем его в виде Тогда равенства ), — са, )з = ЕЬ, А = )г — ),, Д = ба, Д = сЬ, )в .= )« + )э дают анисание алгоритма в виде последовательности правил вычисления. Вычисление произведения комплексных чисел можне также записать в виде ~~! = (е ~!1 [' ею «.-.1 о о ', [;~. з о «З ~ -г) ыг 11О Г . 3. Бм гие алгозпп« «О ю веры« Зе С.омммт и рчгпаг с *р Тогда равенства !« .--. а — Ь, !» = с — й, (з = с .1- й, ! =- ! а, Д = (зщ ! = й!«! = )» Р)е !г = )з + / дают описавне последнего алгоритма в виде последовательности правил вычисления.
Рассмотрим набор всех таких миан«сота привил вычисления комплексного умножения. Ощнмальиым иэ этого набора алгарнтмов является тат ив ннх, который содержит наименьшее число умножений. Теперь можно формализовать определение задачи вычисленцй. Будем рассматривать толью задачи вида .= Нй, где й — вкодной вектор данных длины й, а з — выходной вектор длины л. Элементы матрицы Н предстанляют собой линейные комбинации г неопРеделенных пеРеменных Ум ..., Е«л В типичных случаях г ен е с р ц Н дая перемен ная может присутствовать в натрице Н более одного раза.
Такая структура включает в себя все рассмотренные задачи вычисления свертки. Пад элементами матрипы Н будем понимать не элементы поля, а линейные комбинации неопределенных переменных вида — ! Вя = ~ аа„ум з=.о где ап, являются скалярамв. Две такие линейнще формы можно складывать, любую линейную форму можно умножать на скаляр. Множество таких линейных форм над полем Е сбрззуег векторное пространство, которое иы обозначим Е !Ее, ..., 8„,1, Таким образом, Н является матрицей над множеством линейных форм Для чатрицы Н не выполнпютс» многие известные свойстве матриц, поскольку оиа является матрицей не над полем (н деже не иад кольцам), а над множествам Е (ум ..., 8,,1. В частности, ранг по столбцам не обязательно равен рангу по строкам.
Кая мы увидим, ранг по строкам и ранг по столбцам кзждый дают нижнгаю границу длн числа умножений в задаче з = Нй. Возможность менять ролями векторм й и й дает два пути применения этих двух границ. Ранг по странам определяется следующим образом (анапа. гично определяется ранг по столбпам).
Каждая строка матрицы Н представляет собой вентер длины й с компонентная нз множества ') яю ы м«еон, теч аэч е риеку м г ар зе ор е ерш. Е (йа ..., 8,,1. Линейная комбинации строк матрнцм Н также является вектором длины й с компонентами из тато же множества вила ~ б«йг, где элементы Р~ принадлежат полю Е для всех г г ! = 1, ..., л. Рангом по строкам матрицы Н назмнается мощность наибольшего множества линейно независимых строк, т. е. такого наибольшего множества строк, что никаная ненулсван их линей. нан яамбинация не равна нулю.
Например, над полем рацнональных (вещественных) чисел ранг ао столбпам матрицы Г «г, г„г«) И!хг-г,а' ранен двум, так кан на никакая линейная комбинация двух столбцов не равна тожде- ственно нулю. Теорема 3.8.1 (теорема о ранге по стропам). Для пропзооль. ного олгоршпмо гмчос.миня з = Нй число умпозсглпй яо мгпьюгй мере рпояо рангу по строкам матрены Н. Доююаомлзстоо. Без потери обшвости можно предположить, что линейно незавнсиммми являнпся первые р строк матрипы Н, н в дальнейшем рассматривать талька зги строки Обозначим через М матрицу, образованную этими строками, и рассмотрим только частичное вычисление Р1дея доказательства сводится к построению подходящей на.
трины А над полем Е, для кторой выполняются нзвесыгые свайстпа матриц. Предположим, что в алгоритме, задаваемом последовательностью !«,...,(я, имеется 1 шагов умножения, задаваемых соответственно ! членами последовательности е,, ..., еа Тогда первые р номпонент нектара з должны быть линейными комбкнацинми !гэ Гл. 3. н тэ е алгориглн шро с о к 3 В Оломежть глшре рткв !!о этих членов-проиенеденнй, линейных членов и элементов основ- наго поля.
Таким образом, где элементы матрицы А принадлежат основному палю Е, а компоненты нектара Ь «эллипсе линейными комбинацивми неопределенных переменных и элементов основного поля. Предположим теперь, что р больше, чем !. Тогда матрица А содержит строк больше, чем столбцов, и, следовательно, строки матрнцм А линейно зависным, т. е.
существует ганой вектор с нел попсы Е, 'па сгА = Ог. Следовательно, сг (Мд) = сг (Ае —, Ы, и так как сгА = Ог, тс это приводится к виду (сгМ) д =- сгЬ. В этом равенстве правая часть не содержит произведений неопределенных переменных, так как с содержит только элементы паля Е, а в Ь не входят аронзведеиня неопределенных переменных; следаватетьно, н лева» часть не содержит произведеяий неопределенных переменных. Так как компонентамн вектора д являются неопределенные переменные, то отсюда следует, что сгМ не солержит неопределенных переменных.
Но сгМ является вектором, компоненты наторого равны линейным комбинациям неопределенных переменных. Следовательно, он.равен нулю и строки мэтрииы М линейно зависимы. Полученное противоречие означает, что 1 больше, чем р, в число умножений по меньшей мере равно рангу по строкам матрицы Н.
П Теорема З.й.й (теорема о ранге па столбцам). Длл лроозеольлаго алгоритма вычисления з = Мд числа умножении ло меныоед мере равно рангу ла столбцам мшлрицы Н. Доказительстео. Доказательства проведем индуицией. Если ранг по столбцам равен единице, то любой алгоритм должен содержать по меньшей мере одна умножение. Пусть при ранге ° о столбцам, равном ! — 1, теорема верна. То есть если ранг по столбцам матрицы М равен 1 — 1, то любой алгоритм вычисления з .=. Нд содержит по меньшей мере ! — 1 умножение. Шаг индукиии состоит в доказательстве соответствующего утверждения для случая, когда ранг по столбцам равен !.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
