Đề tài Á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

TÀI LIỆU LUẬN VĂN CÙNG DANH MỤC

TIN KHUYẾN MÃI

  • Thư viện tài liệu Phong Phú

    Hỗ trợ download nhiều Website

  • Nạp thẻ & Download nhanh

    Hỗ trợ nạp thẻ qua Momo & Zalo Pay

  • Nhận nhiều khuyến mãi

    Khi đăng ký & nạp thẻ ngay Hôm Nay

NẠP THẺ NGAY