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

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

2 Постановка задачи и план решения 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<

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

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

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

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

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

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

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

10 Идеи

11 Извлечение информации о матрице А из матрично-векторных операций 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 }

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

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

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

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

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

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

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

19

20

21

22

23

24

25

26

27

28

29

30

31

32

33 Литература Дж. Голуб, Ч. Ван Лоун «Матричные вычисления», 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