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 , phương pháp “giả hạt” của Makino , 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 () đã 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