Qual é o motivo pelo qual o LAPACK usa

9

A rotina QR do LAPACK armazena Q como refletores domésticos. Ele escala o vetor de reflexão com , para que o primeiro elemento do resultado se torne , para que não precise ser armazenado. E ele armazena um vetor separado , que contém os fatores de escala necessários. Portanto, uma matriz refletora é assim:v1/v11τ

H=IτvvT,

onde não é normalizado. Enquanto, nos livros didáticos, a matriz refletora év

H=I2vvT,

onde é normalizado.v

Por que o LAPACK dimensiona com , em vez de normalizá-lo?v1/v1

O armazenamento necessário é o mesmo (em vez de , precisa ser armazenado) e, em seguida, a aplicação de pode ser feita mais rapidamente, pois não há necessidade de multiplicar com (a multiplicação com na versão do livro pode ser otimizada, se, em vez da normalização simples, for dimensionado por ).τv1Hτ2v2/v

(O motivo da minha pergunta é que estou escrevendo uma rotina QR e SVD e gostaria de saber o motivo dessa decisão, se preciso segui-la ou não)

geza
fonte

Respostas:

7

É a variante bloqueada do Householder-QR que está impulsionando esse design. Se você olhar no livro de Golub e Van Loan (Cap 5.2), eles falam sobre como as iterações k do algoritmo podem ser bloqueadas acumulando os refletores individuais em um refletor rank k da forma , onde e são matrizes "magras" com tamanho . Esse algoritmo trabalha mais, mas é mais rápido na prática porque é rico em chamadas gemm (). Infelizmente, é um desperdício de armazenamento devido à necessidade de representar e independentemente.I+WYTWYn×kWY

Em um artigo posterior (citado abaixo), Van Loan descreve uma estrutura de dados "simétrica" ​​mais eficiente, um refletor de blocos no formato . Aqui ainda é , mas o requisito de fracasso / armazenamento para formar foi eliminado pela introdução de , uma pequena matriz triangular superior . Embora a necessidade de multiplicar por introduza uma pequena quantidade de trabalho extra, normalmente é um ganho líquido porque .I+YTYTYn×kWTk×kTk<<n

No LAPACK, o algoritmo não bloqueado é realmente apenas um caso do algoritmo de bloco, até a escolha dos símbolos (o que nos leva a , uma versão do Triângulo ).k1τ1×1T

Citação: Schreiber, Robert e Charles Van Loan. "Uma representação WY de armazenamento eficiente para produtos de transformações domésticas." Jornal SIAM sobre Computação Científica e Estatística 10.1 (1989): 53-57.

rchilton1980
fonte
Obrigado pela resposta! Eu não vejo, que é apenas a -sized . No artigo citado, no algoritmo 5, é e é -2. Então, acaba como a versão do livro, não como a versão do LAPACK. Perco alguma coisa? τ1×1TYvT
geza
2

Você não precisa armazenar , pode recalculá-lo do resto do vetor. (Você pode recalcular a das outras entradas também na versão normalizada, mas é claramente uma computação instável por causa dessas subtrações.)τv1

Na verdade, você pode reutilizar a parte triangular inferior de para armazenar , para que a fatoração seja computada totalmente no local. Lapack se importa muito com essas versões in-loco de algoritmos.Rv2,...vn

Federico Poloni
fonte