Пер. с англ. — М.: Мир, 1988. — 410 с., ил.
Isbn 5-03-000960-4.
книга американского специалиста, охватывающая практически все алгебраические задачи по разреженным матрицам. Представлено много фактического материала по технологии применения разреженных матриц, изложение последовательное и наглядное. Книга удачно дополняет имеющуюся на русском языке литературу по этой тематике.
Для математиков-вычислителей, инженеров, аспирантов и студентов вузов. Оглавление.
предисловие редактора перевода.
Предисловие.
Введение.
Основы.
Введение.
Хранение массивов, списков, стеков и очередей.
Хранение целых списков.
Представление и хранение графов.
Диагональная схема хранения ленточных матриц.
Профильная схема хранения симметричных матриц.
Связные схемы разреженного хранения.
Разреженный строчный формат.
Упорядоченные и неупорядоченные представления.
Сжатие по Шерману.
Хранение блочных матриц.
Символическая обработка и динамические схемы хранения.
Слияние разреженных целых списков.
Метод переменного переключателя.
Сложение разреженных векторов с использованием расширенного вещественного накопителя.
Сложение разреженных векторов с использованием расширенного целого массива указателей.
Скалярное умножение двух разреженных векторов с использованием массива указателей.
Линейные алгебраические уравнения.
Введение.
Некоторые определения и свойства.
Элементарные матрицы к треугольные матрицы.
Некоторые свойства элементарных матриц.
Некоторые свойства треугольных матриц.
Матрицы перестановок.
Гауссово исключение по столбцам.
Гауссово исключение по строкам.
Исключение Гаусса — Жордана.
Оглавление.
Связь между элиминативной формой обратной матрицы и факторизованной формой обратной матрицы.
Разложение Холецкого симметричной положительно определенной матрицы.
Практическая реализация разложения Холецкого.
Прямая и обратная подстановки.
О вычислительных затратах.
Численные примеры.
Вычислительные ошибки в гауссовом исключении.
Введение.
Ошибки округления в операциях с плавающей запятой.
Ошибки округления в разреженной факторизации.
Ошибки округления в разреженной обратной подстановке.
Управление ошибками округления.
Численная устойчивость и выбор главных элементов.
Контроль и оценка роста элементов.
Масштабирование.
Упорядочение для гауссова исключения: симметричные матрицы.
Введение: постановка задачи.
Основные понятия теории графов.
Поиск в ширину и структуры уровней смежности.
Отыскание псевдопериферийной вершины и узкой структуры уровней графа.
Уменьшение ширины ленты симметричной матрицы.
Уменьшение профиля симметричной матрицы.
Теоретико-графовые основы симметричного гауссова исключения.
Алгоритм минимальной степени.
Древовидное разбиение симметричной разреженной матрицы.
Вложенные сечения.
Свойства упорядочений по методу вложенных сечений.
Обобщенные вложенные сечения.
Параллельные сечения для конечноэлементных задач.
Упорядочения для метода конечных элементов.
Поиск в глубину на неориентированном графе.
Лексикографический поиск.
Симметричные незнакоопределенные матрицы.
Упорядочение для гауссова исключения; матрицы общего вида.
Введение: постановка задачи.
Теория графов для несимметричных матриц.
Сильные компоненты орграфа.
Поиск в глубину на орграфе.
Поиск в ширину на орграфе и структуры уровней ориентированной смежности.
Отыскание максимального множества путей с различными вершинами в ациклическом орграфе.
Отыскание трансверсали: алгоритм Холла.
Отыскание трансверсали: алгоритм Хопкрофта — Карпа.
Алгоритм Сарджента — Уэстерберга для отыскания сильных компонент орграфа.
Алгоритм Тарьяна для отыскания сильных компонент орграфа.
Стратегии выбора главных элементов для несимметричных матриц.
Другие методы и имеющееся программное обеспечение.
Разреженные задачи на собственные значения.
Введение.
Отношение Рэлея.
Границы для собственных значений.
Метод бисекции для вычисления собственных значений.
Приведение матриц общего вида.
Приведение симметричной ленточной матрицы к трехдиагональной форме.
Решение задач на собственные значения для трехдиагональных и хессенберговых матриц.
Прямые и обратные итерации.
Подпространства и инвариантные подпространства.
Одновременные итерации.
Алгоритм Ланцоша.
Практическое применение алгоритма Ланцоша.
Блочный и ленточный алгоритмы Ланцоша.
Метод минимизации следа.
Решение задач на собственные значения для эрмитовых матриц.
Задачи на собственные значения для несимметричных матриц.
Алгебра разреженных матриц.
Введение.
Транспонирование разреженной матрицы.
Алгоритм транспонирования разреженной матрицы общего вида.
Упорядочение разреженного представления.
Перестановка строк или столбцов разреженней матрицы: первая процедура.
Перестановка строк или столбцов разреженной матрицы: вторая процедура.
Упорядочение верхнего представления разреженной симметричной матрицы.
Сложение разреженных матриц.
Пример сложения двух разреженных матриц.
Алгоритм символического сложения двух разреженных матриц с размерами NxM : .
алгоритм численного сложения двух разреженных матриц с N строками.
Произведение разреженной матрицы общего вида и вектора-столбца.
Алгоритм умножения разреженной матрицы общего вида на заполненный вектор-столбец.
Произведение вектора-строки и разреженной матрицы общего вида.
Пример умножения заполненной строки на разреженную матрицу общего вида.
Алгоритм умножения заполненной строки на разреженную матрицу общего вида '.
Произведение симметричной разреженной матрицы и вектора-столбца.
Алгоритм умножения симметричной разреженной матрицы на заполненный вектор-столбец.
Умножение разреженных матриц.
Пример умножения двух матриц, хранимых по строкам.
Алгоритм символического умножения двух разреженных матриц, заданных в строчном формате.
Алгоритм численного умножения двух разреженных матриц, заданных в строчном формате.
Треугольное разложение разреженной симметричной матрицы, заданной в строчном формате.
Численное треугольное разложение разреженной симметричной матрицы, заданной в строчном формате.
Алгоритм символического треугольного разложении симметричной разреженной матрицы А.
алгоритм численного треугольного разложения симметричной положительно определенной разреженной матрицы А.
пример прямого хода и обратной подстановки.
Алгоритм решения системы Utdux= b.
Инцидентность и сборка по узлам.
Введение.
Граничные условия для скалярных задач.
Граничные условия для векторных задач.
Пример матрицы инцидентности.
Пример матрицы жесткости.
Алгоритм символической сборки симметричной матрицы жесткости.
Алгоритм численного включения элементной матрицы жесткости и элементного узлового вектора в глобальную матрицу жесткости А и вектор правых частей b Симметричный случай.
Алгоритм численного включения элементной матрицы жесткости и элементного узлового вектора в глобальную матрицу жесткости А и вектор правых частей Ь общий случай.
Алгоритмы общего назначения.
Введение.
Умножение обратной для нижней треугольной матрицы на матрицу общего вида.
Алгоритм символического умножения обратной для нижней треугольной матрицы Ut на матрицу В общего вида.
Алгоритм численного умножения обратной для нижней треугольной матрицы Ut на матрицу В общего вида.
Алгоритм умножения обратной для верхней треугольной матрицы U с единичной диагональю на заполненный вектор х.
Алгоритм умножения транспонированной и обращенной верхней треугольной матрицы U с единичной диагональю на заполненный вектор.
Решение линейной системы итерационным методом Гаусса —Зейделя.
Алгоритм итерационного решения линейной системы методом Гаусса — Зейделя.
Проверка представления разреженной матрицы.
Вывод разреженной матрицы на печать или экран.
Алгоритм преобразования представления симметричной матрицы из формы Rr (с) u в форму Rr (u) u.
алгоритм левого умножения разреженной матрицы А на диагональную матрицу D.
алгоритм копирования разреженной матрицы из Ia, j a, an в Ib, jb, bn.
Литература.
Добавление О программах решения разреженных линейных систем.
Литература.
Предметный указатель.
Isbn 5-03-000960-4.
книга американского специалиста, охватывающая практически все алгебраические задачи по разреженным матрицам. Представлено много фактического материала по технологии применения разреженных матриц, изложение последовательное и наглядное. Книга удачно дополняет имеющуюся на русском языке литературу по этой тематике.
Для математиков-вычислителей, инженеров, аспирантов и студентов вузов. Оглавление.
предисловие редактора перевода.
Предисловие.
Введение.
Основы.
Введение.
Хранение массивов, списков, стеков и очередей.
Хранение целых списков.
Представление и хранение графов.
Диагональная схема хранения ленточных матриц.
Профильная схема хранения симметричных матриц.
Связные схемы разреженного хранения.
Разреженный строчный формат.
Упорядоченные и неупорядоченные представления.
Сжатие по Шерману.
Хранение блочных матриц.
Символическая обработка и динамические схемы хранения.
Слияние разреженных целых списков.
Метод переменного переключателя.
Сложение разреженных векторов с использованием расширенного вещественного накопителя.
Сложение разреженных векторов с использованием расширенного целого массива указателей.
Скалярное умножение двух разреженных векторов с использованием массива указателей.
Линейные алгебраические уравнения.
Введение.
Некоторые определения и свойства.
Элементарные матрицы к треугольные матрицы.
Некоторые свойства элементарных матриц.
Некоторые свойства треугольных матриц.
Матрицы перестановок.
Гауссово исключение по столбцам.
Гауссово исключение по строкам.
Исключение Гаусса — Жордана.
Оглавление.
Связь между элиминативной формой обратной матрицы и факторизованной формой обратной матрицы.
Разложение Холецкого симметричной положительно определенной матрицы.
Практическая реализация разложения Холецкого.
Прямая и обратная подстановки.
О вычислительных затратах.
Численные примеры.
Вычислительные ошибки в гауссовом исключении.
Введение.
Ошибки округления в операциях с плавающей запятой.
Ошибки округления в разреженной факторизации.
Ошибки округления в разреженной обратной подстановке.
Управление ошибками округления.
Численная устойчивость и выбор главных элементов.
Контроль и оценка роста элементов.
Масштабирование.
Упорядочение для гауссова исключения: симметричные матрицы.
Введение: постановка задачи.
Основные понятия теории графов.
Поиск в ширину и структуры уровней смежности.
Отыскание псевдопериферийной вершины и узкой структуры уровней графа.
Уменьшение ширины ленты симметричной матрицы.
Уменьшение профиля симметричной матрицы.
Теоретико-графовые основы симметричного гауссова исключения.
Алгоритм минимальной степени.
Древовидное разбиение симметричной разреженной матрицы.
Вложенные сечения.
Свойства упорядочений по методу вложенных сечений.
Обобщенные вложенные сечения.
Параллельные сечения для конечноэлементных задач.
Упорядочения для метода конечных элементов.
Поиск в глубину на неориентированном графе.
Лексикографический поиск.
Симметричные незнакоопределенные матрицы.
Упорядочение для гауссова исключения; матрицы общего вида.
Введение: постановка задачи.
Теория графов для несимметричных матриц.
Сильные компоненты орграфа.
Поиск в глубину на орграфе.
Поиск в ширину на орграфе и структуры уровней ориентированной смежности.
Отыскание максимального множества путей с различными вершинами в ациклическом орграфе.
Отыскание трансверсали: алгоритм Холла.
Отыскание трансверсали: алгоритм Хопкрофта — Карпа.
Алгоритм Сарджента — Уэстерберга для отыскания сильных компонент орграфа.
Алгоритм Тарьяна для отыскания сильных компонент орграфа.
Стратегии выбора главных элементов для несимметричных матриц.
Другие методы и имеющееся программное обеспечение.
Разреженные задачи на собственные значения.
Введение.
Отношение Рэлея.
Границы для собственных значений.
Метод бисекции для вычисления собственных значений.
Приведение матриц общего вида.
Приведение симметричной ленточной матрицы к трехдиагональной форме.
Решение задач на собственные значения для трехдиагональных и хессенберговых матриц.
Прямые и обратные итерации.
Подпространства и инвариантные подпространства.
Одновременные итерации.
Алгоритм Ланцоша.
Практическое применение алгоритма Ланцоша.
Блочный и ленточный алгоритмы Ланцоша.
Метод минимизации следа.
Решение задач на собственные значения для эрмитовых матриц.
Задачи на собственные значения для несимметричных матриц.
Алгебра разреженных матриц.
Введение.
Транспонирование разреженной матрицы.
Алгоритм транспонирования разреженной матрицы общего вида.
Упорядочение разреженного представления.
Перестановка строк или столбцов разреженней матрицы: первая процедура.
Перестановка строк или столбцов разреженной матрицы: вторая процедура.
Упорядочение верхнего представления разреженной симметричной матрицы.
Сложение разреженных матриц.
Пример сложения двух разреженных матриц.
Алгоритм символического сложения двух разреженных матриц с размерами NxM : .
алгоритм численного сложения двух разреженных матриц с N строками.
Произведение разреженной матрицы общего вида и вектора-столбца.
Алгоритм умножения разреженной матрицы общего вида на заполненный вектор-столбец.
Произведение вектора-строки и разреженной матрицы общего вида.
Пример умножения заполненной строки на разреженную матрицу общего вида.
Алгоритм умножения заполненной строки на разреженную матрицу общего вида '.
Произведение симметричной разреженной матрицы и вектора-столбца.
Алгоритм умножения симметричной разреженной матрицы на заполненный вектор-столбец.
Умножение разреженных матриц.
Пример умножения двух матриц, хранимых по строкам.
Алгоритм символического умножения двух разреженных матриц, заданных в строчном формате.
Алгоритм численного умножения двух разреженных матриц, заданных в строчном формате.
Треугольное разложение разреженной симметричной матрицы, заданной в строчном формате.
Численное треугольное разложение разреженной симметричной матрицы, заданной в строчном формате.
Алгоритм символического треугольного разложении симметричной разреженной матрицы А.
алгоритм численного треугольного разложения симметричной положительно определенной разреженной матрицы А.
пример прямого хода и обратной подстановки.
Алгоритм решения системы Utdux= b.
Инцидентность и сборка по узлам.
Введение.
Граничные условия для скалярных задач.
Граничные условия для векторных задач.
Пример матрицы инцидентности.
Пример матрицы жесткости.
Алгоритм символической сборки симметричной матрицы жесткости.
Алгоритм численного включения элементной матрицы жесткости и элементного узлового вектора в глобальную матрицу жесткости А и вектор правых частей b Симметричный случай.
Алгоритм численного включения элементной матрицы жесткости и элементного узлового вектора в глобальную матрицу жесткости А и вектор правых частей Ь общий случай.
Алгоритмы общего назначения.
Введение.
Умножение обратной для нижней треугольной матрицы на матрицу общего вида.
Алгоритм символического умножения обратной для нижней треугольной матрицы Ut на матрицу В общего вида.
Алгоритм численного умножения обратной для нижней треугольной матрицы Ut на матрицу В общего вида.
Алгоритм умножения обратной для верхней треугольной матрицы U с единичной диагональю на заполненный вектор х.
Алгоритм умножения транспонированной и обращенной верхней треугольной матрицы U с единичной диагональю на заполненный вектор.
Решение линейной системы итерационным методом Гаусса —Зейделя.
Алгоритм итерационного решения линейной системы методом Гаусса — Зейделя.
Проверка представления разреженной матрицы.
Вывод разреженной матрицы на печать или экран.
Алгоритм преобразования представления симметричной матрицы из формы Rr (с) u в форму Rr (u) u.
алгоритм левого умножения разреженной матрицы А на диагональную матрицу D.
алгоритм копирования разреженной матрицы из Ia, j a, an в Ib, jb, bn.
Литература.
Добавление О программах решения разреженных линейных систем.
Литература.
Предметный указатель.