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

(я)5 6 06 Р 15/34 ГОСУДАРСТВЕННЫЙ КОМИТЕТПО ИЗОБРЕТЕНИЯМ И ОТКРЫТИПРИ ГКНТ СССР ЕТЕНИ ОПИСАНИЕ К АВТОРСКОМУ СВИД КА ЕЛЬСТВУ(46) 15.08.92. Бюл, И. 30 (72) И, Г,Кириллов и Д.И,Леховицкий (56) Авторское свидетельство СССР В 1689970, кл. 6 06 Е 15/347, 1989. Изобретение относится к вычислитель- циональная схемаоперационного модуля; ной технике и может быть использовано ав-. на Фиг,4 - функциональная схема дополнитономно или в комплексе с ЦВМ для тельногооперационногомодуля; нафиг.5 - разложения квадратной теплицевой сим- функциональная схема операционного блометричной матрицы на две треугольные и ка; на фиг.6 - функциональная схема блока диагональные матрицы, вычисления детер-. формирования детерминантов,минантов исходной матрицы и суммы мат- Устройство(фиг.1 и 2) содержит первую риц, квадратичных форм с матрицей, группуинформационныхвходов 1, блокдеобратной к исходной, для решения систем ления 2,вычислительныемодулиЗ,вычисли- линейных уравнений, тельные блоки 4, блок синхронизации 5,Целью изобретения является расшире- первую 6 и вторую 7 группы выходов устройние функциональных возможностей устрой- ства, вторую группу информационных вхоства за счет вычисления детерминантов дов 8, буферные регистры 9 и 10, исходной матрицы и суммы матриц квадра- операционные модули 11, дополнительные тичных форм с матрицей, обратной к исход- операционные модули 12, операционные ной, блоки 13, блок формирования детерминанНа фиг.1 и 2 представлена Функцио- тов 14, выходы 15, 16 и 17 устройства. При нальная схема устройства; на фиг.З - функ-, этом каждый вычислительный модуль 3 со(54) УСТРОЙСТВО ДЛЯ РАЗЛОЖЕНИЯ ТЕПЛИЦЕВЫХ СИММЕТРИЧНЫХ МАТРИЦ(57) Изобретение относится к вычислительной технике и может быть использовано для разложения квадратной теплицевой симметричной матрицы на две треугольные и диагональную матрицы, вычисления детерминантов исходной матрицы и суммы матриц квадратичных форм с матрицей, обратной к исходной. а также при построении специализированных устройств, пред-назначенных для решения систем линейныхуравнений. Целью изобретения являетсярасширение функциональных воэможностей за счет вычисления детерминантов исходной матрицы и суммы матриц квад-.ратичных форм с матрицей. обратной к исходной. Цель достигается путем реализацииспециальных способов решения указанных задач на основе методов адаптивнойрешетчатой фильтрации, учитывающих теплицевость и симметрию исходных матриц,Устройство содержит блок деления, вычислительные модули, вычислительные блоки,операционные модули, буферные регистры, дополнительные операционные модули, операционные блоки, блок формирования детерминантов и блок синхронизации.3 ил.Ь = бО, где1=1матрица с единичнойАлгоритм вычислбе 1 (алгоритм номер 3ношениибе 1 А/бет(А ) = ЧО =(В) =ЧХ=:1иагональю.ния детерминбазируется на антов соот/бе 0=1/П б держит первый 18 и второй 19 регистры,первый 20 и второй 21 умножители, первый22 и второй 23 вычитатели, третий 24 и четвертый 25 регистры, первый 26 и второй 27синхровходы, Каждый вычислительный 5блок 4 содержит первый узел деления 28,умножитель 29, регистр 30, вычитатель 31,второй узел деления 32 и регистр ЗЗ,Блок синхронизации 5 представляет собой генератор импульсов, прямой и инверсные выходы, которого подключенысоответственно к синхровходам 26 и 27 всехвычислительных и операционных модулей иблоков. Операционный модуль (фиг.З) содержит первый 34 и второй 35 регистры, 15умножитель 35. Дополнительный операционный модуль (фиг.4) содержит первый 37 ивторой 38 регистры, сумматор 39. Операционный блок (фиг.5) содержит первый 40 ивторой 41 умножители, первый 42 и второй 2043 регистры, Блок формирбванйя детерминантов (фиг.6) содержит сумматор 44, первый 45, второй 46 и третий 47 регистры, блокделения 48, умножитель 49,Устройство предназначено для разложения данной Р-П теплицевой симметричной матрицы А, т,е. матрицы, элементыкоторой удовлетворяют равенствама+с,к+1 = а,к(с,К = 1,.,П - 1),а,к = ак,с ( = 2П,К = 11 - 1)/2,3) 30на две треугольные (нижнююи верхнююЕ, где, знак т обозначает транспонированную матрицу) и диагональную О, такие, чтоА =Осдля вычисления детерминантовбе 1 А исходной матрицы А, бе 1(А+ХХ) суммы лсатриц А+ХХ и квадратичной формыХ А Х, где Х - заданный вектор-столбец.т -1Алгоритм формирования элементов к(1=1,. П,К=с) и элементов б соответствующихлдатриц с и О, приведенный в описании 40работы устройства, есть алгоритм номер 1.Алгоритм вычисления квадратичнойформы Ь (алгоритм номер 2) базируется наразложении матрицы А, обратной к заданной, на две треугольные (нижнюю Ч и верхнюю Чт) и диагональную О, такие, что ААлгоритм вычисления детерминанта бес (А+ХХ) суммы матриц.А+ХХ (алгоритм номер 4) основывается на соотношениибе 1(А+ХХ) = бе 1 + А(1+Ь),Общий алгоритм работы устройства имеет следующий вид: Ссс, пса-аи ( 1-1, , ЛСлсь пс-хбс/а, Сс"-васс;д(11 с.и в.к:с-скы(есть формулы алгоритма номер 1, т,е, алгоритма работы устройства (1),Устройство работает следующим образом,Для кратности описания без потери общности положим П=З. Условимся, что прием информации во все регистры осуществляется по переднему фронту соответствующего синхроимпульса.Первый столбец (или строка) исход теплицевой симметричной матрицы А и данный вектор Х подаются соответственно на группы информационных входов 1 и 8 устройства по первому тактовому импульсу с блока 5.Первый такт, В первой половине такта параллельно вычисляются значения 01г2=Х 1 в первом умножителе 40 операционного блока 13, б 1 = 1/а 11 в блохе 2 деления и с 2 = а 21/а 11 в вычислительном блоке 4.1. Значение б 1 поступает на первый и второй информационные входы соответственно блоков 4.1 и 13.1, а также информационный вход регистра 9. Значение с подается на объединенные третьи информационные входы вычислительных модулей 3,1,1, 3,2,1, 3.3,1 и 3.4.1. Во второй половине такта в регистр 42 операционного блока 13,1 записывается значение х 1 в регистры 18 и 19 вычислительных модулей 3.1.1, 3,2,1, 3,3,1 и 3,4.1 соответственно записываются пары значений а 11 и а 21, а 21 и азс, хс и х 2, х 2 и хз. Вычисляю, ся значения элементов 22 = а 11 - -сга 21; а 22 = а 21 - сга 11 в вычислительном модуле 3.1 1. сзг = агс-сгаз 1: птзг = азс-сгагс в вычислительном модуле 3,2.1, п 22 =- х 1- с 2 х 2; ггг = х 2-с 2 х 1 в вычислительном модуле 3,3.1 и П 32 = х 2 сгхз г 32 = хз с 2 х 2 в Вычисной залительном модуле 3,4.1 значения которых Третий такт. Пары значений 1 зз и п 1 зз, пззподаются соответственно на информацион- и гзз записываются соответственно в региные входы регистров 24 и 25 вычислитель- стры 24 и 25 вычислительных модулей 3,2.2ных модулей 3.13.2,1, 3.3.1 и 3,4,1, Ви 3.3.2, значения сз - в регистр 30 вычислигумножителе 29 вычислительного блока 4.1 5 тельного блока 4,2, бсдг - в регистр 35 опервычисляются значения с 2 и подается на ин- рационного модуля 11.1, Ь - в регистр 37формационный входрегистра 30, Вумножи- дополнительного операционного модулятеле 41 операционного блока 13.1 вычис- . 12,1, бг 02 - в регистр 43 операционногогляется значение Ь( ) = б 1,х 1 и подается на блока 13,2, В первой половийе такта вычисг,информационный вход регистра 4 Э.10 лгятвтся значения Оз = ф/(1-сз ф в вычисли.(1/ 2Второй такт. В начале такта пары значе- - тельном блоке 4,2, Ь = Ь( + б 202 вний 22 и гпггзг и тзгпгг и ггг, пзг и гзг дополнительном операционном модулезаписывается соответственно в регистры 24 " 12.1, которые поступают соответственно ви 25 вычислительных моуулей 3,1,1; Э,2,г регистры 33 вычислительного блока 4.2 и 383.3,1 и 3,4.1, значение с 2 в регистр 30 вы дополнительного операционного модуляч ислительного бло 4.1, значение б 1 - ре,1 и Оз = гзз в операционном блоке 13,3,2 2гистр 9 значение Ь = б 1 х 12 - в регистр 43 Во второй половине такта значения бздсб 2,операционного блока 13,1, В первой поло- Ь и Оз записываются соответственно в(2) 2вине такта параллельно вычисляются б 2 = регистры 33 вычислительного блока 4 . 2 3 4б 1(1-сг) в вычислительном блоке 4.1 и сз = 20 операционного модуля 11.2, 38 дополнипсзг/22 в вычислительном блоке 4,2 и посту- тельного операционного модуля 12,1 и 42пают соответственно на информационный операционного блока 13.3 и параллельновходрегистра 33 вычислительногоблока 4,1 вычисляются значения б 12 бгбз в операциони объединенные третьи информационные ном модуле 11.2 и бзОз в операционномвходы вычислительных модулей 3,2.1 и 25 блоке 13.3.3,3,2, а также. вычисляется значение 02 = Четвертый такт,В первой половине так=ггг в первом умножителе 40 операционно- та значения б 1 б 2 дз, Ь и бзОз записы г ) гго блока 13.2, Во второй половине такте ваются соответственно в регистры 35значение бг принимается в регистр 33 вы- операционного модуля 11.2, 37 дополничислительного блока 4,1 и поступает на 30 тельного операционного модуля 12,2 и 43первый информационный вход вычисли- операционного блока 13.3. Параллельно вы(3) (2) + 2тельного блока 4.2, на вторые информаци- числяются значения Ь = Ь = Ь ) + бзОз вонные входы операционного модуля 11.1 и сумматоре 39 дополнительного операционнооперационного блока 13.2, Значение б 1 за- го блока 12,2, 1/(б 1 бг дз) и (1+Ь) соответстписывается в регистр 34 операционногОмо-"35 венно в блоке деления 48 и сумматоре 44дуля 11.1, в котором вычисляется произве- блока формирования детерминантов 14,дение б 1 бг. Значение Ь записывается в Во второй половинетакта значения бесА=регистр 10 и подается на первый информа- = 1/б 1 бгдз и 1+Ь записываются соответстционный вход дополнительного операци- венно в регистры 45 и 46 блока формироваонного модуля 12,1, Значение 02 = г 22 40 ния детерминантов и 38 дополнительного-гзаписывается в регистр 42 операционногооперационного модуля 12,2, На выходе умблока 13.2 и подается на вход умножителя ножителя 49 блока формирования детер 41,навторойвходкоторогоподается значе- минантов 14 вычисляется значениение бг и начинается вычисление бг 02, На бес(А+ХХ) = бесА(1+Ь) и подается на инфорвыходе умножителя 29 вычислительного 45 мационный. вход регистра 47, в который эаблока 4,2 вычисляется значение сз и пода- писывается в начале пятого такта,ется на информационный вход регистра 30. На этом вычисления в устройстве заверВ регистры 18 и 19 вычислительного модуля шаются. Элементы нижней треугольной3,2,2 записываются значения 122 и гйз 2 и вы- матрицы 1: 111, 121, 131 снимаются в началеЧИСЛяЮтСя ЭЛЕМЕНТЫ 1 ЗЗ =22 - СЗщЗ 2, ПсгЗЗ = 50 ПЕРВОГО таКта С ВЫХОДОВ ПЕРВОЙ ГруППЫ ВЫ=псзг - сз 22, значения которых соответст- ходов устройства 6,1.1, 6.2.1 и 6.3,1 соответвенно подаются на информационные входы ственно, элементы 22, 1 з 2 - в начале второгорегистров 24 и 25 вычислительного модуля такта с выходов первой группы выходов ус 3,2,2. В регистры 18 и 19 вычйслительного тройства 6.2.2 и 6.3,2, элемент зз - в началемодуля 3,3,2 записываются значения элемен третьего такта с выхода первой группы устое п 22 и гз 2 и вычисляются элементы пзз= тройства 6,.3,3. Значения элементов глав=П 22- С 2 ГЗ 2, ГЗЗ- ГЗ 2- СЗП 22, ЗНаЧЕНИЯ КОТОРЫХ НОй ДИаГОНаЛИ ДйаГОйадгЬНОй МатРИЦЫ О:соответственноподаются наинформацион- б 1 бгбз - снимаются в первом, второй иные входы регистров 24 и 25 вычислитель- третьем тактах соответственно с выходовного модуля 3,3.2.явторой группы выходов устройства 7.1, 7,2 и 7.3. Значения Ь - ХА Х и бе 1 А снимаются во второй половине четвертого такта соответственно с выходов устройства 17 и 15, Значение бет(А+ХХ) снимается с выхода устройства 16 в начале пятого такта.Поскольку каждый элемент очередного шага вычислений используется в каждом модуле и блоке только один раз, можно выполнять операции над потолком теплицевых симметричных матриц. Первый столбец (строку) следующей матрицы, а также очередной вектор для вычисления квадратичных форм в этом случае подаются в следующем такте после подачи предыдущих векторов, Для вычисления нескольких квадратичных форм для одйой матрицы необходимо ее первый столбец (сгроку) подавать на информационные входы 1 устройства требуемое число тактов одновременно с подачей на входы 8 устройства новых векторов Х,Процесс определения элементов 11, в 1, пи, г 1, бь Ь и бетА представлен е виде "слоев" с целью распараллеливания вычислений до уровня нескольких типов операций: 1 - сщ или п 1 - с 1, и - сгили г - сп, б/(1-с), Ь+ дО и (б 1 йФ)дь Это позволяет строить структуру из существу:ощих интегральных схем ограниченной номенклатуры или в виде отдельных СБИС,Формула изобретения Устройство для разложения теплицееых симметричных матриц по авт,св. М 1 б 89970, о т л и ч а ю щ е е с я тем, что, с целью расширения функциональных возможностей за счет вычисления детерминантов исходной матрицы и суммы матриц квадратичных форм с матрицей, обратной к исходной, в устройство ввецены первый и второй буферные:регистры, иоперационных модулей (где и - размерность входной матрицы), пдополнительных операционных модулей, и операционных блоков, п(п - 1)/2 вычислительных модулей и блок формирования детерминантов, причем 1-й информационный вход второй группы устройства подключен к первому информационному входу (и+ -1,1)-го вычислительного модуля (1=1п - 1), второй информационный вход которого подключен к (1+1)-му информационному входу второй группы устройства, первый выход О,К)-го вычислительного модуля (1=п, .2 п-З, К=12 п-)-2) подклЮчен к первому информационному входу О,К+1)-го вычислительного модуля, второй информационный вход которого подключен к второму выхо,у (+1,К)-го вычислительного мс дуля, втор эй выход (п,1)-го50 причем каждый опеоационный модуль содержит два регистра и умножитель, первый информационный вход операционного модуля подключен к информационному входу первого регистрэ, синхровход и выход которого подключены соответственно к второму входу синхронизации операционного модуля и первому входу умножителя, второй вход и выход которого подключены соответственно к вгорому информационному входу операционногс модуля и информацивычислительного мод ля подключен к первому информационному входу (1+1)-го операционного блока (1=1 п), выход которого подключен к второму информаци онному входу 1-го дополнительного операционного модуля, первый информационный вход второй группы устройства подключен к первому информационному входу первого операционного блока, выход которого под ключен к информационному входу второгобуферного регистра, выход которого подключен к первому информационному входу первого дополнительного операционного модуля, выход блока деления под ключен к второму информационному входупервого операционного блока и информационному входу первого буферного регистра, выход которого подключен к первому информационному входу первого опера ционного модуля, первый информационный вход (в+1)-о операционного модуля (гп=1,п) подключен к выходу а-го операционно 1 о модуля, выход(п)-го операционного модуля подключен к первому 25 информационному входу блока формирования детерминантон, первый, второй выходы. и второй информационный вход которогоподключены соответственно к первому и второму выходам устройства и второму вы ходу (и)-го дополнительного операционного модуля, первый выход которого подключен к третьему выходу устройства, первый выход гп-го дополнительного операционного модуля подключен к первому 35 информационному входу (п 1+1)-го дополнительного операционного модуля, обьединенные третьи информационные входы (т,)-го вычислительного модуля (т=п 2 п - 1 - 1) подключены к аторому выходу 1-го вычис лительного блока, первый выход которогоподключен к объединенным вторым входам 1-го операционного модуля и (1+1)-го операционного блока, первый и второй синхровходы всех блоков и модулей подключены 45 соответственно к пряному и инверсному еыходам блока синхронизации, синхровходыпервого и второго буферных регистров подключены соответственно к прямому и инверсному выходам блока синхронизации,онному входу второго регистра, синхровход и выход которого подключены соответственно к первому синхровходу и выходу операционного модуля, каждый дополнительный операционный модуль содержит два регист ра и сумматор, первый информационный вход дополнительного операционного модуля подключен к информационному входу первого регистра, синхровход и выход которого подключены соответственно к перво му входу синхронизации дополнительного операционного модуля и первому входу сумматора, второй вход которого подключен к второму информациониОму входу дои ол н и тел ьн ого опера цио нного модуля, 15 второй выход которого подключен к выходу сумматора и информационному входу второго регистра, синхровход и выход которого подключены соответственно к второму входу синхронизации и первому выходу допол нительного операционного модуля, каждый . операционный блок содержит два умножителя и даэ регистра, первый информационный вход операционного блока подключен к объединенным входам первого умножите ля, выход которого подключен к информационному входу первого регистра, синхровход и выход которого подключены соответственно к второму входу синхронизации операционного блока и первому входу второго 30 умножителя, второй вход и выход которогоподключены соответственно к второму информационному входу операционного блока и информационному входу второго регистра, синхровход и выход которого подключены соответственно к первому синхровходу и выходу операционного блока, блок формирования детерминантов содержит блок деления, сумматор, умножитель и три регистра, первый информационный вход блока формирования детерминантов подключен к входу делителя блока деления, выход которого подключен к информационному входу первого регистра, выход которого подключен к первому входу умножителя и первому выходу блока формирования детерминантов, второй информационный вход которого подключен к первому входу сумматора, выход которого подключен к информационному входу второго регистра, выход которого подключен к второму входу умножителявыход которого подключен к информационному входу третьего регистра, синхровход и выход которого подключены соответственно к первому синхровходу и второму выходу блока формирования детерминантов, второй синхровход которого подключен к объединенным синхровходам первого и второго регистров, вход задания единицы устройства подключен к обьединенным входу делимого блока деления и второму входу сумматора,1755295Фиг 5Составитель Е, МурзинаРедактор Ю, Середа Техред М,Моргентал Корректор В.бориса Заказ 2895 Тираж Подписное ВНИИПИ Государственного комитета по изобретениям и открытиям при ГКНТ СС113035, Москва, Ж, Рэушская наб., 4/5оизаодстаенно-издательский комбинат "Патент", г. Ужгород, ул. Гагарина, 101