อ่าน 1 นาที
อัลกอริทึมบล็อกแลนซอส
ในวิทยาการคอมพิวเตอร์อัลกอริทึมบล็อกแลนซอส (Block Lanczos Algorithm)เป็นอัลกอริทึมสำหรับค้นหาช่องว่างว่าง...
อัลกอริทึมบล็อกแลนซอส
ในวิทยาการคอมพิวเตอร์อัลกอริทึมบล็อกแลนซอส (Block Lanczos Algorithm)เป็นอัลกอริทึมสำหรับค้นหาช่องว่างว่าง (nullspace)ของเมทริกซ์บนฟิลด์จำกัดโดยใช้เพียงการคูณเมทริกซ์นั้นกับเมทริกซ์ยาวและบาง (long, thin matrices) เมทริกซ์เหล่านี้ถือเป็นเวกเตอร์ของคู่ ของ สมาชิกในฟิลด์จำกัด ดังนั้นจึงมักถูกเรียกว่า 'เวกเตอร์' ในคำอธิบายของอัลกอริทึม
อัลกอริทึมบล็อกแลนซอสเป็นหนึ่งในวิธีการที่มีประสิทธิภาพที่สุดสำหรับการค้นหาช่องว่างว่าง ซึ่งเป็นขั้นตอนสุดท้ายใน อัลกอริทึม การแยกตัวประกอบจำนวนเต็มเช่นตะแกรงกำลังสองและตะแกรงสนามจำนวนและการพัฒนาของอัลกอริทึมนี้ได้รับแรงผลักดันอย่างเต็มที่จากแอปพลิเคชันนี้
โดยอิงตามและมีความคล้ายคลึงอย่างมากกับอัลกอริทึม Lanczosสำหรับการค้นหาค่าลักษณะเฉพาะของเมทริกซ์จริงแบบเบาบางขนาดใหญ่[ 1 ]
ปัญหาเกี่ยวกับการประมวลผลแบบขนาน
โดยพื้นฐานแล้วอัลกอริธึมนี้ไม่ใช่แบบขนาน: แน่นอนว่าสามารถกระจายการคูณเมทริกซ์กับ 'เวกเตอร์' ได้ แต่เวกเตอร์ทั้งหมดจะต้องพร้อมใช้งานสำหรับขั้นตอนการรวมกันในตอนท้ายของการวนซ้ำแต่ละครั้ง ดังนั้นเครื่องทั้งหมดที่เกี่ยวข้องกับการคำนวณจะต้องอยู่ในเครือข่ายความเร็วสูงเดียวกัน โดยเฉพาะอย่างยิ่ง ไม่สามารถขยายเวกเตอร์และกระจายส่วนย่อยของเวกเตอร์ไปยังเครื่องอิสระต่างๆ ได้
อัลกอริทึม Wiedemann แบบบล็อกมีประโยชน์มากกว่าในบริบทที่มีระบบหลายระบบ แต่ละระบบมีขนาดใหญ่พอที่จะรองรับเมทริกซ์ทั้งหมดได้ เนื่องจากในอัลกอริทึมนี้ ระบบต่างๆ สามารถทำงานได้อย่างอิสระจนถึงขั้นตอนสุดท้ายในตอนท้าย
สรุปเนื้อหา
ข้อมูลสำคัญจากบทความ
ข้อมูลสำคัญเกี่ยวกับ อัลกอริทึมบล็อกแลนซอส
ในวิทยาการคอมพิวเตอร์อัลกอริทึมบล็อกแลนซอส (Block Lanczos Algorithm)เป็นอัลกอริทึมสำหรับค้นหาช่องว่างว่าง...
ปัญหาเกี่ยวกับการประมวลผลแบบขนาน
โดยพื้นฐานแล้วอัลกอริธึมนี้ไม่ใช่แบบขนาน: แน่นอนว่าสามารถกระจายการคูณเมทริกซ์กับ 'เวกเตอร์' ได้ แต่เวกเตอร์ทั้งหมดจะต้องพร้อมใช้งานสำหรับขั้นตอนการรวมกันในตอนท้ายของการวนซ้ำแต่ละครั้ง...