Устройство для LU - разложения матриц Советский патент 1991 года по МПК G06F17/16 

Изобретение относится к вычислительной технике и может быть использовано при построении специализированных устройств, предназначенных для решения систем уравнений, обращения матриц.

Цель изобретения - повышение быстродействия.

На фиг. 1 приведена структурная схема устройства для Ш-разложения матриц; на фиг. 2 - схема (I, 1)-го вычислительного модуля (, N-1; N - размерность обрабатываемых матриц); на фиг. 3 - схема (11. j)-ro вычислительного модуля (, N-1); на фиг. 4 - схема (k, j)-ro вычислительного модуля (, N-1); на фиг. 5 - схема (N, 1)-го вычислительного модуля; на фиг. 6 - схема (1, N)-ro вычислительного модуля; на фиг. 7 - схема (n.m)-ro вычислительного модуля (,N при , N-1 при ).

Устройство содержит матрицу (NxN) вычислительных модулей 1, блок 2 синхронизации, синхровход 3, вход 4 управления, группу информационных входов 5, группу

выходов 6, мультиплексоры 7. регистры 8, делитель 9, умножитель 10 и сумматор 11.

(i, 1)-й вычислительный модуль (фиг. 2) и (N, 1)-й вычислительный модуль (фиг 5) имеют вторые входы (не обозначены), подключенные к выходам регистров б.

(1, j)-u (фиг. 3) и (1, М)-й (фиг. 6) вычисли- тельные модули имеют третьи информационные входы и вторые выходы (не обозначены), подключенные соответственно к входам знаменателя и выходам соответствующих делителей 9.

(k, jj-й вычислительный модуль (фиг. 4) имеет третий и четвертый (информационные входы (не обозначены), подключенные соответственно к первому и второму входам умножителя 10

(п, т)-й вычислительный модуль имеет второй и третий информационные входы (не показаны), подключенные соответственно к первому и второму входам сумматора 11.

.Блок 2 синхронизации может быть выполнен, например, в виде N-разрядного

(/

С

ON ON

О СО

счетчика, работающего в режиме счета синхроимпульсов. На выход блока синхронизации выдается 1, когда содержимое счетчика равно 1, во всех остальных случаях на выходе блока синхронизации О,

Устройство предназначено для разбиения квадратной матрицы А порядка N на две треугольные: нижнюю левую L и верхнюю правую U, такие, что , причем на главной диагонали матрицы К стоят единицы. Преобразование матрицы выполняется по алгоритму исключения Гаусса, в процессе которого получаются элементы lij и Uij матриц L и К на основе рекуррентных формулj -1

lij-aij- 2 lisusj;();

s 1

1 -1 UU--JJJ- (ац- J lisu«j);(KJ).

Рассмотрим работу устройства на примере разбиения произвольной матрицы четвертого порядка

2142 3211 1332 1213

Искомые матрицы L nU, удовлетворяю- щие , будут:

О 1(2

U

О О

о

о

и

114

о

о

2 40-4(«/26

О1

5/2 2G О

3/2 14 /и. На первом такте работы ycTpjoncTea в вычислительные модули 1ц, где ,4, с входов 5ij в регистры 8 принимаются элементы aij матрицы А. В вычислительных модулях 1i,2, 1i,3, 1i,4 происходит деление содержимого регистров 8ij на содержимое регистра 8ц. На выходах делителей 9 вычислительных модулей 11,2,11,3,11,4 получаются числа 1/2, 2,1. В вычислительных модулях 1ц, где ,4, происходит перемножение чисел, поступивших из вычислительных модулей 1 и и 1i|, затем это произведение в сумматоре 11 отнимается от содержимого регистра 8 данного вычислительного модуля 1ij. Таким образом, на выходах сумматоров 11 вычислительных Модулей 12,2, 12,3, 12,4, Ъ.2, 133, 1з,4, 14,2, 14,3. 14,4 ПОлуЧЭЮТСЯ ЧИСЛЭ 1/2,

-5, -2,5/2,1,1, 3/2, -1,2, с выходов 61.1, 62.1, 63,1,64,1 считываются элементы In, 121, lsi, 141 первого столбца матрицы L 2,3,1,1, с выходов 61.2,61.3, 6i.4 считываются элементы Ui2, Ui3, Uu первой строки матрицы U 1 /2, 2, 1.

0 5

0

5

0

5

0 5 0

5

На втором такте с выходов 6ij, где l,,4, в регистры 8 вычислительных модулей 1|-1,-1 принимаются элементы 1/2, -5, -2, 5/2, 1,1, 3/2, -1,2. После аналогичных действий, как на первом такте, на выходах делителей 9 вычислительных модулей 1i,2, Ь,з получаются числа -10, -4, на выходах сумматоров 11 в вычислительных модулях 12,2, 12,3, 1з,2, 1з,з - числа 26, 11, 14, 8. С выходов 6i,i, 62,1, 63,1 считываются элементы I22, 1за, I42 второго столбца матрицы L 1/2,5/2, 3/2, с выходов 61,2. 61,3 считываются элементы U23, U24 второй матрицы U- 10, -4.

На третьем такте с выходов 62,2, 62,3, 6з,2, бз.з, в регистры 8 вычислительных модулей 1i,i, 1i,2, 12,1, 12,2 принимаются элементы 26, 11, 14 и 8. Затем на выходе делителя 9 вычислительного модуля получается число 11/26, на выходе сумматора 11 вычислительного модуля 12,2 получается число 27/13. С выходов 6i,i, 62,1 считываются элементы зз и Us третьего столбца матрицы L 26 и 14, с выхода 61,2 считывается элемент 1)34 третьей строки матрицы U 11 /26.

На четвертом такте с выхода 62,2 в регистр бвычислительного модуля 1и записывается элемент 27/13 и затем с выхода 61.1 считывается последний искомый элемент 144 27/13.

Таким образом, после четырех тактов получены все элементы искомых матриц L и U, удовлетворяющих .

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

Устройство для Ш-разложения матриц, содержащее матрицу NxN вычислительных модулей (N - размерность обрабатываемых матриц) и блок синхронизации, вход которого является синхровходом устройства, группу выходов которого образуют первые выходы (n.m)-x вычислительных модулей (,N при ,N при ), входы управления и синхровходы которых подключены соответственно к выходу и входу блока синхронизации, отличающееся тем, что, с целью повышения быстродействия, синхровходы, (i,j)-x вычислительных модулей (l,,N) подключены к входу блока синхронизации, выход которого соединен с входами управления (l,k)-x вычислительных модулей (l,,N-1), первые информационные входы всех вычислительных модулей образуют группу информационных входов устройства, первый выход (I.J)-ro вычислительного модуля подключен к второму информационному входу (i-1,J-1)-ro вычислительного модуля, второй выход (р, 1)-го вычислительного модуля подключен к третьему информационному входу (р,1)-го вычислительного модуля ( ,N-1) и к второму информационному входу (р.М)-го вычислительного модуля, второй выход (N,1)-ro вычислительного модуля подключен к второму информационному входу (N.l)-ro

дом (1,1)-го вычислительного модуля, второй выход (N, 1)-го вычислительного модуля соединен так же с вторым информационным входом (N,N)-ro вычислительного модуля,

. . - , - -r-ij --t-/ v««w wi t i « , i ч i j Wl РпиДуЛМ,

вычислительного модуля, третий информа-5 третий информационный вход которого

ционный вход которого соединен с четвер-соединен с третьими информационными

тыми информационными входами (k,l)-xвходами (k,N)-x и вторым выходом (1,М)-го

вычислительных модулей и с вторым выхо-вычислительных модулей

дом (1,1)-го вычислительного модуля, второй выход (N, 1)-го вычислительного модуля соединен так же с вторым информационным входом (N,N)-ro вычислительного модуля,

i « , i ч i j Wl РпиДуЛМ,

третий информационный вход которого

Изобретение относится к вычислительной технике, предназначено для LV-разложения матриц и может быть использовано при построении специализированных устройств, предназначенных для решения различных матричных задач. Целью изобретения является повышение быстродействия за счет реорганизации структуры устройства. Устройство содержит матрицу N^.N (N - размерность обрабатываемых матриц) вычислительных модулей и блок синхронизации, синхровход, вход управления, группу информационных входов и группу выходов. В основу работы устройства положен алгоритм исключения Гаусса. Особенностью функционирования устройства является параллельно-поточная организация вычислений. 7 ил.

Н

/

/

в

ч.

бi

(риг 2

.

бi+1,2

ФизЪ

6t.W

./ПА

фигЛ

VwW

.-J

Фиг. В

Ъ&

V V