Одновременное действие со строками и столбцами

18. Дальнейшее преимущество формы Хессенберга состоит в том, что разложение и дальнейшее умножение могут быть совмещены таким образом, что на вычислительной машине с двумя типами памяти итерация будет требовать лишь одного переноса из внешней памяти и ее замены на . С этой целью необходимо запоминать по столбцам.

Заметим, что для разложения требуется только множителей и для определения первых из этих множителей нам потребуются только первые столбцов матрицы Мы можем описать предлагаемую схему, рассмотрев типичный основной шаг. К началу этого шага вычислены первые столбцов матрицы и записаны на места соответствующих столбцов матрицы во внешней памяти. Вычисление столбца еще не закончено, и частично обработанный столбец находится в быстродействующей памяти. Элементы и информация о произведенных перестановках на шагах, в которых эти элементы вычислялись, тоже находятся в быстродействующей памяти. Типичный шаг может быть описан следующим образом:

(i) Переносим столбец в быстродействующую память. Для всех значений от 1 до проделываем шаги (ii) и (iii).

(ii) Меняем местами и в зависимости от того, была ли перестановка при вычислении .

(iii) Вычисляем и записываем на место По завершении столбец подвергся всем операциям, входящим в приведение первых строк .

(iv) Если переставляем эти два элемента и затем вычисляем Запоминаем и регистрируем перестановку, если она имела место. Заменяем на нуль.

Столбец теперь становится столбцом треугольной матрицы, которая была бы найдена после выполнения обычного приведения.

(v) Меняем местами модифицированные столбцы (которые находятся в быстродействующей памяти), если перед вычислением были перестановки.

(vi) К столбцу прибавляем столбец, умноженный на Полученный столбец является теперь столбцом и может быть помещен во внешнюю память.

Комбинированный процесс дает результат одинаковый с первоначальным процессом даже в смысле ошибок округления и не требует больше арифметических действий. Заметим, что мы можем предположить, что ни один из поддиагональных элементов матрицы не равен нулю, ибо в противном случае мы имели бы дело с двумя или более меньшими матрицами Хессенберга. Поэтому в шаге (iv) знаменатель никогда не равен нулю, так как на стадии, когда производится деление, больше заданного и некоторых других чисел.