Lanczos Algorithm

Следующий репозиторий содержит реализацию стандартного алгоритма Lanczos.

Установка

Чтобы разыграть с алгоритмом самостоятельно, git clone репозитория на местную машину. Затем в клонированном каталоге инициализируйте среду Conda, выполняя

 conda env create --file environment.yml

Оттуда вы можете активировать окружающую среду, как

 conda activate LanczosAlgo

и запустите ноутбук в src/lanczos.ipynb .

Введение

Алгоритм Lanczos является прямым алгоритмом, разработанным Корнелиусом Ланзосом, который является адаптацией методов власти, чтобы найти $ m $ «Наиболее полезные» (склонны к экстремальным самым низким/самым низким) собственные значения и собственные векторы $ n times n $ Гермитианская матрица, где $ m $ часто, но не обязательно намного меньше, чем $ n $ Полем

Алгоритм

Алгоритм продолжается следующим образом:

1. Учитывая германианскую матрицу $ A $ размера $ n times n $ и произвольный вектор $ V_1 $ С евклидовой нормой 1 укажите количество вызовов функций по умолчанию $ m = n $
2. Позволять $ W_1 '$ = $ Av_1 $
3. Позволять $ alpha_1 = w_1 '^* v_1 $
4. Позволять $ W_1 = W_1 '^*- alpha_1 V_1 $

Мы называем шаги 2 - 4 первыми шагами итерации. Впоследствии,

5. Позволять $ beta_j = || W_ {J-1} || $
6. Если $ beta_j neq0 $ , позволять $ v_j = frac {w_ {j-1}} { beta_j} $ Полем Иначе, пусть $ V_J $ быть произвольным вектором с евклидовой нормой 1, которая является ортогональным $ V_1, ..., V_ {J-1} $
7. Позволять $ W_J '= AV_J $
8. Позволять $ alpha_j = w_j'v_j $
9. Позволять $ w_j = w_j '- alpha_j v_j- beta_j v_ {j-1} $

где $ J $ обозначает номер итерации и должен удовлетворить $ 2 leq J leq M $ Полем Наконец, выход является тридиагонализованной матрицей $ T $ с $ alpha_1, ..., alpha_m $ вдоль основной диагонали и $ beta_2, ..., beta_m $ вдоль супер- и субдиагонали.

Будущая работа

В настоящее время продолжаются усилия по расширению алгоритма, чтобы включить системы рассеяния. Светь это репо, если вы хотите, чтобы вас уведомляли, когда это заходит вживую!