Алгоритмы оптимизации временной сложности кусочно-полиномиальной аппроксимации функций в применении к быстрому преобразованию Фурье на основе параллельного вычисления элементов базиса тема диссертации и автореферата по ВАК РФ 05.13.17, кандидат технических наук Фирсова, Светлана Александровна

• Фирсова, Светлана Александровна
• кандидат технических наук
• 2004

Оглавление диссертации кандидат технических наук Фирсова, Светлана Александровна

ВВЕДЕНИЕ.

ГЛАВА 1. АЛГОРИТМИЧЕСКОЕ ПОСТРОЕНИЕ И ОПТИМИЗАЦИЯ ВРЕМЕННОЙ СЛОЖНОСТИ ОБОБЩЕННОЙ КУСОЧНО-ПОЛИНОМИАЛЬНОЙ СХЕМЫ АППРОКСИМАЦИИ ФУНКЦИЙ ОДНОЙ ДЕЙСТВИТЕЛЬНОЙ ПЕРЕМЕННОЙ.

1.1. Обобщенная схема кусочно-полиномиальной аппроксимации функций на основе полинома Лагранжа.

1.2. Алгоритм и программное моделирование минимизации временной -сложности обобщенной схемы кусочно-полиномиальной аппроксимации функций на основе полинома Лагранжа.

1.3. Алгоритм кусочно-полиномиальной аппроксимации на основе ряда Тейлора в средах Turbo-Basic и Object Pascal в среде Delphi.

1.4. Обобщенная матричная схема параллельного восстановления коэффициентов полинома по его корням.

1.5. Представление неветвящихся вычислительных алгоритмов в форме параллельной программы с детерминированными значениями управляющих индексов.

1.6. Выводы.

ГЛАВА 2. АЛГОРИТМЫ КУСОЧНО-ПОЛИНОМИАЛЬНОЙ АППРОКСИМАЦИИ ФУНКЦИЙ В ПРИМЕНЕНИИ К БПФ НА ОСНОВЕ ПАРАЛЛЕЛЬНОГО ВЫЧИСЛЕНИЯ ЭЛЕМЕНТОВ БАЗИСА.

2.1. Алгоритм аппроксимации суммы ряда Фурье алгебраическими полиномами.

2.2. Параллельные схемы аппроксимации суммы ряда Фурье алгебраическими полиномами.

2.3. Схема параллельного суммирования.ряда Фурье, совмещенная с параллельным вычислением элементов базиса на основе полиномов Чебышева.

2.4. Параллельные схемы вычисления коэффициентов ряда Фурье.

2.5. Разновидность схемы параллельного суммирования ряда Фурье, совмещенной с вычислением элементов базиса.

2.6. Схема последовательного суммирования ряда Фурье, совмещенная с параллельным вычислением элементов базиса.

2.7. Схема параллельного выполнения дискретного преобразования Фурье, совмещенная с параллельным вычислением коэффициентов и элементов базиса.106'

2.8. Совмещение схемы быстрого преобразования Фурье с параллельным вычислением элементов тригонометрического базиса.

2.9. Обобщенные параллельные схемы суммирования разложений по ортогональным полиномам.

2.10. Преобразование ДПФ в форму алгебраического полинома и в кусочно-полиномиальную форму с параллельной схемой выполнения.

2.11. Выводы.

ГЛАВА 3. ЧИСЛЕННЫЙ ЭКСПЕРИМЕНТ ПО ОБОБЩЕННОЙ КУСОЧНО-ПОЛИНОМИАЛЬНОЙ АППРОКСИМАЦИИ ФУНКЦИЙ И ЭЛЕМЕНТОВ БАЗИСА ТРИГОНОМЕТРИЧЕСКИХ ПРЕОБРАЗОВАНИЙ.

3.1. Специфика программной реализации разложения элементарных функций в ряд Фурье с использованием его преобразования к виду алгебраического полинома.

3.2. Численный эксперимент по переводу частичной суммы ряда Фурье в форму алгебраического полинома.

3.3. Устойчивость вычисления базисных функций преобразования Фурье на основе кусочно-полиномиальной аппроксимации.

3.4. Вычисление коэффициентов кусочно-полиномиальной аппроксимации на основе схем, оптимизирующих временную сложность.

3.5. Выводы.

Введение диссертации (часть автореферата) на тему «Алгоритмы оптимизации временной сложности кусочно-полиномиальной аппроксимации функций в применении к быстрому преобразованию Фурье на основе параллельного вычисления элементов базиса»

Актуальность проблемы. Существует широкий круг задач, решаемых на ЭВМ; в которых используется вычисление функций. При этом в практических приложениях, как правило, от методов вычисления функций требуется:

- высокое быстродействие,

- высокая точность их аппроксимации,

- вычислительная устойчивость,

- минимальные затраты объема оперативной памяти и вычислительных ресурсов,

- универсальность схемы вычисления.

Например, сложные многомерные задачи моделирования, которые необходимо решить в течение строго ограниченного времени, в алгоритмах решения содержат большие наборы разнообразных схем вычисления функций. Компьютерная реализация таких схем в целом и вычисления в них функций в частности требует обеспечения высокого быстродействия и высокой точности вычисления. Один из характерных примеров - задачи обработки метеонаблюдений и прогноза погоды. Область решения (пространственно-временной участок атмосферы) разбивается на отдельные пространственные ячейки, временные изменения в каждой ячейке представляются сложной функцией. Требуется точно и с наименьшими затратами времени для каждой ячейки вычислить изменение функции. Например, требование службы погоды Германии, состоит в том, чтобы расчет прогноза на день по локальной модели с заданным пространственным и временным разрешением занимал не более получаса машинного времени. Очевидно, чтобы прогнозировать погоду на большей территории требуется больший объем вычислений при тех же ограничениях по времени.

Эта ситуация усугубляется экстремальными изменениями погоды. Например, перемещение тайфуна над сравнительно небольшой территорией

Японии или Сахалина требует быстро и точно прогнозировать параметры движения тайфуна с целью принятия своевременных оперативных решений.

К категории задач, требующих большого объема оперативной памяти; относятся, задачи, гидро- и аэродинамики^ по расчету течений в условиях сложной пространственно-временной структуры с учетом влияния различных физических и химических процессов.Такие задачи являются, как правило, многомерными, и расчет по каждому направлению хотя бы для нескольких точек требует оперативной памяти, превышающей 10 Гбайт. В квантовой, химии неэмпирические расчеты электронной структуры молекул требуют вычислительных затрат, пропорциональных N 4 или N5, где N условно характеризует число молекул. По этой причине многие молекулярные системы вынужденно исследуются в, упрощенном модельном представлении в виду нехватки вычислительных ресурсов. Программные модели данных процессов включают разнообразный набор функциональных зависимостей.

Время машинной реализации; последних и затраты на их реализацию ресурсов 1 памяти существенно влияют на значения этих параметров для модели в целом. Это приводит к вопросу об оптимизации временной сложности вычисления функций при ограничениях на объем памяти и вычислительные ресурсы.

Сложная взаимозависимость аргументов и1 значений функций при длительности вычислений влечет накопление погрешности. Отсюда возникает требование устойчивости схемы вычисления каждой функции.

В аналогичных ситуациях в моделях гидро- и аэродинамики, в задачах управления,, в частности, летательными и космическими аппаратами имеет место особый аспект - аспект параллельных вычислений, где помимо естественных требований точности и быстродействия возникает специфическое требование синхронизации параллельных процессов вычисления функций.

Следует особо выделить аспект, вычисления тех функций, которые представляются посредством разложения в ряд Фурье. При каждом конкретном количестве отсчетов и конкретном числе элементов базиса как функцию можно рассматривать любую разновидность преобразования Фурье.

Аппаратом преобразований Фурье пользуются во многих областях фундаментальной и прикладной науки, техники. При этом возникают задачи, связанные со скоростью выполнения преобразований Фурье, с сокращением объема вычислений, с повышением точности и вычислительной устойчивости этих преобразований.

Отдельно следует рассматривать аспект, связанный с динамически изменяющимися параметрами выполнения данных преобразований. Сюда следует отнести переменное число элементов дискретного преобразования Фурье (ДПФ) и быстрого преобразования Фурье (БПФ), задание переменного шага отсчета, переменное количество точек отсчета-и, наконец, задание переменной точности вычисления.

Ряды Фурье и ДПФ с динамически изменяющимися параметрами используются, в частности, для представления многочастотной функции в задачах небесной механики, в задачах цифровой обработки изображений или многомерных сигналов, биометрических сигналов и др.

Во всех таких задачах неизменно сохраняется требование высокого быстродействия данных преобразований.

На этой основе актуален синтез эффективных параллельных алгоритмов преобразований Фурье с динамически изменяющимися; параметрами при • сохранении требования вычислительной устойчивости и высокой точности этих преобразований.

Такую постановку вопроса ^ можно рассматривать как важную часть общей постановки вопроса о построении методов аппроксимации функций, обладающих одновременно высокой точностью, устойчивостью и быстродействием. В контексте преобразований Фурье проблема построения таких методов непосредственно относится к быстрому вычислению элементов базиса с динамически меняющимися отсчетами.

При этом как самостоятельная: может рассматриваться проблема параллельного вычисления всех элементов базиса тригонометрических и общего вида ортогональных преобразований с динамически изменяющимися отсчетами, а также проблема синхронизации соответственных параллельных процессов;

Вычисление функций, непосредственно представимых рядом Фурье, возникает при построении математических моделей объектов управления, при этом большое внимание уделяется определению их динамических и вероятностных характеристик /1 /. Такие модели широко используются при решении краевых задач для уравнений в частных производных; задач механики деформируемого твердого тела, цифровой обработке сигналов и цифровой фильтрации / 2, 3/, моделирования оптических систем и синтезированных голограмм, распознавания образов и др. / 4 /,

Помимо отмеченных выше областей применения, цифровая обработка сигналов применяется в таких различных областях / 2 /, как акустика, звуковая локация, радиолокация, сейсмология, связь, системы передачи данных, ядерная техника и др. При этом выделяются характерные параметры сигнала, отделяются шумовые помехи, выполняется приведение сигнала к виду, , который наиболее удобен для пользователя.

Области применения цифровой обработки сигналов постоянно расширяются.

Ряды и преобразования Фурье, помимо отмеченного, непосредственно используются в теории электрических цепей, теории механических и колебательных систем, лазерной оптике и термодинамике. Нетрадиционные аспекты применения рассматриваемых преобразований освещены в / 5, 6 /.

Теория и практика исследований в > области цифровой обработки продолжает активно развиваться / 7 - 20 /.

Существующие схемы вычисления функций, включая схемы вычисления элементов тригонометрического и ортогонального базисов схем цифровой обработки, в рассматриваемых аспектах можно неформально классифицировать следующим образом / 21,22 /.

1. Многочленные приближения.

2. Разложение функций по невязкам.

3. Дробно-рациональные приближения.

4. Итеративные процессы.

5. Сегментная, в ластности, кусочно-полиномиальная аппроксимация.

6. Приближение тригонометрическими полиномами.

Выбор метода аппроксимации функций зависит от постановки задачи в конкретной предметной области.

Ниже приводится сравнительная характеристика наиболее часто применяемых методов. Для определенности эта характеристика дана для случая приближенного вычисления действительной функции одной действительной переменной на конечном промежутке.

Случай, когда вычисляется базис для комплексных ДПФ и БПФ, сводится к рассматриваемому отделением действительной и, мнимой части элементов базиса.

1. Многочленные приближения.

В случае функции одной переменной одним из источников многочленных приближений является разложение функции в степенной ряд Маклорена

Ъкхк (1) 0 или в ряд Тейлора

00 *=0 где х 0 - постоянная величина, являющаяся центром сходимости ряда.

Если функция /(.х) дифференцируема п +1 раз при хе(х0 —г,х0+ г), г =¿0, то для всех ;се(;с0 -г,х0 + г) имеет место формула Тейлора о к\ с остаточным членом

А о

Необходимым и достаточным условием сходимости ряда (2) к функции f(x), xg(x0-г,х0 +г), является выполнение условия lim Rn (х) =0. оо

При счете на ЭВМ используют не только сходящиеся, но и «полусходящиеся» ряды, которые сходятся при малом количестве членов, обеспечивая необходимую точность, и расходятся при увеличении числа членов. При суммировании большого числа членов степенного ряда накапливаются погрешности от входных данных и погрешности, получаемые за счет ограниченной разрядности представления чисел в ЭВМ.

Наиболее часто вычисление приближения производится по схеме Гор-нера, а также по схемам Винограда, Мотцкина - Белаги - Пана / 23 — 29 /.

Схема Горнера для вычисления значения полинома степени и в заданной точке в общем случае требует п операций сложения (вычитания) и п операций умножения. Эта схема широко используется на практике, однако в случае, когда требуется вычислять один и тот же полином многократно и время выполнения операции умножения значительно больше времени выполнения операции сложения, более экономно применять методы Мотцкина - Белаги - Пана.

С целью ускоренного вычисления функций активно развиваются параллельные вычисления полиномов.

Ускорение в этом случае достигается не за счет сокращения количества последовательных операций, а за счет параллельного выполнения взаимно независимых частей аппроксимирующего функцию алгоритма при условии готовности значений данных.

В качестве примера можно привести обобщенную схему Горнера для вычисления значения полинома (алгоритм Дорна / 30, 31/):

Рп(х) = ах" + а х"~т +-■ +а г , х"^ + а х"» + п\ / „ п-т ип апАх"А + ап^тхпА~т +•■• +а г., л х +ахп,+ где [а] - целая часть а; пе — целочисленный остаток от деления п — 1 на т.

Алгоритм заключается в синхронном вычислении всех строк этой записи, преобразованных к виду

После вычисления всех Рпк (х) т полученных значений суммируются по схеме сдваивания.

Временная сложность выполнения алгоритма на т процессорах в асимптотике составит

Т{т) = \ п т где * , гс - соответственно время бинарного умножения и сложения. В частности, при т=п,

Т(п) = 0(\о%2п),

В дальнейшем эта схема будет рассмотрена детально (раздел 2.2).

Достаточно многочисленные примеры аналогичных схем можно найти в/28, 29,31-34/.

Кусочно-полиномиальные варианты многочленных приближений рассматриваются в/35-37/. Как правило, они не основаны на рядах Тейлора и для них не строятся параллельные схемы вычисления.

Кусочно-полиномиальные многочленные приближения отдельно рассматриваются ниже.

Аппроксимация функции одним полиномом на большом промежутке может повлечь для достижения заданной точности значительного увеличения степени полинома, что пропорционально степени повышает объем вычислений. При ограничении степени аппроксимирующего полинома увеличивается погрешность.

Отсюда возникает задача разработки метода аппроксимации функций на такой основе, которая при малой степени полинома могла бы обеспечивать требуемую точность аппроксимации.

2. Разложение функций по невязкам.

Пусть функция у = /(х) задана уравнением

F(x,y) = 0. (3)

В качестве невязки уравнения (3) можно рассмотреть / 21/ значение функции z0=F{x,y0), (4) получающееся при замене точного значения у на у0, которое является приближением функции у=/(х) на заданном отрезке [а, b\. При этом необходимо выполнение условия lim z0 = 0.

У~*Уо

Один из способов получения разложения функций по невязкам состоит в»том, что из уравнения невязки (4) определяется' х0 =O(y0,z0), а из этого уравнения находится искомая функция /(х)=/(ф(у0,г0))• Для наиболее часто употребляемых элементарных функций допускается представление суперпозиции функций f(o(y0,z0)) в явном виде.

В качестве примера разложения функции в ряд невязок можно привести разложение функции у=

Положив

Х-в'' где у о - приближенное значение д> = 1п(х) для хе[а, б], получим

Разложив 1п —— в ряд Тейлора, получим

1-г

Если оставить т членов этого ряда, то абсолютная погрешность приближения оценивается из равенства / 21 / где Л0 - абсолютная погрешность начального приближения у0.

Разложения функций по невязкам имеют достаточно широкое распространение в качестве метода аппроксимации функций. Однако, необходимая точность вычисления функции достигается лишь при условии правильного вьлбора начального приближения, алгоритм нахождения которого может быть достаточно сложным и не обладает универсальностью.

Данный метод не может быть реализован по единой программе в общем случае.

Метод невязок не гарантирует вычисления функции с заданной точностью при заданном количестве операций (за заданное время).

Для данного метода в периодической литературе не предлагаются параллельные алгоритмы реализации.

Отсюда не представляется целесообразным использовать метод для вьшисления элементов базиса преобразований Фурье с динамически меняюд (-)

АГ

2л1н-1)(2т-1)' щимся количеством отсчетов.

3. Дробно-рациональные приближения.

Под дробно-рациональным приближением функции обычно понимается ее приближение вида / 21'/

0 /=0

Общее количество операций для достижения заданной точности при рациональном приближении обычно меньше, чем при многочленном, однако при использовании дробно-рациональных приближений появляется операция деления. Следует иметь в виду, что во многих ЭВМ само деление организуется как приближенное вычисление функции /{х)=х~\ для которой требуется алгоритм, сопоставимый по числу операций с вычислением Як, (х) .

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

Цепную или непрерывную дробь определяют как выражение а\ Ь«\ а2

I ак где -- к-е звено цепной дроби; Ь0 - нулевое звено; а , - частные делители; К

Ь1 - частные знаменатели (/=1, 2,.).

Область и условия сходимости цепной дроби отличается от области - и условий сходимости степенного ряда при разложении одной и той же функции. Поэтому с помощью цепных дробей вычисляют значения1 тех функций, для которых разложение в степенной ряд сходится недостаточно быстро или даже расходится. Помимо того аппроксимация функций в виде цепных дробей используется как, источник получения рациональных приближений. Иногда цепная дробь используется как средство уменьшения количества операций при счете на ЭВМ. При определенных условиях использование аппарата цепных дробей способствует уменьшению накопления погрешностей округления / 39, 40 /. В частности, для. цепной дроби с единичными частными числителями и положительными частными-знаменателями относительная погрешность ее значения асимптотически (с точностью до бесконечно малых первого порядка) не превышает максимальной из относительных погрешностей' ее компонентов независимо от числа звеньев дроби.

Практическое использование цепных дробей ограничивается некоторыми их особенностями. Так, например, при вычислении цепных дробей в режиме с плавающей запятой погрешности округления могут накапливаться быстрее, чем при счете дробно-рациональной функции / 27 /.

Для приближения функции цепной: дробью - требуется выполнить ряд априорных расчетов искомой функции, на конкретной ЭВМ с целью оценки фактических' погрешностей и определения необходимого числа разрядов в машинном представлении числа (в отличие от степенного ряда цепная дробь не имеет общей формулы остаточного члена приближения).

Помимо отмеченных известных затруднений, цепная дробь сама по себе, непосредственно по построению, не допускает эквивалентной записи в параллельной форме. Отсюда вытекает существенное несоответствие тенденции распараллеливания' вычислений и несоответствие архитектуре программного обеспечения параллельных суперкомпьютеров.

Однако необходимо оговориться, что алгоритмическая структура цепной дроби адекватна архитектуре конвейерного типа.

В контексте темы диссертационной работы не просматривается возможность оптимизации временной сложности аппроксимации функций цепными и рациональными дробями на основе средств одной только информатики. Для этой цели требуются специальные математические приемы / 22, 25,

Отсюда проблематично использовать метод для параллельного вычисления элементов базиса преобразований Фурье с динамически меняющимися параметрами.

4. Итеративные процессы.

Примером итеративного процесса является метод «цифра за цифрой».

В алгоритмах вычисления функций, основанные на методах «цифра за цифрой», используются итеративные процессы, позволяющие последовательно определять цифровое значение / -го разряда af искомого значения функции /(х), заданной в позиционной системе счисления.

Большинство алгоритмов рассматриваемого вида разработано для двоичной системы счисления, хотя имеются алгоритмы для десятичной и произвольной систем счисления / 21 /.

Принцип построения алгоритмов «цифра за цифрой» удобно проиллюстрировать на примере.

Пусть требуется вычислить функцию у=log 2 х для х е[1,2). Значения функции, лежащие вне этого интервала, могут быть вычислены с помощью формул

При х е[1,2) значение функции у е(0,1).

Для функции ^=1о§ 2х последовательно вычисляются двоичные разряды результата ai (у = ^а,2 ', ai = 0 или at =1) на основе следующих

27 - 29 /. п формул:

0, если * ] <2 и 1 =дг ] , а1 =0 если х ] >2 и х1+1=2~1х ] , /=1,2,.,«, х0=*.

Процесс позволяет получать последовательно х1,х2,.,хп и одновременно с этим цифры результата а1,а2,.,ап.

Таким образом, данный метод состоит из последовательного по разрядам выполнения операций, которые включают в свой состав арифметику, логические операции и условные переходы по значениям сложных выражений отношения. Длительность работы алгоритма пропорциональна числу разрядов с достаточно большим значением коэффициента пропорции. Схема «цифра за цифрой» по этим причинам не соответствует архитектуре суперкомпьютеров, число разрядов мантиссы- в которых достигает 256 и более цифр / 41 - 47 /. Трудности усугубляются тем, что в описаниях метода, как правило, не указывается зависимость точности, аппроксимации функции от диапазона изменения независимой переменной.

С другой стороны, методы типа «цифра за цифрой» успешно применяются в специализированных устройствах, где упрощается обработка текущего разряда / 48, 49/. Кроме того, очевидной является возможность аппаратной конвейеризации метода в общем случае.

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

5. Сегментная аппроксимация.

Сегментная аппроксимация включает в себя методы кусочной аппроксимации, основанные на разбиении исходного промежутка задания функции на подынтервалы /217. Широко применяются методы сплайновой интерполяции.

Пусть отрезок\а, b] разбит uaN равных .частичных отрезков [хп х1+, j, где х)=a+ih, /=0,l,.,iV-l, xN=b , h=(b-a)/N.

Функцию Sm (x) называют сплайном степени т дефекта к\ если S'm(x)~ полином степени т на частичном отрезке и

SH{x)eCKk[a,b].

На практике наиболее широкое распространение получили сплайны третьей степени, имеющие на [а, b] непрерывную, по крайней мере, первую производную / 50,51 /.

Однако при условии высокой точности резко возрастает количество частичных отрезков, и, как следствие, время вычисления.

Следует заметить, что с возрастанием степени сплайна возрастает число уравнений. системы, по которым согласуются значения производных, поэтому на практике ограничиваются сплайнами невысокой степени.

Неизбежным следствием такого построения является потеря математических характеристик аппроксимируемой функции, связанных со значениями ; производных высшего порядка.

Сегментный метод наиболее близок к методу, конструируемому в диссертационной работе. Главное отличие предложенного метода от известных будет заключаться в том, что его конструкция основана на обобщенном алгоритме, включающем произвольную степень аппроксимирующего полинома; аппроксимацию произвольной функции на произвольном промежутке при произвольном задании границы абсолютной погрешности приближения.

Предложенный метод главным образом ориентирован на параллельные вычисления, хотя обладает существенно высоким быстродействием при последовательной реализации.

В контексте связи сегментной аппроксимации с ДПФ и БПФ можно отметить риск потери гармонических свойств аппроксимируемых элементов базиса. По крайней мере, это очевидно при сплайновой аппроксимации. В более общем случае затруднительно выполнять динамическую оптимизацию временной сложности метода.

6. Приближение тригонометрическими полиномами.

Рассматриваемый способ приближения функций наиболее близок к теме диссертационного исследования - непосредственные примеры такой аппроксимации представляют собой ряды Фурье, ДПФ, БПФ.

Приближения тригонометрическими полиномами используются, как правило, для характеристики качеств аппроксимируемой функции, выражаемых периодическими свойствами / 52 -54 /. Это делается с тем, чтобы получить по возможности адекватное представление о физическом процессе, который выражается посредством аппроксимируемой функции.

В качестве одного из источников приближения функций тригонометрическими полиномами используется интерполяция на основе полиномов Чебышева.

Полиномы Чебышева I и II рода традиционно / 55, 56 / обозначаются Т'п (jc) и Un(x). При этом для цели аппроксимации функций тригонометрическими полиномами используются следующие соотношения:

Тп (х) = cos{п в), х = cos в, rJsin0) = (-l)ícos(2/!0),. (5)

T2n+l (sin в) = (-1)" sin((2 п + 1)0) i (6)

С/п(х) = cosec(0) sin ((и +jc = cos0, sjny)=(-lNc!((2^j (?) cos0

8) cos 0

На этой основе конструируется полином, интерполирующий функцию /(х), следующего вида т

М=1 ЬкТк(х). (9)

-0

Чаще встречаются разложения по ортогональным полиномам / 57 / вида

Рп Тх (х)+с2 Т2 (х)+.+сп Тп (.X),

С0=- {/(соэ в) <19, ск = -~ {/(соэ 9)соб к9с19, (к> 1), Л о л о

10) где Тк (х) — алгебраические полиномы. Такие приближения используются в качестве наилучших среднеквадратичных приближений. С другой стороны приближения (5) — (9) используются как среднеквадратичные приближения функций непосредственно тригонометрическими полиномами, в частности, для приближения функций заданных таблицей по методу наименьших квадратов.

В последнем случае тригонометрические полиномы образуют ряд Фурье / 57 /.

Обе формы интерполяционных полиномов тесно связаны между собой, допуская преобразование одной формы в другую. Эти преобразования основаны на известных рекуррентных зависимостях / 55, 56 /

Тт^х)=2хТт(х)-Ттх(х) | Г0(х)=1, Тх(х) = х )

С/0(*) = 1, их{х) = 2х 1' которые существенно используются в диссертационной работе с целью преобразования не только тригонометрического полинома, но и отрезка ряда Фурье общего вида, а также ДПФ к виду алгебраического полинома по степеням одной независимой переменной.

В качестве другого источника приближения функции тригонометрическими полиномами используется непосредственно разложение функции f(x) в ряд Фурье:

M=^ + £kcos(m;) + 6„sin(ra:)), (13)

2 л=1 где a0,an,bn, (п = 1,2,.) - постоянные числовые коэффициенты. Из (13) получается приближение а м

М* ~ + zk cos(rar) + Ьп sin (га:)). (14)

Z и=1

В приложениях наряду с (13) широко используются интегральное преобразование Фурье / 1 / }/(*)«?-,вя (15) 00 и ДПФ (16) и = 0 а также БПФ.

Известная конструкция последнего заключается в следующем / 58 /. Предположим, что нужно вычислить ДПФ {Х{к)}, к=0,., N - \ последовательности {*(«)}, п=0,., N-1, где N четно. Последовательность (х(и)} можно разделить на две подпоследовательности (g(w)} и {h(n)} следующим образом: g(n)=x(2n), h{n) = x{2n + í), п=0,., ÍV/2-1. (17)

ДПФ двух последовательностей {g (я)} и {h(n)} можно записать в виде

N12-1

G(k)= £ g{n)e'J " , (18) л=0

N12-} . . j

Н(к)= X Ь{п)е~ » , (19) и=0 тогда как (х(А:)} можно выразить через эти четную и нечетную составляющие следующим образом:

N/2-1 4япк

X{k)= £ g(n)e'J " + h(n)e J

2лк(2п+\)\ n=0 или

N/2-l

4япк

Аяпк . 2xк yy/2—1

Z ,k=0,.,N-l. (20)

Из сравнения (20) с (18) и (19) видно, что 2як N

X(k)=G(k) + e N Н(к), 0<к<—-1, 2

Х\к + N

2 як N G{k)-e~ N Н(к), 0<к< --1.

21)

22)

Следовательно, ДПФ последовательности х{п) из N выборок можно получить с помощью ДПФ двух соответствующих подпоследовательностей длиной N/2 выборок g(n) и h{n), используя N дополнительных комплексных умножений. ох4(р)

Рис. 1. х<о) а

Рис. 2.

На рис. 1 представлен граф для одного отсчета 4-точечного БПФ. Формульная запись в этом случае выглядит следующим образом ХМ = [х(0)+х(2)\¥:]+\¥: [х(1)+х(3)^4°].

На рис. 1 символ «О» обозначает множитель .

На рис. 2 представлен полный граф 4-точечного БПФ, формульная запись которого записывается в виде

X:4(*) = [х{0)+х{2)1У2к]+ И? [х{\)+х(з)1Г2к ], к = 0,1,2,3.

Время, необходимое для вычисления ДПФ, пропорционально числу произведений, и при непосредственной реализации это число пропорционально Л^2. Во втором случае, т. е. при*использовании (21) и (22), время вычислений пропорционально 2 (N/2)2 + Ы= (л^2 /2) + ЫыИ1 /2 при больших N. Отметим, что, если число N12 снова четно, можно повторить процедуру, и если N является степенью числа 2, ее можно повторять до тех пор, пока не будет получено преобразование одной точки, которое, очевидно, совпадает с самой точкой. Отсюда полное число комплексных умножений, необходимых для выполнения ДПФ, пропорционально

Сохраняет актуальность проблема сокращения времени вычисления ряда Фурье, БПФ и ДПФ. Такая проблема имеет место как в случае последовательных, так и параллельных вычислений для компьютеров с различной архитектурой /59-63 /.

В периодической литературе дляч всех представленных приближений функции тригонометрическими полиномами, включая (10), (13) - (16), а также (21) - (22), как правило, не рассматривается перевод преобразований Фурье на основе (5) - (8) в полиномиальную форму.

Иными словами, остается не изученной возможность перевода частичной суммы ряда Фурье, ДПФ и БПФ в форму алгебраического полинома по степеням одной переменной; на основе соотношений Чебышева (5) - (12). Преимущество такого перевода заключалось бы: в том, что все вычислительные схемы частичной суммы ряда и преобразований Фурье можно было бы перевести в хорошо изученную область аппроксимации функций полиномами вида (1). В частности, сюда- можно было применить сегментную аппроксимацию / 21, 36 / и хорошо разработанные / 23, 28, 29, 32 - 34 / параллельные схемы вычисления значений полиномов.

Более того, рассматривая частичную сумму ряда Фурье, ДПФ и БПФ ■ как функцию, можно ставить вопрос о свертке этих преобразований в целом посредством; кусочно-полиномиальной аппроксимации в форму полинома фиксировано малой степени.

На основании изложенного актуальной является задача построения обобщенного метода вычисления элементарных функций и их суперпозиций, в схему которого включались бы преобразования Фурье, и который отличался бы высокой вычислительной устойчивостью и быстродействием. Более точно, речь идет о вычислении произвольной функции одной действительной переменной с априори заданной границей: абсолютной погрешности на произвольном промежутке. При, этом целесообразна постановка вопроса об оптимизации временной сложности вычисления функций рассматриваемого вида при заданных ограничений на объем памяти и вычислительные ресурсы.

Применительно к ДПФ и БПФ метод должен сохранять точностные ш сложностные характеристики при параллельном вычислении всех элементов базиса в случае динамически меняющихся параметров.

Цель диссертационной работы состоит в разработке и; исследовании эффективных методов вычисления элементарных функций, их суперпозиций, а также функций одной действительной переменной более общего вида. Сюда включаются тригонометрические полиномы, используемые в качестве базиса ряда Фурье и преобразований Фурье, в.частности, ДПФ и БПФ. От конструируемых методов требуется, чтобы функции рассматриваемого вида могли быть вычислены с априори заданной границей абсолютной-погрешности на произвольном промежутке. При этом должен быть синтезирован: и программно реализован алгоритм оптимизации временной сложности вычисления функций рассматриваемого вида при условии заданных ограничений на объем памяти и вычислительные ресурсы. Методы должны отличаться, регулярностью, единством конструкции, вычислительной устойчивостью, обладать параллелизмом и простотой синхронизации.

Для достижения поставленной цели в диссертационной работе решаются следующие задачи:

1) выполнить синтез и анализ метода и построить на его основе алгоритмы устойчивого вычисления функций одной; действительной переменной с априори заданной границей абсолютной погрешности на произвольном промежутке с оптимизацией временной сложности. при заданных ограничениях на объем памяти и вычислительные ресурсы;

2) в качестве частных случаев общей схемы должны получаться, с одной стороны, классические аппроксимации на основе интерполяционных полиномов Лагранжа, Чебышева и тейлоровских разложений, с другой стороны, - схемы кусочно-полиномиальной аппроксимации, сегментной фрагментации, а также известные параллельные схемы вычисления полиномов;

3) сконструировать и программно реализовать алгоритм оптимизации временной сложности1 вычисления произвольных функций рассматриваемого вида на произвольном промежутке;

4) разработать схему параллельного вычисления сложной суперпозиции элементарных функций, которая позволяет конечную последовательность ярусов ярусно-параллельной формы вычисления суперпозиции заменить одним единственным ярусом без изменения точности аппроксимации; как результат должна достигаться естественная синхронизация параллельных процессов вычисления функций данного вида;

5) выполнить перенос метода на случай функций, аппроксимируемых тригонометрическими полиномами, включая частные суммы ряда Фурье, ДПФ, БПФ и преобразования на основе ортогональных полиномов; исследовать специфику устойчивости, и параллелизма выполнения преобразований Фурье данным методом;

6) разработать алгоритмы параллельного вычисления всех элементов тригонометрического базиса преобразований Фурье и элементов базиса ортогональных полиномов; синтезировать параллельные алгоритмы суммирования ряда Фурье, ДПФ, БПФ, которые позволяют совмещать выполнение: этих преобразований с одновременным вычислением; всех элементов тригонометрического базиса и всех коэффициентов разложений в данном базисе; :

7) дать формальное описание предложенных алгоритмов вычисления функ-• ций и разработать программные модели с целью отладки, проверки работоспособности; оценок временной сложности и вычислительной устойчивости сконструированных методов вычисления функций;

8) провести численный эксперимент по оценке устойчивости и корректности алгоритма оптимизации временной сложности схем вычисления функций.

Методы исследования опираются на использование теоретических основ информатики, численного анализа; теории сложности, прикладной информатики и алгоритмов цифровой обработки сигналов.

Научная новизна диссертационной работы г заключается в построении обобщенного метода* приближенного-- вычисления элементарных, функций; их суперпозиций, а также функций одной действительной переменной более общего вида, включая тригонометрические полиномы, используемые в качестве элементов базиса преобразований Фурье, в том-числе ДПФ и БПФ. Метод обладает параллелизмом, вычислительной устойчивостью и в широком диапазоне точности приближения функций достигает единичной оценки временной сложности их вычисления: Синтезирован алгоритм оптимизации временной сложности; вычисления, функций рассматриваемого вида при условии заданных ограничений на объем памяти и вычислительные ресурсы.

Конкретно, научная новизна результатов может быть охарактеризована следующим образом:

1) предложен метод и сконструированы алгоритмы устойчивого вычисления < функций одной действительной переменной и их суперпозиций с априори заданной границей абсолютной;погрешности на произвольном промежутке с оптимизацией временной сложности при заданных ограничениях на объем памяти и вычислительные ресурсы;

2) предложенные методы и; схемы характеризуются регулярностью, единством конструкции, эффективно распараллеливаются, обладают- естественной синхронизацией и вычислительной устойчивостью; сочетание двух последних качеств с оптимизированной временной сложностью и быстродействием в целом отличают данные методы от известных;

3) предложена алгоритмическая схема параллельного вычисления сложной суперпозиции элементарных функций, которая позволяет конечную последовательность ярусов ярусно-параллельной формы вычисления суперпозиции заменить одним единственным ярусом без изменения точности аппроксимации; существенно при этом, что ярус произвольно заданных функций с готовыми значениями аргументов; приобретает естественную синхронизацию по шагам схемы Горнера вычисления значения аппроксимирующего такие функции полинома;

4) разработаны параллельные схемы суммирования ряда Фурье, ДПФ и БПФ, которые формально достигают логарифмических оценок временной сложности при совмещении их выполнения с параллельным вычислением всех элементов-тригонометрического базиса, а также коэффициентов^ данных тригонометрических разложений; такое совмещение отличает схемы от известных и позволяет выполнять рассматриваемые преобразования при;динамически меняющемся количестве отсчетов и динамически меняющихся коэффициентах разложений; отличительным качеством полученных схем является их инвариантность относительно количества: элементов базиса и относительно выбора шага дискретизации преобразований Фурье; в частности, шаг дискретизации может быть переменным;

5) разработанные схемы преобразований^ Фурье базируются на переводе этих преобразований в форму полинома; что отличает эти схемы от известных по построению и- позволяет применить.для выполнения данных преобразований методы параллельного вычисления полиномов, а также методы кусочно-полиномиальной аппроксимации; 6) разработанные параллельные схемы преобразований Фурье переносятся на случай разложения по ортогональным полиномам с сохранением отли-. чительных динамических характеристик.

Отличительной особенностью предложенной обобщенной схемы от известных схем приближенного вычисления функций является то,, что оптимизация временной сложности достигается алгоритмическими и программными; средствами, в то время как в известных схемах такая оптимизация, как правило, достигается средствами математического анализа.

Основные положения, выносимые на защиту:

1) обобщенная схема устойчивого вычисления функций одной действительной переменной и их суперпозиций с априори заданной границей абсо лютной погрешности- на произвольном промежутке с оптимизацией временной сложности при заданных ограничениях на объем памяти и вычислительные ресурсы;

2) алгоритмическая схема параллельного вычисления сложной суперпозиции элементарных функций, которая позволяет конечную последовательность ^ ярусов ярусно-параллельной формы вычисления? суперпозиции заменить единственным ярусом без изменения точности аппроксимации;

3) параллельные алгоритмы приближенного вычисления функций; аппроксимируемых тригонометрическими полиномами; включая частные суммы ряда Фурье на основе перевода этих сумм в форму алгебраического полинома;

4) алгоритмы параллельного вычисления ДПФ и БПФ, совмещенные с параллельным вычислением коэффициентов и всех элементов тригонометрического базиса в условиях динамически; меняющихся параметров,, включая меняющееся число отсчетов и переменный шаг дискретизации;

5) схема, согласно которой при условии дополнительного времени на априорный перевод ДПФ в форму алгебраического полинома дальнейшее вычисление N -точечного ДПФ может выполняться г параллельно на N процессорах за время 0( 1).

Практическая ценность диссертационного исследования заключается в прикладном характере предложенных методов и алгоритмов. В частности, методы кусочно-полиномиальной аппроксимации могут составлять библиотеку стандартных и встроенных компьютерных программ устойчивого вычисления функций с единичной оценкой времени. Эти методы пригодны для. бортовых вычислителей, их целесообразно применять для синхронизации параллельных процессов вычисления функций; вместе с тем их можно использовать в персональных компьютерах со стандартной: архитектурой. Практически ценны качества минимизации времени вычислений при заданных ограничениях на объем памяти и вычислительные ресурсы, регулярность и общность предложенных схем.Важной для практики цифровой фильтрации.является применимость предложенных методов для параллельного вычисления; всех элементов базиса ортогональных преобразований, включая ДПФ и БПФ. Практическую направленность имеют представленные в диссертации методы; параллельного выполнения ДПФ за логарифмическое число шагов при переменном шаге дискретизации, переменном количестве отсчетов и переменном* числе элементов базиса.

Внедрение и использование результатов работы. Полученные в работе результаты использованы в госбюджетной НИР «Математические методы устойчивой параллельной обработки, поиска и распознавания», код ВНТИЦ 02 0318 206 0355, регистрационный номер 01.2.00 106436; при разработке изделия «Заря-СК» на ФГУП «Таганрогский завод «Прибой»; в учебном процессе кафедры информационных систем и технологий управления Таганрогского государственного педагогического института, что подтверждено соответствующими актами1 об использовании, приведенными в приложении к диссертационной работе.

Апробация работы. Основные результаты работы докладывались на:

- Всероссийской научно-технической конференции с международным участием «Компьютерные технологии в инженерной и управленческой деятельности» (Таганрог, 1999 г.);

- 6-й Международной конференции «Математические модели физических процессов и их свойства» (Таганрог, 2000 г.);

- международной научно-практической конференции «Проблемы образования студентов гуманитарных вузов в свете развития современных информационных технологий» (Таганрог, 2001 г.);

- Международной научно-технической конференции «Интеллектуальные САПР» (Таганрог, 2002 г.);

- научно-технических конференциях профессорско-преподавательского состава и аспирантов ТГПИ (Таганрог, 2000 - 2003 гг.);

- семинаре «Теоретическая и прикладная информатика» кафедры информатики ТГПИ (Таганрог, 2004 г.).

Публикации. По материалам работы опубликовано 8 печатных работ, включая монографию, с общим объемом 14 печатных листов.

Структура и объем работы. Диссертационная работа состоит из введения, 3 глав основного раздела, заключения, списка литературы и 4 приложений. Основное содержание работы изложено на 149 страницах, включая 23 таблицы, 6 рисунков и список литературы из 85 наименований.

Заключение диссертации по теме «Теоретические основы информатики», Фирсова, Светлана Александровна

Основные результаты диссертационной работы заключаются в следующем.

1. Разработаны обобщенные алгоритмы устойчивого вычисления функций одной действительной переменной и их суперпозиций с априори заданной границей абсолютной погрешности на произвольном промежутке. В основе предложенных алгоритмов лежит кусочно-полиномиальная аппроксимация функций рассматриваемого вида. При этом аппроксимация построена таким образом, что временная сложность вычисления функций минимизируется для любой наперед заданной точности приближения.

2. Обобщенный алгоритм включает аппроксимации на основе интерполяционных полиномов Лагранжа, Чебышева и тейлоровских разложений, а также схемы кусочно-полиномиальной аппроксимации, сегментной фрагментации. Каждая из данных разновидностей полиномиальной аппроксимации преобразуется в форму параллельного алгоритма с логарифмической оценкой временной сложности.

3. Сконструирован и программно реализован алгоритм оптимизации временной сложности вычисления произвольных функций рассматриваемого вида на произвольном промежутке. Оптимизация временной сложности достигается на выходе алгоритма, определяющего минимальное значение времени при условии заданных ограничений на объем памяти и вычислительные ресурсы. При этом в широком диапазоне точности достигается оценка^ временной сложности приближенного вычисления функций порядка 0(1).

4. Представлена алгоритмическая схема параллельного вычисления сложной суперпозиции элементарных функций, которая позволяет конечную последовательность ярусов ярусно-параллельной формы вычисления суперпозиции заменить одним единственным ярусом без изменения точности аппроксимации. В результате достигается естественная синхронизация параллельных процессов вычисления функций данного вида.

5. Разработаны схемы параллельного вычисления функций, аппроксимируемых тригонометрическими полиномами. Данные схемы включают устойчивое параллельное вычисление тригонометрического полинома произвольной степени с единичной оценкой временной сложности в том случае, если аппроксимируемая функция является часто повторяющейся.

6. На основе предложенных схем аппроксимации функций разработаны алгоритмы параллельного вычисления всех элементов тригонометрического базиса преобразований Фурье и элементов базиса ортогональных полиномов.

7. Синтезированы параллельные алгоритмы суммирования ряда Фурье, ДПФ,! БПФ, которые позволяют достигать логарифмических оценок временной сложности при совмещении выполнения этих преобразований с: одновременным, вычислением всех элементов тригонометрического базиса и всех коэффициентов разложений в данном базисе.

8. Предложенные алгоритмы параллельных; преобразований Фурье обобщаются на случай разложения по 1 произвольным ортогональным полиномам, в общем случае не зависят от временного интервала снятия отсчетов, инвариантны относительно количества отсчетов и числа членов разложения.

9. Разработанные алгоритмы параллельного вычисления функций, включая элементы тригонометрического базиса, по построению обеспечивают вычислительную устойчивость. Результаты численного эксперимента, представленные в диссертационной работе, иллюстрируют это свойство алгоритмов и подтверждают их математическую корректность.

Научная новизна результатов диссертационной работы заключается в следующем.

1. Предложенная оптимизация временной сложности кусочно-полиномиальных схем приближенного вычисления функций; отличается от известных тем, что достигается алгоритмическими средствами информатики, в то время как известные схемы оптимизации, как правило, используют средства математического анализа.

2. Предложенные методы и схемы характеризуются регулярностью, единством конструкции, эффективно распараллеливаются, обладают естественной синхронизацией и вычислительной устойчивостью; сочетание двух последних качеств с оптимизированной временной сложностью и быстродействием в целом отличают данные методы от известных.

3. Разработанные параллельные схемы суммирования ряда Фурье, ДПФ и БПФ формально достигают логарифмических оценок временной сложности в условиях совмещения их выполнения с параллельным вычислением всех элементов тригонометрического базиса, а также коэффициентов данных тригонометрических разложений. Такое совмещение отличает схемы от известных и позволяет выполнять рассматриваемые преобразования при динамически , меняющемся количестве отсчетов и динамически; меняющихся коэффициентах разложений. Отличительной чертой представленных схем является их инвариантность относительно количества элементов базиса и относительно выбора шага дискретизации преобразований Фурье. В частности, шаг дискретизации может быть переменным.

4. Представленные схемы преобразований Фурье базируются на переводе этих преобразований в форму полинома, что отличает эти схемы от известных по построению и позволяет применить для выполнения данных преобразований методы параллельного вычисления полиномов, а также методы кусочно-полиномиальной аппроксимации.

Практическая ценность диссертационного исследования заключается в прикладном* характере1 предложенных методов и алгоритмов. В частности, методы кусочно-полиномиальной аппроксимации могут составлять библиотеку стандартных и встроенных компьютерных программ устойчивого вычисления функций с единичной оценкой времени. Эти методы пригодны для бортовых вычислителей, их целесообразно применять для синхронизации параллельных процессов вычисления функций, вместе с тем их можно использовать в персональных компьютерах со стандартной архитектурой. Практически ценны качества минимизации времени вычислений при заданных ограничениях на объем памяти и вычислительные ресурсы, регулярность и общность предложенных схем. Важной для практики цифровой фильтрации является применимость предложенных методов для параллельного вычисления всех элементов базиса ортогональных преобразований, включая ДПФ и БПФ. Практическую направленность имеют представленные в диссертации методы параллельного выполнения ДПФ за логарифмическое число шагов при переменном шаге дискретизации, переменном количестве отсчетов и переменном числе элементов базиса.

Практическое использование результатов работы.

1. В НИР «Математические методы устойчивой параллельной обработки, поиска и распознавания», код ВНТИЦ 02 0318 206 0355, регистрационный номер 01.2.00 106436.

2. При разработке изделия «Заря-СК» на ФГУП «Таганрогский завод «Прибой».

3. В учебном процессе кафедры информационных систем и технологий управления Таганрогского государственного педагогического института.

ЗАКЛЮЧЕНИЕ

Список литературы диссертационного исследования кандидат технических наук Фирсова, Светлана Александровна, 2004 год

1. Задирака B.K. Теория вычисления преобразования Фурье. - Киев: Наук, думка, 1983. - 216 с.

2. Оппенгейм A.B., Шафер Р.В. Цифровая обработка сигналов: Пер. с англ. / Под ред. С. Я. Шаца. М.: Связь, 1979. - 416 с.3." Танеев P.M. Математические модели в задачах обработки сигналов. -М.: Горячая линия Телеком, 2002. - 83 с.

3. Аралбаев Т.З., Синицын Ю.И., Матюшко А.И., Тимонин И.В. Об одном подходе к решению распознавания графического образа. Оренбург, гос. ун-т. Оренбург, 2000, 13 е., ил. Библ. 3. Рус. Деп в Винити 20.11.2000, № 2937 В2000.

4. Weaver H.J. Applications of Discrete and Continuous Fourier Analysis, Wiley-Interscience, New York, 1988.

5. Bloomfield P. Fourier Analysis of Time Series: An Introduction, Wiley' Interscience, New York, 1976.

6. Турулин И.И. Под общей ред. JI.K. Самойлова. Расчет и применение быстродействующих цифровых рекурсивных фильтров с конечной импульсной характеристикой: Монография. Таганрог: Изд-во ТРТУ, 1999. -88 с.

7. Блейхут Р. Быстрые алгоритмы цифровой обработки сигналов: Пер. с англ. М.: Мир, 1989. - 448 с.

8. Henson Emden van. Parallel compact symmetric,FFTs // Vector and Parall. Comput,; Issues Appl. Res. and Dev. New York etc., 1989. - P. 153 - 164.

9. Wu Chen-Mie, Chiou Andy. A SIMD-systolic architecture and VLSI chip for the two-dimensional DCL and IDCT // IEEE Trans. Consum. Electron. -1993.-39,№4.-P. 859-869.

10. Нуссбаумер Г. Быстрое преобразование Фурье и алгоритмы вычисления сверток: Пер. с англ. М.: Радио и связь, 1985. - 248 с.

11. Shi Yun-Tao, Hou Zi-Feng, Song Jian-Ping. A parallel fast Fourier transform algorithm on the star interconnection networks. Jisuanji yahjuu ya faz-han=Comput. Res. and Dev. 2002. 39, №5, p. 625 630.

12. Kober V., Cristobal G. Fast recursive algorithms for short-time discrete cosine transform // Electron. Left. 1999. - 35, № 15. - p. 1236 - 1238.

13. Рабинер JL, Гоулд Б. Теория и применение цифровой обработки сигналов: Перевод с англ. / Под ред. Ю. Н. Александрова. М.: Мир, 1978. -848 с.

14. Хуанг Т.С. (Под ред.). Быстрые алгоритмы в цифровой обработке изображений: Пер. с англ. М.: радио и связь, 1984. - 224 с.

15. Гольденберг JI. М. и др. Цифровая обработка сигналов: Учеб. пособие для вузов. 2 изд., перераб. и доп. - М.: Радио и связь, 1990.

16. Умняшкин С.В. Математические методы и алгоритмы цифровой компрессии изображений с использованием ортогональных преобразований// Автореферат диссертации на соискание степени доктора физико-математических наук. Москва. - 2001. - 48 с.

17. Попов Б.А., Теслер Г.С. Вычисление функций на ЭВМ. Справочник. -Киев: Наук, думка, 1985. 600 с.

18. Люк Ю. Специальные математические функции и их аппроксимации. -М.: Мир, 1980. -608 с.

19. Кнут Д. Искусство программирования для ЭВМ. Т. 2. Получисленные алгоритмы. -М.: Мир, 1977. 726 с.

20. Белага Э.Г. О вычислении значений многочленов от одного переменного с предварительной обработкой коэффициентов. Проблемы кибернетики, 1961, вып. 5, с. 7 - 15.

21. Люстерник Л.А., Червоненкис О.А., Янпольский А.Р. Математический анализ: Вычисление элементар. функций. М.: Физматгиз, 1963. - 248 с.

22. Пан В.Я. Некоторые схемы для вычисления значений полиномов с вещественными коэффициентами. Пробл. кибернетики, 1961, вып. 5, с. 17-29.

23. Fike С.Т. Computer evaluation of mathematical function. New Jersey: Prentice-Hall, 1968.-228 p.

24. Winograd S. On the Parallel Evaluation of Certain Arithmetic Expressions. "Journal ACM", 1975, v. 22, № 4, p. 477 492.

25. Winograd S. On the Speed Gained in parallel methods. "New Concepts and Technologies in Parallel Information Processing, Ed. Coianielle, Leiden, Nordhoft, 1975", 1975, p. 155 165.

26. Кнут Д. Искусство программирования для ЭВМ. Т.З. Сортировка и поиск. -М.: Мир, 1978. 844 с.

27. Ромм Я.Е. Бесконфликтные и устойчивые методы детерминированной параллельной обработки / Диссертация на соискание ученой степени доктора технических, наук. Таганрог: ТРТУ. - 1998. - 546 е.; ВНТИ Центр. - № 05.990.001006.

28. Maruyama К. On the Parallel Evaluation of Polynomials // IEEE Trans, on Computers, 1973, v. с 22, № 1, p. 2 - 5.

29. Miranker W.L. A Survey of Parallelism in Numerical Analysys // SIAM Review, 1971, v. B, № 7, p. 524 547.

30. Stone H.S. Problems of parallel computation. In: Complexity of Sequent. Paral Numer. Algor. / Ed. T.F. Traub. N.Y.: Acad. Press, 1973, p. 1 - 16.

31. Смолов В.Б., БайковВ.Д. Анализ табличных и таблично-алгоритмических методов воспроизведения элементарных функций. — Электронное моделирование. 1980, № 1. - С. 22 - 27.

32. Голубков Ю.А. К правильному выбору алгоритмов аппроксимации функций для ЭВМ, работающих в реальном масштабе времени. В кн.: Труды семинара отделения структурных и логических схем. Вып. 3. -М.: Изд-во АН СССР, 1965.

33. Лебедев В.Н. Введение в системы программирования. М.: Статистика, 1975.-312 с.

34. Хованский А.Н. Приложения цепных дробей и их обобщений к вопросам приближенного анализа. М.: Гостехиздат, 1956. - 203 с.

35. Боднарчук П.И., Скоробогатько В.Я. Успехи и задачи теории цепных и ветвящихся цепных дробей. В кн.: Цепные дроби и их применения. Киев: ИМ АН УССР, 1976, с. 5 - 8.

36. Скоробогатько В.Я. Теория ветвящихся цепных дробей и ее применение в вычислительной математике. -М.: Наука, 1983. 312 с.

37. Головкин Б.А. Параллельные вычислительные системы. М.: Наука, 1980.-520 с.

38. Головкин Б.А. Вычислительные системы с большим числом процессоров.-М.: Радио и связь, 1995. -318 с.

39. Воеводин В.В. Некоторые машинные аспекты распараллеливания вычислений. — М.: Материалы семинара «Проблемы вычислительной математики» под руководством Г.И. Марчука. Препринт № 22, 1981. 10 с.

40. Воеводин В.В. Математические проблемы освоения супер-ЭВМ. В кн.: Вычислительные процессы и системы. 2. (Под ред. Г.И. Марчука). - М.: Наука, 1985.-С. 3-12;

41. Воеводин В.В. Математические модели и методы в параллельных процессах. М.: Наука, 1986. - 296 с.

42. Воеводин В.В. Просто ли получить обещанный гигафлоп? // Программирование. 1995. - № 4. - С. 13-23.

43. Воеводин В.В. Массовый параллелизм и декомпозиция алгоритмов // Ж. Вычисл. мат. и мат. физ. 1995. - 35, № 6. - С. 988 - 996.

44. MeggitT. Psevdo Division and psevdo Multiplication Process. IBM J. Res. and Dev., - 1962, - V. 6, № 2. - P. 210 - 226.

45. Voider Т.Е. The CORDIC Trigonometric Computing Technique. IRE on el. Comput. - 1959. - V.E.C. 8, № 3. - P. 330 - 334.

46. Nosenko Yuri L. Approximation of functions by some means of their Fourier series. Facta Univ. Ser. Math. And Inf. Univ. Nis. 1998, № 13, p. 73 77.

47. Сердук A.C. Приближение периодических аналитических функций интерполяционными тригонометрическими полиномами в метрическом пространстве L. Укр. мат. ж. 2002. 54, № 5, с. 692 699.

48. Flynn М.Т. On Division by Functional Iteration // IEEE trans, on Electron. Comput. 1970. - V. c. 19, 8 - P. 702 - 706.

49. Салтыков А.И. Новые программы вычисления элементарных функций на БЭСМ-6. Дубна, 1976. - 48 с. (Препринт Объед. ин-т ядерн. ис-след.: 011-8612).

50. Березин И.С., Жидков Н.Г. Методы вычислений, т.1. М.: Наука, 1970. -464 с.

51. Каппелини В., Константинидис А.Дж., Эмилиани П. Цифровые фильтры и их применение. М.: Энергоатомиздат, 1983 - 360 с.

52. Jleyc В.А. О временной сложности параллельной реализации численного преобразования Фурье. Мат. моделир. 1995. - 7, № 10. - С. 99 - 110.

53. Селезнев М.Е. К вопросу о минимизации числа сложений в алгоритмах вычисления свертки и ДПФ. Курс. гос. технол. ун-т. Курск, 1999. 9 с. Библ. 9. - Рус. - Деп. в ВИНИТИ 03.12.1999, № 3610В99.

54. Jiang Zengzong, Fu Bin. Fast polynomial transform algorithms and parallel algorithms for two-dimensional DFT of arbitrary length // Guofang Keji daxue Xuebao = J. Nat. Univ. Def. Technol. 1995. - 17. № 1. - P. 97 - 103.

55. Gertner I. A new efficient algorithm to compute the two-demensional discrete Fourier transform (DFT) // IEEE Transactions on Acoustic, Speech and Signal Processing, 1988, v. 36, № 7, p. 1036 1050.

56. Кельберт М.Я., Мазель A.E. О быстром вычислении многомерного ДПФ // Проблемы передачи информации, 1991, т. 27, вып. 2, с. 107 110.

57. Ромм Я.Е., Фирсова С.А. Устойчивое распараллеливаемое вычисление функций на основе таблично-алгоритмической аппроксимации с приложениями в численном анализе / Таганрог: Издательство ТРТУ, 1999. 86 с.

58. Ромм Я.Е. Детерминированная организация параллельной числовой обработки по индексам данных // Кибернетика и системный анализ. 1992. - №4. - С. 133 - 152.

59. Алферова З.В. Теория алгоритмов. М.: Статистика, 1973. - 164 с.

60. Солодовников В.И. Верхние оценки сложности решения систем линейных уравнений // В кн.: Теория сложности вычислений. I: Записки научных семинаров ЛОМИ АН СССР. Л;, 1982. - т. 118. - С. 159 - 187.

61. Никулина Г.С., РоммЯ.Е. Методы и программно-аппаратная организация вычисления функций в ЭВМ. I / ТРТИ Таганрог, 1988. - 59 с. Деп. в ВИНИТИ 2.08. 88, № 6192 - В 88.

62. Фадцеева В.Н., Фаддеев Д.К. Параллельные вычисления в линейной алгебре // Кибернетика, 1977, - № 6. - С. 28 - 40.

63. Фаддеева В.Н., Фаддеев Д.К. Параллельные вычисления в линейной алгебре. II // Кибернетика, 1982, - № 3. - С. 18- 31.

64. Ющенко Е.Л. (Под ред.). ФОРТРАН Киев: Вища Школа, 1980 - 400 с.

65. Сир Ж.-К. Метод потока операндов в многопроцессорных системах типа MIMD / Системы параллельной обработки. М.: Мир, 1985. - С. 240 -276.

66. Ромм Я.Е. Об оптимальности архитектуры фон Неймана для ЭВМ в случае параллельных вычислений. I / ТРТИ Таганрог, 1989. - 38 с. ДЕП в ВИНИТИ 20.04.89, № 2613-В89.

67. Ромм Я.Е., Фирсова С.А. Численный эксперимент по таблично-алгоритмической аппроксимации функции рядом Фурье / ТГПИ. Таганрог, 2001. 37 с. ДЕП в ВИНИТИ 13.02.01. № 362-В2001.

68. Dorn W. Generalization of Gorners rules for polynomial evaluation // IBM'J. Res. and Dev. 1962. - V.6, № 2. - P. 239 - 245.

69. Ромм Я.Е., Шаповал В.Г. Некоторые алгоритмы организации параллельных вычислений / ТРТИ Таганрог, 1982. - 80 с. Деп. в ВИНИТИ 23.02.83, №970-83.

70. Munro I;, Paterson М. Optimal algorithms for parallel polynomial evaluation // J. CSS. 1973. - V. 7, № 4. - P. 189 - 196.

71. Hyafil L., Kung H.T. The Complexity of Parallel Evaluation of Linear Recurrences // J. ACM. 1977. - V. C. 23, № 3. - P. 513 - 521.

72. Ston H.S., Kogge P.M. A parallel algorithm for the efficient solution of a general class of recurrence equations // IEEE Trans, on Comput. 1973. - V. C. 22, №8. -P. 386-392.

73. Пьявченко O.H., Сурженко И.Ф., Ромм Я.Е. Метод распараллеливания схемы Горнера и его приложение к цифровым вычислительным устройствам // АВТ. 1978, № 5. - С. 73 - 78.

74. Пьявченко О.Н., Ромм Я.Е., Сурженко И.Ф. О реализации параллельной полиномиальной аппроксимации в многопроцессорной структуре // АВТ. 1981.-№4. -С. 33-40.

75. Heller D.E. On the efficient computation of recurrence relations // ICASE Rep. NASA Langley Res. Confer. Hampton, Va, Dept. Comput. Sci, Carnegie -Mellon Univ., 1974.

76. Xy T.C. Параллельное упорядочивание и проблемы линии сборки. М.: Кибернетический сборник. Новая серия, 1967, вып. 4. - С. 43 - 56.

77. Cooley J.W., Tukey J.W. Math. Сотр., 1965, 19, p. 297 - 301.

78. Родриг Г. (Под ред.). Параллельные вычисления. М.: Наука, 1986. -. 376 с.