อัลกอริทึมการบีบอัดของ Lubachevsky-Stillinger (LS algorithm, LSA หรือ LS protocol) เป็นขั้นตอนเชิงตัวเลขที่เสนอโดยFH Stillingerและ Boris D. Lubachevsky ซึ่งจำลองหรือเลียนแบบกระบวนการทางกายภาพของการบีบอัดกลุ่มอนุภาคแข็ง^{[ 1 ]}เนื่องจาก LSA อาจต้องใช้การคำนวณทางคณิตศาสตร์หลายพันครั้งแม้จะมีอนุภาคเพียงไม่กี่อนุภาค จึงมักดำเนินการบนคอมพิวเตอร์

กระบวนการทางกายภาพของการบีบอัดมักเกี่ยวข้องกับการหดตัวของขอบเขตแข็งของภาชนะ เช่น ลูกสูบที่กดกับอนุภาค LSA สามารถจำลองสถานการณ์ดังกล่าวได้^{[ 2 ]}อย่างไรก็ตาม LSA ถูกนำมาใช้ครั้งแรกในการตั้งค่าที่ไม่มีขอบเขตแข็ง^{[ 1 ] [ 3 ]}โดยที่อนุภาคเสมือน "บวม" หรือขยายตัวในปริมาตรเสมือนคงที่ที่มีขอบเขตแบบคาบ ขนาดสัมบูรณ์ของอนุภาคเพิ่มขึ้น แต่ขนาดสัมพัทธ์ระหว่างอนุภาคยังคงที่ โดยทั่วไป LSA สามารถจัดการกับการบีบอัดภายนอกและการขยายตัวของอนุภาคภายใน ซึ่งเกิดขึ้นพร้อมกันและอาจรวมกับขอบเขตแข็งได้ แต่ไม่จำเป็นเสมอไป นอกจากนี้ ขอบเขตยังสามารถเคลื่อนที่ได้

ในสถานะสุดท้ายที่ถูกบีอัดหรือ "ติดขัด" อนุภาคบางส่วนไม่ได้ติดขัด พวกมันสามารถเคลื่อนที่ได้ภายใน "กรง" ที่เกิดจากอนุภาคข้างเคียงที่ติดขัดและเคลื่อนที่ไม่ได้ รวมถึงขอบเขตแข็ง (ถ้ามี) อนุภาคที่เคลื่อนที่ได้อย่างอิสระเหล่านี้ไม่ใช่สิ่งประดิษฐ์ หรือคุณลักษณะที่ออกแบบไว้ล่วงหน้า หรือเป้าหมายของ LSA แต่เป็นปรากฏการณ์จริง การจำลองเผยให้เห็นปรากฏการณ์นี้ ซึ่งค่อนข้างไม่คาดคิดสำหรับผู้เขียน LSA แฟรงค์ เอช. สติลลิงเกอร์ เป็นผู้บัญญัติศัพท์ "rattlers" สำหรับอนุภาคที่เคลื่อนที่ได้อย่างอิสระ เพราะหากเขย่ากลุ่มอนุภาคแข็งที่ถูกบีอัด อนุภาค rattlers จะส่งเสียงดัง

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

การใช้ LSA สำหรับอนุภาคทรงกลมที่มีขนาดต่างกันและ/หรือสำหรับการอัดแน่นในภาชนะที่มีขนาดวัดไม่ได้พิสูจน์แล้วว่าเป็นเทคนิคที่มีประโยชน์สำหรับการสร้างและศึกษาโครงสร้างจุลภาคที่เกิดขึ้นภายใต้เงื่อนไขของข้อบกพร่องทางผลึกศาสตร์^{[ 4 ]}หรือความขัดแย้งทางเรขาคณิต^{[ 5 ] [ 6 ]}ควรเพิ่มว่าโปรโตคอล LS ดั้งเดิมได้รับการออกแบบมาเพื่อทรงกลมที่มีขนาดเท่ากันหรือต่างกันเป็นหลัก^{[ 7 ]}

การเบี่ยงเบนใดๆ จากรูปทรงทรงกลม (หรือวงกลมในสองมิติ) แม้แต่แบบที่ง่ายที่สุด เมื่อทรงกลมถูกแทนที่ด้วยทรงรี (หรือวงรีในสองมิติ) ^{[ 8 ]}จะทำให้ LSA ที่ปรับเปลี่ยนดังกล่าวทำงานช้าลงอย่างมาก แต่ตราบใดที่รูปทรงยังเป็นทรงกลม LSA ก็สามารถจัดการกับกลุ่มอนุภาคได้ตั้งแต่หลายหมื่นถึงหลายแสนบนคอมพิวเตอร์ส่วนบุคคล มาตรฐานในปัจจุบัน (2011) มีเพียงประสบการณ์ที่จำกัดมากเท่านั้นที่ได้รับการรายงาน^{[ 9 ]} ในการใช้ LSA ในมิติที่สูงกว่า 3

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

LSA มีประสิทธิภาพในแง่ที่ว่าเหตุการณ์ต่างๆ จะถูกประมวลผลใน ลักษณะ ที่ขับเคลื่อนด้วยเหตุการณ์ เป็นหลัก มากกว่าที่จะขับเคลื่อนด้วยเวลา ซึ่งหมายความว่าแทบจะไม่มีการคำนวณใดๆ ที่สูญเปล่าไปกับการคำนวณหรือการรักษาตำแหน่งและความเร็วของอนุภาคระหว่างการชนกัน ในบรรดา อัลกอริธึม ที่ขับเคลื่อนด้วยเหตุการณ์ซึ่งมีจุดประสงค์เพื่อจำลองการไหลของอนุภาค แบบเดียวกัน เช่น อัลกอริธึมของ DC Rapaport ^{[ 10 ]} LSA โดดเด่นด้วยโครงสร้างข้อมูลและการจัดการข้อมูล ที่ง่ายกว่า

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

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

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

ความล้มเหลวแบบติดค้างในเวลาอาจเกิดขึ้นได้เมื่อจำลองการไหลของอนุภาคโดยไม่มีการบีบอัดหรือการขยายตัวของอนุภาค โหมดความล้มเหลวนี้ได้รับการยอมรับจากผู้ปฏิบัติงานด้านการจำลองการไหลของอนุภาคว่าเป็น "การยุบตัวแบบไม่ยืดหยุ่น" ^{[ 11 ]}เนื่องจากมักเกิดขึ้นในการจำลองดังกล่าวเมื่อค่าสัมประสิทธิ์การคืนตัวในการชนต่ำ (เช่น ไม่ยืดหยุ่น) ความล้มเหลวนี้ไม่ได้จำเพาะเจาะจงเฉพาะอัลกอริทึม LSA เท่านั้น มีการเสนอเทคนิคเพื่อหลีกเลี่ยงความล้มเหลว^{[ 12 ]}

LSA เป็นผลพลอยได้จากความพยายามที่จะหาวิธีการเร่งความเร็ว ที่ยุติธรรม ในการจำลองแบบขนาน อัลกอริทึมการจำลองแบบขนาน Time Warpโดย David Jefferson ได้รับการพัฒนาขึ้นเพื่อจำลองปฏิสัมพันธ์เชิงพื้นที่แบบอะซิงโครนัสของหน่วยรบในแบบจำลองการต่อสู้บนคอมพิวเตอร์แบบขนาน [ ^{13 ] แบบ}จำลองอนุภาคชนกัน^{[ 14 ]}นำเสนอภารกิจการจำลองที่คล้ายกันกับปฏิสัมพันธ์เชิงพื้นที่ของอนุภาค แต่ปราศจากรายละเอียดที่ไม่จำเป็นสำหรับการเปิดเผยเทคนิคการจำลอง การเร่งความเร็วถูกนำเสนอเป็นอัตราส่วนของเวลาการทำงานบนโปรเซสเซอร์เดี่ยวเทียบกับเวลาการทำงานบนโปรเซสเซอร์หลายตัวเมื่อดำเนินการอัลกอริทึม Time Warp แบบขนานเดียวกัน Boris D. Lubachevsky สังเกตเห็นว่าการประเมินการเร่งความเร็วเช่นนี้อาจผิดพลาดได้ เนื่องจากการดำเนินการอัลกอริทึมแบบขนานสำหรับงานบนโปรเซสเซอร์เดี่ยวไม่จำเป็นต้องเป็นวิธีที่เร็วที่สุดในการทำงานบนเครื่องดังกล่าว LSA ถูกสร้างขึ้นเพื่อพยายามสร้างการจำลองโปรเซสเซอร์เดี่ยวที่เร็วขึ้น และด้วยเหตุนี้จึงมีการประเมินการเร่งความเร็วแบบขนานที่ ยุติธรรมมากขึ้น ต่อมาได้มีการเสนออัลกอริทึมการจำลองแบบขนานซึ่งแตกต่างจาก Time Warp ซึ่งเมื่อรันบนโปรเซสเซอร์เดี่ยวจะลดลงเหลือ LSA ^{[ 15 ]}

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