Разряженные матрицы. Р. Тьюарсон (984138), страница 2
Текст из файла (страница 2)
Это привело к ряду публикаций в этой области. Весной 1968 г. я был приглашен в качестве лек-. тора на Симпозиум по разреженным матрицам и нх приложениям, организованный 1ВМ в йорк тауя Хейтс, Нью-у(орк, в сентябре того же года. Летом' 1969 г. последовало другое предложение — написать статью для Конференции по большим разреженным системам линейных уравнений в Оксфордском уни.
верситете (апрель 1970 г.). Летом 1969 г. по просьбе Б!АМ я написал обзорную статью о вычислениях с разреженными матрицами; она была опубликована в сентябрьском выпуске 1970 г. 5!АМ 1!еч(ехч. В том же самом году проф. Р. Беллман предложил мне написать книгу на эту тему. По счастливому совпадению тогда же проф. Л. Фокс пригласил меня вести семинар по разреженным матрицам в Оксфордском уни. верситете.
Из этих лекций и возникла эта книга. Книга предназначена для специалистов по численному анализу, математическому обеспечению, ис. следованию операций, в общем для всех, кому при-. ходится иметь дело с большими разреженными матрицами. Она доступна для студентов старших курсов; предполагается, что читатели знакомы с линейной алгеброй. Я старался избегать сжатого математического стиля изложения, иногда допуская некоторое многословие, а также стремился соблюдать нужный баланс между требованиями строгости изложения и потребностями приложений. Я полагаю, что именно прикладные задачи должны приводить к об общениям и абстракциям. Насколько это возможно, Предисловие придерживался алгоритмического и конструктив. ного подхода к рассматриваемым проблемам.
В книге описаны основные результаты и последние достижения в области прямых методов обраще„пя больших разреженных матриц, а также вычисления их собственных значений и собственных векторов. Я старался не включать в нее сведения, которые легко найти в хорошо известных книгах по численному анализу, за исключением тех, которые необходимы в качестве основы излагаемого в книге материала. Книга построена следующим образом. В гл. 1 описываются некоторые общеупотреби. тельные схемы хранения больших разреженных матриц н приводится метод масштабирования матриц, при котором ошибки округления при вычислениях остаются малыми. В гл.
2 обсуждается хорошо известный метод исключения Гаусса. Показывается, каким образом гауссово исключение может быть использовано для получения обратной для данной разреженной матрицы в факторизованной форме, которая называется элиминативной формой обратной матрицы (ЕР1) '), излагаются способы, позволяющие для заданной матрицы получать форму ЕР1 настолько разреженной, насколько это возможно. Описываются некоторые методы минимизации общего числа арифметических операций при вычислении ЕГЕ Рассматриваются также вопросы хранения и использования ЕР1 при практических расчетах. В гл.
3 даются некоторые методы получения приемлемой разреженности ЕР1. Эти методы не требуют таких затрат труда, как методы, изложенные в гл. 2. Рассматривается также преобразование заданной матрицы к одной из нескольких форм (например, к ленточной форме), подходящих для получения разреженной ЕР1. ') ег) бу нпнмннатпвной формы обратной матрицы — Е11го!па11ап Ропп о1 1птетее. — Прим, перев. Предисловие Методы Краута, Дулитла и Холецкого, тесно свя.
ванные с методом исключения Гаусса, излагаютсл в гл. 4. Для этих методов даются способы минимизации числа ненулевых элементов, создающихся на каждом шаге вычислений. Естественно, эти способы анало. гичны тем, которые приводятся в гл. 2 и 3 для таус . сова исключения, В гл. 5 исследуется хорошо известный метод ис. ключения Гаусса — Жордана и показывается, каким образом можно получить другую форму разложении на множители обратной матрицы, называющуюся мультипликативной формой обратной матрицы (РН)'), рассматривается связь между формами ЕГ! и РР1 и даются способы нахождения разреженной формы РН. Ортонормализация заданного множества разре.
женных векторов с помощью методов Грама— Шмидта, Хаусхолдера или Гивенса излагается в гл.б. Последние два метода используются также в гл. 7 для вычисления собственных значений и собственных векторов разреженных матриц. В другом методе гл. 7 для преобразования заданной матрицы используется способ, подобный гауссову исключению. В обеих главах описываются методы, способствующие сведению к минимуму общего числа новых ненулевых элементов (создаваемых в процессе вычислений). Наконец, в гл. 8 рассматриваются изменения в формах ЕР1 и РР1, вызванные изменением одного или более столбцов в заданной матрице.
Это имеет место во многих приложениях, например в линейном программировании. Приводится также еще одна форма разложения на множители обратной матрицы, подобная ЕН. После гл. 8 приводится обширная библиография по разреженным матрицам. ') РР1 — начальные буквы английского нааванва мультипли. кативной формы обратной матрицы — Ргобнс1 Рогпг о1 1нтегае.— Прим, перев, Предисловие 1з БЛАГОДАРНОСТЬ ~ хотел бы поблагодарить следуюших лиц: проф. д, Фокса за то, что он пригласил меня на год в Оксфордский университет, где я и написал ббльшую часть этой книги; проф.
Р. Беллмана, побудившего меня написать ее и поддержавшего меня своими советами; проф. Р. Джозефа и моих аспирантов— гг. Даффа, Ченя,и Чена за чтение рукописи и предложения об улучшении отдельных мест. Р. Тьюарсон Глава 1 ПРЕДВАРИТЕЛЬНЫЕ СВЕДЕНИЯ !.1. Введение В этой вводной главе мы вначале перечислим некоторые области приложения, использующие разреженные матрицы, затем опишем ряд широко распространенных схем хранения больших разреженных матриц в памяти электронной вычислительной машины — внутренней и внешней. Далее излагается также простой метод масштабирования матриц для обеспечения малости ошибок округления. Глава заканчивается библиографией и соответствующими комментариями. 1.2. Разреженные матрицы Матрица, имеющая небольшой процент ненулевых элементов, называется разреженной. Практически матрицу размеров акал можно считать разреженной, если количество ее ненулевых элементов имеет порядок и; скажем, от двух до десяти ненулевых элементов в каждой строке при больших а.
Разреженными являются матрицы широкого класса задач, относящихся к совокупности людей, связанных совместной работой. Например, матрица, отражающая связи между служащими крупного учреждения, будет разреженной, если предполагать, что элемент 1-й строки и 1ьго столбца матрицы отличен от нуля тогда и только тогда, когда 1-й и 1ьй служащие взаимодействуют друг с другом. Разреженные матрицы встречаются в задачах линейного программирования, структурного анализа, теории цепей и систем распределения энергии, при численном решении дифференциальных уравнений, в задачах теории графов, 16 Гл й Предварительные сведения генетики, социологии и поведенческих наук'), при системном программировании.
В настоящее время проявляется интерес к задачам социологии, бихевиоральных наук и экологии (в частности, к таким задачам, которые возникают для больших городских массивов) (см., например, Роджерс (1971)). Во многих случаях попытки фор. мулировки и решения таких задач приводят к си. стеме уравнений, матрица коэффициентов которой является разреженной и имеет большие размеры.
Если уравнения оказываются нелинейными, то в резуль. тате их линеаризации (которая часто является первым шагом к решению) получаются разреженные матрицы еще больших размеров. Интересные и важные задачи часто не могут быть решены потому, что их решение связано с обраще. пнем матриц больших размеров, которое либо неосуществимо при имеющемся объеме памяти ЭВМ, либо требует больших затрат. Так как такие матрицы, как правило, разрежены, то полезно знать суще. ствующие методы обработки разреженных матриц, что позволяет выбрать лучший метод длянзкаждой разреженной матрицы. Затрата времени и усилий на создание различных методов, пригодных для разре. женных матриц, особенно оправданны в тех случаях, когда рассматриваются несколько матриц с одинаковой структурой распределения нулей и с различными численными значениями ненулевых элементов.
Это имеет место во многих уже упомянутых областях приложения. 1,3. Упакованная форма хранения Большие разреженные матрицы обычно хранятся в ЭВМ в упакованном виде. Другими словами, хранятся только ненулевые элементы таких матриц вме- ') В США под поведенческими (бихевиоральными) науками (Ьейат!ога! зс!епсез) понимают науки, изучающие поведение (ЬеЬатюг) — реакции н действия человека и животных, выражающие их взаимоотношения с внешней средой. — Прим, перев. /.3. 'енанаеанная форма кранения 17 сте с необходимой информацией об их положении з матрице. Можно указать четыре причины непользования упакованной формы хранения. Во-первых, такая форма позволяет хранить и обрабатывать в оперативной памяти ЭВМ матрицы ббльших размерностей, чем при обычном хранении.
Во-вторых, могут встретиться случаи, когда даже в упакованном виде матрица не размещается в оперативной памяти (например, при работе ЭВМ в режиме с разделением времени) и требуется использовать внешнюю память (например, магнитные ленты нли диски). Ввод данных из внешней памяти ЭВМ в оперативную обычно происходит значительно медленнее обработки .этих данных в оперативной памяти. Поэтому упакованная форма хранения предпочтительнее также и при использовании внешней памяти. В-третьих, существенно экономится время благодаря тому, что программой предусматривается исключение тривиальных операций, т.
е. вычисления с нулевыми элементами матрицы опускаются. Это часто является единственной возможностью обработки больших матриц. В-четвертых, можно добиться экономии в памяти при хранении обратных матриц, если их представлять в виде произведения элементарных матриц и в упакованной форме хранить только нетривиальные элементы таких матриц. Такие мультипликативные формы обратной матрицы особенно предпочтительны в тех случаях, когда они многократно используются для умножения на ряд вектор-строк и столбцов, как, например, в линейном программировании.
Существует много различных схем упаковки, Некоторые из пих описаны ниже — они были признаны эффективными и внедрены в программы для ЭВМ. Пусть квадратная матрица А порядка и содержит т ненулевых элементов, причем т « пз. ясно, что матрица А является разреженной. Обозначим элемент 1-й строки и 1-го столбца матрицы через а;;. Лля того чтобы хранить в памяти только ненулевые элементы ац чь О, необходимо запомнить е', 1' н а;;. Если используется одна ячейка памяти для каждой нз этих величин, то для хранения всех ненулевых 18 Гл. Д Предварительные сведения элементов матрицы А требуется Зт ячеек.
Очевидно, Зт должно быть существенно меньше на, чтобы имело смысл тратить на введение упаковки дополнительные усилия и машинное время. Многие алгоритмы, преобразующие матрицу А в какую-либо другую желаемую форму, порождают на различных этапах вычислений дополнительные ненулевые элементы. Поэтому при хранении в упакованной форме должна быть каким-то образом предусмотрена возможность добавления новых ненулевых элементов в различные столбцы (или строки) матрицы А, если в процессе вычислений элементы матрицы изменяются. Идеальным хранением будет такое, при котором минимизируются одновременно и общий объем используемой памяти, и общее затраченное машинное время. Вообще говоря, требования минимума памяти н минимума времени являются несовместными и необходим компромисс.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
