Apa fungsi LAPACK yang sesuai di belakang Matlab [Q, R, E] = qr (A)?

12

Saat ini saya mencoba untuk murah menghitung perkiraan yang baik peringkat untuk matriks . Oleh karena itu saya menghitung penggunaan QR decompostion columnt pivotingA

[Q,R,E]=qr(A)

di Matlab. Saya memperkirakan peringkat menggunakanA

tol = size(A,n)*eps*norm(A,'fro'); 
r = sum(abs(diag(R))>tol)

Ini berfungsi dengan baik dan plot pada semua entri diagonal R terlihat seperti: plot (sort (abs (diag (R)), 1, 'descend'), 'r *')

Jika port keseluruhan algoritma ke C / Fortran saya ganti [Q, R, E] = qr (A) menggunakan DGEQP3 dari LAPACK, yang juga menghitung kolom yang memutar dekomposisi QR. Tetapi jika saya menggunakan estimasi yang sama untuk peringkat saya kebanyakan mendapatkan kesalahan. Sepertinya plot yang sama untuk dihasilkan dari DGEQP3 R

Matriks input sama persis untuk kedua percobaan.

Pertanyaan saya sekarang adalah fungsi LAPACK mana yang diandalkan kolom dekomposisi QR dari Matlab?

Terima kasih atas bantuannya, Grisu

Sunting: DGEQPF memberikan hasil yang salah sama.

Sunting2:

  • Matriks input padat dan dibangun sebagai E + s i g n ( E , F )AE+sign(E,F)
  • A
  • R
  • Saya menggunakan LAPACK 3.4.0 dengan OpenBlas / GotoBLAS (64 bit)
  • Matlab 7, 2007b, 2010b Linux 32bit

Sunting3: - Menggunakan GDB yang saya temukan, bahwa Matlab 2010b memanggil DGEQP3: # 3 0xaa46ce2f di dgeqp3_ () dari /usr/ubuntu10.04/matlabr2010b/bin/glnx86/../../bin/glnx86/../. ./bin/glnx86/mllapack.so Mengapa saya mendapatkan hasil yang salah dengan menggunakan LAPACK (3.4.0 termasuk perbaikan yang disebutkan dalam Catatan Kerja 176)?

MK alias Grisu
sumber
Bisakah Anda memprovokasi perilaku yang sama dengan matriks yang lebih kecil yang mungkin dapat Anda bagikan di sini?
GertVdE
A
A
Grisu - Saya akan senang melihat matriks Anda. Namun, tautan www-e.uni-magdeburg.de/makoehle/A.mtx.gz tidak lagi aktif (saat ini, bagaimanapun). Apakah Anda memiliki tautan saat ini ke matriks? Terima kasih, Les Foster
@LeslieFoster - selamat datang di scicomp!
Aron Ahmadia

Jawaban:

7

Ada dua masalah yang dihadapi di sini:

  • A
  • Apakah Anda memiliki tumpukan perangkat lunak yang sama dengan perpustakaan internal MATLAB?

Padat atau jarang?

ADGEQP3[Q,R,E] = qr(A)A

Apakah Anda memiliki tumpukan perangkat lunak yang sama dengan perpustakaan internal MATLAB?

Mungkin tidak, yang mungkin menjadi salah satu alasan Anda mendapatkan hasil yang berbeda.

Saya mengalami masalah ini ketika unit menguji perpustakaan saya sedang menulis yang menggunakan faktorisasi QR. Saya menggunakan MATLAB untuk membuat prototipe pekerjaan saya dan mendapatkan hasil yang berbeda daripada menggunakan LAPACK atau NumPy. Sejauh yang saya tahu, karena MathWorks tidak membuat informasi ini mudah ditemukan, MATLAB menggunakan versi LAPACK tidak lebih awal dari versi 3.1.1, dan perpustakaan Intel MKL BLAS (untuk Windows, Intel Mac, dan Linux) versi 9.1 atau lebih tinggi (lihat di sini ). Saya tidak dapat menemukan apa pun tentang versi penggunaan MATLAB SuiteSparse. Dengan menggali secara daring atau melihat file perpustakaan untuk sistem Anda, Anda mungkin dapat memperoleh informasi tambahan. Anda dapat mencoba mengubah pustaka yang MATLAB tautkan agar dapat membandingkan dengan pustaka yang sama di seluruh paket perangkat lunak; Eric Chu memberikan tulisan yang bagusyang menunjukkan setidaknya bagaimana Anda dapat mengganti perpustakaan BLAS MATLAB dengan Anda sendiri (tentu saja, Anda melakukan ini dengan risiko Anda sendiri). Dia menyarankan agar Anda dapat melakukan hal yang sama dengan LAPACK juga. Bahkan mungkin untuk mengganti versi SuiteSparse yang digunakan MATLAB dengan versi Anda sendiri.

A=QRQR

Saya akhirnya menggunakan NumPy untuk membuat prototipe hasil saya untuk faktorisasi QR, karena menggunakan sistem perpustakaan BLAS dan LAPACK. NumPy dan SciPy bukan pengganti MATLAB, karena kedua pustaka yang digabungkan kekurangan beberapa fungsi MATLAB, tetapi untuk tugas aljabar linier khusus ini, Python + NumPy + SciPy + Matplotlib harus bekerja dengan baik.

Geoff Oxberry
sumber
Memperoleh tumpukan perangkat lunak yang sama dengan Matlab tidak mungkin saya pikir. Menggunakan lingkungan lain untuk membuat prototipe juga tidak diinginkan. Masalahnya adalah kode bekerja di Matlab dengan benar, tetapi tidak dalam C.
MK alias Grisu
@ Grisu: Saya pikir akan sangat sulit untuk mendapatkan tumpukan perangkat lunak yang sama, sebelum mencoba menautkan di perpustakaan mereka. Yang saya bingung adalah bagaimana Anda tahu hasil di MATLAB benar dan hasil di C salah. Apakah ini semacam tes matriks yang memiliki sifat yang dikenal? Lebih penting lagi, AronAhmadia benar; selain mereplikasi arsitektur dan tumpukan perangkat lunak, Anda tidak dapat mengharapkan untuk mendapatkan hasil yang sama dengan algoritma yang tidak stabil. Saya pada dasarnya diberitahu hal yang sama di forum MATLAB dua tahun lalu.
Geoff Oxberry
Menurut pendapat saya, QR tidak stabil. Saya tidak bisa langsung memeriksa dekomposisi QR mana yang benar, tetapi dari pangkat dan matriks Q saya menghitung sebuah proyektor dan di sana saya dapat dengan mudah memverifikasi apakah mendapatkan hasil yang baik atau buruk dan yang dari Matlab baik. Tapi saya mencoba menghubungkan ke perpustakaan Matlab.
MK alias Grisu
@ Grisu: Ada perbedaan nyata antara hasil yang baik dan hasil yang benar. Baru-baru ini saya menerapkan perhitungan yang salah yang membuat hasil saya terlihat luar biasa. Namun demikian, perhitungannya salah, dan perhitungan yang benar membuat hasil saya terlihat kurang mengesankan (tapi untungnya, menggambarkan bahwa hasil saya benar). Apakah Anda mencoba menghitung proyektor ortogonal atau proyektor miring? (Saya bertanya karena bagian penting dari tesis saya adalah pada proyektor miring.)
Geoff Oxberry
1
@ GeoffOxberry: fwiw, pada versi MATLAB saya, saya bisa menelepon internal.matlab.language.versionPlugins.blasdan internal.matlab.language.versionPlugins.lapackmendapatkan versi BLAS dan LAPACK
Amro
6

Lihat halaman Leslie Foster tentang perangkat lunak yang mengungkapkan peringkat . Lihat juga Catatan Kerja LAPACKxGEQP3 ini yang menganalisis kegagalan QR pengungkapan peringkat .

Anda harus bisa mengetahui rutinitas apa yang digunakan MATLAB dengan mengatur breakpoints dalam debugger dan memeriksa stack. Terakhir saya melihat, diakui beberapa tahun yang lalu, MATLAB menggunakan shared library, dalam hal ini nama simbol tidak dapat dilucuti, sehingga Anda akan melihat nama-nama fungsi pada tumpukan panggilan (tetapi bukan argumen karena itu pasti tidak menyimpan informasi debug).

Jed Brown
sumber
Halaman tentang perangkat lunak yang mengungkapkan peringkat tidak membantu. Prosedur RRQR menggambarkan ada hal pertama yang saya gunakan dalam ide saya tetapi memberikan hasil yang lebih buruk daripada ide pivot kolom.
MK alias Grisu
2
@ Chrisu - Seharusnya membantu Anda. The xGEQP3algoritma tidak benar-benar aman untuk mengungkapkan peringkat. Jika Anda ingin menjamin bahwa Anda mendapatkan hasil yang benar, Anda harus menggunakan SVD atau QR yang lebih aman seperti xGEQPXatau xGEQPY. Anda tidak dapat mengharapkan algoritma yang tidak stabil untuk mengembalikan hasil yang sama pada arsitektur yang berbeda atau dalam implementasi yang berbeda (MATLAB mungkin menggunakan LAPACK yang lebih tua).
Aron Ahmadia
Saya tahu bahwa GEQP3 tidak mengungkapkan peringkat tetapi, ia memberikan hasil yang lebih benar daripada subrutin RRQR. Menggunakan SVD terlalu mahal dalam algoritma luar saya. Saya juga akan berbicara dengan salah satu penulis LAWN-176 dan dia pikir kesalahan ini tidak tercakup oleh bug. Saya juga mencoba DGEQPF / DGEQP3 dari LAPACK 3.0.0 dengan hasil yang sama.
MK alias Grisu