Устройство для операций над матрицами

Устройство для операций над матрицами

Иллюстрации

Показать все

Реферат

 

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

СОЮЗ СОВЕТСКИХ

СОЦИАЛИСТИЧЕСКИХ

РЕСПУБЛИК (я)5 G 06 F 15/347

ГОСУДАРСТВЕННЫЙ КОМИТЕТ

ПО ИЗОБРЕТЕ1!ИЯМ И ОТКРЫТИЯМ

ПРИ ГКНТ СССР

ОПИСАНИЕ ИЗОБРЕТЕНИЯ

К АВТОРСКОМУ СВИДЕТЕЛЬСТВУ (21) 4773082/24 (22) 21.11.89 (46) 23.03,92. Бюл. ¹ 11 (72) В.П.Якуш, Н.А,Лиходед, А.А,Тиунчик и В.В.Косьянчук (53) 681.3(088.8) (56) Авторское свидетельство СССР № 1462353, кл. G 06 F 15/324, 1989.

Авторское свидетельство СССР

¹ 1633422, кл. G 06 F 15/347, 1989. (54) УСТРОЙСТВО ДЛЯ ОПЕРАЦИЙ НАД

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

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

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

„, . Ж„„1721612 Al ванных вычислительных машинах и устройствах обработки сигналов для решения систем линейных алгебраических уравнений и вычисления первого собственного значения и вектора матрицы. Цель изобретения — расширение функциональных возможностей за счет вычисления первого собственного значения и соответствующего ему собственного вектора, Поставленная цель достигается тем, что устройство для операций над матрицами содержит и вычислительных модулей первого типа 9, где n — порядок систем линейных алгебраических уравнений, вычислительный модуль второго типа 10 и блок

11 вывода. 4 ил., 2 табл. для решения систем линейных алгебраических уравнений, содержащее и ВМ, блок вывода и регистр, причем каждый BM содержит три регистра, умножитель и сумматор, блок вывода — 2п регистров, и вычислителей, и узлов сравнения, два элемента И и триггер (2), Недостатком известного устройства является невозможность вычисления первых собственных значений и векторов (и x n)матрицы, Цель изобретения — расширение функциональных возможностей устройства путем вычисления первого собственного значения и первого собственного вектора матрицы.

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

К,(<-й/

Х. +

,(к-

55

Устройство (фиг.1) содержит группу информационных входов 1, первый 2, второй

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

13 признака окончания вычислений.

Вычислительный модуль 9 (фиг,3) содержит первый 14, второй 15 и третий 16 инфор- 10 мационные входы, синхровход 17, первый

18, второй 19 и третий 20 регистры, умножитель 21, сумматор 22, первый 23 и второй 24 информационные выходы.

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

НЕ 50, умножитель 51, первый 52 и второй 25

53 информационные выходы.

В основу работы устройства при вычислении первого собственного значения il> и соответствующего ему собственного вектора xj для некоторых начальных приближе- 30 ний компонент собстве< ного вектоо)< и

Собственного значения х1, x2, ..., х о) (о) о и Л1(ц) положены формулы вида

n — 1 х< = - — (Z à j x)+ à n) хп = 1, < = ",2„,,п-1; 35

1=1 и — 1 1 =, > BnjXj+ 3nn. !

=1

Для вычисления значений х<() и А1() ис(К) (К) пользуется итерационный метод 3 ейделя решения систем линейных алгебраических уравнений, при котором значения х< и iL> определяются рекуррентн ыми соотношениями:

xj ) ) = х<(), 1 = 1 n — 1; xn() ) = 1; (к-<)

>j< < j- «< > j < " К=<2, x . (к)

>,<<->«j+l » ij «j=>,«-<, К=12> х х<() = х<() ("), i = 1,n— - 1, k = 1,2„..; хп()= 1;

gj(k),(j) хп(k) О) х (k) (j-1)+ ап)х)(k-1) ) 1 и „(К) =- Д „(К),(п) = х„(»,(<) Точность вычисления значений х; и Й определяется величиной е. Если разности Лх = xj() — х<() (1 = 1,п — 1) и bib=

= Л +Ц вЂ” Лq® удовлетворяют условию

Ih,x>I ÿ, 1ЛЛ1! я, то можно принять (k+1) (k+1) (k+1) приближенно х1 =(x1, х2, хп-1 1)

Рассмотрим работу вычислительного модуля 10 (фиг,4), логика работы которого приведена в табл.1. Вычислительный модуль 10 работает в четырех режимах, В первом режиме работы на настроечные входы 28 и 29 подаются нулевые сигналы, которые устанавливают двухтактные триггеры 33 и 34 в нулевое состояние, на выходе элемента И 47 формируется единичный сигнал, который открывает группу элементов И 37. При этом значение х, записанное в регистр 31, через группу элементов

И 37, группы элементов ИЛИ 42 и 44 подается на информационные выходы 52 и 53, Во втором режиме работы на настроечные входы 28 и 29 подаются соответственно нулевой и единичный сигналы, которые устанавливают триггеры 33 и 34 соответственно в нулевое и единичное состояния. На входы 26 и 27 постоянно подаются соответственной и единичное число. Группа эле(о) ментов И 3 6 открывается, через н е е значение х, записанное в регистр 31, подается на вход группы элементов ИЛИ 42 и соответственно на выход 52. Кроме того, через открытую группу элементов И 39 единичное число подается на вход группы элементов ИЛИ 44 и на выход 53. На выходе элемента И 46 формируется единичный сигнал, который открывает группу элементов И

38. При этом по заднему фронту тактового импульса значение Л = ib(), поданное через (о) группу элементов И 38 и группу элементов

ИЛИ 43, записывается в регистр 32 (элемент И 48 открыт и разрешает прохождение тактового импульса на синхровход регистра 32).

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

1 значение -г- . х, которое через группу элементов И 40, группы элементов ИЛИ 42 и 44 г одается на выходы 52 и 53, 1721612

В четвертом режиме работы на настроечные входы 28 и 29 подаются единичные сигналы, которые устанавливают триггеры

33 и 34 в единичное состояние, На выходе элемента И 45 формируется единичный сигнал, который открывает группу элементов И

41. Значение ((, поданное на вход 25, че(k рез группу элементов И 41 и группу элементов ИЛИ 43 подается на информационный вход регистра 32. Так как элемент И 48 открыт, значение(. по заднему фронту такто(К) ваго импульча записывается в регистр 32, Значение А с выхода регистра 31 через

k открытую группу элементов И 36 и через группу элементов ИЛИ 42 подается на выход 52. Единичное число через открытую группу элементов И 39 и группу элементов

ИЛИ 44 подается на выход 53.

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

Рассмотрим работу устройства для c óчая и = 3, На вход 2 подаются значения x> ), x2(и 1 соответственно на нулевом, втором (о) и четвертом тактах, на последующих тактах подаются нулевые значения. На входы 3,4 и

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

А1(), которые записываются в регистры блока 11 вывода. На пятнадцатом, семнадцатом и девятнадцатом тактах в вычислительном модуле 10 формируются соответственно х1 2), x2(2) и А1(2), которые также записываются в регистры блока

11 вывода. На двадцатом такте в блоке

11 вывода выполняется проверка условия

i4xi! я и 1ЛЛ1! е. Если условие для всех хлх значений, (i = 1,2) выполняется, то на выходе 13 выдается признак окончания вычислений а = 1 и с выходов 121 и 122 выдаются значения соответственно первой и второй компонент первого собственного вектора х1 = (х1,х2,1), а с выхода 12з — значение первого собствел ного значения Л1, Если

55 признак окончания вычислений а= О, то итерационный процесс вычислений продолжается. Выдача верных результатов х1 и А1 при а=1 обеспечивается блоком 11 вывода в моменты времени t = и + 2n(k+1), где k = 1,2,3,.... В остальные моменты времени t A n + 2n(k+1) съем информации с выходов 12 не производится.

При решении систем линейных алгебраических уравнений на настроечные входы 7 и 8 подаются нулевые сигналы, вычислительный модуль 10 выполняет функцию задержки информации, поступающей на его первый информационный вход 25 на один такт. Значения корней уравнений xi (i = 1,п) снимается с выходов 121 при G = 1 в моменты времени t = n + 2n(k+1), k = 1,2,3,. „

Формула изобретения

Устройство для операций над матрицами, содержащее (n+1) вычислительный модуль (и — порядок системы линейных алгебраических уравнений) и блок вывода, причем первый информационный вход устройства подключен к первому информационному входу и-го вычислительного модуля. первый информационный вход i-го вычислительного модуля (i = 1,п — 1) подключен к первому информационному выходу (i+1)-ro вычислительного модуля, первый информационный выход первого вычислительного модуля подключен к первому информационному входу (n+1)-го вычислительного моду.:я, первый информационный выход которого подключен к первому информационному входу блока вывода. второй информационный выход (и+1)-го вычислительного модуля подключен к второму информационному входу первого вычислительного модуля, второй информационный выход i-ro вычислительного модуля подключен к второму информационному входу (i+1)-го вычислительного модуля; j-й информационный вход группы входов устройства (j = 1,п) подключен к третьему информационному входу

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

xi1/bi если (а3, P) = (1,0) A1+1 =

, если (а, Р ) = (0,0)к(0,1)к(1,1)

, если (а, p) = (0,0) v(1,1) В1 = 1, если (а3, ф) = (0,1) х 1/Ь1, если (а(, p) = (1,0) А1 1 = а1 bj + с1, 10 где

> с, если(а" p )=(0,1) х, если (а р, р р) = (1,1) Bl 1 = bj

Таблица 1

Режим :; Входы Содержимое Выходы работы

25 26 27 i 28 j 29 Рт31 Рт32! 52 53 х (4 1 х 9(o) 1 (1

0 х

1 х

О х х х х 1 (к1 1 ( х — — х к) 1 (g (ê) (К) 1 х (к) Ъ(1 1

50

55 формационные входы устройства подключены соответственно к одноименным входам (и+1)-го вычислительного модуля, первый и второй настроечные входы которого являются одноименными входами устройства, причем вычислительные модули с первого по и-й выполнены с возможностью реализа. ции следующих функций; где aj, bj u cj — значения соответственно на третьем, втором и первом информационных входах вычислительного модуля на j-м такте;

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

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

Aj u bj — значения:соответственно на первом и втором информационных выходах вычислительного модуля на j-м такте.

1721612

10 о к

О Р3 х

Ях х

33 х р

Фэ х

« х о

O CI х л Ю х

Ф х

«» х

С3 х

Ф х

С3

I33

«

3О о к о х о

Хо М х фр х х

Я» х о о мн н ф ol ф о

«х =х о

Хо П3 х

-х о н

gCI х

С3

rg Il

-х

-х о

;н н

-х о х фр х! I ° 1 х

1 1 gj 1

1 I mN 1

1 11

1 1 1

3 1 ° 1

1 Х

Зм !

1!ЮСЧ!

1 1 I

3 CC I 1

i С3 1

3 Р

I m!QN1

3 1 1

1 I I

I 1 1

34Cn !

1 1 f4ë 1! 1 I! 1 1! 1 1

I 1 34 CO 1

1 1 фф 1 л х х

«С4 х

З с3 х х х

5 е х х,о Ol х

Я» х с3 х

A х о о

О,3 х л к о х о о х л

«

g C4 х

D \Ч х

1 1!

Я С3 х

1

1

I

I

I

1

I ! ! !

1

1

1

1

1 ° 1 х

1 2 I

I m34 1

1 I х лм !

1 m N 1

1 1

О 1 1

Е1 МО 1

О!1 QN 1

1 1

1 1

1 34 CPI 1

3 $4 е — 1

1 1

à — -1

I 1

1 3к СО I

Зов l ло л о« х

М» х т х

IA х

Эа к

D х

«» х ю х» х ло х к х х о к о х о с4 х р фд х

«р3 х о

ЙЪ

Q х 3 эс о к х

» х

Ol

М

Ю х

О р3 х

» к х х о х

«« х

1 х зм !

3О 33 Ъ I

Х I

BIN I

CO 33\ 1

1

9.(м 1 х х

«С3 х х о ох ло

С4

13 х со е х х х

Я П3 х

Як х ло

Ио ъ

О С3 х

» х х

Я х р р оСР

СС. С= С а о х о 1

mГ4 1

1

1 о 1 км 1

I

3ъм I ч м

l !

34 33 р, м

1 р

СС С С< р

СС о о о о о о о о о о о о о о

СС СС о

СС Со р о» р о

1 1 1 1 1

1 П3 П3 1

3- 1

I

1

1

301

1 1

1 <в3 сп

С1 m

tO I

П31

3- I

1!

1

1

1

1

1

1

1

I.

1

1

1

1

I .1 О

1 °

Е

1 m

1

I

3

1

I

1

1! . I

I 1 ! 1

1 1

I ° I

1 х 1

I Я - 3 1

I СОN!

1 I

1 1

1 1

1 ° 1

3С

З м

1 m N

1 I

Мо

1 C4N 1

1 1

1 1

1 1

3к CCI I

I C4 1

I 1

1 l

I 1

34 IXI

1 33е а- 1

I

1

1

1

1

1

1

1

1

l

1

1

I

1

I

1

1

1

I

1 р о о о о х о о о о о о о

Р О О О О О О О D O л О о о о о о о оО СЧ М -П а 33 Л СО

Ф С4 х к х

° Ф х о

П3

О С3 х о р ° х

1721612

ФМ с

» ф« а!

Ф«Ф

1721612

1721612 Я/Г5

I !

Заказ 954 Тираж Подписное

ВНИИПИ Государственного комитета по изобретениям и открытиям при ГКНТ СССР

113035, Москва, Ж-35, Раушская наб., 4/5

Производственно-издательский комбинат "Патент", г. Ужгород, ул.Гагарина, 101

4 Х!! I!

Составитель В. Якуш

Редактор И, Шмакова Техред М.Моргентал 0 l

1 (! !

7й

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