Устройство обращения треугольной матрицы

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

Известно устройство для обращения матриц [RU 1819020, 1995 г.], содержащее линейку из n+1 вычислительных модулей, два информационных входа, три настроечных входа и группу выходов. В основу работы устройства для обращения n×n матриц положен метод Гаусса-Жордана, представленный рекуррентными соотношениями.

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

Известно устройство для обращения матриц размерности n×n [RU 2037199, 1995 г. ], содержащее фиксированное число т вычислительных модулей, где m<n, причем каждый вычислительный модуль содержит три триггера, три параллельных регистра, пять сдвигающих регистров, умножитель, вычитатель, узел вычисления обратной величины числа, два элемента НЕ, пять элементов И, десять блоков элементов И, а также четыре блока элементов ИЛИ. В основу работы устройства положен метод Гаусса-Жордана. Вычислительный модуль работает в шести режимах. Режимы работы вычислительного модуля выполняются последовательно.

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

Известно устройство для обращения матриц [SU 1339585, 1987 г.], содержащее два блока хранения матриц, два блока формирования матриц, блок формирования обратной матрицы, блок управления. В устройстве процедура обращения организована рекуррентно. Рекуррентная процедура организуется с использованием вспомогательной матрицы и обратной к ней матрицы. Обращение осуществляется путем последовательной замены во вспомогательной матрице ее строк строками матрицы, подлежащей обращению, и нахождения на каждом шаге обратной для нее матрицы.

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

Известно устройство для обращения матриц [SU 1575204, 1990 г.], содержащее генератор тактовых импульсов, триггер, счетчик, блоки ввода и вывода и вычислительный блок. В устройстве реализован метод исключения обращения матрицы, основанный на алгоритме Гаусса-Жордана. Целью изобретения является расширение функциональных возможностей устройства за счет вычисления определителя обращаемой матрицы. Модификация традиционного алгоритма заключается в перестановке строк и столбцов на каждом шаге рекуррентной процедуры обращения матрицы.

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

Наиболее близким аналогом (прототипом) по совокупности существенных признаков является блок обращения ковариационной матрицы помеховых сигналов [RU 2466482, 2012 г.], в состав которого входят 11 вычислительных модулей, обеспечивающих построение обратной матрицы. В данном блоке реализован алгоритм на основе итерационного метода «окаймления», описанного, например, в [Воеводин В.В., Кузнецов Ю.А. Матрицы и вычисления. - М.: Наука, 1984, стр. 214; Фаддеев Д.К., Фаддеева В.Н. Вычислительные методы линейной алгебры. - М.-Л.: Госиздат, физ.-мат.литературы, 1963, стр. 187]. Входными сигналами блока являются сигналы от блока формирования ковариационной матрицы помеховых сигналов и от предыдущего этапа итераций. Выходными сигналами данного блока являются сигналы, поступающие на следующий этап итераций или сигналы, поступающие на перемножитель, который формирует весовые коэффициенты, т.е. сигналы, соответствующие обратной ковариационной матрице.

В соответствии с методом окаймления для перехода от блочной матрицы порядка n к блочной матрице порядка n+1, выполняемого на n-м шаге преобразования, дополнительно используются элементы {s_1n,s_2n,…,s_n-1n}, образующие матрицу-столбец В, элементы {s_n1,s_n2,…,s_nn-1}, образующие матрицу-строку С, и s_nn, образующий элемент D. С использованием данных элементов матрица определяется как [6, 7]

где

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

Недостатком устройства-прототипа является излишняя сложность реализации процесса обращения матрицы, так как при реализации метода «окаймления» не было учтено то, что матрица является треугольной.

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

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

Проведенный сравнительный анализ заявленного устройства и устройства-прототипа показывает, что заявленное устройство отличается тем, что:

- уменьшено число вычислительных модулей с 11 до 6;

- введены первый и второй блоки хранения коэффициентов и генератор тактовых импульсов;

- изменено схемное выполнение вычислительных модулей вследствие учета того, что матрица является треугольной;

- изменены связи между вычислительными модулями и введенными элементами.

На фиг. 1 представлена структурная схема устройства обращения треугольной матрицы.

На фиг. 2 приведена схема устройства обращения треугольной матрицы с указанием выполняемых математических действий.

В состав устройства обращения треугольной матрицы входят вычислительные модули 1-5, первый блок 6 хранения коэффициентов, второй блок 7 хранения коэффициентов и генератор 8 тактовых импульсов. Выход первого вычислительного модуля 1 подключен к третьему входу четвертого и четвертому входу пятого вычислительных модулей 4 и 5. Первый выход второго вычислительного модуля 2 подключен к третьему входу пятого вычислительного модуля 5, а второй выход - ко второму входу четвертого вычислительного модуля 4, выход которого подключен ко второму входу пятого вычислительного модуля 5. Первый выход первого блока 6 хранения коэффициентов подключен ко второму входу первого вычислительного модуля 1, второй выход - к первому входу четвертого вычислительного модуля 4, третий выход - ко входу третьего вычислительного модуля 3, выход которого подключен к первому входу пятого вычислительного модуля 5. Выход пятого вычислительного модуля 5 подключен к третьему входу первого вычислительного модуля 1. Первый вход первого вычислительного модуля 1 подключен к первому выходу второго блока 7 хранения коэффициентов, второй выход которого подключен ко входу второго вычислительного модуля 2. Управление работой модулей и блоков 1-7 производится генератором тактовых импульсов 8, формирующим управляющие воздействия для каждого из модулей и блоков.

Прежде чем рассмотреть функционирование предлагаемого устройства обращения треугольной матрицы, проведем теоретическое обоснование процесса обращения матрицы методом «окаймления» с учетом того, что она является треугольной.

В соответствии с данным алгоритмом на первом шаге из элементов s_ij, i=1,…,N, j=l,…,N ковариационной матрицы помеховых сигналов выбираются элементы s₁₁, s₁₂, s₂₁, s₂₂. Данные элементы позволяют сформировать блочную матрицу размерности 2×2. Формулы, на основе которых вычисляются данные элементы имеют вид

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

На втором шаге происходит формирование обратной матрицы третьего порядка Для построения данной матрицы дополнительно используются элементы s₁₃, s₂₃, s₃₃, s₃₁, s₃₂ матрицы М, «окаймляющие» полученную на первом шаге матрицу как приведено ниже

Однако для треугольной матрицы s₁₃=0, s₂₃=0. Поэтому для нахождения матрицы третьего порядка будут использоваться элементы s₃₃, s₃₁, s₃₂. Элементы этой матрицы находятся с помощью формул

В общем случае для перехода от обратной матрицы порядка n к обратной матрице порядка n+1, выполняемого на n-м шаге преобразования, дополнительно используются элементы {0,0,…,0}, образующие матрицу-столбец В, элементы {s_n+11, s_n+12, …, s_n+1n} образующие матрицу-строку С, а также элемент s_n+1n+1, представляющий блок D, приведенные в (8).

Так как матрица-столбец В является нулевой матрицей, то есть справедлива запись В=(С×0)^Т, то матрица элементы которой определяются формулами, описанными в [6, 7], примет вид:

где Н = D = s_{n+1 n+1}.

Схема устройства, реализующая данный алгоритм, приведена на фигуре 1. На фигуре 2 даются пояснения по выполнению математических действий.

Устройство работает следующим образом.

Первоначально, если матрица является нижней треугольной, то она преобразуется в верхнюю треугольную путем выполнения операции транспонирования. На первом шаге, как описано выше, на первый и второй входы первого вычислительного модуля 1 из первых выходов первого и второго блоков 6, 7 хранения коэффициентов извлекаются элементы исходной матрицы размерности 2×2 и формируются элементы обратной матрицы в соответствии с формулой (2).

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

Для формирования обратных матриц третьего и более высокого порядков выполняется итерационный алгоритм. На каждом шаге, за исключением последнего выполняются следующие операции. На вход второго вычислительного модуля 2 поступают со второго выхода второго блока 7 хранения коэффициентов сигналы, соответствующие элементам блока D, «окаймляющим» матрицу Во втором вычислительном модуле 2 производится операция по формированию элемента матрицы Н^-1, соответствующие математическому действию, описанному выражением (7). Сигналы с первого выхода второго вычислительного модуля 2 поступают на третьи входы пятого вычислительного модуля 5. Сигналы со второго выхода второго вычислительного модуля 2 поступают на второй вход четвертого вычислительного модуля 4. На первый вход четвертого вычислительного модуля 4 поступают сигналы со второго выхода первого блока 6 хранения коэффициентов, соответствующие матрице-строке С, «окаймляющей» матрицу Сигналы с третьего выхода первого блока 6 хранения коэффициентов, соответствующие матрице-строке С, поступают на вход третьего вычислительного модуля 3, в котором производится умножение матрицы-строки С на нуль и ее транспонирование, то есть операция (С×0)^Т. Далее сигналы с третьего вычислительного модуля 3 поступают на первый вход пятого вычислительного модуля 5. Сигналы с первого вычислительного модуля 1, соответствующие матрице полученной на предыдущем шаге итерации поступают на четвертый вход пятого вычислительного модуля 5 и на третий вход четвертого вычислительного модуля 4, где производится операция - Далее сигналы с выхода четвертого вычислительного модуля 4 поступают на второй вход пятого вычислительного модуля 5, где формируется матрица Выходом пятого вычислительного модуля 5 являются сигналы обращенной матрицы на данном этапе итераций, поступающие в процессе обращения на входы первого вычислительного модуля. После выполнения N-2 шагов итерационного алгоритма формируется обратная матрица порядка N, и обращение матрицы завершается.

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

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

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