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

СОЮЗ СОЕЕТСНИХСО 1.1 ИАЛИСТИЧЕСНИХРЕСПУБЛИН А 1 С 06 Р 15/3гщ:чрС . 110011.1 п щ СУДАРСТВЕННЫЙ НОМИТЕТ СССРО ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТКРЫТИЙ(71) Киевский политехнический институт им.50-летия Великой Октябрьскойсоциалистической революции(56) Седухин С.Г. Параллельная интерпретация прямых методов линейнойалгебры. - Программирование, 1984,У 4,Авторское свидетельство СССРУ 1401478, кл, С 06 Р 15/347, 986.(54) УСТРОЙСТВО ДЛЯ ОПЕРАЦИЙ НАДМАТРИЦАМИ 901443 ОО(57) Изобретение относится к вычисли.тельной технике и может быть использовано дпя выполнения матричных опе-,раций. Целью изобретения является;расширение функциональных возможностей. Устройство содержит М операци -йонных блоков 1, Кэлементов 2 задержки и распределитель 3 импульсовОперационный блок 1, 1.1 содержит входной регистр и блок деления 1,М,операционный блок 1.1,1(д 2,Б,=Г 1 11) содержит два регистра сомножителей, умножитель, вычитатель, выход"ной регистр. Поставленная цель дос-тигается за счет введения новых элементов и связей. 8 ил.Изобретение относится к автоматике и вычислительной технике и можетбыть использовано при построенииспециализированных устройств, "редназначенных для решения систем линейных уравнений,Цель изобретения - расширениефункциональных возможностей эасчетрешения систем линейных уравнений 10и обращения матриц.На фиг.1 представлена структурнаясхема устройства для операций надматрицами; на фиг.2 " функциональная схема операционного блока 151( 1 у 2 уе а уИ) у на фи 13 фнкциональная схема операционного блока11(1.=2,3 И;1,2,,И);наФиг,4 - функциональная схема элемента задержки К(К=1,2И); 20на фиг,5 - схема распределителя импульсов; на фиг,б - 8 - блок-схемаалгоритма Функционирования устройства,йУстройство содержит М операционных блоков 1.1.,1(з,1=1,И), Иэле"ментов 2 задержки, распределитель 3импульсов.Операционный блок 1.1. Ц=1,И)содержит входной регистр 4, блок 5 30деления, синхровход 6. Операционный блок 1, 1,(д 2, И;=1. И) содержит регистр 7 первого сомножителя,умножитель З,вычитатель 9,регистр 10 второго сомножителя, выходной регистр 1, синхровходы 12 -14. Элемент 2,К (К=1,И) содержитрегистры 15 и 16 и синхровходы 7и 18,40Распределитель 3 содержит генератор 19 синхроимпульсов, элемент И 20счетчик 21 тактов, блок 22 памя гимикрокоманд, выходы 23-29 распределителя.45Выход 23 подключен к управляющимвходам 6,1.1 и 6.1.3, выход 24 - куправляющим входам 12.2.1 и 12.2,3,выход 25 - к входам 12.3.1 и 123,3,выход 26 - к входу 6,1.2, выход 27к входу 12.2.2, выход 28 - к входу5012. 3, 2, выход 29 - к управляющим входам 13.2.1, 13,3.1, 13,2,2, 13,3.2,13.2,3, 13,3,3, 14,2,1, 14,3,1,14,2.2,.14,2,3, 14.3,3, 17,1, 7.2)18,1, 18,2,55Устройство для операций над матрицами может выполнять Ы-разложение,вычислять обратную матрицу, решать систему М линейных уравнений методомГаусса-Жордана. Вычисления основанына преобразовании исходной матрицыв треугольную для Л 1-разложения либов единичную.Для получения Ю-разложения устройство обрабатывает исходнуюматрицу размерности И ф И, При решениисистемы линейных уравнений и при вычислении обратной матрицы выполняется обработка расширенной матрицы размерности ИМ, которая представляетсобой исходную матрицу размерностиИИ, к которой справа дописана матрица размерности Их(М-И),При вычислении обратной матрицы кисходной матрице справа дописывается единичная матрица размерностиИМ (в этом случае М=2 И) и после того, как исходная матрица будет преобразована в единичную, на местеприписанной. справа единичной получимобратную,При решении системы линейных уравнений к исходной матрице (ИфИ) справадописывается Я столбцов свободныхчленов (в этом случае М=М+8) и после того, как исходная матрица будетпреобразована в единичную, на местестолбцов свободных членов получимсемейство решений данной системылинейных уравнений. Число Б при данной организации вычислений можетбыть любым натуральным,Все перечисленные алгоритмы объединяют идентичность базовой операции преобразования:к) (к(к(к- а(ки(оа= ах 1 (3 с-и Ск-Оа : а/а , К = 1,2М, Ц = К+1,К+2И.При этом для Ю-разложенияЬ(к-О (к К = 1,2И, Ц = К,К+1,К+2И.Поскольку все вычисления выполняются аналогично, для примера рассмотрим работу устройства при вычислении обратной матрицы размерности 3 3.Условимся, что информация в регистры принимается в конце такта(о)дение С ,. получается На выходе умаг агг аг аа, а,ло элемент С)г(а)ное Са/гистр 10 конце такта част 2тся на вход блока которого получаетсна выходе умножите(а) (о) (а) изона выходе вычиУние Сз и определитель исходной матрицы неравен нулю. Итак, имеется исходнаяматрица 10 Допишем к ней справа единичную мат- рицу и получим расширенную матрицу С, под которой будет выполняться пре образование Сг Сгг Сгз Сга Сгу25 ССг СС)а Сзу С Элементы матрицы С поступают на входы операционных блоков построчносо сдвигом на один такт, т,е, первая35строка поступает на первый вход операционного блока 1.1.1, начиная спервого такта, вторая строка поступае т на первый вход операционного бло 40ка 1,2.1, начиная с второго такта,третья - на вход блока 1.3.1, начиная с третьего такта.(а)В первом такте элемент С = 1 принимается в регистр 4.1.1. Во втором такте элемент С, поступает на(о)вход блока 1.1,1, на выходе которого получается частное С, /С= ц,= С, .Это частное в конце такта принигмается в регистр 10.2.1 блока 1.2,1,; 50а элемент С , = 1 г, принимается в(а)регистр 7,2,1.В третьем такте элемент С поступает на вход блока 1,1.1, на выходе которого получается частное 55 С о /С= Б 1 = С, Элемент поступает на первый вход блока 1,2,1. На выходе умножителя 8.2,1 получается(а) а) (а)произведение С , / С , С ; , которое поступает на вход вычи тателя 9 . 2, 1 , и н а е г о выходе получается выраже, (а) ( ф) (а) (а)ние С = С - Сг /Си Сг 1 гг(а) (а) В конце такта частное С 1 /С(а)В четвертом такте элемент С) подается на вход блока 1,1.1, на выхоце которого получается частное (а) (а)С / С = С , н а выходе умножи те 14 4(а) (а) ля 8 , 2 , 1 - прои зв едение С , / СС которое подается на вход(о)вычитателя 9.21. На второй вход вычитателя поступает элемент (о)Сг, инав 1 на выходе вычитателя43003 5С выхода регистра 11.2.1 С, поступает на вход блока 1,1.2, на выходе которого получается частноеО) Ж (г)Г г /С гг г = Сг. В конце такта, (4)С записывается в регистр 11 2, 1,С - в регистр 11.3.1, С г - в ре(1) )гис тр 7 , 2 . 2 ,(о)В шестом такте элемент С,б поступает на вход блока 1.1.1, на выходе которого получается частное(О), (о), ИС, /С= С(6, на выходе умножителя 8.2.1 получается произведение/С я С на выходе вычитателя 9. 3. 1(а) (о) (а) (о)выражение С ,( = Г 4 - С, /С 11 С выхода регистра 1,21 С пос" " тупает на вход блока 1,.2, на выходе которого получается частное( (г)С,С, .= С, На выходе умножителя 8.2,2 получается произведениеН) (е) (1)Сг)/С, С , а на выходе вычитате, (г) й) . (1),ля 9,2,2 - выражение С = С -С з//С гг С иг = 1 зВ конце такта част(о) , (о)но е С, / С , = С , принимается врегистр 1 0 , 2 . 1 , ч а с тн о еС / С.2,1, С. - в регистр 11.31,ф ЪФС- в регистр 11,2,2В седьмом такте на выходе вычитателя 9.21 получается выражение(1) (о) (о) (о) (о)С 35 - С з- С , /С иС, С выхода регистра 11,2,1 С подается на вход.2.2 С, - в регистр 11.3.2.В восьмом такте на выходе вычитателя 9.3.1 получается выражение(1) (о) (о) (а) (а)Са= Ся - С, /С н Сна выходе 3 блока 1,1.2 - частное Сг/Сгг= Сый) О)ыуна выходе вычитателя 9.2.2 - выраже(г)(1)ние С = С - Сг/С гг С г, на выходе вычитателя 9.3.2 - выражение(г)гистра 11.2.2 С ( подается на входблока 1.1.3, на выходе которого получается частное С) /Сэ = С, Б кон(г) (г) ( )гистр 11.3.1, С- в регистр4 - в рВ девятом такте на выходе вычитателя 9.2.2 получается выражениеи)С , - С г / С г, Сг , н а выходег) г) (з)блока 1,1.3 - частное С)/С) / Сна выходе вычитателя 9,2.3 - выраже) (г) (г) (г) (г)ние С, = С, - С /С,) - С. В кан(о) о)це такта частное С /С= С, принимается в регистр 16,1, частное- (М11.2.3.В десятом такте на выходе вычитателя 9,3,2 получается выражение(г) (1С 6 Ся Сгб/Сгг С, на выходе блои) (г) Л) ка 1,.3 - частное С /С, Сна выходе сумматора 9.2.3, - выраже 1 З) (г) г) г) (г)ние С, = С, - С, /С С на выходе сумматора 9.33 - выражение(ъ 111.2,3, Сг вв регистр 11.3.3:В одиннадцатом такте на выходе вычитателя 9.2,3 получаем выражениеИ) (г) (г) (г) (г)С= С,6 - С 6 /С ) С, на выходе)оЭ бсывяется в регистр 11.2.3, С - врегистр .3.3.5 В двенадцатом такте на выходе вычитятеля 9.3.3 получается выражениеО) (г) (г ) (г) (г)( г 6 = Сгб Сь /(Г г , которое в .конце тяктя принимается в регистр 10 11,3,11 р,. этом вы шсление обратной матрицы зякянчивяется. Иячиная с восьмого тяктя ня первых выходах блоков13, 1,2,3, 1.3.3 появляются эле менты обратной матрицы,(й С,.Ю С а з) С)ь А Формула и з о б р е т е н и я Устройство для операций над матрицами, содержащее И,М+1)/2 операционных блоков и распределитель импульсов, выходы которого подключены к синхровходам операционных блоков,Па вьходях устройства получаются элементы обрятной матрицы по строкам, т.е. ня выходе блока 1.1.3 по 25являются элемет, третьей строки,т,е. ня выходе блока 1.2.3 - первой,ня выходе блока 1.3.3. - второй.Для общего случая 1 выходовраспределение строк следующее: г-ястрока результата выдается с (г+1)30го выходя для г = 1Б),Я-я строка - с 1-го выходя,Сразу же после ввода первой строки исходной матрицы, те. в данномпримере с седьмого такта, можно начинять вводить следующую исходную матрицу аналогичным образом: каждаяследующая строка подается со сдвигом на один такт,При решении системы линейных урав 40некий в качестве элементов матрицыВ подаются свободные члены заданнойсистемы уравнений. Тогда на выходеполучается семейство решений этой145системы уравнений, СтолбецС, Сг Сявляется решением сисЮ (з) И)темы при столбце свободных членовТ М)ЬЬ, Ь)Д, столбецС С г. С.1 -,.50решением свободных членовЬг Ьгг ЬДи т,д.9 1 Дг.ЗООЗ 1 Огде Н - размерность матрицы, о т - (1=13 11 И)первый Вход 1 1 ГО л и ч а м Щ е е с Я тему чтоу с операционного блока подключен к перцельв расширения функциональных воз вому выходу (1+1) (-1)-го операционможностей за счет решения систем ли ного блока, (1=1,И; 1=2,М), первый нейных уравнений и обращения матриц, вход операционного блока М,1 подклюв него введены И (Ы)/2 операцион- чен к выходу (1-1)-го элемента заных блоков и Нэлементов задерж- держки, ( -2,д), вход которого лодки, причем первый вход 1.1-го опера- клячен к второму выходу Ы (1-1)-го ционного блока подключен к "му вхо 10 операционного блока (1=2,И), втоРой ду устройства, (1=1,М), первые выхо- вход ,-го операционного блока подды 1.Н-х и 1,д-х операционньгх блоков клвчен к второму выходу (-1),1-г подключены к выходам устройства, операционного блока (=2,К; 1"1,11)1443003 оставитель М.Сил Корректор Л.Пат каз 6386/46 Проектная, 4 Производственно-полиграфическое предприятие, г, Ужгор актор В.Петраш Техред М.Ходанич Тираж 704 ВНИИПИ Государственно по делам изобретен 13035, Москва, Ж, РаПодписноекомитета СССРи открытийская наб., д. 4