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

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

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

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

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

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

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

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

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

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

Идеи

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

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

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

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

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

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