Устройство для вычисления собственных значений ( ) матрицы

, 198 У.зто 11 с эггау аког Ьеевз. - Ргос.9. 17-21, 1987,ЧИСЛЕНИЯ (и х и)-МАТГОСУДАРСТВЕННЫЙ КОМИТЕТПО ИЗОБРЕТЕНИЯМ И ОТКРЫТИЯПРИ ГКНТ СССР ВТОРСКОМУ СВИДЕТЕЛЬСТВ(56) Авторское свидетельство М 1348855, кл. 6 06 Е 15/347Непгу У.Н. А йхеб зде зу агЬТгагИу 1 аг 9 е е 9 епга це рго 1 пт. Соп 1. РагаПе 1. Ргосазз, ац Ап 1 чегз 1 у РагК р.555, 119.4. (54) УСТРОЙСТВО ДЛЯ В СОБСТВЕННЫХ ЗНАЧЕНИИ РИЦЫ Изобретение относится к вычислительной технике и может быть использовано в высокопроизводительных специализированных вычислительных машинах и устройствах обработки сигналов для вычисления всех собственных значений (и х и)-матрицы.Цель изобретения - расширение функциональных возможностей путем вычисления собственных значений произвольной матрицы.На фиг.1 представлена структурная схема устройства для вычисления собственных значений (и х и)-матрицы; на фиг.2 - структурная схема устройства для случая и = 3; на фиг,З- функциональная схема вычислительного блока; на фиг.4 - функциональная схема вычислительного модуля; на фиг,5 - функциональная схема блока вывода.(57) Изобретение относится к вычислительной технике и может быть использовано в высокопроизводительных специализированных вычислительных машинах и устройствах обработки сигналов для вычисления всех собственных значений (и х п)-матрицы. Цель изобретения - расширение функциональных возможностей устройства за счет вычисления собственных значений произвольной матрицы. Поставленная цель достигается тем, что.устройство содержит п вычислительных блоков, (Зп - и)/2 вычис 2лительных модулей и блок вывода. В основу устройства положен итерационный треугольный степенной метод вычисления собственных значений для произвольной (и х а)-матрицы. 5 ил., 9 табл,Устройство для вычисления собственных значений (и х и)-матрицы (фиг,1) содержит первую группу информационных входов 1 О = 1,2 п), вторю группу информационных входов 2(1 = 1,п), вход 3 задания точности вычислений, пе в ю группу на- О строечных входов 4 О = 1,2 п, вторую группу настррбечных входов 5( = 1,п), синхровход в 6, вычислигельные блоки 7, вычислительные модули 8, блок 9 вывода, первый 101 и второй 102 выходы признака окончания вычислений и информационные выходы 11.Вычислительный блок 7 (фиг.З) содержит первый 12 и второй 13 информационные входы, настроечный вход 14, синхровход 15, первый 16 и второй 17 регистры, узел 18 вычисления обратной величины числа, первый 19 и второй 20 триггеры, первую-пятую группы .21-26 элементов И,,0 ти 0 1 2 3 5 6 7 1 8 9 10 11 12 13 1 14 15 16 Тр Рг Рг 47 40 39 Таблица 9 бй651721611 16 7 И к фР 4 м чБ54Составитель В. Якуш Фив. 5 дактор И. Шмакова Техред М,Моргентал Корректор О. Кравцова аз 954 Тираж Педписное ВНИИПИ Государственного комитета по изобретениям и открытиям при ГКНТ СС 113035, Москва, Ж, Раушская наб., 4/51оизводственно-издательский комбинат "Патент", г. Ужгород, ул.Гагарина, 101группу элементов ИЛИ 26, первый-четвертый элементы И 27-30, первый 31 и второй 32 информационные выходы и настроечный выход 33.Вычислительный модуль 8(фиг.4) содержит первый 34, второй 35 и третий 36 информационные входы, настроечный вход 37, синхровход 38, первый 39, второй 40 и третий 41 регистры, умножитель 42, сумматор 43, первый-четвертый триггеры 44 - 47, первую - восьмую группы 48-55 элементов И, первую 56, вторую 57 и третью 58 группы элементов ИЛ И, первый-четвертый элементы И 59-62, первый 63, второй 64 и третий 65 информационные выходы и настроечный выход 66.Блок 9 вывода (фиг.5) соде 0 жит группу информационных входов 67( = 1,и), информационный вход 68, группу настроечных входов 69( = 1,и), синхровход 70, регистры первой 71 и второй 72 групп ( = 1,и), вычитатели 73 ( = 1,и), схемы 74 сравнения ( = 1,и), триггеры первой 75 ь второй 76 и третьей 77 групп ( = 1,и), элементы И первой 78, второй 79 и третьей 80 групп ( = 1,и), первый 81 и второй 82 элементы И, информационные выходы 83 ( = 1,и), первый 84 и второй 85 выходы признака окончания вычислений.В основу работы устройства положен итерационный треугольный степенной метод вычисления собственных значений матрицы А = (ац), 1Ци, где имеет место распределение Л 1Л 21 . Лп .Пусть С 0 = (Сц, 1,п - нижняя треугольная матрица с единичными элементами по главной диагонали. В основе вычислительной схемы метода лежит последовательное вычисление матрицСк=(сц(,1и, С=1, Сц=О приий = ( гц(, 1,и, тц ) = 0 припо правилу:дС 0= В 1, В 1= СВ 1;АС 1 = В 2, В 2 = С 2 йгДС =ВВ =Со.При этом имеет место сходимостьт -+Л,- оо, 1К следовательно,при достаточно больших М можно положить Л =т;, 1и,Таким образом, на каждом итерационном шаге необходимо выполнить операции перемножения двух матриц В = А Си произвести3-разложение полученнойматрицы В на верхнюю й и нижнюю С треугольйые матрицы.Перемножение матриц А и С и О 3-разложение матрицы В представляются 5 следующимй рекуррентными соотношениями;В=А С; 10 Ьц = Ьцл, 1 ,)и; В=С й; Ь 1=Ьц,1 Ч и; 20 25 30 35 40 45 50 55 Ьц=а,1 и;Ьця=Ьвг.1+аяся,1 и,1 ) и,) р и; с =1,2 и;лтя Ь 4 я Ч ) иСя = Ьячг яя, аи;Ьцч+1 = Ьця - СОйдо, си, ц )иНа фиг.1 и 2 представлена организация подачр входных данных. Начальные данные Сц )(1и, 1 )) подаются в вычислительный блок 7(п-+1) в моменты времени тсц = 2+) - 5. Данные аЦ(11,)и) подаются в вычислительный модуль 8(п,п+1-) в моменты времени Ьц = +) - 4+ (21-1)и, 1 = 1,2,К, где К - число необходимых итерационных шагов, Режим ввода управляющих сигналов г и с, подаваемых соответственно на входы 4 и 5, приведен в табл.1,Логика работы вычислительного блока 7 и вычислительного модуля 8 приведена соответствен но в табл,2 и 3. В ычислител ьный блок 7 и вычислительный модуль 8 работают в четырех режимах. Режим работы вычислительного блока 7 определяют состояния триггеров 19 и 20, а режим работы вычислительного модуля 8 - состояния триггеров 44 и 45, которые устанавливаются соответствующими управляющими сигналами, подаваемыми соответственно на входы 14 и 37. Все регистры в вычислительных блоках 7 и в вычислительных модулях 8 построены на двухтактных триггерах и срабатывают по заднему фронту тактового импульса. В вычислительном блоке 7 с прямого выхода регистра 17 снимается значение Ь, а с инверсного выхода - значение (-Ь).Рассмотрим работу устройства для случая и = 3. Организация входного и выходного потоков да)рых приведена на фиг.2 (в обозначении Ф" индекс М в скобках указы,ает номер итерации, а в обозначении гс=3 - 5+2 иМ,45 50 55 индекс 1 без скобок - номер такта работы устройства, В табл,4 - 9 показаны состояния регистров и триггеров вычислительных блоков 7 и вычислительных модулей 8, а также формируемые значения на их выходах пи числнии собственных значений М Я 2 иЙ( для двух итераций.(1На четвертом и десятом тактах в вычислительном блоке 7 з формируются соответственно со)бственные значения М ) = г 1 1и Й 1 = г 11(, которые подаются на вход 671 (2) (гблока 9 вывода. Кроме того, на четвертом и десятом тактах на вход 691 блока 9 вывода подается единичный сигнал.На седьмом и тринадцатом тактах в вычислительном бл(о)ке 72 ормирются Чс(- ответственно Л 2 = г 22 и Л 2 = г 221которые подаются на вход 672 блока 9 вывода, а на вход 692 - единичный сигнал. На десятом и шестнадцатом тактах в вычислительном блоке 7 з фоомирудтся соответственно Лз(") = гзз(1) и Лзф = гзз(2), которые подаются на вход 67 з блока 9 вывода,на вход 69 з подается единичный сигнал.Таки)м образом, собственные значенийЯ = и ( = 1,и) формируются в вычисли-.тельном блоке 7(п-;+1) в моменты времени В блоке 9 вывода выполняется проверка точности вычислений 1("+") -ЯР . Если такое соотношение выполняется, то на выходе 10 признака окончания вычислений формируется единичный сигнал. При этом с выходов 11(п-+1) в моменты времени 3 - 4+2 и 1 снимаются значения Ь, Если данное соотношение не выполняется, то итерационный процесс вычисления собственных значений Ь продолжается,В процессе вычисления А( ) существуют случаи параллельной проверки соотношении+) - ) в и Ь ) Ь ) - 8, 1(2, Поэтому дляЙ +г) В+1)итераций 1 = 1,3,5, признак окончания вычислений а 1 формируется на выходе 101, а для итераций К = 2,4,6, - признак окончания вычислений а 2 на выходе 102 в моменты времени 1= Зи - 4+ 2 иК, В этом случае блок 9 вывода работает следующим образом. В исходном состоянии регистры и триггеры блока 9 вывода обнулены, На (-м такте на входы 67 и 69 подаются соответственно значение Ь и единичный сигнал д. Зна(1)чение Ь( ) по заднему фронту тактового,(1)импульса записывается в регистр 71 (эле 5 10 15 20 мент И 781 открыт управляющим сигналом д = 1). Триггер 75 устанавливается в единичное состояние и открывает элемент 79 (триггер 75 работает в счетном режиме, т,е, с подачей на его вход единицы он меняет свое состояние на противоположное), На выход(е вычетателя 73 определяется ЬА = 1 А - А 1, а на выходе схемы 74 сравнения - соотношение ЬАя. Если это соотношение выполняется, то на выходе схемы 74 сравнения формируется единичный сигнал, который подается на информационные входы триггеров 76 и 77 ь На (+1)-м такте через элемент И 79 тактовый импульс подается на синхровход триггера 76 и устанавливает его в единичное состояние, если на выходе схемы 74 сравнения сформирован единичный сигнал. Такая проверка на первом итерационном шаге выполняется для всех= 1,и и на выходе элемента И 81 формируется единичный сигнал а 1 = 1, когда все триггеры 76 установлены в единичное состояние,На втором итерационном шаге (К = 2) на вход 67 подается значение ЛР, а на вход 69 - единичный сигнал, который устанавливает триггер 75 в нулевое состояние, При этом открывается элемент И 80 ь который обеспечив(а)ет запись результата сравненияЬ - Я 1е на выходе схемы(2) 174 сравнения в триггер 77 (О или 1). Аналог,ично, на выходе элемента И 82 формируется сигнал а 2 = 1, если все триггеры 77; установлены в единичное состояние. Таким образом, в блоке 9 вывода состояние три гге ров 76 и 77 зависит от состояния триггера 75;, что позволяет определить правильные значения признаков окончания вычислений а 1 и а для четных и нечетных итераций,Формула изобретения Устройство для вычисления собственных значений (и х п)-матрицы, содержащее и /2 вычислительных модулей, о т л и ч а ющ е е с я тем, что, с целью расширения функциональных возможностей путем вычисления собственных значений произвольной матрицы, в него введены (2 и - и)/2 вычислительных модулей, и вычислительных блоков и блок вывода, причем )-й вход информационных входов первой группы устройства ( = 1,2 и - 1) подключен к первому информационному входу (и,Д-го вычислительного модуля, первый информационный вход ,К)-го вычислительного модуля ( = 1,и - 1, 1 = 1,и) подключен к первому1721611 Ь, если (а, ф) = (0,1) Ь 1, если (а, ф) = (0,0) 55 информационному выходу (+1,1)-го вычислительного модуля, первый информационныи вход 1,1 у.го вычиспитвпьного модуля ( = и+1, 2 п - 2,-и =2) подключен к первому информационному выходу 5 (+1, )-го вычислительного модуля, Е-й вход второй группы информационных входов устройства подключен к первому информационному входу 1-го вычислительного блока, первый информационный 10 выход которого подключен к второму информационному входу (с,)-го вычислительного модуля, второй информационный выход (Щго вычислительного модуля подключен к второму информационному входу 15 (К+1)-го вычислительного модуля, второй информационный выход(р,ц)-го вычислительного модуля (р = 2,п, ц = п,2 п, ц - ри) подключен к второму информационному входу (р,ц+1)-го вычислительного модуля, 20 третий информационный вход(р,ц)-го вычислительного модуля подключен к третьему информационному выходу (р,ц+1)-го вычислительного модуля, третий информационный вход (К)-го вычислительного модуля 25 подключен к третьему информационному входу (К,+1)-го вычислительного модуля, третий информационный вход (М,)-го вычислительного модуля подключен к второму информацйионному входу М-го вычислитель ного блока, второй информационный выход которого подключен к К-му входу групп информационных входов блока вывода, вход задания точности вычислений которого является одноименным входом устройства, 35 -й вход группы настроечных входов которого подключен к настроечному входу (п,Д-го вычислительного модуля. настроечный вход (ц, р)-го вычислительного модуля (ц = 2,п) подключен к настроечному 40 входу (ц + 1, р + 1)-го вычислительного модуля, нвстровчныи выход о.в)-го вычис. л ител ьного модуля (з = и+1,2 п - 1, з - 0и - 1) подключен к настроечному входу (ц+ 1, 3 + + 1)-го вычислительного модуля, -й вход 45 второй группы настроечных входов устройства подключен к настроечному входу К-го вычислительного блока, настроечный выход которого подключен к К-му входу группы настроечных входов блока вывода, 50 синхровход устройства подключен к синхровходу блока вывода, синхровходам всех вычислительных модулей и блоков, первый и второй выходы признака окончания вычислений блока вывода являются одноименными выходами устройства, М-й информационный выход которого подключен к М-му выходу группы информационных выходов блока вывода, причем каждыйвычислительный блок выполнен с возможностью реализации следующих функций; 1/Ь, если (а,Р) = (0,0)1+1 -Ь, если (а,Р) = (1,0) а, если(а,ф) =(1,1) В+1 = Ьв, если (о, ф) = (О 1) 0 если (а,ф) =(0,0), (0,1), (1,0),1 если(аф) =(0,1) где а ь Р - значения соответственно на первом и втором настроечных входах вычислительного модуля блока на )-м такте;а и Ь - значения соответственно на первом и втором информационных входах вычислительного блока на)-м такте;А и В - значения соответственно на первом и втором информационных выходах вычислительного блока на )-м такте;С - значение на настроечном выходе вычислительного блока на )-м такте,каждый вычислительный модуль выполнен с возможностью реализации следующих функций:А 1: а В+ ас, если (а, Р) = (1,1); с+ а, если (а,ф) = (0,0)с, если (а", Р) =(0,1)Ь, если(а,ф) =(1,0):ас, если (а, ) = (1,1) где а,Ь и с - значения соответственно на втором, первом и третьем информационных входах вычислительного модуля на -м такте;А,В и С - значения соответственно на втором, первом и третьем информационных выходах вычислительного модуля на)-м такте,1721611 10 Таблица 1 Управляю- Номер ВМ щие сигналые Номер такта Индексы- (О 0) Т а б л и ц а 2 Режимработы Тр 19 Тр Рг 20 16 О О О 1О 1 1 а О 1 О О Ь 1/Ь Ь -Ь Таблица 3 т1Тр ; Рг РгРг Выходы РежимТр работы44 45 40 394164 1 бЭ 65. О О О 1 1 0 3 4 а аса блица 4 вм 9,вн В,с см 7,тр. тр, тр. тр44 45 46 47 Рг Рг Выхоцы39 41 Тр, Тр. Рго19 20 16 17 Рг Рг Вы ходы ТрТр. Тр. Тр, Р40 39 4 " -- 4445 Ьь 47 4 646365 ыхо 3132 63 6 о) с, с, 1 о) о 11 са аа (а с, аоо Ь оа, сла,о Ьо,41 с, ла а 1о 1 о ыЪ М 1цл Ь 1 1 о 1си аоо Ьд вага 1 Ъси 1/ги го ва а) со- (1,1)= (1,0) 8 = (0,1) е = (о,о) ф =. (1,1)+ т - 4 - (21 с)и 2 с 3 си, 1 сс 1 1 сдС т сп, 1 с 1;сК 1 сс 1 с 1 ссК 1 стс 3 сп 1 с 1 ссК 2 с .и, 1 с 1 ссК1 с си, 1 с 1 ссКи + 26 т( 2 п,. т-и (си, 06 1 сс К 1 ( 3. с п, 2 сс и, 1 с 1 сК Рг Выходы 31 32 33 с а Ь с+а Ьс а с1721611 вм 8,Тр, Тр, Рг Рг Рг Выходы Вм 7 Такт Тр 19 Тр Тр, Тр, Рг Рг Рг Выходь Тр.20 17 4 45 46 47 40 39 41 - -г - -" - -"64 6369 46 47 40 39 41646365 а)(з 1 з)1/гт0 0 0 0 16 0 1 Таблица 5 вм вэз вм взе вм 8)а ТакТр, Тр,)рт Рг Рг Выходы 44 45 140 39 4164636 р, Тр, Рг 4 45 40 Рг Рг Выходы Рд и Н О (1 ЬО)ач се ает Ъееы) (г) О) (3) сз, а Ьза гз азз Ь З 1213 1(з) зи Вв Ьага Ьаа 1 000 00 рвы Н)с, аз 4 45 5 55 Выходы332 9 41 - - г -- - 646365(г) (з 15 0 0 сг атг Ьт 16 р, Тр, Рг Рг Рг Выходы4 45 40 39 41 "- - г - -г 646365 Ф 00 (о) (ОО с, аза Ьэи сг азт Ъзс 12 1 Продолжение табл. 4 т(г) 01 РД (ф си а, Ьси со ае Ькат С с кР М сс т сс сР скР Яът с3 фс 3тСн о е с 3