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

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

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

На фиг.1 и 2 представлена функциональная схема устройства; на фиг.З - функциональная схема операционного модуля; на фиг.4 - функциональная схема дополнительного операционного модуля; на фиг.5 - функциональная схема операционного блока; на фиг.6 - функциональная схема блока формирования детерминантов.

Устройство (фиг.1 и 2) содержит первую группу информационных входов 1, блок деления 2, вычислительные модули 3, вычислительные блоки 4, блок синхронизации 5, первую 6 и вторую 7 группы выходов устройства, вторую группу информационных входов 8, буферные регистры 9 и 10, операционные модули 11, дополнительные операционные модули 12, операционные блоки 13, блок формирования детерминантов 14, выходы 15, 16 и 17 устройства. При этом каждый вычислительный модуль 3 содержит первый 18 и второй 19 регистры, первый 20 и второй 21 умножители, первый 22 и второй 23 вычитатели, третий 24 и четвертый 25 регистры, первый 26 и второй 27 синхровходы. Каждый вычислительный блок 4 содержит первый узел деления 28, умножитель 29, регистр 30, вычитатель 31, второй узел деления 32 и регистр 33,

Блок синхронизации 5 представляет собой генератор импульсов, прямой и инверс- ные выходы, которого подключены соответственно к синхровходам 26 и 27 всех вычислительных и операционных модулей и блоков. Операционный модуль (фиг.З) содержит первый 34 и второй 35 регистры, умножитель 35, Дополнительный операционный модуль (фиг.4) содержит первый 37 и второй 38 регистры, сумматор 39. Операционный блок (фиг.5) содержит первый 40 и второй 41 умножители, первый 42 и второй 43 регистры. Блок формирования детерминантов (фиг.6) содержит сумматор 44, первый 45, второй 46 и третий 47 регистры, блок деления 48, умножитель 49,

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

,к+1 ai,K(i,K 1,...,П-1),

ai.K ак.1 0 2П,К - 11-1J/2.3)

на две треугольные (нижнюю L и верхнюю LT, где, знак т обозначает транспонированную матрицу) и диагональную D, такие, что А LDL7 для вычисления детерминантов detA исходной матрицы A, det(A+XXT) сум- мы матриц А+ХХТ и квадратичной формы , где X - заданный вектор-столбец.

Алгоритм формирования элементов IIK (,) и элементов di соответствующих матриц L и D, приведенный в описании работы устройства .есть алгоритм номер 1.

Алгоритм вычисления квадратичной формы b (алгоритм номер 2) базируется на разложении матрицы , обратной к заданной, на две треугольные (нижнюю V и верх- нюю VT) и диагональную D, такие, что VTDV:

Ь XVDVX (VX)TD(VX) UTDU, то есть

Ё, .N

dlUI, где U - {Ui} VX, V -

матрица с единичной диагональю.

Алгоритм вычисления детерминантов det (алгоритм номер 3) базируется на COOT- ношении

detA - 1 /det() 1 /detD 1 /П di.

i 1

Алгоритм вычисления детерминанта det (А+ХХТ) суммы матриц А+ХХТ (алгоритм номер 4) основывается на соотношении

detfA+XX1) det + A(1+b).

Общий алгоритм работы устройства имеет следующий вид:

in, rrtnаи

XI J.

1-1N

пи, ni-xi JU

di-1/aiti b(1) - dilrn2; д - di) сц - тк.к-1/lK-i.K-i. dK-dK-1/О-ск2):. (Ь дЛк (IK - IM.K-I скт|.к-1 1 mix mi,K-i - CjdM.KH L /

DlK m ПМ.1С-1 - СКП.К-1 j

ПК П.К-1 7„гКШ-JLKrl J

UK TKK:b(() + dKUK2

det A - 1 / d; detfA+XX1) detA

где niK.riK, гтк. ск, 6 - промежуточные переменные, b b, подчеркнутые формулы есть формулы алгоритма номер 1, т.е. алгоритма работы устройства (1).

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

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

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

Первый такт, В первой половине такта параллельно вычисляются значения Ui2 Xi2 в первом умножителе 40 операционного блока 13, di I/an в блоке 2 деления и С2 321/ац в вычислительном блоке 4.1. Значение di поступает на первый и второй информационные входы соответственно блоков 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 соответственно записываются пары значений аи и 321, aai и аз1, xi и Х2, ха и хз. Вычисляются значения элементов I22 an -G2321, ГП22 321 С2Э11 В Вычислительном

модуле 3.1.1. 1з2 321-С2аз1: тза азг-С2Э21 в вычислительном модуле 3.2.1, П22 xi- С2Х2, Г22 - Х2-С2Х1 в вычислительном модуле

3,3.1 И П32 Х2 С2ХЗ, Г32 ХЗ- С2Х2 В ВЫЧИСлительном модуле 3.4.1; значения которых подаются соответственно на информационные входы регистров 24 и 25 вычислительных модулей 3.1., 3.2.1, 3.3.1 и 3.4.1. В умножителе 29 вычислительного блока 4.1 вычисляются значения С22 и подается на информационный вход регистра 30. В умножителе 41 операционного блока 13.1 вычисляется значение b 1 di xi2 и подается на информационный вход регистра 43.

Второй такт. В начале такта пары значений I22 И ГП22132 И ГП32П22 И Г22, П32 И Г32

записывается соответственно в регистры 24 и 25 вычислительных модулей 3.1,1, 3.2.1,

3.3.1и 3.4.1, значение С2 в регистр 30 вы- числительного блока 4.1, значение di - регистр 9,значение tr1 dixi2 - в регистр 43 операционного блока 13.1. В первой половине такта параллельно вычисляются d2 di(1-C22) в вычислительном блоке 4.1 и сз тз2/122 в вычислительном блоке 4.2 и поступают соответственно на информационный вход регистра 33 вычислительного блока 4.1

и объединенные третьи информационные входы вычислительных модулей 3.2.1 и 3,3.2, а также вычисляется значение U22 Г222 в первом умножителе 40 операционного блока 13.2. Во второй половине такте значение d2 принимается в регистр 33 вычислительного блока 4.1 и поступает на первый информационный вход вычислительного блока 4.2, на вторые информационные входы операционного модуля 11.1 и операционного блока 13.2. Значение di записывается в регистр 34 операционного мо- дуля 11.1, в котором вычисляется произведение did2. Значение tr1 записывается в регистр 10 и подается на первый информационный вход дополнительного операционного модуля 12.1. Значение U22 Г222 записывается в регистр 42 операционного блока 13.2 и подается на вход умножителя 41, на второй вход которого подается значение d2 и начинается вычисление . На выходе умножителя 29 вычислительного блока 4,2 вычисляется значение сз и подается на информационный вход регистра 30. В регистры 18 и 19 вычислительного модуля

3.2.2записываются значения I22 и тз2 и вычисляются элементы зз I22 сзтз2. тзз - тз2 значения которых соответственно подаются на информационные входы регистров 24 и 25 вычислительного модуля 3.2.2. В регистры 18 и 19 вычислительного модуля 3.3.2 записываются значения элемен- тов П22 и гз2 и вычисляются элементы пзз

П22 С2Г32, ГЗЗ Г32 СЗП22. ЗНЭЧвНИЯ КОТОРЫХ

соответственно подаются на информационные входы регистров 24 и 25 вычислительного модуля 3.3.2.

в вычисли- d2U22 в

Третий такт. Пары значений зз и тзз. пзз и гзз записываются соответственно в регистры 24 и 25 вычислительных модулей 3.2.2 и 3.3.2, значения сз2 - в регистр 30 вычислительного блока 4.2, did2 - в регистр 35 операционного модуля 11.1, b 1 - в регистр 37 дополнительного операционного модуля 12.1, d2U2 - в регистр 43 операционного блока 13.2. В первой половине такта вычисляются значения ds $2/(1-сз2,) в тельном блоке 4.2, tr2 tr1 -t дополнительном операционном модуле 12.1, которые поступают соответственно в регистры 33 вычислительного блока 4.2 и 38 дополнительного операционного модуля 12,1 и U32 гзз в операционном блоке 13.3. Во второй половине такта значения dsdid2,

голо

b и Уз записываются соответственно в регистры 33 вычислительного блока 4.2 34 операционного модуля 11.2, 38 дополнительного операционного модуля 12.1 и 42 операционного блока 13.3 и параллельно вычисляются значения did2d3 в операционном модуле 11.2 и dsUs в операционном блоке 13.3.

Четвертый такт. В первой половине такта значения drda ds, b® и dsUs2 записываются соответственно в регистры 35 операционного модуля 11.2, 37 дополнительного операционного модуля 12.2 и 43

операционного блока 13.3. Параллельно высу

числяются значения b tr tr + dsUs в

сумматоре 39 дополнительного операционного блока 122, 1/(di -d2 d3) и (1+b) соответственно в блоке деления 48 и сумматоре 44 блока формирования детерминантов 14. Во второй половине такта значения detA 1/did2ds и 1+b записываются соответственно в регистры 45 и 46 блока формирования детерминантов и 38 дополнительного операционного модуля 12.2. На выходе умножителя 49 блока формирования детерминантов 14 вычисляется значение det(A+XXT) detA(1+b) и подается на информационный вход регистра 47, в который записывается в начале nfljprp такта,

На этом вычисления в устройстве завершаются. Элементы нижней треугольной матрицы L: In, l2i, Ы снимаются в начале первого такта с выходов первой группы выходов устройства 6.1.1, 6.2.1 и 6.3.1 соответственно, элементы I22,1з2 - в начале второго такта с выходов первой группы выходов устройства 6.2.2 и 6.3,2, элемент зз - в начале третьего такта с выхода первой группы устройства 6.3.3. Значения элементов главной диагонали диагональной матрицы D: did2d3 - снимаются в первом, второй и третьем тактах соответственно с выходов

второй группы выходов устройства 7.1, 7.2 и 7.3. Значения b и detA снимаются во второй половине четвертого такта соответственно с выходов устройства 17 и 15. Значение det(A+XXT) снимается с выхода устройства 16 в начале пятого такта.

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

Процесс определения элементов hj, mij, mj, rij, di, b™ и detA представлен в виде слоев с целью распараллеливания вычислений до уровня нескольких типов операций: l-cm или m-cl, n-cr или r-cn, d/(1-c ), b + dU2 и (did2...di-i)di. Это позволяет строить структуру из существу ощих интегральных схем ограниченной номенклатуры или в виде отдельных СБИС,

Формула изобретения Устройство для разложения теплицевых симметричных1 матриц по авт св. N 1689970, отличающееся тем, что, с целью расширения функциональных возможностей за счет вычисления детерминантов исходной матрицы и суммы матриц квадратичных форм с матрицей, обратной к исходной, в устройство введены первый и второй буферные-регистры, п-1 операционных модулей (где п - размерность входной матрицы), п-1 дополнительных операционных модулей, п операционных блоков, п(п- 1)/2 вычислительных модулей и блок формирования детерминантов, причем 1-й информационный вход второй группы устройства подключен к первому информационному входу (п+-1,1)-го вычислительного модуля (,...,п-1), второй информационный вход которого подключен к (1+1)-му информационному входу второй группы устройства, первый выход (|,К)-го вычислительного модуля (j n2n-3, K 12n-J-2)

подключен к первому информационному входу (|,К+1)-го вычислительного модуля, второй информационный вход которого подключен к второму выходу (j+1,K)-ro вычислительного мс-дуля, второй выход (n,f)-ro

вычислительного модуля подключен к первому информационному входу (1+1)-го операционного блока (1 1п-1). выход

которого подключен к второму информационному входу 1-го дополнительного операционного модуля, первый информационный вход второй группы устройства подключен к первому информационному входу первого операционного блока, выход которого под0 ключей к информационному входу второго буферного регистра, выход которого подключен к первому информационному входу первого дополнительного операционного модуля, выход блока деления под5 ключей к второму информационному входу первого операционного блока и информационному входу первого буферного регистра, выход которого подключен к первому информационному входу первого опера0 ционного модуля, первый информационный вход (т+1)-го операционного модуля (,.,.,n-2) подключен к выходу m-ro операционного модуля, выход (п-1)-го операционного модуля подключен к первому

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

5 информационному входу (m+1)-ro дополнительного операционного модуля, объединенные третьи информационные входы

(t.l)-ro вычислительного модуля (t n2п1-1) подключены к второму выходу 1-го вычис0 лительного блока, первый выход которого подключен к объединенным вторым входам 1-го операционного модуля и (1+1)-го операционного блока, первый и второй синхров- ходы всех блоков и модулей подключены

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

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

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

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

Ай

/,Н.,.Ц

-Э JJf-} N-t

6М

и

91

t-NHЈ

и

Г

WB.

JL Г

К4

I

ti

Ъ гпф

91

Ј-гпф

U

iz-NiЈ

гг-ш

«К

fl ttfl

I NI

if/Ј

т

S62S9it

1716

Фиг. 6