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

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

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

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

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

вторую 7 группы выходов устройства, вычислительный модуль (фиг. 2) содержит первый 8 и второй 9 регистры, первый 10 и второй 11 умножители, первым 12 и второй 13 вычи- татели, третий 14 и четвертый 15 регистры, первый 16 и второй 17 синхровходы.

Вычислительный блок (фиг. 3) содержит первый узел 18 деления, умножитель 19, регистр 20, вычитатель 21, второй узел деления 22 и регистр 23.

Блок 5 синхронизации представляет собой генератор импульсов, прямой и инверсный выходы которого подключены соответственно к синхровходам 16 и 17 всех вычислительных модулей и всех вычислительных блоков (не показано).

Устройство для LDLT - разложения матриц предназначено для разложения данной симметричной теплицевой матрицы А. т.е. матрицы, элементы aik которой удовлетворяют равенствам

ам. k+1 -aik(i, k 1, N-1)

О 00

ю

ЧЭ -Ч

О

a(i.k) a(k,i) (I 2, N1, k 1,1-1) (4,5) на два треугольные (нижнюю L и верхнюю LT, где знак т обозначает транспонированную матрицу) и диагональную D такие, что А LDL/, Алгоритм формирования элементов Ilk ( ГМ, ) и элементов di соответствующих матриц L и D имеет вид.

2ii.m« QMJ i ,

ск WK,K-I / (,K-i „„/(l-cj);

{IK 4i-i,x-i- Ск mi,K-( miKc m-i,K-i CKE-i-i,K-(;

K.

.i V,,M

где ck , rn IK промежуточные переменные.

Устройство работает следующим образом.

Для кратности описания без потери общности положим N 3. Условимся, что прием информации во все регистры осуществляется по переднему фронту соответствующего синхроимпульса.

Первый столбец (или строка) исходной теплицевой симметричной матрицы А подается на группу информационных входов 1 устройства по первому тактовому импульсу с блока 5,

Первый такт. В первой половине такта параллельно вычисляются значения di 1/ац в блоке 2 деления и С2 - а21/ац в вычислительном блоке 4.1 и поступают соответственно не первый информационный вход вычислительного блока 4.1 и объединенные третьи информационные входы вычислительных модулей 3.1.1 и 3.2.1. Во второй половине такта в регистры 8 и 9 вычислительного модуля 3.1.1 записываются значения аи и 321, в регистры 8 и 9 вычислительного модуля 3.2.1 - а21 и аз1. Вычисляются значения элементов

122 311-С2 321; ГП22 321 С2 311 В ВЫЧИСЛИтельном модуле 3.1.1 и 1з2 321 - С2 азк тз2 аз1 - С2 321 в вычислительном модуле 3.2.1, значения которых подаются соответственно на информационные входы регистров 14 и 15 вычислительных модулей 3.1.1 и 3.2.1. На выходе умножителя 19 вычислительного блока 4.1 вычисляется значение С2 и подается на информационный вход регистра 20.

Второй такт. В начале такта значения элементов I22, гша и 1з2. лпз2 записываются соответственно в регистры 14 и 15 вычислительного модуля 3.1.1 и 3.2.1, С22 в регистр 20 вычислительного блока 4.1, В первой половине такта параллельно вычисляются d2 di/(1-C22) в вычислительном блоке 4.1 и сз

Ш32/122 в вычислительном блоке 4.2 и поступают соответственно на информационный вход регистра 23 вычислительного блока 4.2 и третий информационный вход вычисли5 тельного модуля 3.2.2. Во второй половине такта значение da принимается в регистр23 вычислительного блока 4.1 и поступает на первый информационный вход вычислительного блока 4.2. На выходе умножителя

10 19 вычислительного блока 4.2 вычисляется значение сз2 и подается на информационный вход регистра 20. В регистры 8 и 9

вычислительного модуля 3.2.2 записывают- K Z,N,ся значения 122И тз2и вычисляются элемен15 ты зз I22 - сз гпз2, тзз тз2 - сз I22, значения которых соответственно подаются на информационные входы регистров 14 и 15 вычислительного модуля 3.2.2.

Третий такт. Значения элементов зз и

20 гпзз записываются соответственно в регистры 14 и 15 вычислительного модуля 3.2.2, сз2 - в регистр 20 вычислительного блока 4.2. В первой половине такта вычисляется значение ds d2/(1-cs2). Значение элемента ds

25 принимается в регистр 23 вычислительного блока 4.2.

На этом процесс LDLT- разложения теплицевой симметричной матрицы А завершается, Элементы нижней треугольной

30 матрицы L: In, 121, bi - снимаются в начале первого такта с выходов первой группы устройства 6.1.1, 6.2.1, 6.3.1 соответственно, элементы 122, з2 - в начале второго такта с выходов первой группы устройства 6.2.2,

35 6.3.2, элемент 1зз в начале третьего такта с выхода первой группы устройства 6.3.3. Значения элементов главной диагонали диагональной матрицы D: di, d2. d3 снимаются в первом, втором и третьем тактах

40 соответственно с выходов второй группы устройства 7.1, 7.2, 7.3.

Поскольку каждый элемент очередного шага вычислений используется в каждом модуле и блоке только один раз, можно вы45 полнять LDLT - разложение потока матриц. Первый столбец (строку) следующей матрицы можно подавать в следующем такте по- сле начала подачи столбца (строки) предыдущей матрицы.

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

Устройство для разложения теплицевых симметричных матриц, содержащее N(N- 1)/2 вычислительных модулей, где N - размерность разлагаемой матрицы, и блок

55 синхронизации, прямой и инверсный выходы которого подключены соответственно к первому и второму синхровходам всех вычислительных модулей, причем первый информационный вход(1,1)-го вычислительного модуля подключен к i-му информациейному входу первой группы устройства (1-1, N-1), первый jibixofl (I, к}-го вычислительного модуля 0-1, N-2,- k 1, J) подключен к первому информационному входу (J+1, k+1)-ro вычислительного модуля, отличающееся тем, что, с целью повышения быстродействия, в устройство введены блок деления и N-1 вычислительных блоков, причем (+1}-й информационный вход группы устройства подключен к второму информационному входу (I. 1)-го вычислительного модуля, n-й информационный вход группы устройства (п 1, N) является (п, 1}-выходом первой группы устройства, (О. р)-й выход которой (О 27 N, р 2, 0) подключен к первому выходу (0-1, р-1)-го вычислительного модуля, первый информационный вход группы устройства подключен к входу делителя блока деления, вход делимого которого подключен к входу задания единицы устройства, выход блока деления подключен к первому выходу второй группы устройства и первому информационному входу первого вычислительного блока, первый выход j-ro вычислительного блока подключен к первому информационному входу ()+1)-го вычислительного блока, первый выход 1-го вычислительного блока является (1+1)-м выходом второй группы устройства, второй выход (g, h)-ro вычислительного модуля подключен к второму информационному входу (g. h-Hbp вычислительного модуля (g 2, N-1; h 1, g-1). второй и третий информационные входы 1-го вычислительного блока подключены соответственно к первому и второму информационным входам (i, i)-ro вычислительного модуля, второй выход 1-го вычислительного блока подключен к объединенным третьим информационным входам (п, 1)-го вычислительного модуля (), первый и второй синхровходы всех вычислительных блоков подключен соответственно к прямому и инверсному выходам блока синхронизации, причем каждый вычислительный модуль содержит четыре регистра, два умножителя и два вычитателя, первый и второй информационные входы

вычислительного модуля подключены к информационным входам соответственно первого и второго регистров, выходы которых подключены к первым входам соответственно первого и второго умножителей и входам уменьшаемого соответственно первого и второго вычислителей, входы вычитаемого которых подключены к выходам соответственно второго и первого умножителей, обьединенные вторые входы которых являются третьим информационным входом вычислительного модуля, первый и второй выходы которого подключены к выходам соответственно третьего и четвертого регистров, информационные входы которых подключены к выходам соответственно первого и второго вычитателей, объединенные синхровходы первого и второго регистров подключены к второму синхровходу вычислительного модуля, первый синхровход которого подключен к объединенным синхровходам третьего и четвертого регистров, каждый вычислительный блок содержит два узла деления, умножитель,

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

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

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

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

о гCDСП

со со

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