Студопедия

Главная страница Случайная страница

КАТЕГОРИИ:

АвтомобилиАстрономияБиологияГеографияДом и садДругие языкиДругоеИнформатикаИсторияКультураЛитератураЛогикаМатематикаМедицинаМеталлургияМеханикаОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРелигияРиторикаСоциологияСпортСтроительствоТехнологияТуризмФизикаФилософияФинансыХимияЧерчениеЭкологияЭкономикаЭлектроника






Параллельный алгоритм решения.






Заметим, что изложенные в пункте 2 соотношения обладают неприятным свойством для параллельных алгоритмов: высокая степень зависимости по данным. Иными словами, для вычисления каждого следующего элемента необходимо знать некоторое количество элементов, вычисленных ранее. Наличие зависимости затрудняет составление последовательно-параллельной модификации метода и снижает ускорение, которое может быть получено с ее помощью. Поэтому предлагается несколько изменить вышеизложенный метод. Пусть матрица L на главной диагонали не содержит единицы, но останется нижнетреугольной. А матрица U на главной диагонали содержит единицы и остается верхнетреугольной. Это несущественное изменение, которое никак не повлияет на сложность обратного хода при решении СЛАУ, но облегчит составление последовательно-параллельной модификации.

Еще одно немаловажное замечание: матрицы L и U являются нижне- и верхнедиагональными, причем на местах, где у L могут быть ненулевые элементы, у U гарантировано нули, и наоборот. К тому же, после вычисления некоторых значений искомых матриц часть разлагаемой матрицы становится неиспользуемой. Учитывая это при разложении матрицы, можем не заводить две новые матрицы L и U, а записывать найденные элементы прямо в разлагаемую матрицу. Такой подход втрое сократит расходы на память, что существенно при работе с матрицами большой размерности.



Поделиться с друзьями:

mylektsii.su - Мои Лекции - 2015-2024 год. (0.007 сек.)Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав Пожаловаться на материал