Устройство для операций над матрицами
Изобретение относится к вычислительной технике и может быть использовано в высокопроизводительных специализированных вычислительных машинах и устройствах обработки сигналов для решения систем линейных алгебраических уравнений и вычисления первого собственного значения и вектора матрицы. Цель изобретения - расширение функциональных возможностей за счет вычисления первого собственного значения и соответствующего ему собственного вектора. Поставленная цель достигается тем, что устройство для операций над матрицами содержит п вычислительных модулей первого типа 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й Корректор М. Демчик
