Применение различных численных методов, в частности метода напряжений для решения задач механики деформируемого твердого тела приводит к системам линейных и нелинейных алгебраических уравнений, которые часто имеют очень высокий порядок (несколько десятков тысяч). При формировании этих уравнений в большинстве случаев приходится работать с несимметричными, плотно заполненными матрицами, хранящимися либо в оперативной памяти, либо на внешних носителях.
Решение таких систем сопряжено с большими временными затратами и накопление ошибок приводит к неверным результатам. Ситуация ухудшается тем, что большой порядок системы линейных алгебраических уравнений(СЛАУ) приводит к необходимости хранения данных на внешних носителях и к их порционной обработке.
Поэтому исследования и разработки, направленные на ускорение процесса счета, на достижение требуемой точности, разработка специальных алгоритмов и соответствующих комплексов программ решения СЛАУ являются весьма важной и актуальной проблемой, имеющей практическое и научное значение.
В работе приводится схема построения алгоритма распараллеливания на основе метода Гаусса для решения СЛАУ и вычислительный эксперимент.
Структура данных коэффициентов системы основывается на «разрезании», т.е. представлении матрицы системы полосами шириной и длиной , которые записываются в каждый клиентский компьютер.
Предположим, что первые k строк матрицы расположены в памяти 1-го компьютера , следующие k строк - в памяти компьютера 2-го и т.д., которые обрабатываются по следующей схеме: 1. Поиск ведущего элемента по столбцам в каждом p , где p – количество компьютеров. Найденные значения ведущего элемента и номер строки, в котором находится ведущий элемент, возвращается в сервер. 2. Сервер, сопоставляя ведущие элементы, полученные из клиентских компьютеров, определяет наибольший по модулю элемент и соответствующий номер строки. Далее сервер дает запрос этому клиентскому компьютеру , чтобы он отправил на сервер эту строку. При этом сервер формирует временный файл о месте нахождения ведущей строки. 3. Сервер, получив строку с ведущим элементом, отправляет всем клиентским компьютерам эту строку, кроме компьютера у которого был найденный ведущий элемент. 4. Клиентские компьютеры, после получения ведущей строки из сервера, параллельно осуществляют нормализацию первого столбца своей матрицы. 5. Далее повторяется шаг 1-4., пока не закончится нормализация. 6. После окончания прямого хода, для ускорения вычислений и для уменьшения простоя компьютеров в вычислительном кластере, сервер дает команду о начале обратного хода. 7. В процессе обратной подстановки находятся значения неизвестных в каждом компьютере в определённом порядке.
Для апробации алгоритма, для сравнения оценок времени затраты с учетом ошибок на основе чисел обусловленности рассмотрим матрицу Гильберта.
Полученные результаты показывают работоспособность разработанного алгоритма.
Примечание. Тезисы докладов публикуются в авторской редакции
Ваши комментарии Обратная связь |
[Головная страница] [Конференции] |
© 1996-2000, Институт вычислительных технологий СО РАН, Новосибирск
© 1996-2000, Сибирское отделение Российской академии наук, Новосибирск