АЛГОРИТМИ ТА СТРУКТУРИ ДАНИХ ДЛЯ ПОШУКУ НАЙБЛИЖЧИХ СУСІДІВ У МОЛЕКУЛЯРНІЙ ДИНАМІЦІ: ТОЧНІ МЕТОДИ В РЕАЛЬНОМУ ПРОСТОРІ

Анотація

Ефективний пошук найближчих сусідів є визначальним чинником продуктивності обчислювальної молекулярної динаміки (МД): саме на оцінювання локальних взаємодій у межах радіуса обрізання потенціалу припадає основна частка обчислювальних витрат симуляції, а безпосереднє попарне обчислення відстаней має квадратичну складність O(N²) і стає непридатним для систем реалістичного розміру. Метою статті є систематизація та порівняльний аналіз алгоритмів і структур даних для пошуку найближчих сусідів у молекулярній динаміці, а також оцінювання співвідношення їх обчислювальної ефективності та масштабованості. У роботі розмежовано два принципово різні режими такого пошуку. Перший – реальний тривимірний простір, у якому обчислюються міжатомні сили; для нього детально проаналізовано класичні структури даних: списки комірок (cell lists), списки Верле зі «шкіркою» та просторові дерева (KD-дерева, octree), що знижують складність від квадратичної до майже лінійної або O(N log N). Другий режим постав із поширенням машинно-навчених міжатомних потенціалів, де кожне локальне атомне оточення кодується багатовимірним вектором-дескриптором; у ньому пошук сусідів керує процедурами активного навчання, відбору репрезентативних конфігурацій та оцінювання невизначеності, а точні деревоподібні структури зазнають «прокляття розмірності», що зумовлює перехід до наближених методів (Ball-Trees, локально-чутливе хешування, HNSW). Як методичний внесок запропоновано обчислювальний експеримент на канонічній модельній системі – леннард-джонсівському флюїді – для кількісного зіставлення повного перебору, списків комірок, списків Верле та KD-дерева залежно від розміру системи, радіуса «шкірки» та густини. Експеримент підтвердив теоретичні оцінки складності (нахили 2.01 для перебору та 0.96–1.05 для масштабованих методів) і виявив різницю майже на три порядки між перебором і списком комірок за N ≈ 10⁶. Зроблено висновок, що в низьковимірному режимі реального простору структури на основі комірок і дерев є близькими до оптимальних і слугують базовою лінією для оцінювання високовимірного режиму, дослідження якого на реальному матеріалі є предметом окремої роботи.