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

1

2 ИСПОЛЬЗОВАНИЕ ЭКОНОМНЫХ МЕТОДОВ ВЫЧИСЛЕНИЯ ЧАСТИ СПЕКТРА БОЛЬШИХ РАЗРЕЖЕННЫХ МАТРИЦ В ЗАДАЧАХ ГАЗОВОЙ ДИНАМИКИ

3 План Обработка исходной матрицы. Реализация матрично-векторных операций с использованием разреженности и специального вида матриц. Построение проектора Q: Симметричный Вариант. Алгоритм Ланцоша. Несимметричный вариант. Алгоритм Арнольди. Вычисление собственных значений и собственных векторов редуцированной матрицы

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

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

6 Извлечение информации о матрице А из матрично-векторных операций

7 Проблемы С – еще вычислить нужно K – плохо обусловлена В K столбцы все более и более становятся параллельными K – плотная, даже если А – разреженная

8 Концепция Крыловского подпространства Q – ортогональная Q – хорошо обусловлена Q – легко обратима

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

10 Трехдиагонализация

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

12 Идеи

13 Концепция на пальцах

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

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

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

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

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