วิธีการมัลติโพลแบบเร็ว ( FMM ) เป็น เทคนิค เชิงตัวเลขที่พัฒนาขึ้นเพื่อเร่งความเร็วในการคำนวณแรงระยะไกลในปัญหาn -body โดยทำได้โดยการขยายฟังก์ชันกรีนของ ระบบ โดยใช้การขยายมัลติโพลซึ่งช่วยให้สามารถจัดกลุ่มแหล่งกำเนิดที่อยู่ใกล้กันและถือว่าแหล่งกำเนิดเหล่านั้นเป็นแหล่งกำเนิดเดียว^{[ 1 ]}

FMM ยังถูกนำไปใช้ในการเร่งความเร็วตัวแก้ปัญหาแบบวนซ้ำในวิธีการของโมเมนต์ (MoM) ที่ใช้กับปัญหาแม่เหล็กไฟฟ้าเชิงคำนวณ^{[ 2 ]}และโดยเฉพาะอย่างยิ่งในชีวแม่เหล็กไฟฟ้าเชิงคำนวณ FMM ได้รับการแนะนำเป็นครั้งแรกในลักษณะนี้โดยLeslie GreengardและVladimir Rokhlin Jr. ^{[ 3 ]}และมีพื้นฐานมาจากการขยายมัลติโพลของสมการเวกเตอร์เฮล์มโฮลทซ์โดยการจัดการปฏิสัมพันธ์ระหว่างฟังก์ชันพื้นฐานที่อยู่ห่างไกลโดยใช้ FMM องค์ประกอบเมทริกซ์ที่สอดคล้องกันไม่จำเป็นต้องถูกจัดเก็บอย่างชัดเจน ส่งผลให้หน่วยความจำที่ต้องการลดลงอย่างมาก หาก FMM ถูกนำไปใช้ในลักษณะลำดับชั้น จะสามารถปรับปรุงความซับซ้อนของผลคูณเมทริกซ์-เวกเตอร์ในตัวแก้ปัญหาแบบวนซ้ำจากเป็นในเลขคณิตจำกัด กล่าวคือ เมื่อกำหนดค่าความคลาดเคลื่อนผลคูณเมทริกซ์-เวกเตอร์จะรับประกันว่าจะอยู่ภายในค่าความคลาดเคลื่อนความสัมพันธ์ของความซับซ้อนกับค่าความคลาดเคลื่อนคือกล่าวคือ ความซับซ้อนของ FMM คือสิ่งนี้ได้ขยายขอบเขตการประยุกต์ใช้ MOM ไปสู่ปัญหาที่ใหญ่กว่าที่เคยเป็นไปได้มาก่อน ${\displaystyle {\คณิตศาสตร์ {O}}(N^{2})}$${\displaystyle {\คณิตศาสตร์ {O}}(N)}$${\displaystyle \varepsilon }$${\displaystyle \varepsilon .}$${\displaystyle \varepsilon }$${\displaystyle {\mathcal {O}}(\log(1/\varepsilon ))}$${\displaystyle {\mathcal {O}}(N\log(1/\varepsilon ))}$

FMM ซึ่งแนะนำโดย Rokhlin Jr. และ Greengard ได้รับการกล่าวขานว่าเป็นหนึ่งในสิบอัลกอริทึม ที่ดีที่สุด ของศตวรรษที่ 20 ^{[ 4 ]}อัลกอริทึม FMM ช่วยลดความซับซ้อนของการคูณเมทริกซ์กับเวกเตอร์ที่เกี่ยวข้องกับเมทริกซ์หนาแน่นบางประเภท ซึ่งสามารถเกิดขึ้นได้จากระบบทางกายภาพหลายระบบ

FMM ยังถูกนำไปใช้เพื่อจัดการกับปฏิสัมพันธ์คูลอมบ์อย่างมีประสิทธิภาพในวิธีการ Hartree–Fockและ การคำนวณ ทฤษฎีฟังก์ชันความหนาแน่นในเคมีควอนตัม^{[ 5 ] [ 6 ]}

ในรูปแบบที่ง่ายที่สุด วิธีการมัลติโพลแบบเร็ว (fast multipole method) มุ่งที่จะประเมินฟังก์ชันต่อไปนี้: โดยที่เป็นเซตของโพล และเป็นน้ำหนักของโพลที่สอดคล้องกันบนเซตของจุดที่มีนี่คือรูปแบบหนึ่งมิติของปัญหา แต่สามารถขยายอัลกอริทึมนี้ไปยังหลายมิติและเคอร์เนลอื่นๆ นอกเหนือจาก ได้อย่างง่ายดาย $${\displaystyle f(y)=\sum _{\alpha =1}^{N}{\frac {\phi _{\alpha }}{y-x_{\alpha }}},}$$${\displaystyle x_{\alpha }\in [-1,1]}$${\displaystyle \phi _{\alpha }\in \mathbb {C} }$${\displaystyle \{y_{1},\ldots ,y_{M}\}}$${\displaystyle y_{\beta }\in [-1,1]}$${\displaystyle (yx)^{-1}}$

โดยทั่วไป การประเมินค่าบนจุดต่างๆ จำเป็นต้องใช้การดำเนินการ ข้อสังเกตที่สำคัญเบื้องหลังวิธีการมัลติโพลแบบเร็วคือ หากระยะห่างระหว่างและมีขนาดใหญ่พอ ค่าจะถูกประมาณได้ดีด้วยพหุนามโดยเฉพาะอย่างยิ่ง ให้เป็นจุดเชบิเชฟลำดับและให้เป็นพหุนามฐานลากรางจ์ ที่สอดคล้องกัน สามารถแสดงได้ว่าพหุนามการประมาณค่าลู่ เข้าอย่างรวดเร็วด้วยลำดับพหุนามโดยมีเงื่อนไขว่าขั้วอยู่ห่างจากบริเวณการประมาณค่ามากพอและนี่คือสิ่งที่เรียกว่า "การขยายแบบเฉพาะที่" ${\displaystyle f(y)}$${\displaystyle M}$${\displaystyle {\คณิตศาสตร์ {O}}(MN)}$${\displaystyle y}$${\displaystyle x}$${\displaystyle (y-x)^{-1}}$${\displaystyle -1<t_{1}<\ldots <t_{p}<1}$${\displaystyle p\geq 2,}$${\displaystyle u_{1}(y),\ldots ,u_{p}(y)}$$${\displaystyle {\frac {1}{y-x}}=\sum _{i=1}^{p}{\frac {1}{t_{i}-x}}u_{i}(y)+\epsilon _{p}(y)}$$${\displaystyle |\epsilon _{p(y)}|<5^{-p}}$${\displaystyle |x|\geq 3}$${\displaystyle |y|<1}$

ความเร็วที่เพิ่มขึ้นของวิธีการมัลติโพลแบบเร็วมาจากการประมาณค่าแบบสอดแทรกนี้: หากโพลทั้งหมดอยู่ "ไกลออกไป" เราจะประเมินผลรวมเฉพาะที่โหนดเชบิเชฟด้วยต้นทุนและจากนั้นจึงประมาณค่าแบบสอดแทรกไปยังจุดที่ต้องการทั้งหมดด้วยต้นทุน: ${\displaystyle {\mathcal {O}}(Np)}$${\displaystyle {\mathcal {O}}(Mp)}$$${\displaystyle \sum _{\alpha =1}^{N}{\frac {\phi _{\alpha }}{y_{\beta }-x_{\alpha }}}=\sum _{i=1}^{p}u_{i}(y_{\beta })\sum _{\alpha =1}^{N}{\frac {1}{t_{i}-x_{\alpha }}}\phi _{\alpha }.}$$

เนื่องจากโดยที่คือค่าความคลาดเคลื่อนเชิงตัวเลข ดังนั้นต้นทุนรวมคือ ${\displaystyle p=-\log _{5}\epsilon }$${\displaystyle \epsilon }$${\displaystyle {\mathcal {O}}{\big (}(M+N)\log(1/\epsilon ){\big )}}$

เพื่อให้แน่ใจว่าขั้วต่างๆ แยกออกจากกันอย่างดี เราจึงแบ่งช่วงหน่วยออกเป็นส่วนย่อยๆ ซ้ำๆ โดยให้มีเฉพาะขั้วอยู่ในแต่ละช่วงเท่านั้น จากนั้นจึงใช้สูตรที่กำหนดไว้อย่างชัดเจนภายในแต่ละช่วง และใช้การประมาณค่าในช่วงสำหรับทุกช่วงที่แยกออกจากกันอย่างดี วิธีนี้จะไม่ทำให้การปรับขนาดเสียไป เนื่องจากเราต้องการระดับอย่างมากที่สุดภายในค่าความคลาดเคลื่อนที่กำหนด ${\displaystyle {\mathcal {O}}(p)}$${\displaystyle \log(1/\epsilon )}$

• การจำลองแบบบาร์นส์-ฮัท
• การขยายแบบหลายขั้ว
• การจำลองn -body

• Yijun Liu: วิธีองค์ประกอบขอบเขตมัลติโพลแบบเร็ว: ทฤษฎีและการประยุกต์ใช้ในงานวิศวกรรม , สำนักพิมพ์มหาวิทยาลัยเคมบริดจ์, ISBN 978-0-521-11659-6 (2009)

• Gibson, Walton C. วิธีการของโมเมนต์ในแม่เหล็กไฟฟ้า (ฉบับที่ 3), Chapman & Hall/CRC, 2021. ISBN 9780367365066.
• บทคัดย่อจากบทความต้นฉบับของ Greengard และ Rokhlin
• หลักสูตรระยะสั้นเกี่ยวกับวิธีการมัลติโพลแบบรวดเร็วโดย ริค บีทสัน และ เลสลี กรีนการ์ด
• แอนิเมชั่น JAVA ของวิธีการมัลติโพลแบบเร็วแอนิเมชั่นที่สวยงามของวิธีการมัลติโพลแบบเร็วพร้อมการปรับเปลี่ยนต่างๆ

• Puma-EMคือโค้ดโอเพนซอร์สประสิทธิภาพสูงสำหรับการคำนวณทางแม่เหล็กไฟฟ้าด้วยวิธี Method of Moments / Multilevel Fast Multipole Method
• KIFMM3d ( Kernel-Independent Fast Multipole 3d Method) เป็นการนำ FMM มาใช้แบบใหม่ ซึ่งไม่จำเป็นต้องใช้การขยายมัลติโพลอย่างชัดเจนของเคอร์เนลพื้นฐาน และใช้การประเมินค่าเคอร์เนลเป็นพื้นฐาน
• PVFMMคือการนำ KIFMM มาใช้แบบขนานอย่างมีประสิทธิภาพเพื่อคำนวณศักยภาพจากแหล่งกำเนิดอนุภาคและปริมาตร
• FastBEMโปรแกรมองค์ประกอบขอบเขตแบบมัลติโพลที่รวดเร็วและฟรี สำหรับแก้ปัญหาศักยภาพ ความยืดหยุ่น การไหลของสโตกส์ และปัญหาเสียงใน 2 มิติ/3 มิติ
• FastFieldSolversดูแลการเผยแพร่เครื่องมือที่เรียกว่า FastHenry และ FastCap ซึ่งพัฒนาขึ้นที่ MIT สำหรับแก้สมการของแม็กซ์เวลล์และแยกค่าพาราไซต์ของวงจร (ค่าเหนี่ยวนำและค่าความจุ) โดยใช้ FMM
• ExaFMMคือโค้ด FMM 3 มิติที่รองรับทั้ง CPU และ GPU สำหรับเคอร์เนล Laplace/Helmholtz โดยเน้นที่ความสามารถในการขยายขนาดแบบขนาน
• ScalFMM ถูกเก็บถาวรเมื่อวันที่ 2 พฤษภาคม 2017 ที่Wayback Machine ScalFMM เป็นไลบรารีซอฟต์แวร์ C++ ที่พัฒนาขึ้นที่Inria Bordeaux โดยเน้นความสามารถในการใช้งานทั่วไปและการประมวลผลแบบขนาน (โดยใช้OpenMP / MPI )
• DASHMMเป็นไลบรารีซอฟต์แวร์ C++ ที่พัฒนาขึ้นที่มหาวิทยาลัยอินเดียนา โดยใช้ระบบรันไทม์ HPX-5 แบบมัลติทาสกิ้งแบบอะซิงโครนัส มันให้การทำงานแบบรวมศูนย์บนคอมพิวเตอร์ที่มีหน่วยความจำร่วมและแบบกระจาย และมีเคอร์เนลแบบ 3 มิติ Laplace, Yukawa และ Helmholtz
• RECFMM คือ FMM แบบปรับได้พร้อมการประมวลผลแบบขนานแบบไดนามิกบนมัลติคอร์
• FMM3Dคือไลบรารีสำหรับการคำนวณปฏิสัมพันธ์ระหว่างวัตถุ 3 มิติและ N วัตถุอย่างมีประสิทธิภาพบนเครื่องมัลติคอร์