Содержание к диссертации
Введение
1. Перестановки и кронекерово произведение матриц 12
2. Факторизация матриц реверсных перестановок 23
3. Факторизация Кули-Тьюки матрицы Фурье 30
4. Общий подход к вычислению дискретного преобразования Фурье 38
5. Параметрический вариант метода простых множителей 44
6. Параметрический вариант быстрого преобразования Фурье 50
7. Параметрический вариант метода простых множителей с последо вательными перестановками 60
8. Параметрический вариант многомерного быстрого преобразования Фурье 64
9. Быстрое преобразование Фурье малых порядков 73
Литература 87
Приложение. Быстрое преобразование Фурье порядков 2-Ю, 12, 16 94
- Перестановки и кронекерово произведение матриц
- Факторизация Кули-Тьюки матрицы Фурье
- Параметрический вариант метода простых множителей
- Параметрический вариант метода простых множителей с последо вательными перестановками
Введение к работе
Быстрые алгоритмы играют важную роль при обработке дискретных пе-
'Iі риодических сигналов, особенно в многомерном случае. Наиболее популярным и по-прежнему востребованным является быстрое преобразование Фурье (БПФ). Отметим, что теория БПФ далеко не проста [2, 3, 6, 9, 24]. Хороший обзор её развития дан в [40].
Ключевой работой в теории БПФ явилась работа Кули и Тьюки 1965 года [38]. Немаловажную роль в то время сыграло развитие вычислительных средств. В [38] приводится время работы реализации трёхмерного БПФ на «новых» тогда ЭВМ IBM 7094. С тех пор интерес к БПФ не угасает. В известном обзорном отчёте Барраса 1997 года [36] упоминается более 3400 работ по БПФ. Большая часть из них — это работы, связанные с вычислительными аспектами БПФ и вопросами реализации БПФ на различных архитектурах ЭВМ. Вопрос о быстродействии стоит очень остро в связи с обработкой сигналов в реальном времени, а дискретное преобразование Фурье (ДПФ) является базовой операцией для других алгоритмов, и быстродействие системы в целом сильно зависит от эффективной реализации БПФ. Типичные приложения — это цифровые устройства связи, аудио- и видеоустройства.
С развитием микроэлектроники появилось множество микропроцессоров с сильно различающейся архитектурой. В связи с этим встал вопрос об универсальном подходе к реализации БПФ. Самой известной работой в этой области является система FFTW, разработанная Фриго и Джонсоном [42]. Система анализирует вычислительные графы БПФ и адаптирует их для конкретной
вычислительной архитектуры ЭВМ. Для большинства длин периодов и большинства ЭВМ — это самая быстрая реализация БПФ на сегодня. Другой не менее известной работой является проект SPIRAL [48], в котором реализуется новый подход к дискретным преобразованиям, основанный на теории представлений.
Несмотря на то, что эффективные алгоритмы БПФ существуют для практически любых длин периодов, длина, равная степени двойки, остаётся самой популярной. В этом случае БПФ достаточно легко реализуется, и основной вычислительный модуль «бабочка» задаётся всего несколькими инструкциями. Более сложный по реализации, но более эффективный алгоритм БПФ «split-radix» [39, 51] позволяет сократить число вещественных арифметических операций на 20%, а алгоритм, описанный в новой работе [41], — ещё примерно на 6%.
Различные алгоритмы БПФ зависят от арифметических свойств длины периода сигнала. Если эта длина — число составное, то применим алгоритм Кули-Тьюки. Описание различных вариантов алгоритма Кули-Тьюки можно найти в [37]. В случае, когда длина сигнала может быть представлена в виде произведения попарно взаимно простых чисел, применим алгоритм простых множителей, разработанный Гудом в 1958 году [8]. В вычислительном отношении алгоритм простых множителей проще алгоритма Кули-Тьюки.
Если длина сигнала является простым числом, то можно воспользоваться алгоритмом Рейдера [31]. В этом случае задача вычисления ДПФ сводится к задаче вычисления циклической свёртки. Эффектное применение этой идеи нашёл Виноград для вычисления ДПФ небольшой длины [4]. Задача быстрого вычисления циклической свёртки решается с помощью полиномиальной техники. По сути, метод Винограда даёт разложение матрицы Фурье малого порядка в произведение трёх матриц — матрицы предсложений, диагональной матрицы и матрицы постсложений. Такое разложение имеет целью ми-
нимизировать число умножений. Сложения, оптимизируются вручную. Алгоритмы Винограда малых длин эффективно используются в алгоритмах БПФ для составных длин.
Идея факторизации матрицы Фурье представляется наиболее перспективной. Общий подход к построению быстрых алгоритмов связан с разложением матрицы Фурье в произведение слабо заполненных матриц. Поскольку такие разложения не единственны, возникает возможность выбора наилучших в некотором смысле разложений. Впервые на базе кронекерова умножения матриц факторизация матрицы Фурье была получена в работе 1968 года [47]. В этой статье рассматривался вопрос о параллельных вычислениях. Позже в [46] были получены факторизации матрицы Фурье, ориентированные на векторные вычисления. Наиболее полно техника факторизации матриц представлена, в обзорной статье [45]. В ней подробно рассмотрены варианты реализации БПФ на различных архитектурах ЭВМ.
Недавно был разработан новый подход к формированию вейвлет-паке-тов, основанный на построении последовательности ортогональных базисов в пространстве сигналов [11, 12, 23]. Это значительно расширяет возможности цифровой обработки сигналов. Вейвлет-пакеты позволяют получать детальные частотно-временные портреты сигналов, варьируя разрешение (масштабность) по времени и частоте. В этом смысле анализ сигналов с помощью вей-влет-пакетов можно рассматривать как мощное дополнение к традиционному анализу Фурье.
В теории быстрых ортогональных преобразований важную роль играют перестановки. Обычно перестановки особым образом изменяют порядок входных или выходных отсчётов сигнала. Это не всегда удобно. Алгоритмы, не требующие перестановки данных до или после преобразования, получили название «self-sorting». Впервые такой алгоритм БПФ был получен Стокхемом и описан в [37]. Другой алгоритм, основанный на факторизации матрицы
Фурье, был разработан Глассманом [43]. Детально такие алгоритмы рассмотрены в работе [50].
Особенно эффективно идея БПФ работает в многомерном случае. Традиционно используют построчно-столбцевой метод [24, с. 94]. В этом методе для каждой размерности применяется соответствующий одномерный алгоритм БПФ. Более эффективный двумерный алгоритм, похожий на алгоритм Кули-Тыоки, предложил Райворд[49]. Обобщение этого алгоритма было получено в работе [44]. Использовать полиномиальные преобразования для вычисления ДПФ предложили Нуссбаумер и Квенделл [24]. Другой алгоритм с похожими характеристиками был получен в работе [35].
Варианты БПФ основываются на разных представлениях (кодировании) индексов сигнала. Смешанный код используется в методе Кули-Тьюки (если длина периода равна степени двойки, то это бинарный код). Китайский и руритаский коды — в методе простых множителей. М. Б. Свердлик в своих работах [32-34] предложил обобщённое представление индексов, связанное с введением вектора параметров. Это послужило основой для параметрической факторизации матрицы Фурье.
Целью диссертационной работы является:
Исследование различных вариантов факторизации матрицы Фурье на базе кронекерова умножения матриц.
Разработка общего подхода к вычислению ДПФ, основанного на параметрическом кодировании индексов.
Построение параметрического алгоритма БПФ в многомерном случае.
Получение более детальной факторизации матриц Фурье малых порядков.
Данная работа носит теоретический характер. Построена параметрическая теория БПФ. С практической точки зрения все полученные результаты ориентированны на параллельные и векторные вычисления, что особенно актуально в связи с развитием современных технологий.
Приведём краткий обзор содержания диссертации. Работа состоит из девяти параграфов, одной таблицы, одного рисунка, списка литературы и одного приложения. Порядок ссылок на теоремы и формулы определяется двумя числами: первое число указывает номер параграфа, второе — номер теоремы или формулы в параграфе.
В первом параграфе детально анализируется кронекерово умножение матриц [7]. Важным объектом в этой теории является специальная матрица перестановок, которая, как будет видно из следующего параграфа, является матрицей реверсных перестановок. Эта матрица позволяет описать свойство кронекерова умножения матриц заменяющее коммутативность. Стоит отметить важную связь между кронекеровым и обычным произведением матриц. Приводятся различные варианты факторизации кронекерова произведения.
Во втором параграфе рассматривается вопрос о факторизации- матриц реверсных перестановок. Матрицы реверсных перестановок играют важную роль в теории быстрых ортогональных преобразований [6, 11, 12, 45]. Реверс-ные перестановки связаны с переворачиванием смешанного кода целых неотрицательных чисел. В этом параграфе выведены рекуррентные соотношения для матриц реверсных перестановок и на этой основе получены четыре варианта факторизации таких матриц.
В третьем параграфе предлагаются различные варианты факторизации матрицы Фурье по методу Кули-Тьюки на базе кронекерова умножения матриц [6, 45-47]. Рассматривается общий случай смешанного основания. В этом случае БПФ основано на разложении матрицы Фурье в произведение слабо
заполненных матриц специальной структуры, включающих матрицы реверс-ных перестановок, диагональные матрицы вращений и матрицы Фурье малых порядков. В данном параграфе приводятся четыре варианта факторизации матрицы Фурье с сильно различающейся структурой вычислений для соответствующих алгоритмов БПФ.
В четвёртом параграфе представлен усовершенствованный вариант общего подхода к вычислению ДПФ, предложенного М. Б. Свердликом [33]. Этот подход основан на параметрическом представлении индексов по некоторому базису. Рассмотрены три базиса, которые порождают следующие параметрические варианты БПФ: метод простых множителей, БПФ с прореживанием по времени и БПФ с прореживанием по частоте. В заключение рассмотрена обобщённая реверсная перестановка и способ вычисления обратной к ней перестановки.
В пятом параграфе рассматривается параметрический вариант метода простых множителей. Вводится понятие обобщённой эйлеровой перестановки и указан явный вид обратной к ней перестановки. Выведены рекуррентное соотношения для матриц эйлеровых перестановок и приведена их факторизация. В этом параграфе получена наиболее глубокая параметрическая факторизация матрицы Фурье в случае, когда её порядок представим в виде произведения попарно взаимно простых множителей. Представляют интерес самосопряжённые векторы параметров [10]. Приведены примеры самосопряжённых руританских векторов параметров.
В шестом параграфе рассматривается параметрический метод быстрого преобразования Фурье. Введены параметрические перестановки, для которых указаны рекуррентные соотношения и получены факторизации соответствующих матриц. Установлена связь между обобщёнными реверсными перестановками и обычными (непараметрическими). Вводится параметрическая
матрица вращений. В общем случай смешанного основания и произвольного вектора параметров получено наиболее совершенное разложение матрицы Фурье.
В седьмом параграфе на основе предыдущих результатов предложен параметрический вариант метода простых множителей с последовательными перестановками. Для соответствующего алгоритма БПФ не требуется перестановки данных до или после преобразования, а вычисления происходят совместно с перестановками. Получены новые факторизации матриц эйлеровых перестановок. Доказано одно свойство коммутативности, связанное с разложением кроиекерова произведения матриц.
В восьмом параграфе разработан параметрический вариант БПФ в многомерном случае. От многомерного дискретного преобразования можно перейти к кронекерову произведению матриц преобразований по каждому измерению. Каждая из этих матриц может быть параметрически факторизована. В этом параграфе рассматривается общий случай для произвольной матрицы параметров. Приведён пример, демонстрирующий преимущество параметрического подхода. Отметим, что полученный результат может быть использован в методе простых множителей.
Девятый параграф замыкает тему БПФ. Все факторизации матрицы Фурье, рассмотренные ранее, содержат матрицы Фурье малых порядков, которые для более эффективного вычисления ДПФ тоже необходимо факто-ризовать. Виноград в своих работах основывался на разложении матрицы Фурье в произведение трёх матриц — матрицы пределожений, диагональной матрицы и матрицы постсложений. Для минимизации числа сложений предлагается проводить дальнейшую факторизацию матриц предсложений и постсложений на сомножители, в каждой строке которых содержится не более двух отличных от нуля элементов. Такая факторизация неединствен-
на, что позволяет ставить дополнительные условия. В этом параграфе указаны «совершенные» факторизации матриц дискретного преобразования Фурье порядков 3,4, 5,6. Отметим, что при выводе факторизации использовались только элементарные математические средства. В заключение параграфа рассмотрен пример, демонстрирующий, как скалярные операции в алгоритмах БПФ малых порядков преобразуются в векторные и параллельные операции. В приложении диссертации также приведены разложения для порядков 7,8,9,10,11,12,16. Соответствующие алгоритмы БПФ изображены в виде графических схем. В таблице 9.1 указаны характеристики этих алгоритмов.
На защиту выносятся следующие основные результаты:
Выведены рекуррентные соотношения для матриц реверсных перестановок и на этой основе получены четыре варианта факторизации таких матриц.
Получена наиболее глубокая параметрическая факторизация матрицы Фурье. Попутно указаны факторизации матриц параметрических перестановок.
Построена параметрическая факторизация матрицы Фурье в случае, когда её порядок представим в виде произведения попарно взаимно простых множителей. Для этого случая предложен вариант факторизации матрицы Фурье с последовательными перестановками.
Разработан параметрический алгоритм БПФ в многомерном случае для произвольной матрицы параметров.
Усовершенствованы факторизации матриц Фурье малых порядков 3,4,5,6,7,8, 9,10,11,12 и 16.
Основные результаты диссертации опубликованы в работах [15, 17, 18, 22, 29]. Некоторые вопросы по реализации БПФ были рассмотрены в [25].
В ходе работы семинара по дискретному гармоническому анализу и геометрическому моделированию (DHA & CAGD) были сделаны доклады по диссертации [14, 16, 19-21, 27]. В докладе [13] получены факторизации пра-воциркулянтных матриц малых порядков. Вопросы о векторной реализации БПФ были рассмотрены в докладе [28].
В «ЦНИИ «Морфизприбор» автор выполнил НИР «Программы БПФ нетрадиционной длины для сигнальных процессоров DSP96002» и принимал участие в НИР «Разработка алгоритма быстрого ФХН с использованием БПФ малого порядка» в рамках ФНТР института. В 2006 году разработанные программы БПФ были использованы для быстрого формирования характеристик направленности антенных решёток и внедрены в ведущие изделия «Концерн «Океанприбор» (ранее «ЦНИИ «Морфизприбор»). По этим работам были сделаны доклады на конференциях [1, 26, 30].
В 2004 году работа над диссертацией была поддержана грантом Федерального агентства по образованию (шифр гранта А04-2.8-415).
Автор приносит глубокую благодарность всем своим учителям: К. Л. Лейб-сону — учителю математики школы №292, К. Г. Буркову — преподавателю кружка по программирования ГО «Молодёжное», Б. А. Лифшицу — доценту СПбГЭТУ, В. С. Мелькановичу — начальнику сектора «ЦНИИ «Морфизприбор», В. И. Кияеву — доценту СПбГУ. Автор также выражает признательность доценту С. В. Рыбину, который руководил его дипломной работой в СПбГЭТУ (ЛЭТИ). Больше всего автор обязан своему научному руководителю профессору В. Н. Малозёмову. Автор чрезвычайно благодарен своему брату В. В. Просекову за техническую поддержку.
Перестановки и кронекерово произведение матриц
Наиболее популярным и по-прежнему востребованным является быстрое преобразование Фурье (БПФ). Отметим, что теория БПФ далеко не проста [2, 3, 6, 9, 24]. Хороший обзор её развития дан в [40].
Ключевой работой в теории БПФ явилась работа Кули и Тьюки 1965 года [38]. Немаловажную роль в то время сыграло развитие вычислительных средств. В [38] приводится время работы реализации трёхмерного БПФ на «новых» тогда ЭВМ IBM 7094. С тех пор интерес к БПФ не угасает. В известном обзорном отчёте Барраса 1997 года [36] упоминается более 3400 работ по БПФ. Большая часть из них — это работы, связанные с вычислительными аспектами БПФ и вопросами реализации БПФ на различных архитектурах ЭВМ. Вопрос о быстродействии стоит очень остро в связи с обработкой сигналов в реальном времени, а дискретное преобразование Фурье (ДПФ) является базовой операцией для других алгоритмов, и быстродействие системы в целом сильно зависит от эффективной реализации БПФ. Типичные приложения — это цифровые устройства связи, аудио- и видеоустройства.
С развитием микроэлектроники появилось множество микропроцессоров с сильно различающейся архитектурой. В связи с этим встал вопрос об универсальном подходе к реализации БПФ. Самой известной работой в этой области является система FFTW, разработанная Фриго и Джонсоном [42]. Система анализирует вычислительные графы БПФ и адаптирует их для конкретной вычислительной архитектуры ЭВМ. Для большинства длин периодов и большинства ЭВМ — это самая быстрая реализация БПФ на сегодня. Другой не менее известной работой является проект SPIRAL [48], в котором реализуется новый подход к дискретным преобразованиям, основанный на теории представлений.
Несмотря на то, что эффективные алгоритмы БПФ существуют для практически любых длин периодов, длина, равная степени двойки, остаётся самой популярной. В этом случае БПФ достаточно легко реализуется, и основной вычислительный модуль «бабочка» задаётся всего несколькими инструкциями. Более сложный по реализации, но более эффективный алгоритм БПФ «split-radix» [39, 51] позволяет сократить число вещественных арифметических операций на 20%, а алгоритм, описанный в новой работе [41], — ещё примерно на 6%.
Различные алгоритмы БПФ зависят от арифметических свойств длины периода сигнала. Если эта длина — число составное, то применим алгоритм Кули-Тьюки. Описание различных вариантов алгоритма Кули-Тьюки можно найти в [37]. В случае, когда длина сигнала может быть представлена в виде произведения попарно взаимно простых чисел, применим алгоритм простых множителей, разработанный Гудом в 1958 году [8]. В вычислительном отношении алгоритм простых множителей проще алгоритма Кули-Тьюки.
Если длина сигнала является простым числом, то можно воспользоваться алгоритмом Рейдера [31]. В этом случае задача вычисления ДПФ сводится к задаче вычисления циклической свёртки. Эффектное применение этой идеи нашёл Виноград для вычисления ДПФ небольшой длины [4]. Задача быстрого вычисления циклической свёртки решается с помощью полиномиальной техники. По сути, метод Винограда даёт разложение матрицы Фурье малого порядка в произведение трёх матриц — матрицы предсложений, диагональной матрицы и матрицы постсложений. Такое разложение имеет целью ми нимизировать число умножений. Сложения, оптимизируются вручную. Алгоритмы Винограда малых длин эффективно используются в алгоритмах БПФ для составных длин.
Идея факторизации матрицы Фурье представляется наиболее перспективной. Общий подход к построению быстрых алгоритмов связан с разложением матрицы Фурье в произведение слабо заполненных матриц. Поскольку такие разложения не единственны, возникает возможность выбора наилучших в некотором смысле разложений. Впервые на базе кронекерова умножения матриц факторизация матрицы Фурье была получена в работе 1968 года [47]. В этой статье рассматривался вопрос о параллельных вычислениях. Позже в [46] были получены факторизации матрицы Фурье, ориентированные на векторные вычисления. Наиболее полно техника факторизации матриц представлена, в обзорной статье [45].
Факторизация Кули-Тьюки матрицы Фурье
В ней подробно рассмотрены варианты реализации БПФ на различных архитектурах ЭВМ. Недавно был разработан новый подход к формированию вейвлет-паке-тов, основанный на построении последовательности ортогональных базисов в пространстве сигналов [11, 12, 23]. Это значительно расширяет возможности цифровой обработки сигналов. Вейвлет-пакеты позволяют получать детальные частотно-временные портреты сигналов, варьируя разрешение (масштабность) по времени и частоте. В этом смысле анализ сигналов с помощью вей-влет-пакетов можно рассматривать как мощное дополнение к традиционному анализу Фурье.
В теории быстрых ортогональных преобразований важную роль играют перестановки. Обычно перестановки особым образом изменяют порядок входных или выходных отсчётов сигнала. Это не всегда удобно. Алгоритмы, не требующие перестановки данных до или после преобразования, получили название «self-sorting». Впервые такой алгоритм БПФ был получен Стокхемом и описан в [37]. Другой алгоритм, основанный на факторизации матрицы Фурье, был разработан Глассманом [43]. Детально такие алгоритмы рассмотрены в работе [50].
Особенно эффективно идея БПФ работает в многомерном случае. Традиционно используют построчно-столбцевой метод [24, с. 94]. В этом методе для каждой размерности применяется соответствующий одномерный алгоритм БПФ. Более эффективный двумерный алгоритм, похожий на алгоритм Кули-Тыоки, предложил Райворд[49]. Обобщение этого алгоритма было получено в работе [44]. Использовать полиномиальные преобразования для вычисления ДПФ предложили Нуссбаумер и Квенделл [24]. Другой алгоритм с похожими характеристиками был получен в работе [35].
Варианты БПФ основываются на разных представлениях (кодировании) индексов сигнала. Смешанный код используется в методе Кули-Тьюки (если длина периода равна степени двойки, то это бинарный код). Китайский и руритаский коды — в методе простых множителей. М. Б. Свердлик в своих работах [32-34] предложил обобщённое представление индексов, связанное с введением вектора параметров. Это послужило основой для параметрической факторизации матрицы Фурье.
Целью диссертационной работы является: 1) Исследование различных вариантов факторизации матрицы Фурье на базе кронекерова умножения матриц. 2) Разработка общего подхода к вычислению ДПФ, основанного на параметрическом кодировании индексов. 3) Построение параметрического алгоритма БПФ в многомерном случае. 4) Получение более детальной факторизации матриц Фурье малых порядков. Данная работа носит теоретический характер. Построена параметрическая теория БПФ. С практической точки зрения все полученные результаты ориентированны на параллельные и векторные вычисления, что особенно актуально в связи с развитием современных технологий. Приведём краткий обзор содержания диссертации. Работа состоит из девяти параграфов, одной таблицы, одного рисунка, списка литературы и одного приложения. Порядок ссылок на теоремы и формулы определяется двумя числами: первое число указывает номер параграфа, второе — номер теоремы или формулы в параграфе.
В первом параграфе детально анализируется кронекерово умножение матриц [7]. Важным объектом в этой теории является специальная матрица перестановок, которая, как будет видно из следующего параграфа, является матрицей реверсных перестановок. Эта матрица позволяет описать свойство кронекерова умножения матриц заменяющее коммутативность. Стоит отметить важную связь между кронекеровым и обычным произведением матриц. Приводятся различные варианты факторизации кронекерова произведения.
Во втором параграфе рассматривается вопрос о факторизации- матриц реверсных перестановок. Матрицы реверсных перестановок играют важную роль в теории быстрых ортогональных преобразований [6, 11, 12, 45]. Реверс-ные перестановки связаны с переворачиванием смешанного кода целых неотрицательных чисел. В этом параграфе выведены рекуррентные соотношения для матриц реверсных перестановок и на этой основе получены четыре варианта факторизации таких матриц.
Параметрический вариант метода простых множителей
В этом случае БПФ основано на разложении матрицы Фурье в произведение слабо заполненных матриц специальной структуры, включающих матрицы реверс-ных перестановок, диагональные матрицы вращений и матрицы Фурье малых порядков. В данном параграфе приводятся четыре варианта факторизации матрицы Фурье с сильно различающейся структурой вычислений для соответствующих алгоритмов БПФ. В четвёртом параграфе представлен усовершенствованный вариант общего подхода к вычислению ДПФ, предложенного М. Б. Свердликом [33]. Этот подход основан на параметрическом представлении индексов по некоторому базису. Рассмотрены три базиса, которые порождают следующие параметрические варианты БПФ: метод простых множителей, БПФ с прореживанием по времени и БПФ с прореживанием по частоте. В заключение рассмотрена обобщённая реверсная перестановка и способ вычисления обратной к ней перестановки. В пятом параграфе рассматривается параметрический вариант метода простых множителей. Вводится понятие обобщённой эйлеровой перестановки и указан явный вид обратной к ней перестановки. Выведены рекуррентное соотношения для матриц эйлеровых перестановок и приведена их факторизация. В этом параграфе получена наиболее глубокая параметрическая факторизация матрицы Фурье в случае, когда её порядок представим в виде произведения попарно взаимно простых множителей. Представляют интерес самосопряжённые векторы параметров [10]. Приведены примеры самосопряжённых руританских векторов параметров. В шестом параграфе рассматривается параметрический метод быстрого преобразования Фурье. Введены параметрические перестановки, для которых указаны рекуррентные соотношения и получены факторизации соответствующих матриц. Установлена связь между обобщёнными реверсными перестановками и обычными (непараметрическими). Вводится параметрическая матрица вращений. В общем случай смешанного основания и произвольного вектора параметров получено наиболее совершенное разложение матрицы Фурье. В седьмом параграфе на основе предыдущих результатов предложен параметрический вариант метода простых множителей с последовательными перестановками. Для соответствующего алгоритма БПФ не требуется перестановки данных до или после преобразования, а вычисления происходят совместно с перестановками. Получены новые факторизации матриц эйлеровых перестановок. Доказано одно свойство коммутативности, связанное с разложением кроиекерова произведения матриц. В восьмом параграфе разработан параметрический вариант БПФ в многомерном случае. От многомерного дискретного преобразования можно перейти к кронекерову произведению матриц преобразований по каждому измерению. Каждая из этих матриц может быть параметрически факторизована. В этом параграфе рассматривается общий случай для произвольной матрицы параметров. Приведён пример, демонстрирующий преимущество параметрического подхода. Отметим, что полученный результат может быть использован в методе простых множителей.
Девятый параграф замыкает тему БПФ. Все факторизации матрицы Фурье, рассмотренные ранее, содержат матрицы Фурье малых порядков, которые для более эффективного вычисления ДПФ тоже необходимо факто-ризовать. Виноград в своих работах основывался на разложении матрицы Фурье в произведение трёх матриц — матрицы пределожений, диагональной матрицы и матрицы постсложений.
Параметрический вариант метода простых множителей с последо вательными перестановками
Для минимизации числа сложений предлагается проводить дальнейшую факторизацию матриц предсложений и постсложений на сомножители, в каждой строке которых содержится не более двух отличных от нуля элементов. Такая факторизация неединствен на, что позволяет ставить дополнительные условия. В этом параграфе указаны «совершенные» факторизации матриц дискретного преобразования Фурье порядков 3,4, 5,6. Отметим, что при выводе факторизации использовались только элементарные математические средства. В заключение параграфа рассмотрен пример, демонстрирующий, как скалярные операции в алгоритмах БПФ малых порядков преобразуются в векторные и параллельные операции. В приложении диссертации также приведены разложения для порядков 7,8,9,10,11,12,16. Соответствующие алгоритмы БПФ изображены в виде графических схем. В таблице 9.1 указаны характеристики этих алгоритмов.
На защиту выносятся следующие основные результаты: 1) Выведены рекуррентные соотношения для матриц реверсных перестановок и на этой основе получены четыре варианта факторизации таких матриц. 2) Получена наиболее глубокая параметрическая факторизация матрицы Фурье. Попутно указаны факторизации матриц параметрических перестановок. 3) Построена параметрическая факторизация матрицы Фурье в случае, когда её порядок представим в виде произведения попарно взаимно простых множителей. Для этого случая предложен вариант факторизации матрицы Фурье с последовательными перестановками. 4) Разработан параметрический алгоритм БПФ в многомерном случае для произвольной матрицы параметров. 5) Усовершенствованы факторизации матриц Фурье малых порядков 3,4,5,6,7,8, 9,10,11,12 и 16. Основные результаты диссертации опубликованы в работах [15, 17, 18, 22, 29]. Некоторые вопросы по реализации БПФ были рассмотрены в [25]. В ходе работы семинара по дискретному гармоническому анализу и геометрическому моделированию (DHA & CAGD) были сделаны доклады по диссертации [14, 16, 19-21, 27]. В докладе [13] получены факторизации пра-воциркулянтных матриц малых порядков. Вопросы о векторной реализации БПФ были рассмотрены в докладе [28].
В «ЦНИИ «Морфизприбор» автор выполнил НИР «Программы БПФ нетрадиционной длины для сигнальных процессоров DSP96002» и принимал участие в НИР «Разработка алгоритма быстрого ФХН с использованием БПФ малого порядка» в рамках ФНТР института. В 2006 году разработанные программы БПФ были использованы для быстрого формирования характеристик направленности антенных решёток и внедрены в ведущие изделия «Концерн «Океанприбор» (ранее «ЦНИИ «Морфизприбор»). По этим работам были сделаны доклады на конференциях [1, 26, 30].
В 2004 году работа над диссертацией была поддержана грантом Федерального агентства по образованию (шифр гранта А04-2.8-415).
Автор приносит глубокую благодарность всем своим учителям: К. Л. Лейб-сону — учителю математики школы №292, К. Г. Буркову — преподавателю кружка по программирования ГО «Молодёжное», Б. А. Лифшицу — доценту СПбГЭТУ, В. С. Мелькановичу — начальнику сектора «ЦНИИ «Морфизприбор», В. И. Кияеву — доценту СПбГУ. Автор также выражает признательность доценту С. В. Рыбину, который руководил его дипломной работой в СПбГЭТУ (ЛЭТИ). Больше всего автор обязан своему научному руководителю профессору В. Н. Малозёмову. Автор чрезвычайно благодарен своему брату В. В. Просекову за техническую поддержку.
