Устройство для операций над матрицами Советский патент 1992 года по МПК G06F15/347 

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

Известно устройство для решения систем линейных алгебраических уравнений, содержащее 2п-1 вычислительных модулей (ВМ), где п - порядок системы линейных алгебраических уравнений, 2п-1 блоков па- мяти и блок вывода 1.

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

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

для решения систем линейных алгебраических уравнений, содержащее п ВМ, блок вывода и регистр, причем каждый ВМ содержит три регистра, умножитель и сумматор, блок вывода-2п регистров, п вычислителей, п узлов сравнения, два элемента И и триггер 2.

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

Цель изобретения - расширение функциональных возможностей устройства путем вычисления первого собственного значения и первого собственного вектора матрицы.

На фиг.1 представлена структурная схема устройства; на фиг.2 - то же, для случая п 3; на фиг.З и 4 - функциональные схемы вычислительных модулей.

VJ

|sj

О N

Устройство (фиг,1) содержит группу информационных входов 1, первый 2, второй 3 и третий 4 информационные входы, вход 5 задания ошибки вычислений, синхровход 6, первый 7 и второй 8 настроечные входы, вычислительные модули 9 и 10, блок 11 вывода, информационные выходы 12 и выход 13 признака окончания вычислений.

Вычислительный модуль 9 (фиг.З)содержит первый 14, второй 15 и третий 16 инфор- мационные входы, синхровход 17, первый 18, второй 19 и третий 20 регистры, умножитель 21, сумматор 22, первый 23 и второй 24 информационные выходы.

Вычислительный модуль 10 (фиг.4) со- держит первый 25, второй 26 и третий 27 информационные входы, первый 28 и второй 29 настроечные входы, синхровход 30, первый 31 и второй 32 регистры, первый 33 и второй 34 триггеры, узел 35 вычисления обратной величины числа, первую-шестую группы 36-41 элементов И, первую 42, вторую 43 и третью 44 группы элементов ИЛИ, первый-пятый элементы И 45-49, элемент НЕ 50, умножитель 51, первый 52 и второй 53 информационные выходы.

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

x(0Vi

п - 1

хг

-т-( 2 aijxj + ain), xn 1,1 1,2п-1;

A1 j 1

n -1

Л-1 2 SnjXj + 3nn. j -

Для вычисления значений xpk и Ark используется итерационный метод Зейделя решения систем линейных алгебраических уравнений, при котором значения xi и AI определяются рекуррентными соотношениями:

Xi(o),(o) x.(o).Xn(o),(o)1.

.(i) J/xW,(i-o/ ; V

/ц.|)

a;.j-U)Xj-;+nJ4 1, .,...;

,(0

50

lQj,n-i+i+ixB.i,j,,K.w1...j

xi{k) Xj(k)(n), i TjPF, k 1,2,...; Хп(.55

А1(Ю,0) Xn(k).(J). XnfrMM) + . T7; AlM,AlM,(n) Xn(H,M

0

5 0 5

0

5

0

5

0

5

Точность вычисления значений xi и AI определяется величиной е. Если разности Axl xj(k+1)-xi(k)()H AAi A/k+1 - A/k удовлетворяют условию IA xi I с, lAAil Ј, то можно принять приближенно xi «( х2(ж), xn-i(k+1l 1) и Ai«Ai +4

Рассмотрим работу вычислительного модуля 1.0 (фиг.4), логика работы которого приведена в табл.1. Вычислительный модуль 10 работает в четырех режимах.

В первом режиме работы на настроечные входы 28 и 29 подаются нулевые сигналы, которые устанавливают двухтактные триггеры 33 и 34 в нулевое состояние, на выходе элемента И 47 формируется единичный сигнал, который открывает группу элементов И 37. При этом значение х, записанное в регистр 31, через группу элементов И 37, группы элементов ИЛИ 42 и 44 подается на информационные выходы 52 и 53.

Во итором режиме работы на настроечные входы 28 и 29 подаются соответственно нулевой и единичный сигналы, которые устанавливают триггеры 33 и 34 соответственно в нулевое и единичное состояния. На входы 26 и 27 постоянно подаются соответ- ственноАг0 и единичное число. Группа элементов И 36 открывается, через нее значение х, записанное в регистр 31, подается на вход группы элементов ИЛИ 42 и соответственно на выход 52. Кроме того, через открытую группу элементов И 39 единичное число подается на вход группы элементов ИЛИ 44 и на выход 53. На выходе элемента И 46 формируется единичный сигнал, который открывает группу элементов И 38. При этом по заднему фронту тактового импульса значение A Ai, поданное через группу элементов И 38 и группу элементов ИЛИ 43, записывается в регистр 32 (элемент И 48 открыт и разрешает прохождение тактового импульса на синхровход регистра 32).

В третьем режиме работы на настроечные входы 28 и 29 подаются соответственно единичный и нулевой сигналы, которые устанавливают триггеры 33 и 34 соответственно в единичное и нулевое состояния. При этом на выходе элемента И 49 формируется единичный сигнал, который открывает группу элементов И 40. На выходе узла вычисления обратной величины числа 35 формируется значение 1/А, на выходе умножителя 51 значение -у- х, которое через группу элементов И 40, группы элементов ИЛИ 42 и 44 подается на выходы 52 и 53.

В четвертом режиме работы на настроечные входы 28 и 29 подаются единичные сигналы, которые устанавливают триггеры 33 и 34 в единичное состояние. На выходе элемента И 45 формируется единичный сигнал, который открывает группу элементов И 41. Значение А™, поданное на вход 25, через группу элементов И 41 и группу элементов ИЛИ 43 подается на информационный вход регистра 32. Так как элемент И 48 открыт, значениеА по заднему фронту тактового импульса записывается в регистр 32. Значение А с выхода регистра 31 через открытую группу элементов И 36 и через группу элементов ИЛИ 42 подается на выход 52. Единичное число через открытую группу элементов И 39 и группу элементов ИЛИ 44 подается на выход 53.

При описании работы устройства в обозначении первый индекс в скобках (к) указывает номер итерации, а второй индекс в скобках (j) - номер рекуррентного шага для k-й итерации. В обозначении x k 1 индекс в скобках (к) указывает номер итерации, а индекс t без скобок - номер такта работы устройства.

Рассмотрим работу устройства для случая п 3. На вход 2 подаются значения xi , Х2 и 1 соответственно на нулевом, втором и четвертом тактах, на последующих тактах подаются нулевые значения. На входы 3,4 и 5 постоянно подаются соответственно значения AI , 1 и Ј. Организация подачи входного потока элементов на входы 1i (i 1,2,3) и управляющих сигналов на входы 7 и 8 приведена на фиг.2. Работа устройства по тактам поясняется табл.2, в которой приведены значения на входах, состояния регистров, триггеров и значения на выходах вычислительных модулей 9 и 10.

На девятом, одиннадцатом и тринадцатом тактах в вычислительном модуле 10 формируются соответственно xr1 , w и Аг , которые записываются в регистры блока 11 вывода. На пятнадцатом, семнадцатом и девятнадцатом тактах в вычис- лительном модуле 10 формируются соответственно , Х2 и Аг2 , которые также записываются в регистры блока 11 вывода. На двадцатом такте в блоке 11 вывода выполняется проверка условия iAxil Ј и lAAil Е. Если условие для всех Xi-x значений, (i 1,2) выполняется, то на выходе 13 выдается признак окончания вычислений а 1 и с выходов 12i и 122 выдаются значения соответственно первой и второй компонент первого собственного вектора xi (xi,x2,1), а с выхода 12з значение первого собственного значения AL Если

признак окончания вычислений а 0, то итерационный процесс вычислений продолжается. Выдача верных результатов xi и AI при обеспечивается блоком 11 выво5 да в моменты времени t n + 2n(k+1),

где к 1,2,3 В остальные моменты

времени t s n + 2n(k+1) съем информации с выходов 12 не производится. При решении систем линейных алгебра0 ических уравнений на настроечные входы 7 и 8 подаются нулевые сигналы, вычислительный модуль 10 выполняет функцию задержки информации, поступающей на его первый информационный вход 25 на один

5 такт. Значения корней уравнений xi (i 1,n) снимается с выходов 12i приа 1 в моменты

времени t n + 2n(k+1), k 1,2,3

Формула изобретения Устройство для операций над матрица0 ми, содержащее (п+1) вычислительный модуль (п - порядок системы линейных алгебраических уравнений) и блок вывода, причем первый информационный вход устройства подключен к первому информаци5 онному входу n-го вычислительного модуля, первый информационный вход i-ro вычислительного модуля ( ,п-1) подключен к первому информационному выходу (i+1)-ro вычислительного модуля, первый информа0 ционный выход первого вычислительного модуля подключен к первому информационному входу (п+1)-го вычислительного модуля, первый информационный выход которого подключен к первому информаци5 онному входу блока вывода, второй информационный выход (п+1)-го вычислительного модуля подключен к второму информационному входу первого вычислительного модуля, второй информационный выход i-ro вычислительного модуля подключен к второму информационному входу (i+1)-ro вычислительного модуля, j-й информационный вход группы входов устройства (j 1 ,п) подключен к третьему информационному входу j-ro вычислительного модуля, вход задания ошибки вычислений устройства подключен к второму информационному входу блока вывода, синхровход устройства подключен к синхровходам всех вычислительных модулей и блока вывода, выход признака окончания вычислений которого подключен к одноименному выходу устройства j-й информационный выход блока вывода является одноименным выходом устройства,

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

5

0

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

Aj+1 aj bj + cj,

В

i+1 hi

bj,

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

А и В - значения соответственно на первом и втором информационных выходах вычислительного модуля на J-M такте;

(п+1)-й вычислительный модуль выполнен с возможностью реализации следующих функций:

AJ+1

BJ+1

0

5

где

Ы

0

fxj1/bj, если (d,/) (1,0)

У, если (о1, $ (0,0X0,1X1.1) xj, если (d, (0,0X1,1)

1, если (d,ft) (0,1)

xJ1/bj, если (d,/) (1,0) (с. если (,) (0,1) х, если (,р) (1.1)

d и j$ - значения соответственно на первом и втором настроечных входах вычислительного модуля на j-м такте;

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

А ы Ы - значения .соответственно на первом и втором информационных выходах вычислительного модуля на j-м такте.

и ц а 1

1

t« X

®UZ3

Изобретение относится к вычислительной технике и может быть использовано в высокопроизводительных специализированных вычислительных машинах и устройствах обработки сигналов для решения систем линейных алгебраических уравнений и вычисления первого собственного значения и вектора матрицы. Цель изобретения - расширение функциональных возможностей за счет вычисления первого собственного значения и соответствующего ему собственного вектора. Поставленная цель достигается тем, что устройство для операций над матрицами содержит п вычислительных модулей первого типа 9, где п - порядок систем линейных алгебраических уравнений, вычислительный модуль второго типа 10 и блок 11 вывода. 4 ил., 2 табл.

Фиг. 4.

Редактор И. Шмакова

Составитель В. Якуш Техред М.Моргентал

Г77 г I,

I И

Корректор М. Демчик