ระเบียบวิธีปริภูมิไครลอฟ

ระเบียบวิธีปริภูมิไครลอฟใช้ในการแก้ระบบสมการเชิงเส้นขนาดใหญ่แบบสปาร์ส โดยการสกัดค่าประมาณที่ดีที่สุดจากปริภูมิย่อยที่สร้างขึ้นจากการคูณเมทริกซ์กับเวกเตอร์ซ้ำๆ ซึ่งต้องการเพียงการกระทำของเมทริกซ์เท่านั้น ไม่ใช่ค่าในเมทริกซ์

Definition

ระเบียบวิธีปริภูมิไครลอฟเป็นตัวแก้ปัญหาแบบวนซ้ำที่ในขั้นตอนที่ m จะหาคำตอบโดยประมาณในปริภูมิไครลอฟมิติ m ซึ่งแผ่ขยายโดยเศษเหลือและภาพต่อเนื่องภายใต้เมทริกซ์ โดยเลือกค่าที่วนซ้ำโดยเงื่อนไขการฉายภาพหรือการทำให้มีค่าน้อยที่สุด

Scope

หัวข้อนี้ครอบคลุมปริภูมิไครลอฟและการสร้างโดยกระบวนการ Arnoldi และ Lanczos, ระเบียบวิธีเกรเดียนต์สังยุคสำหรับระบบสมมาตรบวกแน่นอน, MINRES และ GMRES สำหรับเมทริกซ์สมมาตรไม่แน่นอนและเมทริกซ์ทั่วไป, ระเบียบวิธีไบออร์โธโกนอลไลเซชัน เช่น BiCGSTAB, และทฤษฎีการลู่เข้าที่เชื่อมโยงจำนวนรอบการวนซ้ำกับสเปกตรัมและสภาพของเมทริกซ์

Core questions

• ปริภูมิไครลอฟคืออะไร และจะสร้างฐานเชิงตั้งฉากปรกติสำหรับปริภูมินี้ได้อย่างเสถียรได้อย่างไร?
• เหตุใดระเบียบวิธีเกรเดียนต์สังยุคจึงเหมาะสมที่สุดและมีการวนซ้ำสั้นๆ สำหรับระบบสมมาตรบวกแน่นอน?
• GMRES จัดการกับระบบไม่สมมาตรทั่วไปอย่างไร และเหตุใดจึงต้องใช้พื้นที่จัดเก็บเพิ่มขึ้น?
• คุณสมบัติสเปกตรัมของเมทริกซ์กำหนดอัตราการลู่เข้าได้อย่างไร?

Key theories

ระเบียบวิธีเกรเดียนต์สังยุค

สำหรับระบบสมมาตรบวกแน่นอน ระเบียบวิธีเกรเดียนต์สังยุคจะลดบรรทัดฐานพลังงานของข้อผิดพลาดในปริภูมิไครลอฟโดยใช้การวนซ้ำสามพจน์สั้นๆ ซึ่งลู่เข้าในจำนวนขั้นตอนไม่เกิน n ในการคำนวณที่แม่นยำ และเร็วกว่ามากเมื่อค่าลักษณะเฉพาะมีการรวมกลุ่ม

GMRES และกระบวนการ Arnoldi

สำหรับเมทริกซ์ทั่วไป GMRES ใช้กระบวนการ Arnoldi เพื่อสร้างฐานไครลอฟเชิงตั้งฉากปรกติและลดบรรทัดฐานของเศษเหลือในปริภูมิย่อย แต่เนื่องจากไม่มีการวนซ้ำสั้นๆ โดยทั่วไป จึงต้องจัดเก็บเวกเตอร์ฐานทั้งหมด ซึ่งเป็นแรงจูงใจให้เกิดรูปแบบที่เริ่มต้นใหม่

Mechanisms

แต่ละระเบียบวิธีจะคูณเวกเตอร์ด้วยเมทริกซ์ซ้ำๆ เพื่อขยายปริภูมิไครลอฟและทำให้ทิศทางใหม่ตั้งฉากกับทิศทางก่อนหน้า สำหรับเมทริกซ์สมมาตร กระบวนการ Lanczos จะให้การฉายภาพแบบไตรไดอะโกนอลและการวนซ้ำสั้นๆ ดังนั้นระเบียบวิธีเกรเดียนต์สังยุคและ MINRES จึงต้องการเพียงเวกเตอร์ไม่กี่ตัวในการจัดเก็บ สำหรับเมทริกซ์ไม่สมมาตร กระบวนการ Arnoldi จะสร้างการฉายภาพแบบ upper-Hessenberg ที่สมบูรณ์ และ GMRES จะลดค่าเศษเหลือให้เหลือน้อยที่สุดโดยการแก้ปัญหาค่าน้อยที่สุดกำลังสองขนาดเล็กในแต่ละขั้นตอน โดยมีค่าใช้จ่ายในการจัดเก็บฐานทั้งหมด การเริ่มต้นใหม่จะจำกัดค่าใช้จ่ายนี้ การลู่เข้าถูกกำหนดโดยการกระจายตัวของค่าลักษณะเฉพาะ ซึ่งการปรับสภาพ (preconditioning) ถูกออกแบบมาเพื่อปรับปรุง

Clinical relevance

ระเบียบวิธีไครลอฟ โดยเฉพาะอย่างยิ่งเกรเดียนต์สังยุคแบบปรับสภาพและ GMRES เป็นตัวแก้ปัญหามาตรฐานที่ใช้ในรหัสจำลองไฟไนต์เอลิเมนต์และไฟไนต์วอลุ่ม การหาค่าเหมาะสมที่สุดขนาดใหญ่ และการคำนวณทางวิทยาศาสตร์โดยทั่วไป ลักษณะที่ไม่ต้องใช้เมทริกซ์ทำให้สามารถแก้ปัญหาระบบที่มีตัวแปรที่ไม่ทราบค่าหลายล้านหรือหลายพันล้านตัว ซึ่งระเบียบวิธีโดยตรงไม่สามารถแยกตัวประกอบได้

History

ระเบียบวิธีเกรเดียนต์สังยุคถูกนำเสนอโดย Hestenes และ Stiefel ในปี 1952 และกระบวนการ Lanczos ที่เป็นพื้นฐานในปี 1950 พลังเต็มที่ของมันในฐานะตัวแก้ปัญหาแบบวนซ้ำได้รับการยอมรับในช่วงทศวรรษ 1970 และการพัฒนา GMRES โดย Saad และ Schultz ในปี 1986 และระเบียบวิธีไบออร์โธโกนอลแบบเสถียรได้ขยายแนวทางนี้ไปยังระบบไม่สมมาตรทั่วไป

Key figures

• Magnus Hestenes
• Eduard Stiefel
• Cornelius Lanczos
• Yousef Saad
• Henk van der Vorst

Seminal works

• saad2003
• greenbaum1997

Frequently asked questions

เหตุใดระเบียบวิธีเกรเดียนต์สังยุคจึงใช้ได้กับเมทริกซ์สมมาตรบวกแน่นอนเท่านั้น?

การวนซ้ำที่สั้นและมีประสิทธิภาพ และความเหมาะสมที่สุดในบรรทัดฐานพลังงานนั้นอาศัยการที่เมทริกซ์เป็นสมมาตรบวกแน่นอน สำหรับเมทริกซ์สมมาตรไม่แน่นอนหรือไม่สมมาตร จำเป็นต้องใช้วิธีการที่แตกต่างกัน เช่น MINRES หรือ GMRES ซึ่งโดยทั่วไปแล้วจะใช้พื้นที่จัดเก็บหรือการทำงานต่อขั้นตอนมากขึ้น

เหตุใด GMRES จึงต้องการหน่วยความจำมาก?

สำหรับเมทริกซ์ไม่สมมาตรทั่วไป ไม่มีการวนซ้ำสั้นๆ ที่ทำให้ฐานไครลอฟตั้งฉากปรกติ ดังนั้น GMRES จึงต้องจัดเก็บเวกเตอร์ฐานทุกตัวเพื่อลดเศษเหลือให้เหลือน้อยที่สุด GMRES แบบเริ่มต้นใหม่จะจำกัดหน่วยความจำโดยการทิ้งฐานเป็นระยะๆ โดยมีค่าใช้จ่ายในการลู่เข้าที่ช้าลง