Вычисление функций на сетках, т. е. на конечных множествах точек, используется во многих областях информатики, в частности, в задачах компьютерной графики и разнообразных расчетных задачах. При этом в ряде таких задач подобные вычисления требуют больших временных затрат. Поэтому разработка программных средств, позволяющих ускорять вычисление функций на сетках, является актуальной проблемой.
На практике вычисление значений заданной функции на сетке часто производится «наивным» методом, путем независимого вычисления в каждой точке сетки.
Однако, вычисляя значение этой функции в очередной точке сетки, можно попытаться использовать часть ранее проделанной работы по вычислению функции в предыдущих точках, сокращая таким образом число операций и ускоряя процесс вычислений. Основанные на этой идее методы вычисления функций мы будем называть сеточно-ориентировап-ными.
Сеточно-ориентированные методы позволяют достичь большей скорости вычислений путем преобразования методов независимых вычислений функций к виду, позволяющему сохранить некоторую часть промежуточных результатов вычислений в уже пройденных точках сетки, и последующего использования этих результатов для вычисления значений функции в новых точках.
Заметим, что при таком подходе может потребоваться значительное количество быстрой машинной памяти для хранения промежуточных результатов, что до недавнего времени было неприемлемо или нежелательно из-за небольшого размера оперативной памяти и малого числа регистров центрального процессора. Кроме того, частое обращение к сохраненным данным требует высокой скорости обмена процессора с памятью. На прежних компьютерах часто оказывалось так, что вычисление некоторой величины производилось быстрее, чем выборка этой величины из оперативной памяти. Современные же компьютеры, обладающие большими объемами как оперативной, так и быстрой кэш-памяти, делают возможными хранение и быструю обработку большого объема промежуточных результатов.
Для некоторых классов функций хорошо известны алгоритмы, позволяющие экономить операции при вычислениях на сетках с помощью предварительной обработки. Например, если для вычисления полиномов общего вида Рп (х) — аоХп + 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, поддерживающая сеточно-ориентированные вычисления и включающая, в частности, реализацию алгоритмов, указанных в предыдущем пункте.
