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

 

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

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

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

РЕСПУБЛИК (я)з G 06 F 15/347

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

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

ПРИ ГКНТ СССР

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

КА

К АВТОРСКОМУ СВИДЕТЕЛЬСТВУ (61) 1689970 . (21) 4880891/24 (22) 05.11.90 (46) 15.08.92. Бюл, М 30 (72) И, Г,Кириллов и Д.И.Леховицкий (56) Авторское свидетельство СССР . t4 1689970, кл. G 06 F 15/347, 1989. (54) УСТРОЙСТВО ДЛЯ РАЗЛОЖЕНИЯ

ТЕПЛИЦЕВЫХ СИММЕТРИЧНЫХ МАТРИЦ (57) Изобретение относится к вычислительной технике и может быть использовано для разложения квадратной теплицевой симметричной матрицы на две треугольные и диагональную матрицы, вычисления детерминантов исходной матрицы и суммы матриц квадратичных форм с матрицей, обратной к исходной. а также при построеИзобретение относится к вычислительной технике и может быть использовано автономно или в комплексе с ЦВМ для разложения квадратной теплицевой симметричной матрицы на две треугольные и диагональные матрицы, вычисления детер-. минантов исходной матрицы и суммы матриц, квадратичных форм с матрицей, обратной к исходной, для решения систем линейных уравнений, Целью изобретения является расширение функциональных возможностей устройства за счет вычисления детерминантов исходной матрицы и суммы матриц квадратичных форм с матрицей, обратной к исходной, На фиг.1 и 2 представлена функциональная схема устройства; на фиг.3 — функ!

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

3 ил. циональная схема операционного модуля; на фиг,4 — функциональная схема дополнительного операционного модуля, на фиг.5— функциональная схема операционного блока; на фиг.6 — функциональная схема блока формирования детерминантов, Устройство (фиг.1 и 2) содержит первую группу информационных входов 1, блок деления 2, вычислительные модули 3, вычислительные блоки 4, блок синхронизации 5, первую 6 и вторую 7 группы выходов устройства, вторую группу информационных входов 8, буферные регистры 9 и 10, операционные модули 11, дополнительные операционные модули 12, операционные блоки 13, блок формирования детерминантов 14, выходы 15, 16 и 17 устройства. При этом каждый вычислительный модуль 3 со1755295 держит первый 18 и второй 19 регистры, первый 20 и второй 21 умножители, первый

22 и второй 23 вычитатели, третий 24 и четвертый 25 регистры, первый 26 и второй 27 синхровходы, Каждый вычислительный блок 4 содержит первый узел деления 28, умножитель 29, регистр 30, вычитатель 31, второй узел деления 32 и регистр ЗЗ, Блок синхронизации 5 представляет собой генератор импульсов, прямой и инверсные выходы, которого подключены соответственно к синхровходам 26 и 27 всех вычислительных и операционных модулей и блоков. Операционный модуль (фиг.3) содержит первый 34 и второй 35 регистры, умножитель 35. Дополнительный операционный модуль (фиг.4) содержит первый 37 и второй 38 регистры, сумматор 39. Операционный блок (фиг.5) содержит первый 40 и второй 41 умножители, первый 42 и второй

43 регистры. Блок формированйя детерминантов (фиг.6) содержит сумматор 44, первый 45, второй 46 и третий 47 регистры, блок деления 48, умножитель 49, Устройство предназначено для разложения данной П-П теплицевой симметричной матрицы А, т.е. матрицы, элементы которой удовлетворяют равенствам

a}+1,к+1 = а},к(1,К = 1,.„,П вЂ” 1), а.,к = ак,; (! = 2,...,П,К = 1,...,1 — 1)/2,3) на две треугольные (нижнюю L и верхнюю

L, где, знак т обозначает транспонированную матрицу) и диагональную D, такие, что

А = ЫЗ(для вычисления детерминантов

detA исходной матрицы А, det(A+XX ) суммы матриц А+ХХ и квадратичной формы

X А Х, где Х вЂ” заданный вектор-столбец. т -1.

Алгоритм формирования элементов 11к (1=1,. „П,К=1) и элементов dd соответствующих матриц L и О, приведенный в описании работы устройства, есть алгоритм номер 1.

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

=Чт0V

Ь = X А "Х =ХтЧтОЧХ =(VX) O(VX) = u Du, то есть г ь - dlUI, riie U = IUI} = нх, u.d =1 i =:1 матрица с единичной диагональю.

Алгоритм вычисления детерминантов

det (алгоритм номер 3) базируется на соотношении

-1 и бесА-1/det(A ) =1/detD 1/Ï dd.

1=1

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

det(A+XX ) = det+ A(1+b), 5 Общий алгоритм работы устройства имеет следующий вид:

1», пт}т - а}1 j 1- 1, ..., л1 лн. nt - к} k-1

dt-1/ç»; b т1}1Г»;д" dt (11 2. сКШ11К= -1 Ы а-й=*1; -Ь г.

1}к - dl-l,ê-l — cKml.к-l

mIK - mI,K-1 — cKdI-1,K-t

fllK III-1,K-1 С КГ}.К-1

Г}К Г}.К-1 Дкп}- к-1

UK " Гкк: Ь1" = b1 1+ бк1.1к ет R . 1/ д; det(A+XX ) - detA(1+b1 } .

10 к-, М

20 где п}к,г}к, mg, ск, д — промежуточные переменные, Ь = b, подчеркнутые формулы ( есть формулы алгоритма номер 1, т,е, алгоритма работы устройства (1), Устройство работает следующим обра25 эом.

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

30 синхроимпульса.

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

35 устройства по первому тактовому импульсу с блока 5.

Первый такт, В первой половине такта параллельно вычисляются значения U1 г

=X1 в первом умножителе 40 операцион40 ного блока 13, d1 = 1/а11 в блохе 2 деления и с2 = a21/a11 в вычислительном блоке 4.1.

Значение d1 поступает на первый и второй информационные входы соответственно блоков 4.1 и 13.1, а также информационный

45 вход регистра 9. Значение с подается на объединенные третьи информационные входы вычислительных модулей 3.1.1, 3,2,1, 3.3,1 и 3.4.1. Во второй половине такта в регистр 42 операционного блока 13.1 запи50 сывается значение х1 в регистры 18 и 19 вычислительных модулей 3.1.1, 3,2,1, 3,3.1 и

3,4.1 соответственно записываются пары значений а11 и а21, аг1 и аз1, х1 и х:, хг и хз.

Вычисляются значения элементов 122 = а11—

55 -сга21; п122 = a21 — сга11 в вычислительном модуле 3.1 1. (зг = а21-сгаз1; ma2 = аз1-сгаг1 в вычислительном модуле 3,2.1, n22 =-. х1сгхг, r22 .= хг-с2х1 в вычислительном модуле

3.3.1 и n32 = х2 с2хз; гз2 =- хз С2х2 в Вычис

1755295 лительном модуле 3,4.1 значения которых Третий такт. Пары эначений133 и гпзз, п33

1 подаются соответственно на информацион- и гзз записываются соответственно в региные входы регистров 24 и 25 вычислитель- стры 24 и 25 вычислительных модулей 3,2.2 ных модулей 3.1., 3.2,1, 3.3.1 и 3.4,1, В и3.3.2, значения сз — в регистр 30вычислиг умножителе 29 вычислительного блока 4.1 5 тельного блока 4,2, d1dz — в регистр 35 опев(( вычисляются значения сг и подается на ин- рационного модуля 11.1, Ь вЂ” в регистр 37 формационный входрегистра30, Вумножи- дополнительного операционного модуля теле 41 операционного блока 13.1 вычис- .. 12,1, dzUz — в регистр 43 операционного г ляется значение Ь{ ) = d1,х1 и подается на блока 13.2, В первой половййе такта вычисг, информационный вход регистра 43. 10 лгятвтся значения Оз = ф/(1-сз в вычисли(1) 2

Второй такт. В начале такта пары значе- - тельном блоке 4,2, Ь = b + dzU2 в ний 122 и в22132 и тзгпгг и Ггг, пэг и гзг дополнитЕЛьНОм ОпЕРационном модуле записывается соответственно в регистры 24 12.1, которые поступают соответственно в и 25 вычислительных моуулей 3,1,1; 3,2,1 - регистры 33 вычислительногоблока4.2и38

3.3.1 и 3,4.1, значение cz a регистр 30 вы- 15 дополнительного операционного модуля ч ислительного бло 4.1, значение d1 — ре- 12,1 и (13 = гзз в операционном блоке 13.3.

2 2

1 гистр 9 значение b = с11х12 — в регистр 43 Во второй половине такта значения d3d1dz, операционного блока 13 1, В первой поло- b и 03 записываются соответственно в

I (2) 2 вине такта параллельно вычисляются dz = регистры 33 вычислительного блока 4 . 2 3 4

d1(1-сг ) в вычислительном блоке 4.1 и c3 = 20 операционного модуля 11.2, 38 дополнип132!122 в вычислительном блоке 4,2 и посту- тельного операционного модуля 12,1 и 42 пают соответственно на информационный операционного блока 13.3 и параллельно вход регистра 33 вычислите/)ьного блока 4,1 вычисляются значения d dzd3 в операциони объединенные третьи информационные ном модуле 11.2 и d3U3 в операционном входы вычислительных модулей 3,2.1 и 25 блоке 13.3.

3,3.2, а также вычисляется значение 02 = Четвертый такт, В пеовой половинетак=ггг в первом умножителе 40 операционно- та значения d1 dz d3, Ь и d3U3 записы г ) г го блока 13.2, Во второй половине такте ваются соответственно в регистры 35 значение dz принимается в регистр 33 вы- операционного модуля 11.2, 37 дополничислительного блока 4.1 и поступает на 30 тельного операционного модуля 12.2 и 43 первый информационный вход вычисли- операционного блока 13.3. Параллельно вы(3) (2) + 2 тельного блока 4.2, на вторые информаци- числяются значения Ь = Ь = Ь ) + d3U3 в онные входы операционного модуля 11.1 и сумматоре 39 дополнительного операционнооперационного блока 13.2. Значение d1 за- го блока 12,2, 1/(с(1 бг d3) и (1+b) соответстписываетсяврегистр34операционногОмо-"35 венно в блоке деления 48 и сумматоре 44 дуля 11.1, в котором вычисляется произве - блока формирования детерминантов 14. дение 0162. Значение b() записывается в Во второй половине такта значения detA= регистр 10 и подается на первый информа- -= 1/d1dzd3 и 1+b записываются соответстционный вход дополнительного операци- венно в регистры 45 и 46 блока формироваонного модуля 12,1. Значение Uz = ггг 40 ния детерминантов и 38 дополнительного

-г записывается в регистр 42 операционного операционного модуля 12,2. На выходе умблока 13.2 и подается на вход умножителя ножителя 49 блока формирования детер41, навторойвходкоторогоподается значе- минантов 14 вычисляется значение ние dz и начинается вычисление dzU2, На det(A+XX ) = с1етА(1+Ь) и подается на инфорвыходе умножителя 29 вычислительного 45 мационный вход регистра 47, в который эа. блока 4,2 вычисляется значение сз и пода- писывается в начале пятого такта, 2 ется на информационный вход регистра 30. На этом вычисления в устройстве заверВ регистры 18 и 19 вычислительного модуля шаются. Элементы нижней треугольной

3,2,2 записываются значения 122 и m32 и вы- матрицы L: 111, 121, 131 снимаются в начале

ЧИСЛяЮтСя ЭЛЕМЕНТЫ 1Зз =122 — С3П132, П1гзэ = 50 ПЕРВОГО таКта С ВЫХОДОВ ПЕрВОй ГруППЫ ВЫ=m32 с3122, значения которых соответст- ходов устройства 6,1.1, 6.2.1 и 6.3,1 соответвенно подаются на информационные входы ственно, элементы 122, 132 — в начале второго регистров 24 и 25 вычислительного модуля такта с выходов первой группы выходов ус3,2,2. В регистры 18 и 19 вычйслительного тройства 6.2.2 и 6.3,2, элемент 133 — в начале модуля 3,3.2 записываются значения злемен- 55 третьего такта с выхода первой группы устов пгг и г32 и вычисляются элементы пзз= тройства 6..3.3. Значения элементов глав=A22 — С2Гзг, Г33- Гзг - СЗП22, ЗНаЧЕНИЯ КОТОРЫХ НОй ДИаГОНаЛИ ДйаГОйбЛгЬНОй МатРИЦЫ D: соответственно подаются на информацион- d1dzd3 — снимаются в первом, второй и ные входы регистров 24 и 25 вычислитель- третьем тактах соответственно с выходов ного модуля 3,3.2. я

1755295 второй группы выходов устройства 7.1, 7,2 и

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

Поскольку каждый элемент очередного шага вычислений используется в каждом модуле и блоке только один раз, можно выполнять операции над потолком теплицевых симметричных матриц. Первый столбец (строку) следующей матрицы, а также очередной вектор для вычисления квадратичных форм в этом случае подаются в следующем такте после подачи предыдущих векторов. Для вычисления нескольких квадратичных форм для одйой матрицы необходимо ее первый столбец (сгроку) подавать на информационные входы 1 устройства требуемое число тактов одновременно с подачей на входы 8 устройства новых векторов Х, Процесс определения элементов III, mII, nII, rII, dI, b и detA представлен е виде "слоев" с целью распараллеливания вычислений до уровня нескольких типов операций: I— - cm или m — cl, n — cr или r — cn, d/(1-с ), b+ dU u (did ...сц-1)dI. Это позволяет строить структуру из существу:ощих интегральных схем ограниченной номенклатуры или в виде отдельных СБИС, Формула изобретения

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

1)/2 вычислительных модулей и блок формирования детерминантов, причем 1-й информационный вход второй группы устройства подключен к первому информационному входу (n+ -1,1)-го вычиСлительного модуля (1=1,...,n — 1), второй информационный вход которого подключен к (1+1)-му информационному входу второй группы устройства, первый выход g,К)-го вычислительного модуля (j=n,...,2n-3, К=1,...,2n-)-2) подключен к первому информационному входу Ц,К+1)-го вычислительного модуля, второй информационный вход которого подключен к второму выхо,iy ()+1,К)-го вычислительного мс дуля, втор зй выход (n,l)-го

50 причем каждый операционный модуль содержит два регистра и умножитель, первый информационный вход операционного модуля подключен к информационному входу первого регистрэ, синхровход и выход которого подключены соответственно к второму входу синхронизации операционного модуля и первому входу умножителя, второй вход и выход которого подключены соответственно к вгорому информационному входу операционногс модуля и информацивычислительного мод ля подключен к ïåðвому информационному входу (I+1)-ro операционного блока (l=1...,,n-1), выход которого подключен к второму информаци5 онному входу I-ro дополнительного операционного модуля, первый информационный вход второй группы устройства подключен к первому информационному входу первого операционного блока, выход которого под10 ключен к информационному входу второго буферного регистра, выход которого подключен к первому информационному входу первого дополнительного операционного модуля, выход блока деления под15 ключен к второму информационному входу первого операцион ного блока и информационному входу первого буферного регистра, выход которого подключен к первому информационному входу первого опера20 ционного модуля, первый информационный вход (m+1)-ro операционного модуля (m=1„„,п-2) подключен к выходу m-ro операционно о модуля, выход(п-1)-ro операционного модуля подключен к первому

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

35 информационному входу (m+1)-го дополнительного операционного модуля, объединенные третьи информационные входы (t,l)-ro вычислительного модуля (t=n...„2n—

1 — 1) подключены к второму выходу I-го вычис40 лительного блока, первый выход которого подключен к объединенным вторым входам

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

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

10 онному входу второго регистра, синхровход и выход которого подключены соответственно к первому синхровходу и выходу операционного модуля, каждый дополнительный операционный модуль содержит два регист- 5 ра и сумматор, первый информационный вход дополнительного операционного модуля подключен к информационному входу первого регистра, синхровход и выход которого подключены соответственно к перво- 10 му входу синхронизации дополнительного операционного модуля и первому входу сумматора, второй вход которого подключен к второму информационному входу дополнительного операционного модуля, 15 второй выход которого подключен к выходу сумматора и информационному входу второго регистра, синхровход и выход которого подключены соответственно к второму входу синхронизации и перво4у выходу допол- 20 нительного операционного модуля, каждый операционный блок содержит два умножителя и даэ регистра, первый информационный вход операционного блока подключен к объединенным входам первого умножите- 25 ля, выход которого подключен к информационному входу первого регистра, синхровход и выход которого подключены соответственно к второму входу синхронизации операционного блока и первому входу второго 30 умножителя, второй вход и выход которого подключены соответственно к второму информационному входу операционного блока и информационному входу второго регистра, синхровход и выход которого подключены соответственно к первому синхровходу и выходу операционного блока, блок формирования детерминантов содержит блок деления, сумматор, умножитель и три регистра, первый информационный вход блока формирования детерминантов подключен к входу делителя блока деления, выход которого подключен к информационному входу первого регистра, выход которого подключен к первому входу умножителя и первому выходу блока формирования детерминантов, второй информационный вход которого подключен к первому входу сумматора, выход которого подключен к ин-формационному входу второго регистра, выход которого подключен к второму входу умножителя„выход которого подключен к информационному входу третьего регистра, синхровход и выход которого подключены соответственно к первому синхровходу и второму выходу блока формирования детерминантов, второй синхровход которого подключен к объединенным синхровходам первого и второго регистров, вход задания единицы устройства подключен к объединенным входу делимого блока деления и второму входу сумматора, 1755295

1755295

Фиг 5

Составитель E. Мурзина

Техред М,Моргентал

Редактор Ю. Середа

Корректор В.Борисов

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

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

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

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