Apa alasan bahwa LAPACK menggunakan

QR rutin LAPACK menyimpan Q sebagai reflektor rumah tangga. Ini skala vektor refleksi dengan , jadi elemen pertama hasilnya menjadi , sehingga tidak harus disimpan. Dan itu menyimpan vektor terpisah , yang berisi faktor skala yang diperlukan. Jadi matriks reflektor adalah seperti ini:$v$$1/v_1$$1$$\tau$

di mana tidak dinormalisasi. Sementara, dalam buku teks, matriks reflektor adalah$v$

di mana dinormalisasi.$v$

Mengapa LAPACK berskala dengan , alih-alih menormalkannya?$v$$1/v_1$

Penyimpanan yang dibutuhkan sama (bukan , harus disimpan), dan setelah itu, menerapkan dapat dilakukan lebih cepat, karena tidak perlu mengalikan dengan (perkalian dengan dalam versi buku teks dapat dioptimalkan, jika alih-alih normalisasi sederhana, diskalakan oleh ).$\tau$$v_1$$H$$\tau$$2$$v$$\sqrt 2/\|v\|$

(Alasan pertanyaan saya adalah saya menulis rutin QR dan SVD, dan saya ingin tahu alasan keputusan ini, apakah saya perlu mengikutinya atau tidak)

Varian yang diblokir dari Householder-QR yang menggerakkan desain ini. Jika Anda melihat dalam buku Golub dan Van Loan (Bab 5.2 atau lebih), mereka berbicara tentang bagaimana k-iterasi dari algoritma dapat diblokir bersama-sama dengan mengumpulkan reflektor individu ke dalam reflektor peringkat-k dari bentuk , di mana keduanya dan adalah matriks "kurus tinggi" dengan ukuran . Algoritma ini bekerja lebih banyak tetapi lebih cepat dalam praktik karena kaya akan panggilan permata (). Sayangnya itu boros dalam penyimpanan karena kebutuhan untuk mewakili dan secara mandiri.$\mathbf I + \mathbf W \mathbf Y^{\mathrm T}$$\mathbf W$$\mathbf Y$$n \times k$$\mathbf W$$\mathbf Y$

Dalam makalah selanjutnya (dikutip di bawah), Van Loan menjelaskan struktur data "simetri" yang lebih efisien, sebuah reflektor blok dari formulir . Di sini masih , tetapi persyaratan gagal / penyimpanan untuk membentuk telah dieliminasi dengan memperkenalkan , sebuah matriks segitiga atas kecil atas . Meskipun kebutuhan untuk mengalikan dengan memperkenalkan sejumlah kecil pekerjaan tambahan, itu biasanya merupakan keuntungan bersih karena .$\mathbf I + \mathbf Y \mathbf T \mathbf Y^{\mathrm T}$$\mathbf Y$$n \times k$$\mathbf W$$\mathbf T$$k \times k$$\mathbf T$$k << n$

Di dalam LAPACK, algoritma yang tidak diblokir sebenarnya hanya kasus yang membatasi algoritma blok, sampai ke pilihan simbol (yang membawa kita ke , versi dari segitiga).$k \rightarrow 1$$\tau$$1\times1$$\mathbf T$

Kutipan: Schreiber, Robert, dan Charles Van Loan. "Representasi WY yang efisien-penyimpanan untuk produk-produk transformasi Householder." Jurnal SIAM tentang Komputasi Ilmiah dan Statistik 10.1 (1989): 53-57.

Anda tidak harus menyimpan , Anda dapat menghitung ulang dari sisa vektor. (Anda dapat menghitung ulang dari entri lain juga dalam versi yang dinormalkan, tetapi jelas merupakan perhitungan yang tidak stabil karena pengurangan tersebut.)$\tau$$v_1$

Sebenarnya, Anda dapat menggunakan kembali bagian segitiga-bawah untuk menyimpan , sehingga faktorisasi dikomputasi sepenuhnya di tempat. Lapack sangat peduli dengan versi algoritma ini.$R$$v_2,...v_n$

Saran saya didasarkan pada dokumentasi untuk Intel MKL https://software.intel.com/en-us/mkl-developer-reference-c-geqrf . Sepertinya nilai-nilai pada dan di atas diagonal dari toko keluaran R sehingga hanya ada segitiga bawah yang tersisa untuk Q. Tampaknya alami untuk menggunakan penyimpanan tambahan untuk faktor penskalaan.