Документация Engee

Метод Голуба-Кахана-Ланцоша (SVDL)

Метод SVDL вычисляет частичное, приближенное SVD-разложение общего линейного оператора .

Использование

svdl(A) -> Σ, L, [history]

Вычисляет некоторые сингулярные значения (и при необходимости векторы), используя бидиагонализацию Голуба-Кахана-Ланцоша [1] с массовым перезапуском [2].

Если log имеет значение true, метод выведет кортеж X, L, ch. Где ch является объектом ConvergenceHistory. В противном случае будет возвращены только X, L.

Аргументы

  • A: матрица или матричный объект, сингулярные значения которого требуются.

Ключевые слова

  • nsv::Int = 6: количество запрашиваемых сингулярных значений;

  • v0 = random unit vector: вектор начальных предположений в области A. Длина q должна совпадать с количеством столбцов в A.

  • k::Int = 2nsv: максимальное количество векторов Ланцоша, которые нужно вычислить перед перезапуском;

  • j::Int = nsv: количество векторов, которые необходимо сохранить в конце перезапуска. Не рекомендуется использовать j < nsv.

  • maxiter::Int = minimum(size(A)): максимальное количество выполняемых итераций;

  • verbose::Bool = false: вывод информации при каждой итерации;

  • tol::Real = √eps(): максимальная абсолютная ошибка в каждом нужном сингулярном значении;

  • reltol::Real=√eps(): максимальная абсолютная ошибка в каждом нужном сингулярном значении относительно оцененной нормы входной матрицы;

  • method::Symbol=:ritz: используемый перезапускающий алгоритм. Вот возможные варианты.

    1. :ritz: массовый перезапуск со значениями Ритца [Wu2000].

    2. :harmonic: перезапуск с гармоническими значениями Ритца [Baglama2005].

  • vecs::Symbol = :none: возвращаемые сингулярные векторы.

    1. :both: возвращаются и левый, и правый сингулярные векторы.

    2. :left: возвращаются только левые сингулярные векторы.

    3. :right: возвращаются только правые сингулярные векторы.

    4. :none: сингулярные векторы не возвращаются.

  • dolock::Bool=false: если задано значение true, блокирует сходящиеся значения Ритца, удаляя их из подпространства Крылова, в котором будет выполняться поиск в следующей макроитерации;

  • log::Bool = false: вывод дополнительного элемента типа ConvergenceHistory, содержащего дополнительную информацию о выполнении метода.

Возвращаемые значения

если log имеет значение false

  • Σ: список требуемых сингулярных значений, если vecs == :none (по умолчанию), иначе возвращает объект SVD с заполненными требуемыми сингулярными векторами;

  • L: вычисленные частичные разложения A.

если log имеет значение true

  • Σ: список требуемых сингулярных значений, если vecs == :none (по умолчанию),

иначе возвращает объект SVD с заполненными требуемыми сингулярными векторами;

  • L: вычисленные частичные разложения A;

  • history: история сходимости.

Ключи ConvergenceHistory

  • :betas => betas: История вычисленных бета.

  • :Bs => Bs: История вычисленных проецируемых матриц.

  • :ritz => ritzvalhist: Значения Ритца, вычисленные в каждой итерации.

  • :conv => convhist: Данные сходимости.

Сведения о реализации

Реализация массивного перезапуска в точности повторяет реализацию SLEPc, описанную в [3]. Этот перезапуск можно отключить, установив значение k = maxiter, но чаще всего делать это нежелательно.

Сингулярные векторы вычисляются напрямую путем формирования векторов Ритца из произведения векторов Ланцоша L.P/L.Q и сингулярных векторов L.B. Дополнительную точность в сингулярных тройках можно получить с помощью обратной итерации.

1. Golub, Gene, and William Kahan. "Calculating the singular values and pseudo-inverse of a matrix." Journal of the Society for Industrial and Applied Mathematics, Series B: Numerical Analysis 2.2 (1965): 205-224.
2. Wu, Kesheng, and Horst Simon. "Thick-restart Lanczos method for large symmetric eigenvalue problems." SIAM Journal on Matrix Analysis and Applications 22.2 (2000): 602-616.
3. Висенте Эрнандес (Vicente Hernández), Хосе Э. Роман (José E. Román) и Андрес Томас (Andrés Tomás). A robust and efficient parallel SVD solver based on restarted Lanczos bidiagonalization. Electronic Transactions on Numerical Analysis 31 (2008): 68-85.