Устройство для решения систем ли-нейных уравнений c разреженнойматрицей

Союз Советскни Соцналнстнческнк Реслублнк(22) Заявлено 20,1178 (21) 2685166/18-24с присоединением заявки Ио(51)М. кл. а 06 Г 15/324 Госуаарствеииый комитет СССР оо делам иэобретеиий и открытий(72) д ры изобретения Л.Я.Нагорный и П.А.ЛебедевКиевский ордена Трудового Красного Знамени( внстйтутинженеров гражданской авиации,(71) Заявитель(54) УСТРОЙСТВО ДЛЯ РЕШЕНИЯ СИСТЕМЛИНЕЙНЫХ УРАВНЕНИЙ С РАЗРЕЫЕННОЙИАтРицей Изобретение относится к цифровой вычислительной технике и можетбыть использовано при построенииспециализированных и клавишных вытчислительных машин, предназначенныхдля решения задач методами матричной алгебры.Известно устройство, содержащеесхемы набора элементов матриц, ариФметический блок, генератор импульссн,программный и коммутирующий блоки,блок управления, блок нывода и индикации, блоки установки размерности матрицы, определения знаков членов определителей равных нулю, элементы ИЛИ, И (1).Недостатки, этого устройства состоят в том, что процесс вычислениязаканчивается на стадии раскрытияи вычисления определителя, его функциональные возможности ограничены,а также в малом быстродействии вычисления и больших аппаратурных затратах,25Наиболее близким по техническойсущности и достигаемому результатук предлагаемому является устройство, содержащее первую, вторую итретью матрицы решающих блокон, арифметический блок, блок упранления,блок вывода и индикации, .два программных блока, блок постоянной памяти,блок оперативной памяти, блок сравнения, блок ввода коэффициентов,три элемента ИЛИ, а каждый решающийблок содержит дна элемента И, элемент НЕ, регистр и элемент ИЛИ,каждый программный блок содержит счетчик столбцов и счетчик строк 2.Недостатки такого устройствасложность и большие аппаратурныезатраты при решении системы линейных уравнений высокого порядка,Цель изобретения - упрощение устройства,Поставленная цель достигаетсятем, что устройстно для решения систем линейных уравнений с разреженной матрицей, содержащее матрицурешающих блоков, арифметическийблок, блок управления, блок вывода,программный блок, блок постояннойпамяти, блок оператинной памяти,блок сравнения, блок ввода коэффициентов, элемент ИЛИ, причем первый и второй разрешающие выходыблока управления соединены соответственно с первыми и вторыми входамирешающих блоков матрицы, выходы которых соединены через элемент ИЛИс пе рвым входом ариф мети чес ко го блока, первый выход которого подключен к третьим входам решающих блоковматрицы, арифметический блок соединен двухсторонними связями с блокомпостоянной памяти и с блоком управления, установочный выход которогосоединен с первым и вторым входамипрограммного блока, третий и четвертый входы которого соединены спервым выходом блока ввода коэффициентов, второй, третий и четвертыйвыходы которого подключены соответственно к первому входу блока опетивной памяти, входу запуска, блокауправления и второму входу. арифметического блока, выход блока оперативной памяти соединен с третьим входомарифметического блока, выход которогоподключен к первому входу блока вывода, первый и второй выходы программного блока соединены соответственно 20со вторым и третьим входами блока вывода и первым и вторым входами блока сравнения, выход которого подключен к сигнальному входу блока управления, выход записи которого соеди- з 5нен со вторым входом блока оперативной памяти, группа выходов программного блока соединена с управляющими входами решающих блоков матрицы, содержит счетчик синхронизации,причем первый выход счетчика синхронизации подключен к четвертому входуарифметического блока, а второй выход - к синхронизирующему входу блока управления.На чертеже представлена блок-схемаустройства.Устройство содержит матрицу 1 решающих блоков, арифметический блок 2,блок 3 управления, блок 4 вывода,программный блок 5, блок 6 постоянной памяти, блок 7 сравнения, блок 8ввода коэффициентов, элемент ИЛИ Э,блок10 оперативкой памяти, счетчик 11строк, счетчик 12 столбцов, решающийблок 13, элементы И 14, 15, элемент 45НЕ 16, регистр 17, элемент ИЛИ 18,счетчик 19 синхронизации,В устройстве реализуется методрешения систем линейных уравнений сразреженной матрицой по частям. Вобщем случае система уравнений представляется в кратной Форме:(1)где Н - неособенная матрица коэффициентов системы;Х - вектор столбца неизвестныхвеличин;0 - известный вектор правых частей.Используя операцию развертывания,исходную систему порядка и можно е 0привести к виду(2)65 где Х - квадратная подматрица связи;Н - блочно-диагональная матрицаисходной систеьн, содержащая ЕЕ подматриц, размерностью 3;6 Ф - прямоугольные подматрицыпосле операции развертывания, количество котопых равно И, размерностьюХ - вектор дополнительно введенных переменных;6 - порядок блочных матриц после разбиения системг,Такая система решается по частямсогласно ее разбиения на прямоугольные блоки,Согласно алгоритма определяетсяматричное произведение Вн -1В= Йе,. Н;Ф;, (3)где Н, - обратная матрица подматрицы Н;.Определяем ККС=ЕЕс,-в (4)Далее определяется вектор Яц =76; Н, (5)Находится йеизвестный вектор связи ХХс Кс 0 с (6)Далее определяются подвектоЕ:ы О;,выраженные через вектор связи Хс,которые необходимы для окончательного решения по частям системыуравненийО; =0;-фХ (7)Далее решейие сводится к определению неизвестных подвекторов ХХ,Х р ., Хн в виде матричного йроизведенияХ;=Н; О (8)Полученные подвекторы Х; состоят из неизвестных численных величинвидаХ= Х.е ХХя ф Х ХЪХ Х, Хг Устройство работает следующимобразом,Счетчик 19 синхронизации вырабатывает синхронизирующие импульсы,которые поступают в блок 3 управления и арифметический блок 2 и стробируют обрабатываемую информацию,Информация в регистрах арифметического блока 2 обрабатывается при помощи микрокоманд, синхронизированных во времени счетчиком 19 синхронизации и поступающих с блока 3 управления. Счетчик 19 синхронизациисинхронизирует информацию так, чторегистр 17 каждого решающего блока13 матрицы 1 условно разбит на трирегистра а б С по времени синхронизации, которое задает счетчик 19синхронизации, Таким образом, вопределенное время в одном регистре17 можно хранить три числа в условно обозначенных регистрах а, , с,15 40 30 И 60 Следовательно, одна матрица 1 условно разбивается на три матрицы Ма, МЬ, М по времени синхронизации определяемого счетчиком 19 синхронизацииРегистр 17 каждого решающего блока прЕдставляет собой сдвиговый регистр с обратной связью через элемент НЕ 16 и элемент ИЛИ 18, Один оборот регистра 17 равен времени счета счетчика синхронизации,С помощью блока 8 ввода коэффициентов набираются построчно коэффициент за коэфФициентом подматрицы Н, Прн наборе 1-ой строки счетчик 11 строк программного блока 5 устанавливается в 1-ое состояние,а при наборе первого коэффициента Й, счетчик 12 столбцов программного устройства 5 устанавливается в 1-ое состояние, по сигналам, поступающим с блока 8 ввода коэФфициентов. В этот момент счетчик строк 11 и счетчик столбцов 12 соответственно вырабатывают сигналы у и 2, поступающие на входы второго элемента И 15 решающего блока 13 матрицы 1, Таким образом произошел выбор реша- ющего блока С . В эту ячейку С матрицы Мр заносится преобразованный на арифметическом блоке 2 коэффициент: Й, При вводе коэффициента Ь запускается блок 3 управления, который работает по микропрограмме преобразования коэффициентов подматрицы Н по методу разложения матрицы на треугольные множители с записью этих коэффициентов в виде таблицы множителей в матрицу Мр, Коэффициентзаносится в арифметический блок 3, преобразуется и пересылается в ячейку Срешающего блока матрицы Мц через элемент И 15, на который поступает микрокоманда с блока 3 управления, Прн совпадении сигналов у , 2 и микрокоманды происходит запись элементачерез элемент И 15, элемент ИЛИ 18 в регистр 17 р, в котором Ь, хранится при помощи циклической перезаписи через элемент НЕ 1 Ь и элемент ИЛИ 18,Ввод последующих коэффициентов подматрицы Н осуществляется аналогично, при этом счетчик 11 строк и счетчик 12 столбцов вырабатывают соответствующие координатные сигналы у и 2 , которые выбирают соответствующйе решающие блоки С мат-, рицы 1, Блок 7 сравнения сравнивает содержимое счетчиков строк и столбцов, Если эти счетчики равны, идет обработка диагональных элементов подматрицы Н. Если содержимое счетчика 11 строк меньше содержимого счетчика 12 столбцов, то ведется обработка коэФФициентов выше главной диагонали подматрицы, Если содержимое счетчика 11 строк больше содержимого счетчика 12 столбцов, то об 10 20 2 35 45 рабатываются коэфФициенты, расположенные виже главной диагонали подматрицы, Результаты сравнения передаются в блок 3 управления, которыйвырабатывает определенные микрокоманды, необходиже для обработкикоэффициентов в арифметическом блоке2, Арифметический блок 2 выполняетоперации сложения вычитания, умножения, деления, накопления и алгебраического сложения, которые обеспечивают весь вычислительный процесс,Микропрограьва, выполняющие данныеоперации, служат, как микроподпрограммы для решения системы линейныхуравнений.после ввода всех коэффициентовподматрицы Н нажимается, например,клавиша Н, По этой команде запускается блок 3 управления, который работает по микропрограмме обращениягодматрицы Н в обратную подматрицуН. Цля обращения подматрицы используется метод пряьых решений с ис ользованием разложения матрицы на треугольные множители, Обращение матрицы Н заключается в том, что из полученной матрицы коэффициентов матрицы 1 Мр выбирается треугольная матрица, которая поэлементно пересылается в матрицу 1 М 6 через элементИЛИ 9 и ариФметический блок 2.далее производится матричнаяоперация умножения матрицы МЬ наматричные треугольные множителиматрицы Мо, Результирующая матрицанакапливается в матрице М, При умножении матриц коэффициенты вызываются в арифметический блок 2 черезэлемент ИЛИ 9 и происходит их умножение с алгебраическим накоплением.Обратная матрица Н накапливаечся в матрице 1 М, Далее на блоке 8 ввода коэффициентов нажимает"ся клавиша О, это означает, что вматРиЦУ 1 Мр ввоДЯтсЯ коэффиЦиентыподматрицы 6 . Нажимается клавишамножить и происходит операция матричного умножения 61, на Н .Матричное произведение 6 Н, хранитсяв матрице 1 Ма.Нажимается клавиша Я и осуществляется ввод Я - часть йзвестноговектора, которая соответствует части матрицы Н. Ввод Я поэлементноосуществляется в блок 10 оперативной памяти по микрокоманде с блока3 управления, После этого нажимаетйся клавишаУмножить и происходитматричное умножение матрицы мр наизвестный вектор 0. Получим произведение 61 Н01 йо выражению (1)в виде вектора размерностью 01Полученный вектор для накоплейиязасылается в блок 6 постоянной памяти, где будет накапливаться вектор 0 по выражению (5),по нажатию клавиши ф запускаетсяблок 3 управления и происходитзанесение коэффициентов подматрнцы Фв матрицу 1 М через арифметич ский блок 2 с блока 8 ввода коэффициенто, После чего нажимаетсяяклавиша множить и происходит операция матричного умножения матрицы Мр на матрицы М. В результате получается матричное произведение 6 Н ф, по выражению (3), которое хранится в матрице Мр.Подматрица связи Ис - единичная матрица и она находится в матрице Мс, Определяется Кс операцией матричного сложения по выражению (4) Кс, =Мс.-Мр=Ис Н 4. Результат величнйы Кс накаплйвается в матри-це Мс.Далее осуществляется ввод второй части исходной матрицы Н, т.е. осу-, ществляется последовательный ввод подматриц Н,6, 0 и 6 и про делываются все матричные операции с этими подматрицами тем же способом, Последовательность нажатий клавиш остается без изменения.После выполнения всех операций в блоке б постоянной памяти накалливается выражение 5 , а в матри-це М накапливается результат К выражени я (4) .Осуществляя ввод последукщих частей исходной матрицы Н по подматрицам Н;, 6, ; и 4;до последней части Н , 6 ц, Ощ и фи проделав матричные операции, получаем окончательный результат Яс и Кс по выражениям (5) и (4), которые накап-.ливаются соответственно в блоке б постоянной памяти и в матрице Мс.Для определения неизвестного вектора связи Хс по выражению б нажи- маетсЯ клавиша Хс, по кютоРой ПРоисходит обращение К в обратную матсрицу К по методу прямых решений с использованием разложения матрицы на треугольные множители. Обращение идет тем же способом, когда находилась обратная матрица Н . Далее происходит матричная операция умножения К=Мр Яс,Для этого поэлементно на арифметический блок 2 вызываются Яс из блока б постоянной памяти и Киз матрицы 1 Мр через элемент ИЛИ 9. Результат вектора Х накапливается в блоке б постоянной памяти.После получения вектора Х с.можно наДи неизвестный вектор Х по частям, Для этого нажимается клавиша Ф, по которой запускается блок 3 управления и происходит занесение коэффици-, ентов подматрицы Ф в матриц 1 М. По нажатию клавиши еумножить происНходит матричное умножение Ф 1 Х е выражения (7) на ариФметическом блоке 2 е вызовом поэлементно Ф и Хс из матрицы М и блока б постоянной памяти. Результат накапливается в блоке б постоянной памяти.сХ= Х Х, Х- Х, Х, Хз Х 4 35е 5 10 15 26 25 ЗО При нажатии клавиши Я осуществляется ввод Ц - части известного вектора в блок 10 оперативной памяти, После ввода происходит векторное вычитание по выражению (7) 0 =01 в Ф 1 Хс Вычитание происходит в арифметическом блоке с вызозом элементов вектора О из блока 10 оперативной памяти и вектора Ф Хс из блока б памяти. Результат засылается в блок б постоянной памяти.Осуществляется ввод подматрицы Н 1 в матрицу Мр. Находится обратная матрица Н , которая записывается в матрицу М . После этого нажимаетяся клавишамножить, по которой происходит матричная операция умножения матрицы 1 Мо на блок б постоянйой памяти, На арифметическом блоке 2 выполняется выражение (8) Х=Н., 0е 1 Результат вектора Х,Ха записывается в блок постоянной памяти. Численное значение найденного вектора Х передается в блок 4 вывода и индикации. Этот результат мэжет выпечатываться в устройстве вывода на бумажной ленте или высвечиваться на цифровом табло.Осуществляется ввод последующих частей матрицы Н по подматрицам Ф;, 01 и Н; до последней части Фн, Яи, Нн . Произведя все матричные операции и вычисления по выражениям (7) и (8) получим все численные значения вектора Х Полученные результаты решения исходной системы уравнения по частямпечатаются на бумажной ленте иливысвечиваются на цифровом табло. Эффективность использования предлагаемого устройства и метода решения системы линейных уравнений сразреженной матрицей проявляетсяв экономичном использовании аппаратуриых затрат. Уменьшается количество связей между блоками и количество самих блоков. Упрощается методика микропрограммирования при разработке устройства и само устройство, которое дает воэможность решить практически любую большую системулинейных уравнений с разреженнойматрицей в. малом аппаратурном объеме,Формула изобретения Устройство для решения систем линейных уравнений с разреженной матрицей, содержащее матрицу решающих блоков, арифметический блок, блок управления блок вывода, программныйблок, блок постоянной памяти, блокоперативной памяти, блок сравнения,блок ввода коэффициентов, элементИЛИ, причем первый и второй разрешающие выходы блока управления соединены соответственно с первыве н вторыми входами решающих блоков матрицы, выходы которых соединены черезэлемент ИЛИ с первым входом арифметического блока, первый выход которого подключен к третьим входамрешающих блоков матрицы, арифметический блок соединен двухсторон-ними связями с блоком постояннойпамяти н с блоком управления, установочный выход которого соединенс первым и вторым входами программного блока, третий и четэеРтый входы которого соединены с первым выходом блока ввода коэффициентов,второй, третий и четвертый выходыкоторого подключены соответственнок первому входу олока оперативнойнамяги, входу запуска блока управлания н второму входу арифметического блока, выход блока оперативнойпамяти соединен с третьим входомарифметического блока, выход которого подключен к первому входу бло.ка вывода, первый и второй выходыпрограммного блока соединены соответственно совторым и третьим входами блока вывода н первым н вторымвходами блока сравнения, выход которого подключен к сигнальному вхо -ду блока управления, выход записикоторого соединен со вторым входомблока оперативной памяти, группа выходов программного. блока соединенас управляющими входами решающих бло"ков матрицы, о т л и ч а ю щ е е с ятем, что, с целью упрощения устройства, оно содерзит счетчик синхронизации, причем первый выход счетчикасинхронизации подключен к четверто му входу арифметического блока, авторой выход - к синхронизирующемувходу блока управления,Источники информации,принятые во внимание при экспертизе20 1. Авторское свидетельство СССРМ 294144, кл. 6 Об Г 15/32, 1971.2, Авторское свидетельство СССРпо заявке 9 2531210/18-24,кл. О Об Р 15/32, 1977 (прототип)813444 Составитель Н. Палеевааедактор И.Касарда Техреду,ТабаковичКорректор Е.Рошко ак филиал ППППатент , г.Уигоро. Проектная 5/б 3 Тираж 745 ВИИИПИ Государстаенногпо делам изобретени 13035, Москва, З, Ра Подписноекомитета СССРи открытий,сная наб., д.4/5