Lanczos Algorithm

ที่เก็บต่อไปนี้มีการใช้งานอัลกอริทึม Lanczos มาตรฐาน

การติดตั้ง

หากต้องการเล่นกับอัลกอริทึมด้วยตัวคุณเอง git clone ที่เก็บลงในเครื่องในท้องถิ่นของคุณ จากนั้นในไดเรกทอรีที่ถูกโคลนเริ่มต้นสภาพแวดล้อม conda โดยการวิ่ง

 conda env create --file environment.yml

จากนั้นคุณสามารถเปิดใช้งานสภาพแวดล้อมได้เช่นนั้น

 conda activate LanczosAlgo

และเรียกใช้สมุดบันทึกใน src/lanczos.ipynb

การแนะนำ

อัลกอริทึม Lanczos เป็นอัลกอริทึมโดยตรงที่คิดค้นโดย Cornelius Lanczos ซึ่งเป็นการปรับวิธีการใช้พลังงานเพื่อค้นหา $ m $ "มีประโยชน์มากที่สุด" (มีแนวโน้มที่จะสูงที่สุด/ต่ำสุด) ค่าลักษณะเฉพาะและ eigenvectors ของ AN $ n times n $ Hermitian Matrix ที่ไหน $ m $ บ่อยครั้ง แต่ไม่จำเป็นต้องเล็กไปกว่านี้มากนัก $ n $ -

อัลกอริทึม

อัลกอริทึมดำเนินการดังนี้:

1. ได้รับเมทริกซ์เฮอร์ติน $ a $ ขนาด $ n times n $ และเวกเตอร์โดยพลการ $ v_1 $ ด้วย Euclidean Norm 1 ให้ระบุจำนวนการเรียกใช้ฟังก์ชันเริ่มต้น $ m = n $
2. อนุญาต $ w_1 '$ = $ av_1 $
3. อนุญาต $ alpha_1 = w_1 '^* v_1 $
4. อนุญาต $ w_1 = w_1 '^*- alpha_1 v_1 $

เราอ้างถึงขั้นตอนที่ 2 - 4 เป็นขั้นตอนการทำซ้ำครั้งแรก ต่อมา

5. อนุญาต $ beta_j = || w_ {j-1} || $
6. ถ้า $ beta_j neq0 $ , อนุญาต $ v_j = frac {w_ {j-1}} { beta_j} $ - อื่นให้ $ v_j $ เป็นเวกเตอร์โดยพลการที่มีบรรทัดฐานแบบยุคลิด $ v_1, ... , v_ {j-1} $
7. อนุญาต $ w_j '= av_j $
8. อนุญาต $ alpha_j = w_j'v_j $
9. อนุญาต $ w_j = w_j '- alpha_j v_j- beta_j v_ {j-1} $

ที่ไหน $ j $ หมายถึงหมายเลขการวนซ้ำและต้องตอบสนอง $ 2 leq j leq m $ - ในที่สุดเอาต์พุตเป็นเมทริกซ์ tridiagonalized $ t $ กับ $ alpha_1, ... , alpha_m $ ตามแนวทแยงมุมหลักและ $ beta_2, ... , beta_m $ ตามแนว super- และ subdiagonals

งานในอนาคต

ขณะนี้ความพยายามกำลังดำเนินการต่อไปเพื่อขยายอัลกอริทึมเพื่อรวมระบบการกระเจิงของรัฐ แสดง repo นี้หากคุณต้องการได้รับการแจ้งเตือนเมื่อมีชีวิตอยู่!