По какой причине LAPACK использует

9

QR-код LAPACK хранит Q в качестве отражателей для домохозяев. Он масштабирует вектор отражения с , поэтому первый элемент результата становится , поэтому его не нужно сохранять. И он хранит отдельный вектор , который содержит необходимые масштабные коэффициенты. Таким образом, матрица отражателя выглядит так:v1/v11τ

ЧАСзнак равноя-τvvT,

где не нормируется. В то время как в учебниках матрица отражателейv

ЧАСзнак равноя-2vvT,

где нормализуется.v

Почему LAPACK масштабирует с вместо его нормализации?v1/v1

Необходимое хранилище остается тем же (вместо , должно быть сохранено), и после этого применение может быть выполнено быстрее, так как нет необходимости умножать на (умножение на в версии учебника можно оптимизировать, если вместо простой нормализации масштабируется как ).τv1ЧАСτ2v2/| |v| |

(Причина моего вопроса в том, что я пишу процедуру QR и SVD, и я хотел бы знать причину этого решения, нужно ли мне следовать этому или нет)

Геза
источник

Ответы:

7

Это заблокированный вариант Householder-QR, который управляет этим дизайном. Если вы посмотрите в книге Голуба и Ван Лоанна (гл. 5.2 или около того), они говорят о том, как k-итерации алгоритма могут быть заблокированы вместе путем накопления отдельных отражателей в отражатель ранга k вида , где и и являются "тощими" матрицами с размером . Этот алгоритм делает больше работы, но быстрее на практике, потому что он богат вызовами gemm (). К сожалению, это расточительно при хранении из-за необходимости представлять и независимо друг от друга.я+WYTWYN×КWY

В более поздней статье (цитируется ниже) Ван Лоан описывает более эффективную «симметризованную» структуру данных - блочный отражатель в виде . Здесь по-прежнему , но требование создания флопа / памяти для формирования было устранено введением , небольшой верхней треугольной матрицы. Хотя необходимость умножения на вносит небольшой объем дополнительной работы, обычно это чистый выигрыш, потому что .я+YTYTYN×КWTК×КTК<<N

В LAPACK неблокируемый алгоритм на самом деле является просто ограничивающим случаем блочного алгоритма, вплоть до выбора символов (что приводит нас к , небольшой версии треугольник).К1τ1×1T

Образец цитирования: Шрайбер, Роберт и Чарльз Ван Лоан. «Эффективное для хранения WY представление для продуктов преобразований Домохозяев». Журнал СИАМ по научным и статистическим вычислениям 10.1 (1989): 53-57.

rchilton1980
источник
Спасибо за ответ! Я не вижу, что находится всего в -sized . В цитируемой статье в Алгоритме 5 равно , а равно -2. Таким образом, он становится версией учебника, а не версией LAPACK. Я что-то пропустил? τ1×1TYvT
19
2

Вам не нужно хранить , вы можете пересчитать его из оставшейся части вектора. (Вы можете пересчитать из других записей также в нормализованной версии, но это явно нестабильное вычисление из-за этих вычитаний.)τv1

На самом деле, вы можете повторно использовать нижнюю треугольную часть для хранения , так что факторизация вычисляется полностью на месте. Лапак заботится об этих версиях алгоритмов на месте.рv2,,,,vN

Федерико Полони
источник
1

Мое предложение основано на документации для Intel MKL https://software.intel.com/en-us/mkl-developer-reference-c-geqrf . Это выглядит как значения на и выше диагонали выходного хранилища R, поэтому для Q остается только нижний треугольник. Кажется естественным использовать дополнительное хранилище для коэффициентов масштабирования.

VorKir
источник