Процесс Гивенса на вычислительной машине с двухступенчатой памятью

24. Если мы представляем себе процесс Гивенса в том плане, как он использовался в § 22, то он сравнительно неэффективен для вычислительных машин с двухступенчатой памятью. Даже если мы воспользуемся симметрией, то найдем, что в каждый вспомогательный шаг включаются переносы как строки, так и столбца. Если, например, наддиагональные элементы записаны во внешней памяти по строкам, то на основном шаге строки от -йдо должны переноситься из внешней памяти и обратно на каждом вспомогательньм шаге, хотя в каждой строке, кроме двух, на которых основано текущее вращение, изменяются лишь два элемента. Опишем сейчас модифицированный процесс, предложенный Роллетом и Уилкинсоном (1961) и Иогансеном (1961), в котором перенос каждой из строк от до в вычислительное запоминающее устройство и обратно делается только один раз за весь основной шаг.

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

и частично в быстродействующей, мы несколько отклонимся от алгорифмического языка, использованного ранее.)

(1) Переносим первую строку А в первую группу рабочих ячеек.

(2) Для каждого значения от 3 до вычисляем

где

Записываем на место и запоминаем во второй группе рабочих ячеек.

(3) Переносим вторую строку в третью группу рабочих ячеек. (У этой и всех последующих строк используются элементы, лежащие на диагонали и выше ее.)

Для каждого значения к от 3 до выполняем шаги (4) и (5):

(4а) Переносим строку в четвертую группу рабочих ячеек.

(4б) Выполняем строчные и столбцовые операции, включающие над текущими элементами

(4в) Для каждого значения I от к до выполняем часть строчного преобразования, включающую над и

(4г) Для каждого значения I от к до выполняем часть столбцового преобразования, включающую над и используя тот факт, что в силу симметрии. После того как (4а), (46), (4в) и (4г) для данного к окончены, будут выполнены преобразования первого основного шага над всеми элементами строки к и над элементами к строки 2. Элементы 2, к строки 2 подвергаются пока лишь преобразованиям, включающим

(5) Переносим полученную строку во внешнюю память и возвращаемся к (4а) со следующим значением k.

25. Когда этапы (4) и (5) выполнены для всех соответствующих значений к, то тем самым выполнены и все вычисления над строкой 2. Измененные элементы первой строки (т. е. первые два элемента трехдиагональной матрицы), от 3 до могут быть записаны во внешнюю память, а строка 2 перенесена в первую группу рабочих ячеек. Так как вторая строка на втором основном шаге играет такую же роль, как первая на первом шаге, то уже все готово для этапа (2) второго основного шага. Этап (1) на всех последующих основных шагах не нужен, так как соответствующая строка уже находится в быстродействующей памяти.

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

Удобно для матрицы отвести во внешней памяти ячеек, сохраняя каждую строку полностью, несмотря на то, что поддиагональные элементы не используются, так как полное число ячеек необходимо для запоминания синусов и косинусов. Последние должны быть сохранены, если требуются собственные векторы. Удобный способ запоминания окончательной информации показан в (25.1). С этим способом запоминания «адресная»

арифметика особенно проста:

Иогансен отметил, что если переносы из внешней памяти выполняются по к слов за один раз, то в быстродействующей памяти можно иметь к рабочих ячеек вместо так как нам не нужно иметь в памяти одновременно целую строку матрицы А.