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

Введение.

1 Вычисление функций на сетках с переменным шагом

1.1 Настройка на интервал значений аргумента

1.1.1 Идея подхода.

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

1.2 Использование базовых точек.

1.2.1 Идея подхода.

1.2.2 Вычисление значений некоторых элементарных функций.

1.3 Настройка на значение параметра.

1.3.1 Идея подхода.

1.3.2 Модифицированные функции Бесселя

1.3.3 Исходные алгоритмы.

1.3.4 Сеточно-ориентированные алгоритмы

2 Программные средства поддержки сеточно-ори-ентированных вычислений

2.1 Архитектура.

2.2 Программный интерфейс библиотеки.

2.2.1 Схемы работы с библиотекой.

2.2.2 Программный интерфейс.

2.3 Модуль символьной обработки.

2.4 Численная библиотека.

2.4.1 Описание.

2.4.2 Интерфейс

2.5 Модуль рекурренций.

2.5.1 Описание.

2.5.2 Интерфейс

2.6 Интерфейсный модуль Maple.

2.7 Дополнительные реализации.

2.7.1 JMCR.

2.7.2 Система ESU.

2.7.3 Пакет gridbessel.

2.8 Дальнейшее развитие.

3 Дополнение. Вычисление произведений с помощью сеточно-ориентированных алгоритмов

3.1 Постановка задачи вычисления произведений

3.2 Основные алгоритмы.

3.3 Применение развертки и цепочек рекурренций

3.4 Реализация.

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

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

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

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

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

Для некоторых классов функций хорошо известны алгоритмы, позволяющие экономить операции при вычислениях на сетках с помощью предварительной обработки. Например, если для вычисления полиномов общего вида Рп(х) — аоХп + aixn~ljr. .+an-ix+an водной точке наиболее быстрой является схема Горнера (п умножений и п сложений), то для вычислений таких полиномов на сетке можно применить более экономные вычислительные алгоритмы, позволяющие сократить число операций по сравнению с применением схемы Горнера независимо в каждой точке сетки. Применение таких алгоритмов осуществляется в два этапа: на первом этапе исходный полином преобразуется к специальному виду; на втором этапе производится вычисление значений исходного полинома с помощью нового представления в точках заданной сетки. При этом число операций на втором этапе меньше числа операций при вычислении полиномов по схеме Горнера независимо в каждой точке. К таким вычислительным схемам относятся схемы Дж. Тодта, Ю.Л. Кеткова, В.Я. Пана [lj.

Например, в схеме Тодта на втором этапе для вычисления значения приведенного полинома шестой степени требуется три умножения и семь сложений для каждой точки сетки. Таким образом, достигается небольшая экономия по сравнению со схемой Горнера, согласно которой в данном случае потребовалось бы пять умножений и шесть сложений. Более общая схема Кеткова требует для произвольного полинома п-й степени (для п > 6) выполнения [{п + 1)/2] 4- [п/А] умножений и п 4-1 сложений. В работе Э. Белаги [2J дается строгое доказательство невозможности построения схемы вычислений произвольных полиномов 71-й степени, использующей на втором этапе менее 4-1 умножений и п сложений. Схемы Пана [3] позволяют достичь количества действий, близких к этой оценке.

Однако, если рассматривать вычисление полиномов на равномерной сетке, что является часто встречающейся задачей, то можно достичь гораздо большей экономии числа операций с помощью известного метода конечных разностей. Идея этого метода состоит в следующем: если первая разность интересующей нас функции (р(х) = /(ж4-1) — f(x) может быть вычислена посредством меньшего числа операций, чем f(x 4-1), то для вычисления значения функции / в новой точке сетки можно использовать функцию ср(х) и значение / в предыдущей точке сетки. Если, например, функция / является полиномом степени п, то ее первой разностью будет полином степени п — 1. Для вычисления ip(x) можно снова использовать первую разность, и т.д. В результате для вычисления заданного полинома в новой точке потребуется всего лишь п сложений.

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

На идее метода конечных разностей основана предложенная Е. В. Зимой в [4] техника цепочек рекурренций. Этот подход может применяться к более широкому классу функций, чем полиномы. В [4, 5, б, 7, 8] рассматривалась возможная экономия числа операций при вычислении значений различных элементарных функций и их суперпозиций в точках равномерной сетки. Подход, описываемый в этих работах, позволяет получить существенное ускорение вычислений на сетках для достаточно широкого класса функций. Этот подход может быть применен для случая функций многих переменных [9, 10].

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

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

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

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

На основе этих подходов разработаны и реализованы сеточ-но-ориентированные алгоритмы вычисления некоторых элементарных и специальных функций, в том числе модифицированных функций Бесселя 2v(z), jCv(z).

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

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

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

Заключение

Сформулируем основные результаты диссертации:

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

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

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

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

2. Белага Э. Г. О вычислении значений многочленов от одного переменного с предварительной обработкой коэффициентов. // Проблемы кибернетики, вып. 5. М.: Физматлит, 1961. С. 7-16.

3. Пан В. Я. Некоторые схемы для вычисления многочленов с действительными коэффициентами. // Проблемы кибернетики, вып. 5. М.: Физматлит, 1961. С. 17-30.

4. Зима Е. В. Автоматическое построение систем рекуррентных соотношений. // Журнал вычисл. матем. и матем. физ., 1984, 24, № 12, С. 1897-1902.

5. Bachmann О., Wang P. S., Zima Е. V. Chains of Recurrences a method to expedite the evaluation of closed-form functions. // Proc. of the ISSAC'94, Oxford, UK, July 1994, ACM Press, P. 242-249.

6. Zima E. V. Simplification and Optimization Transformations of Chains of Recurrences. // Proc. of the ISSAC'1995, Montreal, Canada, July 1995, ACM Press, P. 42-50.

7. Бахвалов Н. С. Численные методы. М.: Наука, 1973.

8. William Н. Press, Brian P. Flannery, Saul A. Teukolsky, William T. Vetterling Numerical Recipes in C. The Art of Scientific Computing. Cambridge University Press, 1993

9. Temme M. N. On the numerical evaluation of the modified Bessel function of the third kind. //J. Comput. Phys., 1975, v.19, N 3, 324-337.

10. Скороходов С. JI. Алгоритмы вычисления цилиндрических функций Бесселя и их нулей в комплексной области. Дисс. канд. физ.-мат. наук. М. ВЦ АН СССР. 1985.

11. Справочник по специальным функциям. Ред. Абрамовиц М., Стиган И. М.: Наука, 1979.

12. Гамма Э., Хелм Р., Джонсон Р., Влиссидес Дж. Приемы объектно-ориентированного проектирования. Паттерны проектирования. СПб: Питер, 2001.

13. Borwein J., Borwein P. Pi and the AGM. Wiley, 1987.

14. Haible В., Papanikolaou T. Fast multiprecision evaluation of series of rational numbers. // Technical report TI-97/7, University of Darmstadt, 1997.

15. Cohen H. A Course in Computational Algebraic Number Theory. Springer-Verlag, 1991

16. Кнут Д. Искусство программирования для ЭВМ. т. 2 "Получисленные алгоритмы", секция 4.3.3. М., Мир, 1977.

17. Shoup V. http: //www. shoup. net.

18. Zima E. V. Safe Numerical Computations with Chains of Recurrences. // Programmirovanie № 3, 1997, P. 36-42