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

 

Изобретение относится к автоматике и вычислительной технике и может быть использовано при построении специализированных устройств, предназначенных для решения систем линейных уравнений. Цель изобретения - сокращение аппаратурных затрат. Устройство выполняет первую фазу решения системы алгебраических уравнений AX = B (где X и B N - мерные векторы

A - ленточная матрица порядка N), которая состоит в отыскании нижне-и верхнетреугольных матриц L и V, таких, что V = L . A. Преобразование выполняется методом исключения Гаусса - прямого исключения с локальным выбором ведущего элемента. Перестановки строк запоминаются и выдаются в виде матрицы перестановок V. Особенностью работы устройства является параллельно-поточная организация вычислений в матрице вычислительных модулей двух типов. 2 з.п. ф-лы, 4 ил.

СОЮЗ СОЕЕТСКИХ

СОЦИАЛИСТИЧЕСКИХ

РЕСПУБЛИК

„„SU „„1587540

А1

egg)S G 06 F 15/347

ОПИСАНИЕ ИЗОБРЕТЕНИЯ

К A ВТОРСКОМ,Ф СВИДЕТЕЛЬСТВУ

ГОСУДАРСТВЕННЫЙ КОМИТЕТ

ПО ИЗОБРЕТЕНИЯМ И ОТКРЫТИЯМ

ПРИ ГКНТ СССР (21) 4462956/24-24 (22) 20,07.88 (46) 23.08.90. Бюл. № 31 (71) Киевский политехнический институт им. 50-летия Великой Октябрьской социалистической революции (72) Роман Выжиковски (Р?.), Ю.С.Каневский и О.В.Масленников (SU) (53) 681. 3 (088. 8) (56) Авторское свидетельство СССР

¹ 1509933, кл. С 06 F 15/347, 1987.

Kung Н.Т. Leiserson К.Е. Systolic

arrays for VLST. Proc.Symp.on Sprase Matrix Computations and their

Applications, 1978, р.256. (54) УСТРОЙСТВО ДЛЯ ТРЕУГОЛЬНОГО РАЗЛОЖЕНИЯ ЛЕНТОЧНЫХ МАТРИЦ (57) Изобретение относится к автоматике и вычислительной технике и может быть использовано при построеИзобретение относится к автома тике и вычислительной технике и может быть использовано при построении специализированных устройств, предназначенных дпя решения систем линейных уравнений.

Цель изобретения — сокращение аппаратурных затрат.

На фиг.1 представлена структурная схема устройства для треугольного разложения ласточных матриц;на фиг.2 — структурная схема (р,k)-го вычислительного модуля (р 1,Й, 2(d, (d f+h+ 1, f иЬ - соответственно число под- и наддиаго. нальных элементов матрицы);на фиг.3-.

2 нии специализированных устройств, предназначенных для решения систем линейных уравнений. Цель изобретения — сокращение аппаратурных затратт. Устройство выполняет первую фазу решения системы алгебраических Ь -Ф ч уравнений Ах = Ь (где х и Ь вЂ” N-мерные векторы; А — ленточная матрица порядка N) которая состоит в отыскании нижне- и верхнетреугольных матриц L и U, таких, что U = L A

Преобразование выполняется методом исключения Гаусса — прямого исключения с локальным выбором ведущего элемента. Перестановки строк sanoминаются и выдаются в виде матрицы перестановок V. Особенностью работы устройства является параллельно-поточная организация вычислений в -матрице вычислительных модулей двух типов. 2 з.п. ф-лы, 4 ил. структурная схема (р, 1 ) -го вычислительного модуля; н а фиг. 4 — порядок ввода и вывода элементов матрицы для случая = 2, h,=

Устроство для треугольного разложения ленточных матриц содержит (фиг.1) матрицу (р,q) (где с 1,ч) вычислительных модулей 1 р.q и генератор синхроимпульсов (не показав) „ выход которого подключен к синхровходам всех вычислительных модулей.

Вычислительный модуль 1 р k (фиг.2) содержит умножитель 2, второй регистр 3, первый мультиплексор 4, первый регистр 5, второй мультиплексор

1587540

Ь, D-триггер 7, третий регистр 8 и сумматор 9.

Вычислительный модуль 1 р .1 (фиг.3) содержит первый регистр 10, схему 11 сравнения, первый 12 и второй 13 мультиплексоры, D-триггер 14, второй регистр 15, инвертор 16 и делитель 17.

Устройство для треугольного раз- 1р ложения ленточных матриц предназначено для выполнения первой фазы решения системы линейных алгебраических уравнений Ах =:Ь (где х и Ь вЂ” N — мерные векторы-столбцы, а А - ленточная ма- 15 трица N-ro порядка) методом исключения Гаусса — прямого исключения, которое состоит в нахождении такой нижней треугольной матрицы L, которая преобразует матрицу А в верхнюю тре- 2р угольную матрицу U, т.е. U = L А.

Преобразование ленточной матрицы A = (а;; ) с шириной ленты И= f+h+1 где f u h " "число соответственно под- и наддиагональных элементов ма- 25 трицы А, выполняется по алгоритму исключения Гаусса с локальным выбором главного (ведущего) элемента.

Локальный выбор ведущего элемента предполагает, что исключение элемента а" на i-м шаге алгоритма Гаус31 са (i = 1,h-1), j = i+1, j+f) предше ствуе т сравнение элемен тон а и а ц;1;, причем, если а<. „>, а (, то осуществялется перестановка 1-й и (j-1)-й строк. Затем производится пре. образование j -й строки путем поэлементного вычитания из нее (j -1) -й строки, умноженной на коэффициент а; /а 11, = -1;. В противном случае 4О перестановка строк не производится.

Таким образом в качестве ведущего при исключении элемента а; используется теперь максимальный по абсо-. лютной величине элемент i-го столб- 45 ца, расположенный в .строках от (j

1) -й до j-й включительно. При этом все происходящие перестановки строк запоминаются и выдаются (в качестве нижней треугольной матрицы перестановок V = )U.; )) для дальнейшего использования.

Устройство работает следующим образом. .Положим Д = 4, (д= 4, f = 2, условимся, что прием информации во все регистры и триггеры осуществляются по заднему фронту синхроимпульса, т а, в конце такта все триггеры и регистры перед началом вычисления устанавливаются в нулевое состояние.

Обозначим а 1 элемент à íà i-м ша.1„ j4

re вычислений.

Информационные входы устройства второй группы подключаются к потенциалу логического нуля.

В первом такте на первые входы вычислительных модулей 1.1.1-1.1.4 поступают (фиг. 4) соответственно 0,0, a„, О. Мультиплексор 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 переписывается а из

fI регистра 8.1.3.

В третьем такте на первые входы вычислительных „модулей 1. 1 . 1 и 1. 1. 3 поступают соответственно элементы а, и а . а, сравнызается в схеме сравнения 11. 1,1 с а, ° Пусть в нашем случае а,t((à,j. Тогда нуль с выхода схемы сравнения записывается в триггер 14.1.2 и поступает на управляющие входы мультиплексоров 12,1.1 и 13.1.1, которые пропускают на свои выходы соответственно а 1 и а „, В делителе 17, 1. 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 сравнения поступают соответственно а, и а „. Пусть (a 1 р а„, . Тогда едйница с выхода схемы 11.2.1 сравнения переключает D-триггер 14.2.1 и мультиплексоры 12.2.1 и 13.2 ° 1, которые пропускают на свои выходы соответственно а, н а „ . В делителе

17.2.1 вычисляется (-а 11/a ) и записывается в регистр 15 .2 .1. В регистр

10.21 записывается а = U„ и поступа1587540

10 !

2О ет на первый выход первой группы выходов устройства.

В этом же такте (-а

3.1.2 и поступает ка второй вход умножителя, на первый вход которого из регистра 8.1.3 через мультиплексор

4.1.2 поступает а, а записывается также в регистр 5.1.2. Результат умножения (-а zz- a3, /à z,) суммируется с а и а = a3z а 2а3 /а, записывается в регистр 8.1.2, в регистр 8.1.4 — az» в 5.1.3 — aqz.

В пятом также в умножителе 2.2.2 вычисляется (-а. а,„/а „), в сумма( торе 9.2.2 — а 2 = а12 — а а,/а2 которое записывается в регистр

8.2.2 D-триггер 7.2.2, переключается единичным сигналом с выхода Dтриггера 14.2.1, а записывается в регистр 5.2.2 и U = а поступает на второй выход первой группы выходов устройства. В схеме 11. 1 ° 1 сравf

Heíèÿ сравниваются а и а з . Пусть (a+z )(а, тогда единица с выхода схемы сравнения записывается в Р-триггер 14. 1. 1, а также поступает на управляющие входы мультиплексоров t2.1. 1 и 13. 1.1, которые пропускают на свои выходы соответственно а и а,, В делителе 17.1.1

I вычисляется (-а /а, ) . В регистры

3z

10.1.1 и 15.1.1 запйсывается соответственно а и -а /а . В этом м же такте нуль из D-триггера 7.1.2 переписывается в D-триггер 7.1.3 а .поступает на первый вход вычисли33 тельного модуля 1.1.3 и в этом вычислительном модуле вычисляется элеI

33 a z a> /a zg KQTop6IH записывается в регистр 8.1.3. Элемент а 3 записывается в регистр

5. 1. 3.

В шестом такте схеме 11.2.1 сравнения сравниваются а и а 2 . Пусть (f a (> f a «/ . Тогда нуль с выхода схемы 11.2. 1 сравнения записывается в триггер 14.2. 1, а мультиплексоры

12.2.1 и 13.2.1 пропускают на выходы соответственно а и а . В делителе вычисляется (-а a ), а на первый выход первой группы устройства из регистра 10.2.1 поступает U =

= azz °

В этом же такте нуль из D-триггера 7. 1. 3 переписывается в D-триггер 7.1.4, и на первый выход второй группы выходов устройства поступает

ЗО

4О

55 элемент матрицы перестановок 7> О, На первый выход третьей группы выходов устройства поступает L>, = -а,/

/а21. С первого входа вычислительного модуля 1. 1.4 элемента а через суьжатор 9.1.4 и мультиплексор 6.1.4 записывается в регистр 8,1.4.

В этом же такте в вычислительном модуле 1.2 .3 вычисления а — (-а „ /а 2,) на третий выход первой группы выходов устройства через регистр 5.2.3 поступает U<> = а .

В вычислительном модуле 1. t.2 формируется элемент а +3 = -а . а 3 /а к и записывается в регистр 8.1.2. В регистры 5. 1.2 и 5. 1. 4 записываются со отв етс твенно а 3 и нуль.

Далее элементы матриц U Ь и Ч формируются аналогичным образом.

Формула изобретения

1. Устройство для треугольного разложения ленточных матриц, содержащее f ° (д вычислительных модулей (Ю =

f + h + 1, f u h — соответственно число под- и наддиагольных элементов матрицы), о т л и ч а ю щ е е с я тем, что, с целью сокращения аппаратурных затрат, -й вход первой группы информационных входов устройства подключен к первому информационному входу (t,i) -го вычислительного модуля (i = 1,ю ), i-й выход первой группы выходов устройства подключен к пе рвом у выходу (f, i ) -го вычислительного модуля, первый информационный вход (j, i) -го вычислительного модуля, (1 = 2,f) подключен к первому выходу (j — 1, i) -го вычислительного модуля, второй и третий информационные входы (p,ц)-го вычислительного модуля (р = t, f, q = 2,с4 подключены соответственно к второму и третьему выходам (р,q-1)-го вычислительного модуля, а второй и третий выходы (р, M)-го вычислительного модуля являются р-ми выходами соответственно второй и третьей групп выходов устройства, второй информационный вход (р, 1)-ro вычислительного модуля подключен к четвертому выходу (р,2)-го вычислительного модуля, четвертый информационный вход (р,И)-го вы.числительного модуля является р-м . входом второй группы информационных входов устройства, а четвертый информационный вход (р, С)-го вычисли1587540 тельного модуля (t 2, М-1 J поделю- чен к четвертому выходу (р, 7+1)-ro вычислительного модуля, синхровход, устройства подключен к синхровходам всех вычислительных модулей.

2. Устройство по п.f. о т л и— ч а ю щ е е с я тем, что (р,q)-й вычислительный модуль содержит умножитель, сумматор, два мультиплексо- 10 ра, три регистра и D-триггер, причем первый информационный вход вычислительного модуля подключен к первым информационным входам первого и второго мультиплексоров, выходы которых подключены к первым входам соответственно умножителя и сумматора, первый выход вычислительного модуля подключен к выходу первого регистра, информационный вход которого подключен 20 к выходу первого мультиплексора, управляющий вход которого соединен с управляющим входом второго мультиплексора и информационным входом Р-триггера, второй и третий информацион- 25 ные входы вычислительного модуля подключены к информационным входам

D-триггера и второго регистра, выходы которых являются соответственно вторым и третьим выходами вычисли- щ тельного модуля, четвертый информационный вход которого подключен к вторым информационным входам первого и. второго мультиплексоров, информационный вход второго регистра подключен к второму входу умножителя, выход которого подключен к второму входу сумматора, выход которого подключен к информационному входу третьего регистра, выход которого явля- 40 ется четвертым выходом вычислительного модуля, синхровход которого подключен к синхровходам всех регистров и D-триггера.

3. Устройство по п.1, о т л и— ч а ю щ е е с я тем, что (p,1)-й вычислительный модуль содержит два регистра, два мультиплексора, схему сравнения, делитель, инвертор и Dтриггер, причем первые информационные входы первого и второго мультиплексоров соединены с первым входом схемы сравнения и с первым информационным входом вычислительного модуля, первый выход которого соединен с выходом первого регистра, информационный вход которого подключен к выходу первого мультиплексора, первому входу- делителя и входу инвертора, выход которого соединен с входом обнуления второго регистра, информационный вход которого соединен с выходом делителя, второй вход которого соединен с выходом второго мультиплексора, второй информационный вход которого соединен с вторым информационным входом второго мультиплексора, вторым входом схемы сравнения и вторым информационным входом вычислительного модуля, второй и третий выходы которого соединен с выходами соответственно D-триггера и второго регистра, выход схемы сравнения подключен к управляющим входам мультиплексоров и входу D-триггера, синхровход вычислительного модуля подключен к синхровходам всех регистров и D-триггера.

1587540

1587540

Т

Ф 06

023

8 УУ3

Я

) Oyy

423 Î3 32 +It

4g >sz n Ъ +31

leg 31 д 10У87Ю

7 0

2 з а

Ф 42 б а

О о

g23 л

УЗУ Ъ

Составитель К.Кухаренко

Редактор С.Патрушева Техред A.Кравчук . Корректор И.Максимишинец

Заказ 2422 Тираж 568 Подписное

BHHHIJH Государственного комитета по изобретениям и открытиям при ГКНТ СССР

113035, Москва, Ж-35, Раушская наб., д. 4/5

° ввюю аиююе

Ирциз@одстаенно-издательский комбинат "Патент", r. Ужгород, ул. Гагарина, 101