Устройство для выполнения операций обращения матриц Советский патент 1986 года по МПК G06F17/16 

Изобретение относится к вычислительной технике. Целью изобретения является расширение функциональных возможностей за счет получения псевдообразных матриц для вьфожденных,квадратных, прямоугольных, плохообусловленных матриц и для матриц, полученных перемножением векторов. На фиг. 1 представлена схема уст ройства; на фиг. 2 и 3 - схемные пр меры блоков формирования матриц на фиг. А - схема блока умножения и су мирования j на фиг. 5 - схема блока управления. Устройство содержит блоки 1 и 2 памяти, блок 3 управления, блок 4 памяти, блоки 5 и 6 формирования . матриц, блок 7 умножения и суммирования, блок 8 умножения, блоки 9-14 элементов задержки, умножители 15, узлы 16 умножения и суммирования, сумматоры 17, делители 18, узлы 19 коммутации, группы 20 элементов И, узлы 21 памяти, схема 22 сравнения, буферный запоминающий узел 23, умножители 24, узлы 25 коммутации, сумматоры 26, узлы 27 умножения и суммирования, схема 28 сравнения, группы 29 элементов И, делители 30 узлы 31 и 32 памяти, умножитель 33 сумматор 34, генераторы 35 прямоугольных импульсов, счетчики 36, эл менты 37 И, генератор 38 прямоуголь ных импульсов и счетчик 39. Устройство работает следующим об разом. Блок 1 памяти хранит вспомогательную матрицу , которая может быть представлена в виде вектора-столбца а- размера п-1 и мат рицы AJ размера Ln-m-lj: S; ta;|A;, Блок 2 памяти хранит матрицу ра мера пГп, подлежащую обращению, которая может быть представлена в виде вектор-столбцов Х-: . ...-.;Х;|..Х„. Блок 4 содержит известную для вспомогательной матрицы S; псевдообратную матрицу . Работа устройства начинается после поступ ления с блока 3 признака смены информации п импульсов на сдвиг инфо мации в блоке 2. В результате на выходе блока 2 будут сигналы, соот 962 ветствующие элементам вектор-столбца . Эти сигналы поступают на входы блока 1, вытесняя из него элементы вектора-столбца а. В результате в блоке 1 образуется новая матрица Т;, А; X;j, псевдообратную для которой необходимо найти. Сиг-, налы с выходов блока 1 поступают на блок 5 формирования матриц А. Сигналы Xj с выхода блока 2 проходят на входы блоков 10 и 11 элементов задержки. На вход блока 5 поступают сигналы, считанные из блока 4, соответствующие элементам матрицы Sj. Они считываются из блока 4 по сигналам блока 3. Кроме того, по этим же сигналам из блока 1 считывается матрица А; размера n-m-l и поступает на вход блока 9 элемента задержки. На выходе блока 5 появляются сигналы, соответствующие элементам псевдообратной матрицы А; размером m-l-nl; Эти сигналы поступают на вход блока 8 умножения, на другой вход которого поступают задержанные на время формирования матриць А; сигналы, соответствующие элементам вектора-строки X;. С выходов блока 8 сигналы, соответствующие элементам вектора-строки А,Х. размера т-Ь , поступают на вход блока 6 формирования матриц, на вход которого поступают также сигналы с выхода блока 5, задержанные на время формирования матрицы и вектора в блоке 9 сигналы о матрице AJ, а также задержанные на это же самое время в блоке 11 сигналы о векторе Xj, В блоке 6 происходит формирование вектора-строки, который является последней строкой псевдообратной для матрицы Т;, матрицы Т , которая имеет вид г -1нУ, Сигналы, соответствующие элементам строки hT, поступают на вход блока 7, на другие входы которого поступают задержанные в блоке 12 на время формирования строки сигналы с выхода блока 8 умножения и с в псода блока 5 формирования матриц, задержанные в блоке 13 сигналы о составляющих А;. В результате на выходе блока 7 получаются сигналы, соответствующие элементам матрицы Н;, размерности fm-l-nj. Эти сигналы.

так же как и задержанные в блоке 14 на время формирования Н ;, сигналы о векторе h, , поступают на вход блока 4, осуществляя в нем полную замену старой псевдообратной матрицы S; на новую S,. Перед этим из блока 3 на блок 4 поступает сигнал С5, который приводит в исходное состояние блок 4 перед записью в него вычисленной псевдообратной матрицы. Блок 3 выдает преобразованные в импульсы сигналы на блок 2, из которого вытесняется следующий столбец. Операции по формированию псевдообратной матрицы для матрицы X продолжаются до тех пор, пока из блока 2 не будут вытеснены все m столбцов матрицы X. В этом случае в блоке 4 на каждом шаге формируется некоторая промежуточная псевдообратная матрица, которая на последнем шаге будет равна псевдообратной матрице Х для матрицы X. Таким образом для псевдообращения матрицы размерности п-т} требуется m шагов. Блок 3 осуществляет не только формирование импульсов .на вытеснение информации из блока 2, но и формирование сигналов для управления блоками устройства.

Блок 5 формирования матриц (фиг,2 работает следующим образом.

Сигналы о векторе а; поступают на вход блока 5, а именно на вход умножителя 15, на вход которого поступают сигналы с выхода блока 4. Сигналы с выхода умножителя 15, соответствуюрще составляющим векторастолбца .1, поступают на вход сумматора 17, на второй вход которого поступает информация о векторе g размерности имеющего вид

Из узла 21 (хранения g) считьшается информация по сигналу С1 кольцевого счетчика 36. Сигналы с выхода сумматора 17 поступают на входы схемы 22 сравнения, в котором происходит сравнение вектора () с нулевым вектором той же размерности tr-lj. В результате сравнения сигналы с выхода схемы 22 сравнения поступают на входы одной из двух групп 20 элементов И в зависимости от того, равен результат сравнения нулю или нет. Информация о составляющих вектора g из узла 21 одновременно поступает на узел 19 векторастолбца g и далее - на умножитель, па второй вход которого поступают сигналы о составляющих матрицы. Сигнальт о векторе-строке проходят через группу 20 элементов И, если результат сравнения в схеме сравнения не равен нулевому вектору, и поступают на вход умножителя 15, на второй вход которого одновременно постпает информация о составляющих вектора-столбца (g-S- а;), Выходные сигналы, соответствующие элементам матрицы

()gs fm-n,

поступают на вход делителя 18, на второй вход которого поступает скалярная величина. Эта величина формируется следующим образом.

Сигналы о составляющих вектора S;aj поступают на узел 19 и далее на узел 16 умножения суммирования, на второй вход которого поступают сигналы о составляющих вектора S,а j. На выходе узла 16 фо.рмируется скалярная величина, которая поступает на вход сумматора 17, на второй вход которого поступает информация о единице, хранимой в узле 21 и считанной оттуда сигналом С, кольцевого счетчика 36. Получившийся на выходе сигнал вида 1 - (S; а,) (S| а; )j приходит на вход делителя 18, С выхода 18 сигнала матрицы М пост Т1ают на вход сумматора 17, на второй вход которого поступают сигналы об элементах матрицы S. В сумматоре 17 происходит вычитание из элементов матрицы ST размера m.nl элементов матригцл . М размера m-n. С выхода сумматора 17 сигналы поступают на вход узла 23 для исключения верхней нулевой строки. В результате на выходе узла 23 будут сигналы, соответствукяцие элементам матрицы А раз1мера т-1- п В том случае, когда в схеме 22 сравнения получается нулевой вектор, то сигналы с выхода схемы 22 поступают на первые входы элементов И второй группы, на вторые входы которых поступают сигналы о составляющих вектора , которые проходят далее на умножитель 15. Одновременно сигналы о векторе поступают на первый вход умножителя 15, на второй вход которого поступают сигналы о транспонированной матрице (St) n-m с узла 19. Сигналы с выхода умножителя.13 о составляющих вектора (St)(sta) n-l поступают на вход узла 19 транспонирования и далее на вход узла 16 умножения и суммирования, на второй вход которо го поступают сигналы с тех же составляющих вектора (S-,) (,), На выходе узла 1 б получается скалярный сигнал, соответствующий величине (S:r(S,)4(S;r(sta,). Этот сигнал по,ступает на вход делителя 18. Сигналы с выхода узла 19 матрицы (S) поступают на первый вход умножителя 15, на второй вход которого поступают сигналы о состав ляющих матрищ, ST . На выходе данного умножителя 15 получаются сигналы, соответствующие элементам матрицы st (St ) fm-mi. Эти сигналы поступают на второй вход умножителя 15, на первый вход которого поступают сигналы с элементов И 20. На выходе умножителя 15 получаются сигналы о составляющих вектора S(S;) () размера m- 1 , Эти сигналы поступают на первый вход умножителя, на второй вход которого поступают сигналы о векторе-столбце . На выходе данного умножителя I5 получаются сигналы о составляющих матрицы SjSt S - a;ff S; размера . Эти сигналы поступают на делитель 18 с выхода которого сигналы проходят на вход сумматора 17, в котором из сигналов, соответствующих матрице R;, вычитаются сигналы, соответствующие матрице N(S; S, 5,а;д S;), S-. S S,aJ. Получившиеся сигналы, соответствующие матрице S-.-N размера , поступают на узел 23, на выходе которого формируются сигналы о составляющих матрицы К размера Гт-. ПО сигналам СЗ счетчика 36. По сигналу Сброс осуществляется прив дение всех узлов в исходное состоян Блок 6 (фиг. 3) работает следующим образом. Сигналы соответствующие элемен: там матриц А т-Т-п и Aj nm-1J, поступают на вход умножителя 24, на выходе которого формируются сиг налы, соответствующие элементам матрицы А;А размера . Эти сигналы поступают на сумматор 26, в котором вычитаются из единичной матрицы размера n-nj, поступающей 66 на вход сумматора из узла 31 по сигналам С1 счетчика 36. Сигналы с выхода сумматора 26 поступают на вход умножителя 24, на вход которого поступают сигналы о составляющих вектора X; . Сигналы с выхода этого умножителя 24, соответствующие элементам вектора (1-А, А )Х; fn- , поступают на вход схемы 28 сравнения сигналов о векторе с нулевым вектором, а также на вход узла 27 умножения и суммирования, на вход которого поступают сигналы о составляюпщх транспонированного вектора с узла 25. На выходе узла 27 формируется скалярный сигнал, соответствующий величине X |(1-А;А ;)Х; который поступает на вход делителя 30. На вход делителя 30 поступают прощедшие через элементы И 29 (если результат сравнения не равен нулю) сигналы о составляющих вектора (l-AjA)X-. В результате на выходе делителя 30 формируются сигналы, соответствующие составляющим вектора-столбца h;, п-1. Эти сигналы проходят через узел 25, на выходе которого получается искомая векторстрока. В том случае, если резуль т сравнения в схеме 28 сравнения равен нулю, то сигналы с него поступают на входы элементов И другой группы. Сигнапы о составляющих вектора A;X; m-1lj поступают на вход узла 25, после чего проходят на вход узла 27, на второй вход которого поступают сигналы о векторе . на выходе узла 27 формируетсяскаляр„ сигнал, соответствующий величи„е (AtX; Г (Д-Х;). Этот сигнал посту„ ет на сумматор 26, в котором происходит его суммирование с единичным сигналом, поступивщим из узла 32 по сигналу С2 счетчика 36. Выходной v-rjii ntwijr v с, ч.с: 1 ЧЛ,1.С1 JV/ JJDI. сигнал сумматора 26 поступает на 30, на второй вход которого поступают прошедшие через элементы И 29 сигналы с выхода умножителя 24, соответствующие элементам векто-„ , .- , ра (А; ) ; п-1J . На вход умножителя 24 поступают сигналы о составляющихвектора AjX; n-11J, а на другой вход - сигналы с выхода узла 25 (А j) об элементах этой матрицы n-m-l. Сигналы с выхода делителя 30, соответствующие величинам At А;Х;/1 + ()( ) поступа- ют на вход узла 25,на выходе котооого формир тотся сигналы об искомом векторе . По сигналу Сбро осуществляется приведение в исходное всех узлов блока 6. Блок 7 (фиг. 4) работает следующим образом. Поступающие на его вход о составляющих вектора-строки h ,-, и вектора-столбца AjX;{m-b1 поступают на входы умножителя 33, на выходах которого формируются сиг налы о составляющих матрицы А.Х; h1- -, / 1 размерности m-l-nj. Эти сигналы поступают на вход сумматора 34, на другой вход которого поступают сигналы о составляющих матрицы А(т-1 кр). На выходе сумматора 34 формиру ются сигналы искомой матрицы Н- , X X А-А; X; h;,. По сигналам С4 эта информация переписьшается в блок 4, а по сигналу Сброс осуществляется приведение в исходное состояние умножителя 33 и сумматора 34. Генератор 35 и счетчик 36 в блоках 5 и 6 предназначены для синхронизации работы устройства. Узел ком мутации осуществляет переворот матрицы относительно главной диагонали (операцию транспонирования). Все блоки памяти содержат в своем соетаве, например, регистры сдвига, столько, сколько необходимо в каждом из рассмотренных в устройстве блоков. Буферный запоминанщий узел представляет собой узел памяти, состоящий, например, из регистра сдвига, однако считывание информации в этом узле осуществляется со всех параллельных регистров сдвига, кроме первого, Блок 3 управления работает следующим образом. По сигналу пуска включается в работу генератор 38, импульсы с которого поступают на вход счетчика 39, сигнал с выхода счетчика 39 С, поступают на одни входы элементов И 37, на вторые входы которых поступают импульсы с выхода генератора 38. Импульсы с выходов элементов И 37 поступают на входы блока 2 Время действия импульсов определяется временем действия сигнала Ср. По сигналам С1 осуществляется считы вание информации из блоков 4 и 1, по сигналам С2, СЗ, С4 - синхронизация работы блоков 5-7, по сигналу С5 осуществляется приведение в ис968ходное блока 4, по сигналу Сброс приведение в исходное блоков 5-8. Формула изобретения 1. Устройство для выполнения операций обращения матриц, содержащее первый блок памяти и блок управления, отличающееся тем, что, с целью расширения функциональных возможностей за счет получения псевдообратных матриц для вьфожденных, квадратных, прямоугольных, плохообусловленных матриц и для матриц, полученных перемножением векторов, в него введены блок умножения и сум- . мирования, второй и третий блоки памяти, первый и второй блоки формирования матриц, блок умножения и шесть блоков элементов задержки, причем первая и вторая группы информационного выхода первого блока памяти подключены соответственно к первому информационному входу первого блока формирования матриц и к входу первого блока элементов задержки, выход второго блока памяти соединен с информационным входом первого блока памяти и с входами второго и третьего блоков элементов задержки, выход второго блока элементов задержки соединен с первым информационным входом блока умножения, выход которого подключен к входу четвертого блока элементов задержки и к первому информационному входу второго блока формирования матриц, второй информационный вход которого, второй информационный вход блока умножения и вход пятого блока элементов задержки с выходом первого блока формирования матриц, второй информационный вход которого соединен с выходом третьего блока памяти, выходы первого и третьего блоков элементов задержки соединены соответственно с третьим и четвертым информационными входами второго блока формирования матриц, выход которого соединен с первым информационным входом блоке умножения и суммирования и через тестой блок элементов задержки подключен к первому информационному входу третьего блока памяти, выходы четвертого и пятого блоков элементов задержки соединены соответственно с вторьм и третьим информационными входами блока умножения и суммирования.. выход которого подключен к второму информационному входу третьего блока памяти, вход пуска блока управления является входом пуска устройства, установочный выход блока управления подключен к установочтагм входам блок умножения первого и второго блоков формирования матриц и блока умножения и суммирования, группа выходов считывания блока управления подключе на к группе входов считывания второго блока памяти, первый синхронизиру ющий выход блока управления подключен к входам считьгеания первого и третьего блоков памяти, второй, третий, четвертый и пятый синхронизирующие выходы блока управления соединенъ соответственно с синхронизирующими входами первого и второго блоков формирования матриц, блока умножения и суммирования и третьего блока памяти, причем первый блок формирования матриц содержит умножители, делители, сумматоры, узлы коммутации, узлы памяти, схему сравнения, буферный запоминающий узел, счетчик и генератор прямоуголь ных импульсов, вход которого является синхронизирующим входом первого блока формирования матриц, а выход подключен к счетному входу счетчика, установочный вход которого I является установочным входом первого блока формирования матриц, выходы разрядов счетчика подключены соответственно к входам считывания перво го и второго узлов памяти и буферного запоминающего узла, выход кото рого является выходом блока, первый вход первого умножителя является пер вым информационным входом первого блока формирования матриц, выход . первого узла памяти соединен с пер-, вым входом первого сумматора и через первый узел коммутации - с первым входом второго умножителя, выход пер вого умножителя соединен с первым входом третьего умножителя, с вторым входом первого сумматора и через второй узел коммутации - с первьм входом первого узла умножения и сум мирования, выход второго умножителя подключен к первым входам четвертог умножителя и элементов И первой i-py пы, выходы которых соединены с первы входом пятого умножителя, выход кот рого соединен с первым входом перво го делителя, выход которого подключен к первому входу второго сумматора, выход которого соединен с первым информационным входом буферного запоминающего узла, выход первого сумматора соединен с вторым входом пятого умножителя и с входом схемы сравнения, выход ненулевого значения которой соединен с вторыми входами элементов И первой группы, выход нулевого значения схемы сравнения соединен с первыми входами элементов И второй группы, вторые входы которых и второй вход первого узла умножения и суммирования соединены с выходом первого умножителя, вьпсод первого узла умножения и суммирования соединен с первым входом третьего сумматора, второй вход которого соединен с выходом второго узла памяти, выход третьего сумматора соединен с вторым входом первого делителя, второй информационный вход первого блока формирования матриц соединен с вторыми входами первого и второго умножителей и второго сумматора, с первым входом четвертого сумматора, с входами третьего узла коммутации и шестого умножителя, выход которого подключен к первому входу седьмого умножителя, второй вход которого соединен с выходами элементов И второй группы, выход третьего узла коммутации соединен с вторым входом третьего умножителя, выход которого соединен с первым входом второго узла умножения и суммирования, второй вход которого через четвертый узел коммутации соединен с выходом третьего умножителя, выход второго узла умножения и суммирования соединен с первым входом второго делителя, выход которого подключен к второму входу четвертого сумматора,второй вход второго делителя соединен с выходом четвертого умножителя, второй вход которого соединен с выходом седьмого умножителя, выход четвертого сумматора подключен к второму информационному входу буферного запоминающего узла, второй блок формирования матриц содержит узлы коммутации, умножители, сумматоры,, делители, узлы памяти, узлы умножения и суммирования, группы элементов И, счетчик и генератор прямоугольных импульсов, вход которого является синхронизирующим входом второго блока формирования матриц, а выход подключей к счетному входу счетчика, ;установочный вход которого является установочным входом второго блока формирования матриц, второй информационный вход второго блока формирования матриц соединен с первым входом первого умножителя и через первый узел коммутации - с первым входом второго умножителя, первый информационный вход второго блока формирования матриц соединен с вторым входом второго умножителя, с первым входом первого узла умножения и суммирования и через второй узел коммутации - с вторым входом первого уз ла умножения и суммирования, второй вход первого умножителя является тре тьим информационным входом второго блока формирования матриц, четвертый информационный вход которого соединен с первым входом третьего умножителя и через третий узел коммутации с первым входом второго узла умножения и суммирования, входы первого сумматора соединены соответственно с Выходами первого умножителя и первого узла памяти, выход первого сум матора подключен к второму входу тре тьего умножителя, выход которого соединен с вторым входом второго узла умножения и суммирования, с первыми входами элемента И первой группы и с входом схемы сравнения, выходы которой подключены соответственно к первым входам элементов И второй группы и к вторым входам элементов И первой группы, входы первого делителя соединены соответственно с выходом второго узла умножения и суммирования и с выходами эле162 ментов И первой группы, входы четвертого узла коммутации соединены соответственно с выходами первого и второго делителей, выход четвертого узла коммутации является выходом второго блока формирования матриц, входы второго делителя соединены соответственно с выходом второго сумматора и с выходами элементов И второй группы, вторые входы которых соединены с выходом второго умножителя, входы второго сумматора соединены соответственно с выходами второго узла памяти и первого узла умножения и суммирования, выходы разрядов счетчика подключены соответственно к входам считывания первого и второго узлов памяти. 2. Устройство по п, 1, отличающееся тем, что блок управления содержит элементы И, счетчик и генератор прямоугольных импульсов, вход которого является входом пуска блока, а первый выход подключен к счетному входу счетчика, выход первого разряда которого соединен с первыми входами элементов И, выходы последующих разрядов счетчика являются соответственно с первого по пятый синхронизирующими выходами блока управления, выход переполнения счетчика соединен с установочным выходом блока и с установочным входом счетчика, вторые входы элементов И соединены с вторым выходом генератора прямоугольных импульсов, третьи входы подключены к пятому синхронизирующему выходу блока, выходы элементов И являются группой выходов считывания блока.

Изобретение относится к вычислительной технике. Целью изобретения является расширение функциональных возможностей за счет получения псевдообратных матриц для вырожденных квадратных, прямоугольных, плохообусловленных матриц и для матриц, полученных перемножением векторов. Устройство содержит три блока памяти, вьтолненные на регистрах и предназначенные для хранения матриц, три блока формирования матриц, шесть блоков элементов задержки, блок умножения и блок управления. Устройство позволяет получать псевдообратные матрицы не для узкого класса матриц, образованных умножением вектора-столбца на вектор-строку, а для любых матриц, плохообусловленных, вырожденных, квадратных, прямоугольных, в том числе и для матриц, полученных перемножением векторов. Вспомогательная матрица представляет собой обычную единичную матрицу (для квадратной матрицы) или единичную матрицу с отброшенным n-m количеством строк или столбцов. Псевдообратная матрица для вспомогаi тельной единичной матрицы представляет собой транспонированную еди(Л ничную (или усеченную единичную) мат- рицу. Псевдообращение осуществляется С посредством последовательной замены во вспомогательной матрице S; a;:A; | S столбцов а. столбцами матрицы ХГХ-, г X,...,, которую необходимо обратить. Постоянно на каждом шаге вычисляется псевдообратная матрица. 1 э.п, 9) ф-лы, 3 нл. :л х сь