ИСПОЛЬЗОВАНИЕ ЭКОНОМНЫХ МЕТОДОВ ВЫЧИСЛЕНИЯ ЧАСТИ СПЕКТРА БОЛЬШИХ РАЗРЕЖЕННЫХ МАТРИЦ В ЗАДАЧАХ ГАЗОВОЙ ДИНАМИКИ Дипломная работа на тему Сабиров Г. Р. Группа 506 Москва 2006 г.

Постановка задачи и план решения Ax=λx, x0 Ax=λx, x0 Обработка исходной матрицы A. Реализация матрично-векторных операций с использованием разреженности и специального вида матриц. Обработка исходной матрицы A. Реализация матрично-векторных операций с использованием разреженности и специального вида матриц. Построение ортогонального проектора Q: Q T Q=Е Построение ортогонального проектора Q: Q T Q=Е Q T AQ=H ; A (nxn), Q(kxn) => H(kxk), k H(kxk), k<<n Несимметричный вариант. Алгоритм Арнольди. Несимметричный вариант. Алгоритм Арнольди. Симметричный Вариант. Алгоритм Ланцоша. Симметричный Вариант. Алгоритм Ланцоша. Вычисление собственных значений и собственных векторов редуцированной матрицы Н Вычисление собственных значений и собственных векторов редуцированной матрицы Н

Компактное хранение и обработка матриц – формула доступа к элементам Исходная матрица имеет размер NxN; M ненулевых элементов

Недостатки: Неочевидные формулы работы с матрицами в компактном виде. Неочевидные формулы работы с матрицами в компактном виде. Трудоемкий последовательный доступ к конкретному элементу матрицы. Трудоемкий последовательный доступ к конкретному элементу матрицы.Преимущества: Занимаемая память меньше во много раз. Занимаемая память меньше во много раз. Быстрое умножение матрицы на вектор: порядок операций не О(N*N), а О(M) Быстрое умножение матрицы на вектор: порядок операций не О(N*N), а О(M) Компактное хранение и обработка матриц – недостатки и преимущества

Концепция Крыловского подпространства K=span(b 1,Ab 1,A 2 b 1,…, A k b 1 ) (1.) (2.) (2.)(3.)

Понижающий размерность ортогональный проектор Q Q – ортогональная Q – хорошо обусловлена Q – легко обратима

Алгоритм Арнольди для (частичного) приведения к форме Хессенберга

Случай симметричной матрицы А

Алгоритм Ланцоша для (частичного) приведения к симметричной трехдиагональной форме

Идеи

Извлечение информации о матрице А из матрично-векторных операций A = f(x) A = f(x) A = LL T A = LL T A: {u 1,u 2,…,u k } A: {u 1,u 2,…,u k }

Построение проектора Q без использования самой матрицы А (i-й шаг)

Диагонализация

Неявный симметричный QR-шаг со сдвигом Уилкинсона

Симметричный QR-алгоритм Выполнить трехдиагонализацию по некоторому алгоритму. Получится матрица T. until q=n Для i=1:n-1 положить и равными нулю, если Найти наибольшее q и наименьшее p, такие, что если то диагональная, а неприводимая. if q < n Применить QR-шаг с каким-либо сдвигом к end Этот алгоритм требует примерно флопов.

Примеры спектров

Спектр оператора левой разности

Пример спектра

Литература Дж. Голуб, Ч. Ван Лоун «Матричные вычисления», 548 с. М.: Мир, 1999 Дж. Голуб, Ч. Ван Лоун «Матричные вычисления», 548 с. М.: Мир, 1999 Templates for the Solution of Algebraic Eigenvalue Problems: a Practical Guide - Edited by Zhaojun Bai, James Demmel, Jack Dongarra, Axel Ruhe, and Henk van der Vorst Templates for the Solution of Algebraic Eigenvalue Problems: a Practical Guide - Edited by Zhaojun Bai, James Demmel, Jack Dongarra, Axel Ruhe, and Henk van der Vorst Дж. Деммель «Вычислительная Линейная Алгебра теория и приложения», 430 с. М: Мир, 2001 Дж. Деммель «Вычислительная Линейная Алгебра теория и приложения», 430 с. М: Мир, 2001 Ф. Р. Гантмахер «Теория матриц», 559 с. М.: Физматлит, 2004 Ф. Р. Гантмахер «Теория матриц», 559 с. М.: Физматлит, 2004 Parallelizing the QR algorithm for the unsymmetric algebraic eigenvalue problem: myth and reality – Greg Henry and Robert van de Geijn pdf Parallelizing the QR algorithm for the unsymmetric algebraic eigenvalue problem: myth and reality – Greg Henry and Robert van de Geijn pdf pdf A test Matrix Collection for Non-Hermitian Eigenvalue Problems – Zhaojun Bai and David Day and James Demmel and Jack Dongarra (October 6, 1996) pdf A test Matrix Collection for Non-Hermitian Eigenvalue Problems – Zhaojun Bai and David Day and James Demmel and Jack Dongarra (October 6, 1996) pdf pdf On restarting the arnoldi method for large nonsymmetric eigenvalue problems – Ronald B. Morgan pdf On restarting the arnoldi method for large nonsymmetric eigenvalue problems – Ronald B. Morgan pdf pdf A parallel algorithm for the non-symmetric eigenvalue problem – Jack Dongarra Majed Sidani pdf A parallel algorithm for the non-symmetric eigenvalue problem – Jack Dongarra Majed Sidani pdf pdf Numerical Solvers for Complex Eigenvalue Problems Arising with Gyrotropiv Materials in Resonator Cavities – Stefan Feigh pdf Numerical Solvers for Complex Eigenvalue Problems Arising with Gyrotropiv Materials in Resonator Cavities – Stefan Feigh pdf