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

СОЮЗ СОВЕТСКИХ СОЦИАЛИСТИЧЕСКИ УБЛИ(5)5 О 06 Р 15/34 ПИСАНИЕ ИЗОБРЕТЕНИ ОСУДАРСТВЕННЫЙ КОМИТЕТПО ИЗОБРЕТЕНИЯМ И ОТКРЫТИЯПРИ ГКНТ СССР К АВТОРСКОМУ СВИДЕТЕЛЬСТ(56) Авторское свидетельство СССР М 1251104, кл, 6 06 Г 15/324, 1986.Авторское свидетельство СССР В 1401478, кл. 6 06 Е 15/347, 1988.(54) УСТРОЙСТВО ДЛЯ РАЗЛОЖЕНИЯ ТЕПЛИЦЕВЫХ СИММЕТРИЧНЫХ МАТРИЦ(57) Изобретение относится к.вычислительной технике и может быть использовано для разложения квадратной теплицевой симИзобретение относится к вычислительной технике и может быть. использовано автономно или в комплексе с ЦВМ для. разложения квадратной теплицевой симметричной матрицы на две треугольные и диагональную матрицы и при построении специализированных устройств, предназначенных для решения систем линейных уравнений.Цель изобретения - повышение быстродействия устройства при разложении теплицевых симметричных матриц.На фиг. 1 представлена структурная схема устройства; на фиг. 2 - функциональная схема (1, 1-го ( -1, Й, 1( = Г 1) вычислительного модуля; на фиг. 3 - функциональная схема 1-го вычислительного блока (Й - размерность входной матрицы),Устройство (фиг. 1) содержит группу информационных входов 1, блок 2 деления, вычислительные модули 3, вычислительные блоки 4, блок 5 синхронизации, первую 6 и метричной матрицы на две треугольные и диагональную матрицы и при построении специализированных устройств, предназначенных для решения систем линейных уравнений. Целью изобретения является повышение быстродействия. Цель достигается за счет реализации специального алгоритма разложения матриц на треугольные сомножители, учитывающие специфику (теплицевость и симметрию) раэлагаемых матриц. Устройство содержит Й (Й)/2 вычислительных модулей, блок деления, Йаычислительных блоков и блок синхронизации, где Й - размерность разлагаемой матрицы. 3 ил. вторую 7 группы выходов устройства, вычислительный модуль (фиг. 2) содержит первый 8 и второй 9 регистры, первый 10 и второй 11 умножители, первы 112 и второй 13 вычитатели, третий 14 и четвертый 15 регистры, первый 16 и второй 17 синхровходы.Вычислительный блок (фиг. 3) содержит первый узел 18 деления, умножитель 19, регистр 20, вычитатель 21, второй узел деления 22 и регистр 23.Блок 5 синхронизации представляет собой генератор импульсов, прямой и инверсный выходы которого подключены соответственно к синхровходам 16 и 17 всех вычислительных модулей и всех вычислительных блоков (не показано),Устройство для 1 01- разложения матриц предназначено для разложения данной ЙЙ симметричной теплицевой. матрицы А. т.е. матрицы, элементы аа которой удовлетворяют равенствама+1, +1- аа (1, 1( = 1, Й), 1689970а(Е) = а(ц) ( = 2, И, К = 1, 1-1) (4,5) на два треугольные (нижнюю . и верхнюю, где знак т обозначает транспонированную матрицу) и диагональнчю О такие. что А =0., Алгоритм формирования элементов а (1=1, й, 1=1) и элементов б соответствующих матриц 1 и 0 имеет вид. 3: 1/а ;к к кд= 1/( е - ек" - , к к ,к- где с, гп к - промежуточные перемекные,Устройство работает следующим образом.Для кратности описания без потери общности положим М = 3, Условимся, что прием информации во все регистры осуществляется по переднему фронту соответствующего синхроимпульса.Первый столбец (или строка) исходной теплицевой симметричной матрицы А подается на группу информационных входов 1 устройства по первому тактовому импульсу с блока 5,Первый такт, В первой половике такта параллельно вычисляются значения б 1 = 1/а 11 в блоке 2 деления и сг = аг 1/а 11 в вычислительном блоке 4,1 и поступают соответственно на первый информационный вход вычислительного блока 4,1 и объединенные третьи информационные входы вычислителькых модулей 3,1.1 и 3.2.1. Во второй половине. такта в регистры 8 и 9 вычислительного модуля 3.1.1 записываются значения.а 11 и аг 1, в регистры 8 и 9вычислительного модуля 3.2.1 - аг 1 и аз 1. Вычисляются значения элементов гг = а 11-сг дг 1; Ягг = аг 1" сг а 11 В Вычислительном модуле 3.1,1 и 1 эг = аг 1 - сг аз 1; п 1 зг = аз 1 - сг аг 1 В вычислительном модуле 3.2.1, значения которых подаются соответственно на информационные входы регистров 14 и 15 вычислительных модулей 3.1.1 и 3.2.1. На выходе умножителя 19 вычислительного блока 4.1 вычисляется значение сгг и подается на информационный вход регистра 20,Второй такт. В начале такта значения элементовгг, гпгг и зг, п 1 зг записываются соответственно в регистры 14 и 15 вычислительного модуля 3.1.1 и 3.2.1, сгг в регистр 20 вычислительного блока 4.1. В первой половине такта параллельно вычисляются бг = б 1/(1-сгг) в вычислительном блоке 4.1 и сз =30 35 взг/гг в вычислительном блоке 4,2 и поступают соответственно на информационный вход регистра 23 вычислительного блока 4.2 и третий информационный вход вычислительного модуля 3.2.2. Во второй половине такта значение бг принимается в регистр 23 вычислительного блока 41 и поступает на первый информационный вход вычислительного блока 4.2. На выходе умножителя 19 вычислительного блока 4.2 вычисляется значение сз и подается на информационгный вход регистра 20, В регистры 8 и 9 вычислительного модуля 3.2.2 записываются значения гг и гпзг и вычисляются элементы 1 зз= гг-сз гпзг, гпзз= пззг-сз гг, значениякоторых соответственно подаются на информационные входы регистров 14 и 15 вычислительногоо модуля 3.2.2.Третий такт. Значения элементов зз и взз записываются соответственно в регистры 14 и 15 вычислительного модуля 3.2.2, сз - в регистр 20 вычислительного блока 4.2. В первой половике такта вычисляется значение бз = бг/(1-сз). Значение элемента бз принимается в регистр 23 вычислительногоблока 4.2,На этом процесс01 " - разложения теплицевой симметричной матрицы А завершается, Элементы нижней треугольной матрицы .:111, г 1, 1 з 1 - снимаются в начале первого такта с выходов первой группы устройства 6.1.1, 6,2.1, 6.3.1 соответственно, элементы гг,зг - в начале второго такта с выходов первой группы устройства 6.2.2, 6.3.2, элемент зз - в начале третьего такта с выхода первой группы устройства 6.3.3.Значения элементов главной диагонали диагональной матрицы 0: б 1, бг, бз - снимаются в первом, втором и третьем тактах 40 соответственно с выходов второй группыустройства 7,1, 7.2, 7.3.Поскольку каждый элемент очередногошага вычислекий используется в каждом модуле и блоке только один раз, можно вы полнять01 - разложение потока матриц.Первый столбец (строку) следующей матрицы можно подавать в следующем такте посл е н а ч ал а и ода ч и стол бца (стро ки) предыдущей матрицы.50 Формула изобретенияУстройство для разложения теплицевыхсимметричных матриц, содержащее И(й)/2 вычислительных модулей, где М - размерность разлагаемой матрицы, и блок 55 синхронизации, прямой и инверсный выходы которого подключены соответственно к первому и второму синхровходам всех вычислительных модулей, причем первый информационный вход(1, 1)-го вычислительного модуля подключен к 1-му информацион1609970 5 10 30 40 50 ному входу первой группы устройства (1 -1, Й), первый выход (1, Ц-го вычислительного модуля 9 - 1, й; М" 1, ) подключен к первому информационному входу (+1, 1+1)-го вычислительного модуля, о т л ич а ю щ е е с я тем, что, с целью повышения быстродействия, в устройство введены блок деления и йвычислительных блоков, причем (1+1)-й информационный вход группы устройства подключен к второму информационному входу (1, 1)-го вычислительного модуля, и-й информационный вход группы устройства (и = 1, й) является (и, 1)-выходом первой группы устройства, (О, р)-й выход которой (О = 2, Й, р = 2, О). подключен к первому выходу(0-1, р)-го вычислительного модуля, первый информационный вход группы устройства подключен к входу делителя блока деления, вход делимого которого подключен к входу задания единицы устройства, выход блока деления подключен к первому выходу второй группы устройства и первому информационному входу первого вычислительного блока, первый выход )-го вычислительного блока подключен к первому информационному входу О+1)-го вычислительного блока, первый выход 1-го вычислительного блока является (1+1)-м выходом второй группы устройства, второй выход (д, Ь)-го вычислительного модуля подключен к второму информационному входу (у, 3+1)-,го вычислительного модуля (д = 2, й; Ь = 1, 9-1), второй и третий информационные входы 1-го вычислительного блока подключены соответственно к первому и второму информационным входам (1, 1)-го вычислительного модуля, второй выход 1-го вычислительного блока подключен к объединенным третьим информационным входам (п, 1)-го вычислительного модуля (п=1, 8-1), первый и второй синхровходы всех вычислительных блоков подключень соответственно к прямому и инверсному выходам блока синхронизации, причем каждый вычислительный модуль содержит четыре регистра, два умножителя и два вычитателя, первый и второй информационные входы вычислительного модуля подключены к информационным входам соответственно первого и второго регистров, выходы которых подключены к первым входам соответственно первого и второго умножителей и входам уменьшаемого соответственно первого и второго вычислителей, входы вычитаемого которых подключены к выходам соответственно второго и первого умножителей. объединенные вторые входы которых являются третьим информационным входом вычислительного модуля, первый и второй выходы которого подключены к выходам соответственно третьего и четвертого регистров, информационные входы которых подключены к выходам соответственно первого и второго вычитателей, объединенные синхровходы первого и . второго регистров подключены к второму синхровходу вычислительного модуля, первый синхроаход которого подключен к объединенным синхровходам третьего и четвертого регистров, каждый вычислительный блок содержит даа узла деления, умножитель, вычитатель и даа регистра, причем первый информационный вход вычислительного блока подключен к входу делимого второго узла деления, вход делителя которого подключен к выходу вычитателя, входы уменьшаемого и вычитаемого которого подключены соответственно к входу задания единицы устройства и к выходу первого регистра, информационный и синхровходы которого подключены соответственно к выходу умножителя и первому синхровходу вычислительного блока, второй синхроаход и первыйвыход которого подключены соответственно к синхровходу и выходу второго регистра, информационный вход которого подключен к выходу второго узла деления, второй и третий информационные входы вычислительного блока подключены соответственно к входам делителя и делимого первого узла деления, выход которого является вторым выходом вычислительного блока и подключен к объединенным входамумножителя, 1689970льский комбинат "Патент", г, Ужгород, ул.Гаг изводственно-из каз 3815 Тираж Подписное ВНИИПИ Государственного комитета по изобретениям и открытиям при ГКНТ СС 113035, Москва, Ж. Раушская наб., 4/5