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

,.801587540 1)5 С 06 Р 15/34 ГОСУДАРСТВЕННЫЙ КОМИТЕТПО ИЗОБРЕТЕНИЯМ И ОТКРЫТИЯПРИ ГКНТ СССР ОПИСАНИЕ ИЗОБРЕТЕНИЯН АВТОРСКОМУ СВИДЕТЕЛЬСТВУ ский инс Октябрьс ий 1), Ю.С.(54) УСТРОЙСТВО ДЛЯ ТРЕУГОЛЬНОГО РАЗЛОЖЕНИЯ ЛЕНТОЧНЫХ МАТРИЦ(57) Изобретение относится к автоматике и вычислительной технике иможет быть использовано при построеИзобретение относится к автома тике и вычислительной технике и может быть использовано при построенииспециализированных устройств, предназначенных дпя решения систем линейных уравнений.Цель изобретения - сокращение аппаратурных затрат,На фиг.1 представлена структурная схема устройства для треугольного разложения ласточных матриц;нафиг,2 - структурная схема (р,Е)-говычислительного модуля (р1,Г,2(о, И Г+Ь+ 1, Е ий - соответственно число под- и наддиаго. нальных элементов матрицы);на фиг.3-. 2нии специализированных устройств,предназначенных для решения системлинейных уравнений, Цель изобретения - сокращение аппаратурных затрат. Устройство выполняет первуюфазу решения системы алгебраическихч Ф ч -Фуравнений Ах = Ь (где х и Ь - И-мерные векторы; А - ленточная матрицапорядка Б), которая состоит в отыскании нижне- и верхнетреугольныхматриц 1, и П, таких, что 11 = ЬА.Преобразование выполняется методомисключения Гаусса - прямого исключения с локальным выбором ведущегоэлемента. Перестановки строк запоминаются и выдаются в виде матрицыперестановок Ч, Особенностью работыустройства является параллельно-поточная организация вычислений в матрице вычислительных модулей двухтипов. 2 з.п. ф-лы, 4 ил,структурная схема (р,1)-го вычислительного модуля," на фиг,4 - порядок ввода и вывода элементов матрицы для случая Г = 2, Ь,= 1.Устроство для треугольного разложения ленточных матриц содержит (фиг.1) матрицу (р,с 1) (где Ч 1,ч) вычислительных модулей 1 р ц и генератор синхроимпульсов (не показав) выход которого подключен к синхровходам всех вычислительных модулей. ительный модуль 1 р 1 (фиг.2умножитель 2, второй репервый мультиплексор 4, пертр 5, второй мультиплексор(фиг.3) содержит первый регистр 10,схему 11 сравнения, первый 12 и второй 13 мультиплексоры, 0-триггер 14,второй регистр 15, инвертор 16 и делцтель 17,Устройство для треугольного раз Оложения ленточных матриц предназначено для выполнения первой фазы решениясистемы линейных алгебраических уравнений Ах =:Ь (где х и Ь - И - мерныевекторы-столбцы, а А - ленточная матрица И-го порядка) методом исключения Гаусса - прямого исключения, которое состоит в нахождении такойнижней треугольной матрицы Ь, котораяпреобразует матрицу А в верхнюю тре Оугольную матрицу П, т.е. П = ,А.Преобразование ленточной матрицы А =1 а 1 с шириной ленты у= 1+Ь+1,где Г и й " число соответственнопод- и наддиагональных элементов матрицы А, выполняется по алгоритмуисключения Гаусса с локальным выбором главного (ведущего) элемента.Локальный выбор ведущего элемента предполагает, что исключение элемента а" на -м шаге алгоритма Гаус 1са ( = 1,Ь), 1 = д+1, 3+1) предше ствуе т сравнение элемен тон аи а (;,1;, причем, еслиа. .;ато осуществялется перестановка 3-й и(1-1)-й строк, Затем производится преобразование 1-й строки путем поэлементного вычитания из нее Ц)-йстроки, умноженной на коэффициента, /а - = -1;1. В противном случаеперестановка строк не производится.Таким образом в качестве ведущегопри исключении элемента а ; используется теперь максимальный по абсолютной величине элемент х-го столбца, расположенный в .строках от Ц1) -й до 1-й включительно. При этомвсе происходящие перестановки строкзапоминаются и выдаются (в качественижней треугольной матрицы перестановок Ч = П; ) для дальнейшегоиспользования,Устройство работает следующим образом..Положим У = 4, д= 4, Г = 2, условимся, что прием информации во всерегистры и триггеры осуществляютсяпо заднему фронту синхроимпульса,т а, в конце такта все триггеры и регистры перед началом вычисления устанавливаются в нулевое состояние,Обозначим а 1 элемент а на -м ша.1ге вычислений.Информационные входы устройства второй группы подключаются к потенциалу логического нуля.В первом такте на первые входы вычислительных модулей 1.1.1-1.1.4 поступают (фиг.4) соответственно 0,0, аи, О. Мультиплексор 6.1.3 пропускает ан на вход сумматора 9.1.3, а с выхода мультиплексора 4.1.3 на вход умножителя 2.1,3 выдается нуль из регистра 8.1,4, и в конце первого такта азаписывается в регистр 8.1. 3.Во втором такте а и а посту 21пают на первые входы вычислительных модулей - соответственно 1.1.2 и 1,1,4 и в конце такта записываются в регистры 8,1.2 и 8,1,4 соответственно. В регистр 5,1,2 через мультиплексор 4.1.2 переписывается а из1 Ю регистра 8.1.3.В третьем такте на первые входы вычислительныхмодулей 1.1.1 и 1.1.3 поступают соответственно элементы а, и а . а , сравнивается в схеме сравнения 11. 1, 1 с а , . Пусть в нашем случае 1 а, (а,. Тогда нуль с выхода схемы сравнения записывается в триггер 14.1,2 и поступает на управляющие входы мультиплексоров 12,1.1 и 13.1.1, которые пропускают на свои выходы соответственно а , и а , В делителе 17, 1. 1 вычисляется частное (-аз,/а,) и записывается в регистр 15.1.1. В регистр 10.1.2 записывается ав регистр 8.2.2 через мультиплексор 6.2,2 и сумматор 9.2,2 из регистра 5. 1.2 переписывается а, В регистр 8. 1.3 записывается а . В четвертом такте на первые входы вычислительных модулей 1,1,2 и 1,1,4 поступают .соответственно а и а. На первый и второй входы схемы 11,2,1 сравнения поступают соответственно а, и а . Пусть а 1р а,. Тогда едйница с выхода схемы 11.2.1 сравнения переключает В-триггер 14.2.1 и мультиплексоры 12,2,1 и 13.21, которые пропускают на свои выходы соответственно а , н а. В делителе 17.2,1 вычисляется (-а 11/а д,) и записывается в регистр 15 .2 .1. В регистр 10.21 записывается а= Б и поступа 15875405 1 О 5 2 О ет на первый въкод первой группы выходов устройства.В этом же такте (-а э/а,) переписывается из регистра 15. 1. 1 в регистр 3.1,2 и поступает ка второй вход умножителя, на первый вход которого из регистра 8,1.3 через мультиплексор 4.1.2 поступает а , а записывается также в регистр 5.1,2. Результат умножения (-а . аз, /а ,) суммируется с а и а,= а - а аэ,/а, записъвается в регистр 8.1.2, в регистр 8.1.4 - аэ, в 5.1.3 - а,.В пятом также в умножителе 2.2.2 вычисляется (-а. а,/а), в сумма(торе 9.2,2 - а = а- а а,/а.1, которое записывается в регистр 8.2,2 Р-триггер 7.2.2, переключается единичным сигналом с выхода Р- триггера 14.2. 1, а записывается в регистр 5.2,2 и У, = а поступает на второй выход первой группы выходов устройства. В схеме 11.11 срав( нения сравниваются а и а з . Пустьа+)(а, тогда единица с выхода схемы сравне ния з аписыв ается в Р-триггер 14,1,1, а также поступает на управляющие входы мультиплексоров 12.1.1 и 13.1.1, которые пропускают на свои выходы соответственно а и аВ делителе 17. 1. 1 вычисляется (-а/а, ), В регистрыЗХ10. 1. 1 и 15, 1. 1 запйсьвается соответственно а и -а /а . В этоммже тактенуль из Р-триггера 7,1,2 переписъвается в Р-триггер 7,1,3 а .поступает на первый вход вычислите:тельного модуля 1.1,3 и. в этом вычислительном модуле вычисляется элемент а з = а з - а, аз,/а который записъвается в регистр 8.1.3. Элемент аэ записывается в регистр 5. 1. 3.В шестом такте схеме 11.2. 1 сравнения сравниваются а и а. Пусть(131 а 4Тогда куль с выхода схемъ 11.2, 1 сравнения записъвается в триг гер 14. 2, 1, а мультиплексоры 12,2,1 и 13.2.1 пропускают на выходы соответственно а и а, В делителе ысляес (-а, а), а на первый выход первой группы устройства из регистра 10,2,1 поступает Р=аВ этом же такте нуль из Р-триггера 7.1.3 переписьвается в Р-триггер 7.1.4, и на первый выход второй группы выходов устройства поступает 25 ЗО 35 4 О 45 50 55 элемент матрицы перестановок 7,О,. На первъъй выход третьей группы выходов устройства поступает 1, = -а ,/ /а 1. С первого входа вычислительного модуля 1. 1.4 элемента а через сукчатор 9.1.4 и мультиплексор 6.1.4 записывается в регистр 8,1.4.В этом же такте в вычислительном модуле 1.2.3 вычисления а - (-а/а ,) на третий выход первой группы выходов устройства через регистр 5,2,3 поступает Уэ = а. В вычислительном модуле 1.1.2 формируется элемент а= -а азу/аки записъвается в регистр 8.1.2. В регистры 5. 1.2 и 5. 1. 4 записываются соответственно абаз и нуль.Далее элементы матриц П, Ь и Ч Формируются аналогичным образом. Формула изобретения 1, Устройство для треугольного разложения ленточных матриц, содержащее 1 6) вычислительных модулей ( Ю =Е + Ь + 1, Г и Ь - соответственно число под- и наддиагольных элементов матрицы), о т л и ч а ю щ е е с я тем, что, с целью сокращения аппаратурных затрат, -й вход первой группы информационных входов устройства подключен к первому информационному входу (1,) -говычислительного модуля Й = 1,ю), 1-й выход первой группы выходов устройства подключен к первому выходу (Г, )-го вычислительного модуля, первый информационный вход Ц,д)-го вычислительного модуля, (1 = 2,й) подключен к первому выходу Ц - 1, ) -го вычислительного модуля, второй и третий информационные входы (р,ц) -го вычислительного модуля (Р = 1 Ч = 2,Д подключены соответственно к второму и третьему выходам (р,о)-го вычислительного модуля, а второй и третий выходы (р, Ю)-го вычислительного модуля являются р-ми въиодами соответственно второй и третьей групп выходов устройства, второй информационный вход (р,1)-го вычислительного модуля подключен к четвертому въосоду (р,2)-го вычислительного модуля, четвертый информационный вход (р,И)-го вы.числительного модуля является р-м . входом второй группы информационных входов устройства, а четвертый информационный вход (р, С)-го вычиспи 1587540тельного модуля ( 2,Ь) поделю-) чен к четвертому выходу (р, +1)-го вычислительного модуля, синхровход, устройства подключен к синхровходам всех вычислительных модулей.2. Устройство по п.1. о т л и - ч а ю щ е е с я тем, что (р,ц)-й вычислительный модуль содержит умно- житель, сумматор, два мультиплексо ра, три регистра и Э-триггер, причем первый информационный вход вычислительного модуля подключен к первым информационным входам первого и второго мультиплексоров, выходы которых подключены к первым входам соответственно умножителя и сумматора, первый выход вычислительного модуля подключен к выходу первого регистра, информационный вход которого подключен 20 к выходу первого мультиплексора, управляющий вход которого соединен с управляющим входом второго мультиплексора и информационным входом Р-триггера, второй и третий информацион ные входы вычислительного модуля подключены к информационным входам 0-триггера и второго регистра, выходы которых являются соответственно вторым и третьим выходами вычисли тельного модуля, четвертый информационный вход которого подключен к вторым информационным входам первого и второго мультиплексоров, информационн й вход второго регистра под ключен к второму входу умножителя, выход которого подключен к второму входу сумматора, выход которого подключен к информационному входу третьего регистра, выход которого явля ется четвертым выходом вычислительного модуля, синхровход которого подключен к синхровходам всех регистрови Р-триггера. 3. Устройство по п.1, о т л и -ч а ю щ е е с я тем, что (р,1)-йвычислительный модуль содержит дварегистра, два мультиплексора, схемусравнения, делитель, инвертор и 12 триггер, причем первые информационные входы первого и второго мультиплексоров соединены с первым входомсхемы сравнения и с первым информационным входом вычислительного модуля, первый выход которого соединенс выходом первого регистра, информационный вход которого подключенк выходу первого мультиплексора, первому входу делителя и входу инвертора, выход которого соединен с входомобнуления второго регистра, информационный вход которого соединен свыходом делителя, второй вход которого соединен с выходом второго мультиплексора, второй информационныйвход которого соединен с вторым информационным входом второго мультиплексора, вторым входом схемы сравнения и вторым информационным входомвычислительного модуля, второй и третий выходы которого соединен с выходами соответственно 0-триггера ивторого регистра, выход схемы сравнения подключен к управляющим входаммультиплексоров и входу Э-триггера,синхровход вычислительного модуляподключен к синхровходам всех регистров и П-триггера,1587540 43 ф 32 б 1 , гР 1 2 з а Ф Фцг. Составитель К.Кухаренкоеда тор С.Патрушева Техред А.Кравчук . КоРРектоР И.Максимишинец аказ 2422НИИПИ Государс Тираж 568 Подписно ГКНТ СССР енного 13035,аааеааевеабмаецроизнодстаенно здательский комбинат "Патент", г. Ужгород, ул. Гагарина, 10 Т Ф 50 7 д Уд) Оу О фи фО а 8 УР 1 у яу 87 Ю омитета по изобретениям и открытиям иМосква, Ж"35, Раушская наб., д. 4/5