Введение к работе
Актуальность. Одним из этапов решения таких задач, как численное решение дифференциальных уравнений, задач интерполяции и других, является решение систем линейных алгебраических уравнений Ах = г с латрицали специальной структуры, то есть матрицами, ненулевые элементы которых расположены на небольшом (слюсительно порядка матрицы) числе диагоналей.
К таким матрицам относятся: трехдиагональные, пятидиагональные, блочно-трехдиагональные, ленточные и другие матрицы.
Появление параллельных и векторных вычислительных систем привело к качественному пересмотру существующих алгоритмов решения таких систем уравнений с целью достижения их наибольшей эффективности. При этом учитываются следующие особенности векторно-конвейерных ЭВМ :
каждое функциональное устройство может работать независимо от других и параллельно с ними;
при выполнении различных операций использован принцип конвейера;
введены векторные регистры.
Реализация конвейера позволяет максимально загрузить функциональные устройства выполнением полезной работы, но для достижения этой цели необходимо организовать данные специальным образом, объединяя в отдельные потоки независимые однотипные операции.
Существование векторных регистров потребовало представления алгоритмов в виде последовательностей операций над векторами большой длины.
Для реализации на векторной архитектуре алгоритм необходимо представить в виде последовательности групп операций. Все операции одной группы должны быть независимы и обладать возможностью быть выполненными одновременно на имеющихся в системе функциональных устройствах. Если алгоритм представим в описанном выше виде, то можно надеяться, что при его реализации на векторно-конвейерной ЭВМ будет достигнуто высокое быстродействие.
Можно выде.мть несколько способов построения эффективных векторных алгоритмов, а именно:
модификация известных алгоритмов с целью их эффективной реализации на векторной архитектуре;
создание новых алгоритмов, ориентированных на рассматриваемую
вычислительную архитектуру;
- комбинирование различных алгоритмов.
Известные эффективные последовательные алгоритмы решения систем с матрицами специальной структуры теряют свои преимущества при переходе на ВК ЭВМ. В частности, распространенный алгоритм прогонки для решения трехдиагональных систем не поддается эффективной векторизации. Причина этому - небольшая средняя степень векторизации (средняя длина используемых векторов) основных вычислений, которая в большинстве алгоритмов не превосходит числа диагоналей в ленте. Так, средняя степень векторизации алгоритма прогонки равна 1. Однако для матриц с шириной ленты больше 10 можно эффективно использовать алгоритмы исключения для решения таких систем на ВК ЭВМ.
Это один из примеров того, что эффективность векторной реализации того или иного алгоритма во многом зависит от структуры матрицы.
Цель работы состоит в разработке и реализации пакетов ЛЕНТА и ИТЕРА, при помощи программ которых можно эффективно решать системы линейных уравнений с матрицами специальной структуры на ВК ЭВМ прямыми и итерационными методами.
Научная новизна. При разработке пакета ЛЕНТА наряду с эффективной векторизацией известных векторных алгоритмов был эффективно реализован алгоритм конвейерной прогонки и разработан новый эффективный векторный алгоритм решения трехдиагональных систем линейных уравнений, алгоритм "деление на блокип.
Структура пакетов такова, что возможен выбор оптимальной программы,, решающей данную конкретную задачу.
Программы пакета ИТЕРА эффективно реализуют основные итерационные метода и ориентированы на возможное расширение класса итерационных методов. Программы пакетов взаимосвязаны, а именно, программы пакета ЛЕНТА используются при реализации итерационных методов.
Теоретическая и практическая ценность. Разработанные пакеты программ позволяют эффективно решать системы линейных алгебраических уравнений с :
трехдиагональными матрицами;
произвольными матрицами, имеющими заполненную широкую ленту;
пятидиагональными разреженными матрицами.
В зависимости от условий конкрентной задачи может быть осуществлен выбор наиболее эффективной программы для ее решеїшя. Программы пакетов могут быть использованы в качестве ядер программ пользователя при решении любой системы с матрицей специальной структуры.
Программы пакета ИТЕРА можно использовать при расширении класса итерационных алгоритмов, основанных на расщеплении матрицы системы, при использовании попеременных и вложенных итераций.
Апробация работы. Основные результаты работы докладывались на семинарах отдела базового программного обеспечения института проблем кибернетики АН СССР, на международной информационной встрече по комплексной научной программе "Новые алгоритмы и архитектуры обработки гагформации" стран-членов СЭВ (г.Москва, 1989), на семинаре в Центре информатики и вычислительной техники Болгарской академии наук.
Публикации. Представленные на защиту результаты опубликованы в работах [1-4].
Структура диссертации. Диссертация состоит из введения, двух глав, заключения и списка литературы, содержащего 60 наименований.
