Разряженные матрицы. Р. Тьюарсон

И ЖУЮ ТУ~~ Р. Тьюарсон РАЗРЯЖЕН НИЕ МАТРИЦЫ МАТНЕМАТ!СВ !й 80!ЕНСЕ Ай0 ЕНО!НЕЕ!1!НЯ, У. 98 ЕС!ТЕ0 ВУ й[СНАй0 ВЕ!.!.МАй Сераг1пгвп1 о1 Арр!!ег! Ма1пегпа1гсе апг! 81а1!еИое 81аее Опгчегв!1у о1 йваг Уог!г 81опу Вгоогг, йеег Уог!с 8РАЯЗЕ моя~ сиз йвц!па! г! Р. Теугагеоп АСАСЕМ!С РйЕ88 йеег Уог!г апо !.оппоп 1918 Р. Тьюарсон РАЗРЕЗНЕННЫЕ МАТРИЦЫ Перевод с английского Э. М. ПЕЙСАХОВИЧА Под редакцией Х. Д. ИКРАМОВА 45~.66 Л ИЗДАТЕЛЬСТВО „МИРн МОСКВА 19Т7 УДК 312.83 Первая в мировой литературе книга, специально посвященная разреженным матрицам, — матрицам с большим числом нулевых элементов. В ией в доступвой форме излагается техиика примеиеиия разрежениых матриц в широких классах задач, использующих вычислительные методы линейной алгебры и математического программироваиия.

Учет разреженности матриц позволяет экоиомкть время решения иа влек. тронных вычислительиых машинах, увеличить размерность задач.' Книга будет полезна математикам-вычислителям, специалистам по прикладиой математике и исследова. иию операций, а также ииженерам различиых специальвостей. Редакция литература по математическим наукам 20203-028 Т 00 ~0 > 28-77 © Перевод иа русский язык, «Мир», 1077 ПРЕДИСЛОВИЕ РЕДАКТОРА ПЕРЕВОДА Разреженной называют матрицу, имеющую малый процент ненулевых элементов.

При этом относительно местоположения нулей никаких предположений не выдвигается: они могут быть расположены совершенно случайным образом. Журнальная литература последних пятнадцати лет, относящаяся к таким матрицам, насчитывает сотни названий, по этой проблематике состоялось по крайней мере два международных симпозиума.' И вместе с тем до последнего времени не было ни одной книги, специально посвященной разреженным матрицам.

Понятно поэтому, что выход в свет книги Р. Тьюарсона, в которой основное внимание уделяется вопросам реализации прямых методов для решения систем линейных уравнений очень высокого порядка с разреженными матрицами, †событ примечательное. Представляя эту книгу советскому читателю, хотелось бы вкратце обрисовать круг вопросов, в ней затрагиваемых, и ее место в нынешней литературе по вычислительной алгебре.

Хотя в численной алгебре за два минувших десятилетия был достигнут значительный прогресс, вопросы, связанные с разреженными матрицами, ускользнули от внимания большинства вычислителей-профессионалов. Наиболее интенсивные разработки велись в это время в других направлениях. С одной стороны, это были задачи для заполненных матриц средних размеров, которые можно целиком разместить в быстродействующей памяти вычислительной машины. С другой стороны, рассматривались и матрицы Предисловие редактора перевода высокого порядка с большим количеством нулей.

Однако для них выдвигалось условие (выполняющееся во многих приложениях) о закономерном характере расположения ненулевых элементов, которое может быть учтено программой метода заранее. Таковы ленточные матрицы, матрицы Хессенберга, матрицы со свойством А и т.

д. Вследствие сказанного, вопросами, связанными с разреженными матрицами произвольной структуры, занялись главным образом математики прикладных дисциплин, а также специалисты в некоторых других областях численного анализа, например, в области математического программирования, линейного н нелинейного. Так как многие задачи для разреженных матриц естественным образом формулируются на языке теории графов, то к исследованиям примкнули и специалисты в этой области. Книга Р. Тьюарсона фиксирует достигнутый уровень разработки проблемы. Можно отметить следующие особенности полученных до сих пор результатов.

Не делалось серьезных попыток создать принципиально новые алгебраические алгоритмы, рассчитанные именно на разреженные матрицы. Считалось, что вполне достаточно найти разум. ную модификацию существующих методов. Вопросам устойчивости не отводится столь первостепенная роль, как в численной алгебре «средних размеровь. Основ, ное внимание уделяется тому, чтобы при данных возможностях вычислительной машины решить задачу максимального порядка, быть может, за счет некоторой потери точности результатов.

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

При этом сохраняются нули, полученные ранее в предыдущих столбцах; Однако операции по получению нулей, вообще говоря, приводят к появлению новых ненулевых элементов в еще не приведенной части матрицы, ее заполнению. 24инимнзировать это заполнение — вот основная задача, рассматриваемая в книге. Возможность такой минимизации заложена в самой структуре прямых методов.

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

Эта, вообще говоря довольно значительная, предварвтельная работа вполне оправданна, если решается целый класс задач с одинаковым расположением ненулевых элементов. В книге имеется также глава, посвященная вычислению собственных значений и собственных векторов разреженных матриц. Читатель заметит, что эта глава, опирающаяся только на работы самого автора, носит менее систематический характер, чем предыдущее изложение, и в основном демонстрирует отдельные приемы, которые можно использовать для минимизации локального заполнения при приведении матрицы к форме Хессенберга.

В 'действительности Дафф и Рейд' ) в своей недавней работе на основании численных экспериментов делают вывод, что при преобразовании к хессенберговой форме разреженную матрицу целесообразно рассматривать как за') Опп 1. 5., йе!д Л. К. Оп 1Ье гедпс1!оп о1 врагве гпаписев !о сопдепвед 1оггп Ьу зпп!!агиу !гааз!ос!па!!оп, еЭ. 1пз!.

Ма!Ь. апд Арр! ип !975, !5, !Чо 2, 217 — 224. Предисловие редактора перевода полненную, если исключить случай сверхразреженности, Давая оценку книге в целом, нужно сказать, что она предоставляет читателю краткое и вместе с тем очень ясное изложение указанных выше вопросов, Можно надеяться на то, что она окажется полезной широкому кругу математиков-вычислителей, приклад.

ников и инженеров и вызовет еще больший интерес к этой важной области. Х. Икрамов ПРЕДИСЛОВИЕ Эта книга написана с целью представить в унифицированной и доступной форме обширный материал по исследованиям в области вычислений, связанных с разреженными матрицами, который разбросан по специальным журналам, До сих пор не было книги, в которой излагались бы результаты в этом направлении, в частности по прямым методам обращения больших разреженных матриц и вычислению их собственных значений и собственных векторов.

Разреженные матрицы встречаются при решении многих важных практических задач: структурного анализа, теории электрических сетей и энергосистем распределения энергии, численного решения дифференциальных уравнений, теории графов, а также генетики, социологии и поведенческих наук, программирования для ЭВМ. В связи с развитием современной техники можно ожидать, что и дальше большие разреженные матрицы будут встречаться во многих прикладных задачах, включающих большие системы", например, при планировании работы городской пожарной службы и службы скорой помощи, при моделировании системы сигнализации, управляющей движением транспорта, в распознавании образов и при планировании городов. Возникновение моего интереса к разреженным матрицам относится к 1962 †19 гг., когда я участвовал в разработке системы команд вычислительной машины для решения задач линейного программирования для крупного изготовителя электронных 1О Предисловие вычислительных машин.

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