Algoritma Lanczos

Algoritma Lanczos adalah algoritma iteratif adaptasi dari metode daya (power method) untuk menemukan  nilai dan vektor eigen yang "paling berguna" (umumnya yang tertinggi/terendah) dari sebuah matriks Hermite berukuran , dengan  tidak perlu jauh lebih kecil dari . Algoritma ini dirancang oleh Cornelius Lanczos pada tahun 1950. Meskipun secara prinsip metode ini efisien dalam aspek komputasi, metode yang dirancang pada awalnya tidak berguna karena sifatnya yang tidak stabil secara numerik.

Pada tahun 1970, Ojalvo dan Newman menunjukkan cara membuat metode ini stabil secara numerik, dan mengaplikasikannya untuk menemukan mode getaran dari sebuah struktur teknik berukuran besar. Hal ini dicapai dengan menggunakan sebuah teknik untuk 'memurnikan' vektor-vektor Lanczos (misal dengan mengortogonalkan secara berulang setiap vektor yang baru ditemukan dengan semua vektor yang sudah ditemukan) sampai ke suatu akurasi yang diinginkan. Jika teknik tidak diterapkan, metode akan menghasilkan vektor-vektor yang sangat 'terkontaminasi' oleh vektor-vektor yang berasosiasi dengan frekuensi alami yang rendah.

Dalam karyanya, Ojalvo dan Newman juga mengusulkan cara memilih vektor awal (starting vector; misalnya dengan menggunakan pembangkit bilangan acak), dan mengusulkan metode menentukan nilai  secara empiris (sebaiknya dipilih kurang lebih 1.5 kali dari banyak nilai eigen akurat yang diinginkan). Kontribusi lain diberikan oleh Paige, yang juga memberikan analisis galat untuk metode ini. Pada tahun 1988, Ojalvo memberikan sejarah yang lebih akurat dari algoritma ini, dan sebuah uji galat nilai eigen yang efisien.

 Algoritma 
Algoritma ini memerlukan sebuah matriks Hermite  berukuran , dan secara opsional sebuah bilangan  yang menyatakan banyak iterasi yang diinginkan. Jika nilai  tidak ditentukan, umumnya diambil . Sebenarnya, algoritma tidak memerlukan akses ke matriks secara eksplisit, melainkan sebuah fungsi  yang menghasilkan produk perkalian matriks dengan vektor. Fungsi ini dipanggil paling banyak  kali. Pada proses iterasi, algoritma rentan terhadap ketidakstabilan numerik. Ketika dieksekusi dalam aritmetika non-eksak (non-exact arithmetic), pertimbangan-pertimbangan tambahan harus diambil untuk memastikan validitas hasil (dijelaskan di bagian selanjutnya). Di akhir iterasi, algoritma akan menghasilkan sebuah matriks ortonormal  berukuran  dan sebuah matriks simetrik real tridiagonal  berukuran . Dalam kasus , maka  akan berupa matriks uniter, dan matriks .

Pada prinsipnya ada empat cara untuk menulis prosedur iterasi. Paige dan karya-karya lainnya menunjukkan bahwa urutan operasi berikut adalah yang paling stabil secara numerik.:

 Anggap  sebagai sebarang vektor dengan norma Euklidean 
 Langkah awal iterasi yang disingkat:
 Tetapkan .
 Tetapkan .
 Tetapkan 
 Untuk nilai , lakukan:
 Tetapkan  (juga sebuah norma Euklidean).
 Jika , tetapkan nilai  . Namun jika , pilih  sebagai sebarang vektor bernorma Euclidean  yang ortogonal dengan semua vektor .
 Tetapkan .
 Tetapkan .
 Tetapkan .
 Bentuk matriks  dengan menyusun  sebagai kolom-kolomnya; dan bentuk matriks

Catatan:  untuk .

Dalam praktiknya vektor awal  dapat dianggap sebagai argumen input tambahan dari prosedur; sedangkan  dan indikator-indikator galat numerik dapat diikutsertakan sebagai tambahan kondisi penghentian iterasi.

Tanpa menghitung perkalian matriks-vektor, setiap iterasi melakukan  operasi aritmetika. Perkalian matriks-vektor sendiri dapat dilakukan dalam  operasi aritmetika, dengan  menyatakan rata-rata jumlah elemen bukan nol dalam sebuah baris. Dengan demikian, algoritma Lanczos memiliki total kompleksitas sebesar , atau  dalam kasus ; hal ini membuatnya bisa sangat cepat untuk matriks rongga. Skema-skema untuk meningkatkan stabilitas numerik biasanya dibandingkan dengan kinerja tinggi ini.

Vektor  disebut dengan vektor Lanczos. Vektor  tidak digunakan setelah nilai  dihitung, dan vektor  tidak digunakan setelah  dihitung. Hal ini memungkinkan untuk menggunakan penyimpanan yang sama untuk ketiga vektor tersebut. Begitu juga jika kita hanya ingin mencari matriks tridiagonal , proses iterasi tidak memerlukan  setelah menghitung ; meskipun beberapa skema untuk meningkatkan stabilitas numerik akan membutuhkan vektor ini nantinya. Terkadang vektor-vektor Lanczos yang berikutnya dihitung ulang dari  jika diperlukan.

 Aplikasi untuk masalah eigen 
Algoritma Lanczos paling sering digunakan dalam konteks menemukan nilai eigen dan vektor eigen dari sebuah matriks. Namun berbeda dengan diagonalisasi matriks yang menghasilkan vektor-vektor eigen dan nilai-nilai eigen terlihat jelas dari pemeriksaan, tridiagonalisasi yang dilakukan algoritma Lanczos memerlukan langkah-langkah tambahan yang nontrivial bahkan untuk menghitung satu nilai atau vektor eigen. Meskipun demikian, menerapkan algoritma Lanczos sering kali merupakan langkah signifikan yang dalam menghitung dekomposisi eigen. Jika  adalah nilai eigen dari  dan  adalah vektor eigen dari  (sehingga ), maka  adalah vektor eigen yang bersesuaian dari ; karena Hal ini mengartikan algoritma Lanczos mengubah masalah dekomposisi eigen matriks  menjadi masalah dekomposisi eigen matriks .

Terdapat sejumlah algoritma khusus untuk memroses matriks tridiagonal, sering kali dengan kompleksitas komputasi yang lebih baik daripada algoritma yang umum. Misalkan  adalah matriks simetris tridiagonal berukuran . Beberapa algoritma tersebut diantaranya:

 Rekursi kontinu (continuant recursion) memungkinkan komputasi polinomial karakteristik dengan  operasi, dan mengevaluasinya pada sebuah titik dalam  operasi.
 Algoritma nilai eigen bagi-dan-taklukkan (divide-and-conquer) dapat digunakan untuk menghitung seluruh dekomposisi eigen dari  dalam  operasi.
 Metode Multipole Cepat (Fast Multipole method) yang dapat menghitung semua nilai eigen hanya dengan  operasi.

Beberapa algoritma dekomposisi eigen yang umum, terutama algoritma QR, diketahui konvergen lebih cepat pada kasus matriks tridiagonal daripada pada matriks yang umum. Kompleksitas asimtotik QR untuk matriks tridiagonal adalah , sama seperti untuk algoritma bagi-dan-taklukkan (meskipun faktor konstantanya mungkin berbeda). Mengingat semua vektor eigen memiliki   total elemen, algoritma ini optimal secara asimtotik. Bahkan untuk algoritma yang tingkat konvergensinya tidak terpengaruh oleh transformasi uniter (seperti metode daya dan iterasi invers), dapat menikmati manfaat kinerja ketika diterapkan ke matriks tridiagonal  daripada matriks asli . Karena struktur  yang sangat rongga dengan semua elemen bukan nol dalam posisi yang dapat diprediksi, hal ini memungkinkan penyimpanan yang ringkas dengan kinerja yang sangat baik jika dibandingkan dengan menggunakan tembolok (caching). Selain itu,  berupa matriks real dengan semua vektor eigen dan nilai eigen berupa real, sedangkan matriks  secara umum mungkin memiliki elemen kompleks dan vektor eigen; penggunaan aritmetika real cukup untuk mencari vektor eigen dan nilai eigen dari .

Jika  sangat besar, nilai  dapat dikurangi sehingga matriks   yang dihasilkan masih memiliki ukuran yang dapat dikelola. Pengurangan ini masih memungkinkan untuk menemukan nilai eigen dan vektor eigen yang ekstrem dari . Dalam keadaan , algoritma Lanczos dapat dianggap sebagai skema kompresi lossy untuk matriks Hermite, yang mengutamakan meyimpanan nilai-nilai eigen ekstrem.

Kombinasi kinerja yang baik untuk matriks rongga dan kemampuan untuk menghitung beberapa (tanpa menghitung semua) nilai eigen adalah alasan utama untuk memilih menggunakan algoritma Lanczos.

 Aplikasi 
Algoritma Lanczos sangat menarik karena perkalian dengan  adalah satu-satunya operasi linier berskala besar. Karena mesin pengambilan teks jangka berbobot hanya menerapkan operasi ini, algoritma Lanczos dapat diterapkan secara efisien ke dokumen teks (lihat Pengindeksan Semantik Laten). Vektor eigen juga penting untuk metode peringkat skala besar seperti Algoritma HITS yang dikembangkan oleh Jon Kleinberg, atau PageRank yang digunakan oleh Google.

Algoritma Lanczos juga digunakan dalam Fisika Materi Terkondensasi sebagai metode untuk menyelesaikan  Hamiltonians dari  sistem elektron berkorelasi kuat, serta dalam kode  model cangkang pada fisika nuklir.

 Implementasi 
 Perpustakaan NAG berisi beberapa rutinitas untuk solusi sistem linear skala besar dan masalah eigen yang menggunakan algoritma Lanczos.

MATLAB dan GNU Octave hadir dengan ARPACK bawaan. Baik matriks yang tersimpan dan implisit dapat dianalisis melalui fungsi  eigs()  (Matlab/Octave).

Implementasi Matlab dari algoritma Lanczos (masalah presisi catatan) tersedia sebagai bagian dari Gaussian Belief Propagation Matlab Package. The GraphLabGraphLab  perpustakaan pemfilteran kolaboratif menggabungkan implementasi paralel skala besar dari algoritma Lanczos (dalam C ++) untuk multicore.

PRIMME perpustakaan juga menerapkan algoritma seperti Lanczos.

 Referensi 

 Bacaan lebih lanjut 



Kategori:Algoritme
Kategori:Komputasi