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

МИНИСТЕРСТВО ОБРАЗОВАНИЯ РОССИЙСКОЙ ФЕДЕРАЦИИ ТАГАНРОГСКИЙ ГОСУДАРСТВЕННЫЙ ПЕДАГОГИЧЕСКИЙ ИНСТИТУТ

На правах рукописи

Фирсова Светлана. Александровна

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

Специальности:

05.13.17 — Теоретические основы информатики

05.13.18 - Математическое моделирование, численные методы

и комплексы npoгpaмм

АВТОРЕФЕРАТ

диссертации на соискание ученой степени кандидата технических наук

Таганрог 2004

Работа выполнена в Таганрогском Государственном педагогическом институте.

Научный руководитель: доктор технических наук, профессор

Ромм Яков Евсеевич

Официальные оппоненты: доктор технических наук, профессор

Турулин Игорь Ильич

кандидат технических наук, с.н.с. Станишевский Олег Борисович

Ведущая организация: Южно-Российский региональный центр информатизации высшей школы при Ростовском государственном университете

Защита состоится "_"_2004 г. в_часов на заседании диссертационного совета Д 212.259.02 Таганрогского Государственного Радиотехнического университета по адресу (347928, Таганрог, Ростовская область, ГСП-17А, пер. Некрасовский, 44).

С диссертацией можно ознакомиться в библиотеке университета.

Автореферат разослан "__"_2004 г.

Ученый секретарь диссертационного совета Д 212.259.02

абенко Л. К.

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ

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

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

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

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

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

БКБЛИОТЕКА

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Апробация работы. Основные результаты работы докладывались на Всероссийской научно-технической конференции с международным участием «Компьютерные технологии в инженерной и управленческой деятельности» (Таганрог, 1999 г.); 6-й Международной конференции «Математические модели физических процессов и их свойства» (Таганрог, 2000 г.); международной научно-практической конференции «Проблемы образования студентов гуманитарных вузов в свете развития современных информационных технологий» (Таганрог, 2001 г.); Международной научно-технической конференции «Интеллектуальные САПР» (Таганрог, 2002 г.); научно-технических конференциях профессорско-преподавательского состава и аспирантов ТГПИ (Таганрог, 2000 - 2003 гг.); семинаре «Теоретическая и прикладная информатика» кафедры информатики ТГПИ (Таганрог, 2004 г.).

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

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

СОДЕРЖАНИЕ РАБОТЫ

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

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

Постановка задач диссертации выполнена на основе анализа представленных в обзоре методов и схем.

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

Первоначально схема строится на основе интерполяционного полинома Ла-гранжа следующим образом.

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

У = /(х), хь[а,Ь\, О)

где промежуток ^, Ь] произвольно фиксирован. Выбирается система непересекающихся подынтервалов равной длины, объединение которых совпадает с ^, Ь\:

М]=р[*/>*/*.)> (2)

Р для определенности предполагается целой степенью по основанию 2. Таким образом,

={Ь-а)/Р, / = 0,1,...,/»-!, Р = 2', *е{0,1,...}. (3)

При заранее заданной границе е погрешности аппроксимации функций (1) и для каждого отдельно взятого подынтервала из (2), (3) строится интерполяционный полином Лагранжа степени п

£/(*>») J/ -*„) • (4)

где

= l/2((*w -jcJcos((2y + l)^/(2/j + 2))+х„, + *,), j = 0,1,..., п.

С использованием представленного в данной главе видоизменения формул Вие-

та каждое произведение ■*,,) программно преобразуется к виду полинома с

заданными значениями коэффициентов. Коэффициенты умножаются на и

делятся на . при каждом у из (4). Почленное сложение полученных

полиномов влечет окончательное вычисление искомых коэффициентов, в результате полином (4) примет вид

РЛх)=ао„ +аи/х + аи/х2 +-+Я.,/*". (5)

В (5) индекс / коэффициента означает зависимость этого коэффициента от номера подынтервала, индекс /— зависимость того же коэффициента от вида аппроксимируемой функции.

В.дальнейшем коэффициенты (5) делаются хранимыми в памяти компьютера для всех номеров подынтервалов и для каждой функции (1), аппроксимируемой данным полиномом. Полный набор этих коэффициентов определяет затраты памяти. Время вычисления определяется только степенью полинома, поскольку номер подынтервала служит относительным адресом выборки коэффициентов и вычисляется посредством - операции целочисленного деления /=|_(х-а)/А_]., где \ccJ означает

ближайшее целое к а , не меньшее а .

Идея оптимизации заключается в том, что, вычисление коэффициентов (5) начинается для л = 1 при минимальном значении к из (3). В случае невозможности достижения заданной границы погрешности s значение к увеличивается на 1; это продолжается до нарушения допустимых границ значений кг, при их нарушении снова делается переход к минимальному значению к, но уже при л = 2 и т.д. На этой основе достигается минимум временной сложности кусочно-полиномиальной = аппроксимации функции. Схема алгоритма минимизации представлена ниже и реализована программно в общем случае.

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

По схеме Горнера значение этого полинома вычислится за время

'(0 = " (',+'.) (6) где R в /(/?) взято равным единице (в виду последовательности схемы); tr, tc -время бинарного умножения и сложения. При параллельном вычислении набора

функцию у =

функций R равно числу процессоров, одновременно вычисляющих функции набора.

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

/(Л) = 0(1). (7)

За счет уменьшения длины подынтервала степень п в (6) можно сделать «сколь угодно» малой при соответственном возрастании Р"ь--(3) и» увеличения по этой причине количества хранимых массивов коэффициентов.

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

В главе представлены примеры программ на языке Object Pascal в среде Delphi, моделирующим изложенную схему.

В частности, как показывает работа модели, схема позволяет вычислить

с точностью 10"'° за время двух умножений и двух

сложений ценой затрат памяти объемом 3x10" констант (коэффициентов аппроксимирующих функцию полиномов на всей совокупности подынтервалов).

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

По отношению к полиному Лагранжа предложенная схема универсальна, в главе ее построение повторяется для ортогональных полиномов Чебышева. Однако, в том и в другом случае схема не позволяет достигнуть точности аппроксимации, более высокой чем порядка 10~'°. На этой основе с целью повышения точности аппроксимации схема была перенесена на случай аппроксимации функций полиномами Тейлора.

Отличие этой схемы от изложенной состоит в том, что на каждом подынтервале основного промежутка из (2), (3) выбирается средняя точка

_ Х1* I ~Х1 _Х, хоI 2 ~ 2 '

в окрестности которой строится разложение функции

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

Для функций, представимых разложением в ряд Тейлора, схема аппроксимации может быть представлена в виде

/'(*„)

0; л о,=Л*о,);

= + Ан \ Л/,

I/ / V -*„,),£ = 0,1,

(8)

/СО

^(<♦1) / - ° а ли '> л(<»|) / ~~ ^о " аы ' Vе Х1

где аи - предполагаются заранее вычисляемыми числовыми коэффициентами; для

каждого подынтервала и для каждой функции они предполагаются хранимыми в памяти компьютера. Дальнейшее обращение с алгоритмом (8) повторяет обращение с полиномом Ря1(х) из предыдущей схемы.

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

Таблица 1.

Соответствие границы погрешности и степеней полинома, аппроксимирующего функцию у= 1х, хе [1/2, 1]

е к 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15

22 15 И 8 7 6 5 4 4 3 3 3 2 2 2 2

10 м 24 16 12 9 7 6 5 5 4 4 3 3 3 3 2 2

кг» 26 17 13 10 8 7 6 5 4 4 4 3 3 3 3 2

КГ" 28 19 14 11 9 7 6 5 5 4 4 3 3 3 3 3

ю-17 30 20 15 И 9 8 7 6 5 5 4 4 3 3 3 3

ю-18 31 22 16 12 10 8 7 6 5 5 4 4 4 3 3 3

0,5x10 -" 32 22 16 12 10 8 7 6 6 5 5 4 4 3 3 3

В этой таблице е - заданная граница допустимой погрешности аппроксимации, к - степень числа подынтервалов из (3). На пересечении строки и столбца - минимизированная степень аппроксимирующего полинома. Как видно из табл. 1,операцию вычисления корня у = 4х по предложенной схеме можно выполнить за время двух умножений и двух сложений с точностью до 1015.

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

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

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

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

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

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

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

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

Исходные преобразования заключаются в следующем. На основе известных рекуррентных зависимостей для полиномов Чебышева I и II рода Тт(х) и Ue{x) тригонометрические полиномы эквивалентно преобразуются в форму алгебраических полиномов.

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

r„(x)=cos(rt0), jc = cos0, r2„(sin0)= (-1)" cos(2л(9), 7^,(sin0) = (-l)" sin((2«+l>?), (9)

U,(x) = cosec в sin((n +, x = cosd,

gJM^'^+M. ии^^Щ^М, (10)

COS0 cos в

и удовлетворяют рекуррентным зависимостям:

г.С

TmJx) = 2xT (x)-Tm^x) 1

UmJx)=2xU (x)-Um_Ax) 1 0=1, I/,(x) = 2*

Последние можно преобразовать к виду (например, для.Г.(х))

..... ™

отсюда

(14)

(15)

Ш-ШШ-

Аналогичные соотношения получаются и для и (х)

(ШКГо'ГЙШ-

Элементы матрицы можно записать в виде полиномов с явно задан-

ными значениями коэффициентов: при т = 2л -

¿Г ' « (2Л+1)!(«-А:-1)!

(Г-.Т-

аналогичные соотношения для т = 7п+\ приведены в данной главе диссертации.

vV_..»и (n + kjl _w., а » (n + *-l)i

& } (2*+1)!(я-*-1)! U } (2А)!(«-А-1)! )

(16)

Эти соотношения доказаны по индукции и позволяют представить левые части (14), (15) в виде полиномов с окончательными значениями числовых коэффициентов. При этом необходимо заметить, что из (9), (10) следует

c°sM= (-lV TJsmx), cos((2л + 1ш = (-1Y cos х Uи fan л) , sin ((2 л + lVx) = (-1; (sinх), sin(2njc)=(-l/" cos* C/j„_i(sinjc),

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

Если действительная- функция одной действительной переменной f(x) разлагается в ряд Фурье

/(*)=Y + ¿k cos(fix)+Ъ, sin(«x)),

где a0,am,bm, (w = l,2,...) - постоянные числовые коэффициенты, то в результате рассматриваемых преобразований получим:

/ о

+ I <(-1)" Ти (го) + Ъи (-1)"' Z, ÍV, (г,).

(17)

После подстановки полученных выражений в (17) и приведения подобных получим окончательное представление произвольной частичной суммы правой части в виде алгебраического полинома

р. (*) = с0+ с,х + с2х2 + с,х' + ••• + с.х"» (18)

где значения с, получены путем рассматриваемого преобразования. При этом

/(*)*/>„(*). (19)

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

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

Если исходная функция является часто повторяющейся, то коэффициенты с, можно рассчитать априори и хранить в памяти компьютера. Тогда при переменном х правую часть (18) можно вычислять с помощью известных параллельных схем для полиномов. В результате, если (19) удовлетворяет заданной точности приближения, то с такой точностью сумму ряда Фурье можно приблизить с временной сложностью r(/?)=o(log2 п), где R, как и в (7), - количество процессоров, которое в

данном случае определяется равенством R=n.

Заметив, что сам полином (18) можно преобразовать путем кусочно-полиномиальной аппроксимации по схеме предыдущей главы, приходим к выводу о том, что сумму ряда Фурье можно аппроксимировать с наперед заданной точностью с единичной оценкой временной сложности т(п)= O(l). Последняя имеет место согласно (6), (7).

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

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

2<

чений/я из (И)-(15) первоначально находятся все двоичные степени А , I = 0,1,2,..., где 2' £т, А= ^2|* , по схеме:

Вычисления (20) производятся до тех пор, пока не выполнится неравенство т й 2', - за число шагов (_1о^ т\. Комбинацией найденных двоичных степеней можно образовать любую из предшествующих степеней А', для каждого £ = 1,2,...,т. Значению

1.1°« О

lWJ . fo

е= X or,.2\ I =1,2,...,т.

í-o L1

(21)

можно взаимно однозначно сопоставить процессор с номером £ (из числа априори выбранных 0{тп) процессоров). Тогда все такие процессоры, работая параллельно и синхронно, найдут все степени матрицы А,Аг,А\...,Ат за число шагов A[log2mj умножения матриц порядка 2 х2. По окончании этого процесса можно найти все полиномы Чебышева первого рода Т[х) путем домножения степеней на вектор

Аналогично, путем их домножения на в е к т j^j j овременно могут

быть получены все полиномы Чебышева второго рода Ut '\x).

Отсюда, по представленным выше соотношениям, оказываются выраженными все значения элементов тригонометрического базиса sin (¿г) и eos (¿с), ¿=1,2,...,«.

Остается найденные значения sin (¿г) и cos(&c) умножить на соответствующие значения коэффициентов а, и Ь(., чтобы окончательно получить все элементы ряда Фурье: а0, a, cosx, bx sin х, аг cos 2х, b¡ sin 2х,..., am cos mx, bm sin mx.

Для параллельного вычисления суммы m элементов данного ряда полученные значения можно сложить по схеме сдваивания за время T"(w)=(|_Iog2 m\+1) tc.

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

7-(«)=0(log2nJ, (22)

где количество процессоров

Эта и другие предложенные в главе схемы позволяют параллельно вычислять не только элементы тригонометрического базиса, но и сами коэффициенты ряда Фурье. При этом оба процесса могут быть совмещены во времени. Оценка временной сложности такой схемы r(w/A)=o(log2 и), где h - шаг интегрирования.

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

Для одного отсчета х=сот1 при вычислении ДПФ фактически (с точностью до формальных оговорок) можно повторить каждую из схем, предложенных для ряда Фурье. Для N отсчетов такие схемы могут выполняться параллельно.

Для последовательности хв, n=Q,l,...,N-l ДПФ определяется формулой

хЛк)=%*(")К. (23)

где множитель

(24)

го тригонометриче(

. (. 2лЛ (, lit\ sin кп— . cos кп— Хшя I N)' I N)

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

Значения всех элементов базиса sin Цп— , cos шя всех значений

л=0,1,...,//—1, можно вычислить параллельно по представленным выше схемам за время г(/?)=о(^2гу), где Я=й(^. Данные элементы базиса требуются для всех значений £ = 1,2,...,Ы, поэтому требуется в N раз увеличить число процессоров для максимально параллельного вычисления одновременно при всех рассматриваемых

кип.

Дальнейшее вычисление ДПФ (23) можно произвести путем параллельного умножения на все коэффициенты с применением схемы сдваивания для суммирования при каждом отдельно взятом отсчете, параллельно по всем отсчетам. Отсюда ТУ -точечное ДПФ, ограниченное N членами., может быть вычислено на К2 процессорах с временной сложностью т(ы 2 Л^), причем оценка включает вычисление всех элементов тригонометрического базиса ДПФ.

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

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

На основе представленных схем параллельного вычисления элементов тригонометрического базиса предлагается организовать совмещение схемы выполнения БПФ с параллельным вычислением элементов этого базиса.

Общая запись БПФ представима в виде

(*)= ¿(2+ К 2r + lK* ,

где W* из (24) может быть вычислен по предложенным схемам. В данном случае временная сложность выполнения алгоритма БПФ, совмещенного с параллельным вычислением всех элементов тригонометрического базиса, будет оцениваться из соотношения 7'(/i)=0(logjAr), R=Nlog1N . При этом базис вычисляется с использованием схемы (20), (21), и предполагается предварительная рассылка степеней (20) в узлы схемы «бабочки» БПФ с учетом их повторяющихся, согласно схеме БПФ, значений. Они параллельно вычисляются до окончательных значений (21) во всех узлах при одновременном выполнении операций БПФ.

Если использовать кусочно-полиномиальную схему аппроксимации одновременно каждого из N элементов базиса, то потребуется N процессоров и будет достигнута временная сложность О{1). Полученные данные априори рассылаются по схеме «бабочка». Затем N процессоров синхронно переходят от яруса к ярусу «бабочки», параллельно выполняя все операции яруса N -точечного БПФ. В таком варианте схемы временная сложность выполнения N -точечного БПФ с N элементами базиса составит г^)=О(к^2 N), где R=N — число процессоров.

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

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

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

Известна

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

Q~,{*)={4.* + B.)Q.{x)-C.Q^{x). « = 1,2,... . (25)

На основе соотношения (25) предложенные для ряда и преобразований Фурье схемы можно перенести на случай аналогов этих преобразований, основанных на разложениях по ортогональным полиномам. Из (25) следует

гДе 0оОО=Ь й (*)=•* • Применяяк произведению в цоавой части аналог схемы Стоуна (20), (21), можно утверждать, что значения (?<(*)> ¿=0,1,...,и, могут быть параллельно вычислены для всех значений ( на 0{Ы) процессорах за время ) При этом единственное изменение схемы (20), (21) заключается в том, что вместо

А1' будет вычисляться произведение ^

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

/(*)«!>,&(*).

может быть вычислено на N процессорах с временной сложностью г(Лг)=0(1о§2 Л^).

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

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

корня произвольной степени, представленные в виде и при произвольном вещественном а , могут быть выполнены за время одного умножения и одного сложения с точностью до 10"9, за время двух умножений и двух сложений - с точностью до 10*14, за время трех умножений и трех сложений - с точностью до 0,5x10 "". Эти

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

аппроксимации для случая а=2 приведена выше (табл. 1).

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

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

Помимо того, проводилось моделирование схемы аппроксимации полинома высокой степени путем кусочно-полиномиальной аппроксимации с помощью полиномов малой степени, как этого требует выполнение преобразований Фурье с помощью кусочно-полиномиальной аппроксимации. В частности, было показано, что полином 18-й степени аппроксимируется по кусочно-полиномиальной схеме полиномом 2-й степени с точностью до 10"'°, полином 36-й степени - полиномом той же степени с точностью до 10"*. Этот результат получается при аппроксимации на основе интерполяционного полинома Лагранжа. Аппроксимация на основе отрезка ряда Тейлора существенно повышает точность аппроксимации.

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

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

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

Численные эксперименты были проведены на различных языках программирования, включая Фортран, Basic, Pascal и Object Pascal в среде Delphi.

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

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

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

ОСНОВНЫЕ РЕЗУЛЬ ТА ТЫ ДИССЕРТАЦИОННОЙ РАБОТЫ 1. Разработаны обобщенные алгоритмы устойчивого вычисления функций одной действительной переменной и их суперпозиций с априори заданной границей абсолютной погрешности на произвольном промежутке. В основе предложенных алгоритмов лежит кусочно-полиномиальная аппроксимация функций рассматриваемого вида. При этом аппроксимация построена таким образом, что временная сложность вычисления функций минимизируется для любой наперед заданной точности приближения.

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

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

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

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

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

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

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

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

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

20

р 15.3 0

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

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

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

3. Ромм Я. Е, Фирсова С.А. Таблично-алгоритмические и параллельные схемы для аппроксимации рядом Фурье 7 ТГПИ. - Таганрог, 2000. 17 с. ДЕП в ВИНИТИ 13.03.00. №618-В00.

4. Ромм Я.Е., Фирсова С. А. Распараллеливаемое устойчивое вычисление функций на основе таблично-алгоритмической аппроксимации // Компьютерные технологии в инженерной и управленческой деятельности. Материалы Всероссийской научно-технической конференции с международным участием, 19.05.1999 - 21.05.1999 г. Таганрог, 2000. С. 166-168.

5. Ромм Я.Е., Фирсова С.А. Таблично-алгоритмические и параллельные вычислительные схемы для ряда Фурье // Математические модели физических процессов и их свойства. Материалы 6-й Международной научной конференции (28 - 30 июня 2000 года). / Под ред. Т.М. Абрамовича. - Таганрог: Изд-во ТГПИ, 2000. С. 63-64.

6. Ромм Я.Е., .Фирсова С.А. О представлении ряда Фурье в форме степенного ряда // Проблемы образования студентов гуманитарных вузов в свете развития современных, информационных технологий. Материалы международной научно-практической конференции. / Под ред. А.К. Юрова. - Таганрог: Изд-во ТГПИ, 2001. С.35-36.

7. Фирсова С.А. О представлении ряда Фурье в форме степенного ряда // Известия ТРТУ. Тематический выпуск: «Интеллектуальные САПР». Материалы Международной научно-технической конференции «Интеллектуальные САПР». Таганрог: Издательство ТРТУ, 2002, № 3(26). С. 118 - 121.

8. Ромм Я.Е., Фирсова С.А. Паскаль-программы вычисления элементарных функций и их суперпозиций на основе таблично-алгоритмической аппроксимации / ТГПИ. - Таганрог, 2002. 86 с. ДЕП в ВИНИТИ 31.12.2002. № 2319 - В2002.

Личный вклад автора в публикациях, написанных в соавторстве, состоит в следующем: [1,4] - схемы кусочно-полиномиальной аппроксимации на основе полинома Лагранжа и на основе формул Тейлора; [2,3] - схемы преобразования элементов тригонометрического базиса и частичных сумм ряда Фурье в форму алгебраического полинома, а также вывод формул коэффициентов данных полиномов; [5, 6] -схемы анализа устойчивости параллельных преобразований ДПФ и БПФ; [8] - метод повышения точности кусочно-полиномиальной. аппроксимации суперпозиции функций.

ОСНОВНЫЕ ПУБЛИКАЦИИ ПО ТЕМЕ РАБОТЫ

Соискатель

Фирсова С.А.

ВВЕДЕНИЕ.

ГЛАВА 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. В учебном процессе кафедры информационных систем и технологий управления Таганрогского государственного педагогического института.

ЗАКЛЮЧЕНИЕ

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 с.