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

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

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