เหตุใดจึงไม่คำนวณแรงทุกคู่โดยตรง?

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

ระเบียบวิธีต้นไม้และมัลติโพลควบคุมข้อผิดพลาดได้อย่างไร?

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

ระเบียบวิธี N-Body และ Particle-Mesh

การคำนวณแรงโน้มถ่วงหรือแรงไฟฟ้าสถิตระหว่างอนุภาคจำนวนมากโดยตรงนั้นมีค่าใช้จ่ายสูงเป็นกำลังสองของจำนวนอนุภาค แต่ระเบียบวิธี N-body และ particle-mesh ที่รวดเร็วสามารถลดค่าใช้จ่ายนี้ให้ใกล้เคียงเชิงเส้น ทำให้การจำลองกาแล็กซีและพลาสมาที่มีอนุภาคนับล้านเป็นไปได้

ค้นหาหัวข้อด้วย PaperMindเร็ว ๆ นี้Find papers & topics

Tools & resources

ดาวน์โหลดสไลด์

Learn & explore

วิดีโอเร็ว ๆ นี้

Definition

ระเบียบวิธี N-body และ particle-mesh เป็นอัลกอริทึมที่ประมาณแรงระยะไกลระหว่างอนุภาคที่โต้ตอบกันจำนวนมากในเวลาที่น้อยกว่ากำลังสอง โดยการจัดกลุ่มอนุภาคที่อยู่ห่างไกล หรือการแก้สนามบนกริด

Scope

หัวข้อนี้ครอบคลุมอัลกอริทึมที่ปรับขนาดได้สำหรับการโต้ตอบของอนุภาคระยะไกล: รหัสต้นไม้แบบลำดับชั้น เช่น Barnes-Hut, ระเบียบวิธีมัลติโพลแบบเร็ว (fast multipole method) และระเบียบวิธี particle-mesh และ particle-particle particle-mesh ที่ใช้กริด นอกจากนี้ยังกล่าวถึงการแลกเปลี่ยนระหว่างความแม่นยำกับต้นทุน และบทบาทของระเบียบวิธีเหล่านี้ในการจำลองแรงโน้มถ่วงและไฟฟ้าสถิตขนาดใหญ่

Core questions

เหตุใดการรวมแรงระยะไกลแบบคู่โดยตรงจึงมีค่าใช้จ่ายสูงเกินไป?
รหัสต้นไม้จัดกลุ่มอนุภาคที่อยู่ห่างไกลเพื่อลดต้นทุนการคำนวณแรงได้อย่างไร?
ระเบียบวิธีมัลติโพลแบบเร็วบรรลุการปรับขนาดใกล้เชิงเส้นพร้อมการควบคุมข้อผิดพลาดได้อย่างไร?
ระเบียบวิธี Particle-mesh แก้สนามบนกริดเพื่อจัดการกับแรงระยะไกลได้อย่างไร?

Key theories

รหัสต้นไม้แบบลำดับชั้น: อัลกอริทึม Barnes-Hut จัดกลุ่มอนุภาคที่อยู่ห่างไกลออกเป็นเซลล์ ซึ่งแรงรวมของพวกมันถูกประมาณโดยจุดศูนย์กลางมวลของพวกมัน ทำให้ลดต้นทุนการประเมินแรงจากกำลังสองเป็นอันดับ N log N
ระเบียบวิธีมัลติโพลแบบเร็ว: ระเบียบวิธีมัลติโพลแบบเร็วแสดงกลุ่มอนุภาคด้วยการขยายมัลติโพลที่ถูกตัดทอนและแปลพวกมันตามลำดับชั้น ทำให้ได้การปรับขนาดใกล้เชิงเส้นพร้อมความแม่นยำที่ควบคุมได้อย่างเคร่งครัด
ระเบียบวิธี Particle-mesh: ระเบียบวิธี Particle-mesh และ particle-particle particle-mesh จะประมาณค่าประจุหรือมวลลงบนกริด แก้สนามด้วยการแปลงฟูเรียร์แบบเร็ว และเพิ่มการแก้ไขระยะสั้น ซึ่งช่วยจัดการกับการโต้ตอบระยะไกลได้อย่างมีประสิทธิภาพ

Clinical relevance

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

History

ระเบียบวิธี Particle-mesh ได้รับการจัดระบบโดย Hockney และ Eastwood ในทศวรรษ 1980; รหัสต้นไม้ Barnes-Hut ในปี 1986 และระเบียบวิธีมัลติโพลแบบเร็วของ Greengard และ Rokhlin ในปี 1987 ได้เปลี่ยนแปลงการจำลอง N-body ทำให้สามารถจำลองจักรวาลวิทยาและโมเลกุลขนาดใหญ่ที่ตามมาได้

Key figures

Josh Barnes
Piet Hut
Leslie Greengard
Vladimir Rokhlin

Seminal works

barneshut1986
greengard1987

Frequently asked questions

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