Đồ Án Áp dụng phương pháp SVD tính lực xấp xỉ trong bài toán mô phỏng động lực phân tử

TÓM TẮT KHÓA LUẬN


Mô phỏng động lực phân tử là một trong những phương pháp phổ biến để
nghiên cứu các hệ vật lý và hóa học. Trong mô phỏng động lực phân tử, thời gian tính
toán lực tương tác giữa các hạt trong hệ chiếm phần lớn tổng thời gian mô phỏng.
Thuật toán khai triển đa cực nhanh Fast Multipole Method [5, 7, 8] và các cải tiến của
nó là những phương pháp được sử dụng phổ biến trong mô phỏng động lực phân tử
nhằm tăng tốc độ tính toán lực. Trong cài đặt thuật toán khai triển đa cực nhanh,
phương pháp phân tích ma trận SVD (Singular Value Decomposition [17, 18]) được
sử dụng để nhằm tăng độ chính xác của tính lực xấp xỉ. Một trong những vấn đề chưa
được giải quyết trong cài đặt thuật toán khai triển đa cực nhanh là nghiên cứu ảnh
hưởng của phương pháp SVD đến độ chính xác của tính lực xấp xỉ. Khóa luận sẽ
nghiên cứu vấn đề nêu trên bằng thực nghiệm, nhằm tìm ra cách ứng dụng phương
pháp SVD hợp lý để làm tăng độ chính xác và hiệu năng của thuật toán khai triển đa
cực nhanh trên các máy tính chuyên dụng hoặc các máy tính thông thường. Các kết
quả thu được trong khóa luận là khả quan và sẽ được ứng dụng trong các nghiên cứu
về cài đặt thuật toán khai triển đa cực nhanh tiếp theo.



MỤC LỤC

TÓM TẮT KHÓA LUẬN i
LỜI CẢM ƠN . ii
MỤC LỤC . iii
DANH MỤC HÌNH VẼ v
DANH MỤC BẢNG BIỂU . vi
BẢNG THUẬT NGỮ vii
MỞ ĐẦU .1
Chương 1. TỔNG QUAN VỀ BÀI TOÁN MÔ PHỎNG ĐỘNG LỰC PHÂN TỬ 3
1.1 Bài toán mô phỏng động lực phân tử 3
1.1.1 Giới thiệu chung .3
a. Các bước trong mô phỏng động lực phân tử 3
b. Ứng dụng của phương pháp mô phỏng động lực phân tử 4
1.1.2 Bài toán mô phỏng động lực phân tử dưới góc độ tính toán 4
1.2 Các phương pháp trong mô phỏng động lực phân tử 5
1.2.1 Phương pháp tính trực tiếp tương tác hạt-hạt .5
1.2.2 Thuật toán cây 6
1.2.3 Phương pháp khai triển đa cực nhanh 7
1.2.4 Một số phương pháp khác 7
1.3 Mục tiêu của khóa luận 8
1.4 Tổng kết chương 8
Chương 2. THUẬT TOÁN KHAI TRIỂN ĐA CỰC NHANH 9
2.1 Thuật toán khai triển đa cực nhanh FMM .9
2.1.1 Phương pháp khai triển đa cực .9
2.1.2 Thuật toán FMM .15
a. Các pha chính trong thuật toán FMM 16
b. Cài đặt thuật toán FMM 19
c. Độ phức tạp của thuật toán FMM 22
2.2 Các biến thể của thuật toán FMM .23
2.2.1 Phương pháp của Anderson 23
2.2.2 Phương pháp giả hạt của Makino .26
a. Trong hệ tọa độ 2 chiều .27
b. Trong hệ tọa độ 3 chiều .28
2.3 Tổng kết chương 30
Chương 3. ÁP DỤNG PHƯƠNG PHÁP SVD TRONG MÔ PHỎNG ĐỘNG LỰC
PHÂN TỬ 31
3.1 Phương pháp SVD .31
3.1.1 SVD của ma trận vuông .32
3.1.2 Giải hệ phương trình tuyến tính .33
a. Cách giải hệ phương trình tuyến tính bằng SVD 33
b. Vấn đề chọn tham số “gần 0” trong phương pháp SVD .35
3.1.3 Cài đặt phương pháp SVD trên máy tính .35
3.2 Ứng dụng của phương pháp SVD trong inner P2
M2
.36
3.2.1 Cài đặt thuật toán FMM trên máy GRAPE 36
a. Chức năng của máy GRAPE .36
b. Cài đặt thuật toán FMM trên máy GRAPE .37
3.2.2 Ứng dụng của SVD trong cài đặt inner P2
M2
.38
3.3 Tổng kết chương 40
Chương 4. KẾT QUẢ THỰC NGHIỆM VÀ ĐÁNH GIÁ .41
4.1 Môi trường thực nghiệm 41
4.1.1 Phần cứng .41
4.1.2 Phần mềm .41
4.2 Thử nghiệm phương pháp khai triển đa cực nhanh FMM 41
4.2.1 Thời gian tính toán của phương pháp FMM 41
4.2.2 Đánh giá kết quả .43
4.3 Thử nghiệm phương pháp SVD trong biến đổi A2P .44
4.3.1 Độ chính xác của khai triển inner P2
M2
và biến đổi A2P 44
a. Phương pháp thực nghiệm .44
b. Kết quả thực nghiệm .45
4.3.2 Ảnh hưởng của tham số gần không trong phương pháp SVD đến độ chính
xác của thuật toán FMM 46
a. Phương pháp thực nghiệm .46
b. Kết quả thực nghiệm .47
4.4 Tổng kết chương 50
KẾT LUẬN .51
Kết quả đạt được 51
Hướng phát triển 51
Phụ lục A: Cài đặt SVD bằng ngôn ngữ C 53
A1. Thủ tục svdcmp() 53
A2. Thủ tục svbksb() .57
A3. Thủ tục zero_small_values() 57
TÀI LIỆU THAM KHẢO . 58

DANH MỤC HÌNH VẼ

Hình 1: Xấp xỉ trong cây (trên) và FMM (dưới) .6
Hình 2: Hai tập hợp hạt đủ xa trên mặt phẳng 12
Hình 3: Dịch chuyển tâm của khai triển đa cực. .14
Hình 4: Ý tưởng tính lực xấp xỉ trong FMM .16
Hình 5: Một vài mức phân chia trong FMM .17
Hình 6: Pha M2M trong thuật toán FMM .17
Hình 7: Danh sách hàng xóm và danh sách tương tác 18
Hình 8: Pha M2L trong thuật toán FMM 18
Hình 9: Pha L2L trong thuật toán FMM .19
Hình 10: Phương pháp của Anderson 25
Hình 11: Phương pháp giả hạt của Makino .26
Hình 12: Tính thế năng và lực từ phân phối khối lượng của các giả hạt 39
Hình 13: Thời gian tính lực của thuật toán trực tiếp (trên) và FMM (dưới) .43
Hình 14: Sai số trung bình bình phương của thế năng được tính bằng khai triển inner
P2
M2
và biến đổi A2P. Từ trên xuống, 8 đường cong tương ứng với các bậc khai triển
p = 1, 2, 3, 4, 5, 6, 7, 8 .46
Hình 15: Sai số trung bình bình phương của lực được tính bằng khai triển inner P2
M2

và biến đổi A2P. Từ trên xuống, 8 đường cong tương ứng với các bậc khai triển = p 1,
2, 3, 4, 5, 6, 7, 8 .46
Hình 16: Sai số trung bình bình phương của thế năng ứng với các tham số gần 0 khác
nhau. Từ trên xuống, các đường tương ứng với bậc khai triển từ 1 đến 5 48
Hình 17 : Sai số trung bình bình phương của thế năng ứng với các tham số gần 0 khác
nhau. Từ trên xuống, các đường tương ứng với bậc khai triển từ 6 đến 10 48
Hình 18: Sai số trung bình bình phương của lực ứng với các tham số gần 0 khác nhau.
Từ trên xuống, các đường tương ứng với bậc khai triển từ 1 đến 5 49
Hình 19 : Sai số trung bình bình phương của lực ứng với các tham số gần 0 khác nhau.
Từ trên xuống, các đường tương ứng với bậc khai triển từ 6 đến 10 49

DANH MỤC BẢNG BIỂU

Bảng 1: Các phần mềm mô phỏng động lực phân tử tiêu biểu .4
Bảng 2: Phân tích độ phức tạp của thuật toán FMM .23
Bảng 3: Công cụ sử dụng trong thử nghiệm 41
Bảng 4: Thời gian tính toán của FMM với số hạt thay đổi .42
Bảng 5: Thời gian tính toán trực tiếp với số hạt thay đổi 42
Bảng 6: Tham số gần 0 ứng với các mức khai triển khác nhau .50

BẢNG THUẬT NGỮ

Từ hoặc cụm từ Từ viết tắt Tên tiếng Anh
Bài toán giá trị biên boundary value problem
Bước thời gian Time step
Coulomb Lực Coulomb
Danh sách tương tác Interaction list
Danh sách hàng xóm Neighbor list
Động lực phân tử MD Molecular Dynamics
Giả hạt Pseudoparticle
Hạng Rank Rank
Khai triển đa cực Multipole expansion
Phương pháp khai triển đa
cực nhanh
FMM Fast multipole method
Khai triển địa phương Local expansion
Mô phỏng động lực phân tử MD Simulation Molecular Dynamics Simulation
Nghịch đảo ma trận Matrix inversion
Nullspace Nullspace
Range Range
Số điều kiện Condition Number
SVD SVD Singular value decomposition
Phương pháp giả hạt P2
M2
Pseudo-particle multipole method
Tương tác hạt-hạt PP Particle-Particle
Vật lý thiên văn astrophysics


MỞ ĐẦU
Sự phát triển nhanh chóng của công nghệ thông tin, đặc biệt là sự xuất hiện
của các hệ thống siêu máy tính có tốc độ tính toán nhanh đã mở ra một phương pháp
mới trong nghiên cứu khoa học, đó là phương pháp mô phỏng bằng máy tính. Mô
phỏng bằng máy tính đóng vai trò như cầu nối giữa lý thuyết với thực hành, giữa các
thí nghiệm thực tế với các thí nghiệm được thực hiện trên máy tính. Các lý thuyết có
thể được kiểm định bằng các hệ mô phỏng, mặt khác tính chính xác của một hệ mô
phỏng cũng có thể được kiểm định bằng các kết quả thí nghiệm thực tế. Hơn thế nữa,
các thí nghiệm mà hiện nay con người chưa thể tiến hành được trong phòng thí nghiệm
(ví dụ các thí nghiệm yêu cầu phải làm việc trong một môi trường nhiệt độ, hay áp suất
rất cao) có thể được mô phỏng bằng máy tính. Như vậy có thể nói, mô phỏng bằng
máy tính là một phương pháp có vai trò quan trọng, và ngày càng được sử dụng nhiều
trong nghiên cứu khoa học.
Mô phỏng động lực phân tử là một phương pháp phổ biến để nghiên cứu các
hệ vật lý và hóa học. Bài toán mô phỏng động lực phân tử xét dưới trên khía cạnh tính
toán thực chất là bài toán tính toán tương tác giữa các hạt trong một hệ phân tử. Dễ
thấy nếu sử dụng phương pháp tính toán trực tiếp tương tác của từng cặp hạt, độ phức
tạp tính toán sẽ là với là số hạt trong hệ. Như vậy đối các hệ có số hạt lớn
(ví dụ vài triệu hạt) thì thời gian tính toán là lớn đến mức không thể chấp nhận được
trong thực tế.
) (N O N
Đối với hầu hết các bài toán mô phỏng động lực phân tử, thời gian tính toán
lực thường chiếm tới 95% tổng thời gian mô phỏng. Do đó đã có nhiều nghiên cứu
nhằm làm giảm thời gian tính toán lực của bài toán mô phỏng. Các hướng nghiên cứu
chính gồm có: Phát triển các thuật toán tính toán nhanh có độ phức tạp tính toán
hoặc , phát triển các phần cứng đặc biệt để tăng tốc độ tính lực và kết
hợp hai hướng nghiên cứu trên.
) log ( N N O ) (N O
Thuật toán khai triển đa cực nhanh [5, 7, 8] là thuật toán tính toán nhanh do
Greengard và Rokhlin phát triển có độ phức tạp . Thuật toán khai triển đa cực
nhanh (viết tắt FMM) được phát triển trên các máy tính thông thường nên không áp
dụng được trên các máy tính đặc biệt. Do đó đã có nhiều cải tiến của thuật toán FMM
như các cải tiến của Anderson [2], phương pháp “giả hạt” của Makino [16], L. Ying
) (N O

[21, 22]. Các thuật toán này đã đơn giản hóa cài đặt của thuật toán FMM gốc và có thể
áp dụng các cài đặt này trên các máy tính đặc biệt.
Dựa trên các nghiên cứu của Anderson và Makino, các tác giả Chau, Kawai,
Ebisuzaki ([13]) đã cài đặt thuật toán FMM trên máy tính chuyên dụng GRAPE ([15,
20]) trong đó có sử dụng phương pháp SVD (Singular Value Decomposition [17, 18])
để tăng độ chính xác trong tính lực xấp xỉ. Một vấn đề chưa được giải quyết trong cài
đặt thuật toán khai triển đa cực nhanh là nghiên cứu ảnh hưởng của phương pháp SVD
đến độ chính xác của tính lực xấp xỉ. Vì vậy khóa luận sẽ nghiên cứu vấn đề chưa
được giải quyết nêu trên nhằm làm tăng độ chính xác và hiệu năng của thuật toán khai
triển đa cực nhanh trên máy tính chuyên dụng cũng như các máy tính thông dụng khác.
Phương pháp nghiên cứu trong khóa luận là dựa trên thực nghiệm.
Ngoài phần mở đầu và kết luận, kết cấu của khóa luận bao gồm bốn chương:
– Chương 1 “Tổng quan về bài toán mô phỏng động lực phân tử” trình bày cơ bản
về bài toán mô phỏng động lực phân tử và các phương pháp được sử dụng trong
mô phỏng động lực phân tử.
– Chương 2 “Thuật toán khai triển đa cực nhanh” sẽ trình bày các vấn đề cơ bản
về thuật toán khai triển đa cực nhanh và các biến thể của thuật toán.
– Chương 3 “Áp dụng phương pháp SVD trong mô phỏng động lực phân tử” trình
bày về bài toán mà khóa luận đưa ra và đề xuất cách giải quyết dựa trên thực
nghiệm.
– Chương 4 “Kết quả thực nghiệm và đánh giá” mô tả quá trình thực nghiệm, các
bảng số liệu, đồ thị, và đưa ra đánh giá về kết quả thu được.

LỜI CẢM ƠN
Đầu tiên, em muốn gửi lời cảm ơn sâu sắc đến TS. Nguyễn Hải Châu, người
đã hướng dẫn và chỉ bảo em tận tình trong suốt quá trình làm khóa luận. Cảm ơn thầy
vì những định hướng, những tài liệu quý báu và những động viên, khích lệ, giúp em
hoàn thành tốt khóa luận.
Em xin gửi lời cám ơn tới TS Nguyễn Năng Tâm, giảng viên trường Đại học
Sư phạm Hà Nội II vì những hỗ trợ về mặt toán học được sử dụng trong khóa luận.
Em xin bày tỏ lời cảm ơn sâu sắc đến các thầy cô giáo đã giảng dạy em trong
bốn năm qua, những kiến thức mà em nhận được trên giảng đường Đại học sẽ giúp em
vững bước trong tương lai.
Cuối cùng, tôi xin gửi lời cảm ơn sâu sắc tới những người thân trong gia đình,
những người luôn quan tâm, động viên khích lệ tôi trong học tập và trong cuộc sống.


Sinh viên thực hiện khóa luận
Phạm Quang Nhật Minh