## Tổng quan nghiên cứu

Trong bối cảnh phát triển mạnh mẽ của công nghệ tính toán song song và nhu cầu giải quyết các bài toán biên phức tạp trong toán học ứng dụng, việc nghiên cứu các phương pháp lặp song song dựa trên tư tưởng chia miền trở nên cấp thiết. Các bài toán biên elliptic cấp hai với điều kiện biên hỗn hợp hoặc gián đoạn thường không thể giải chính xác bằng các phương pháp truyền thống, do đó cần các thuật toán giải gần đúng với độ phức tạp tính toán thấp và khả năng mở rộng cao. Mục tiêu của luận văn là nghiên cứu và phát triển các phương pháp lặp song song dựa trên thuật toán chia miền để giải các bài toán biên elliptic cấp hai, đồng thời xây dựng và đánh giá các sơ đồ tính toán song song hiệu quả.

Phạm vi nghiên cứu tập trung vào các bài toán biên elliptic trên miền hình chữ nhật, sử dụng phương pháp sai phân để rời rạc hóa bài toán và áp dụng thuật toán thu gọn khối lượng tính toán của Samarski-Nicolaev. Thời gian nghiên cứu chủ yếu trong giai đoạn 2010-2012 tại Đại học Khoa học - Đại học Thái Nguyên. Ý nghĩa của nghiên cứu được thể hiện qua việc giảm thiểu thời gian tính toán, tăng hiệu quả xử lý song song, đồng thời cung cấp các công cụ tính toán số chính xác cho các bài toán phức tạp trong toán ứng dụng và kỹ thuật.

## Cơ sở lý thuyết và phương pháp nghiên cứu

### Khung lý thuyết áp dụng

- **Lý thuyết xử lý song song:** Định nghĩa và đánh giá thuật toán song song dựa trên thời gian tính toán, thời gian truyền thông, số bộ xử lý, và các giao thức đồng bộ hóa. Các nguyên lý thiết kế thuật toán song song bao gồm nguyên lý lập lịch, nguyên lý hình ống và nguyên lý chia để trị.
- **Phương pháp sai phân:** Rời rạc hóa bài toán vi phân elliptic cấp hai thành hệ phương trình đại số trên lưới sai phân, đảm bảo độ chính xác cấp hai.
- **Thuật toán thu gọn khối lượng tính toán (Samarski-Nicolaev):** Giảm thiểu khối lượng tính toán khi giải hệ phương trình vec tơ ba điểm, sử dụng các bước khử liên tiếp và các công thức truy toán để tính toán hiệu quả.
- **Thuật toán chia miền:** Các phương pháp chia miền như Patrick le Talle, J. Vavalis - Daopi Yang, và Saito – Fujita, nhằm phân chia miền tính toán thành các miền con độc lập, giải quyết song song các bài toán con với điều kiện biên phù hợp.
- **Sơ đồ lặp song song:** Phương pháp lặp chẵn lẻ QD1 và phương pháp song song QD2 dựa trên chia miền, cho phép giải song song các bài toán con trên các miền con, đồng thời cập nhật giá trị biên để đảm bảo hội tụ.

### Phương pháp nghiên cứu

- **Nguồn dữ liệu:** Dữ liệu đầu vào là các bài toán biên elliptic cấp hai với điều kiện biên Dirichlet và hỗn hợp trên miền hình chữ nhật, được rời rạc hóa bằng lưới sai phân kích thước M×N.
- **Phương pháp phân tích:** Sử dụng phân tích độ phức tạp thuật toán dựa trên số bước lặp K, kích thước lưới M×N, và số bộ xử lý p. Đánh giá thời gian tính toán (tcomp) và thời gian truyền thông (tcomm) theo các công thức chuẩn trong xử lý song song.
- **Timeline nghiên cứu:** 
  - Giai đoạn 1: Tổng hợp lý thuyết và xây dựng thư viện TK2004 giải số bài toán biên elliptic (6 tháng).
  - Giai đoạn 2: Phát triển các sơ đồ lặp song song dựa trên chia miền, cài đặt thử nghiệm trên Matlab (6 tháng).
  - Giai đoạn 3: Đánh giá hiệu quả thuật toán qua các ví dụ thực nghiệm, phân tích kết quả và hoàn thiện luận văn (6 tháng).

## Kết quả nghiên cứu và thảo luận

### Những phát hiện chính

- **Hiệu quả của thuật toán thu gọn khối lượng tính toán:** Độ phức tạp tính toán của thuật toán là khoảng O(M×N log N), giúp giảm đáng kể thời gian giải hệ phương trình đại số so với phương pháp truyền thống.
- **Sự hội tụ của sơ đồ lặp song song QD1:** Qua thực nghiệm với lưới 64×64 và 19 miền chia, sơ đồ lặp chẵn lẻ QD1 hội tụ với sai số nhỏ hơn 10^-5 sau khoảng 20 bước lặp, tham số lặp tối ưu nằm trong khoảng (0.2, 0.4).
- **Khả năng xử lý song song của QD1 và QD2:** QD1 sử dụng (n+1) bộ xử lý song song cho các miền lẻ và n bộ xử lý cho các miền chẵn, trong khi QD2 sử dụng n bộ xử lý song song cho n miền con. Độ phức tạp tổng thể của các thuật toán này là O(KMN log N), trong đó K là số bước lặp.
- **Độ phức tạp truyền thông:** Thời gian truyền thông được ước lượng theo công thức tcomm = 2N t_startup + N t_data, trong đó N là số lượng dữ liệu trao đổi trên biên chung giữa các bộ xử lý.

### Thảo luận kết quả

Nguyên nhân chính giúp các phương pháp lặp song song dựa trên chia miền đạt hiệu quả là do khả năng phân chia bài toán lớn thành các bài toán con độc lập, tận dụng tối đa khả năng xử lý song song của các bộ xử lý. So với các phương pháp truyền thống, các sơ đồ lặp QD1 và QD2 giảm thiểu đáng kể thời gian tính toán nhờ giảm độ phức tạp và tận dụng hiệu quả bộ nhớ cục bộ.

So sánh với các nghiên cứu trước đây, phương pháp chia miền Saito – Fujita chỉ cần giải một bài toán Dirichlet và một bài toán Neumann mỗi bước lặp, giảm khối lượng tính toán so với các thuật toán Patrick le Talle và Vavalis-Yang, tuy nhiên các sơ đồ lặp QD1 và QD2 mở rộng khả năng xử lý song song cho nhiều miền con hơn, phù hợp với các hệ thống đa bộ xử lý hiện đại.

Dữ liệu thực nghiệm có thể được trình bày qua các bảng số liệu về số bước lặp và sai số, cùng các đồ thị nghiệm xấp xỉ minh họa sự hội tụ của thuật toán, giúp trực quan hóa hiệu quả và độ chính xác của phương pháp.

## Đề xuất và khuyến nghị

- **Phát triển thuật toán song song đa miền:** Mở rộng số miền con để tận dụng tối đa số bộ xử lý hiện có, giảm thời gian tính toán tổng thể, hướng tới xử lý các bài toán biên phức tạp hơn trong thực tế.
- **Tối ưu tham số lặp:** Nghiên cứu và áp dụng các phương pháp chọn tham số lặp α, β, θ tối ưu nhằm tăng tốc độ hội tụ của sơ đồ lặp, giảm số bước lặp cần thiết.
- **Cải tiến giao thức truyền thông:** Giảm thiểu thời gian truyền thông giữa các bộ xử lý bằng cách tối ưu hóa kích thước dữ liệu trao đổi và sử dụng các giao thức đồng bộ hiệu quả.
- **Ứng dụng thư viện TK2004:** Khuyến khích sử dụng thư viện TK2004 trong các dự án tính toán số liên quan đến bài toán biên elliptic, giúp tiết kiệm thời gian phát triển và đảm bảo độ chính xác cao.
- **Đào tạo và chuyển giao công nghệ:** Tổ chức các khóa đào tạo về phương pháp lặp song song và sử dụng thư viện TK2004 cho các nhà nghiên cứu và kỹ sư trong lĩnh vực toán ứng dụng và kỹ thuật.

## Đối tượng nên tham khảo luận văn

- **Nhà nghiên cứu toán học ứng dụng:** Nắm bắt các phương pháp giải số hiện đại cho bài toán biên elliptic, áp dụng trong nghiên cứu và phát triển thuật toán.
- **Kỹ sư phần mềm tính toán:** Áp dụng các thuật toán song song và thư viện TK2004 để phát triển phần mềm tính toán hiệu quả trên hệ thống đa bộ xử lý.
- **Giảng viên và sinh viên cao học:** Là tài liệu tham khảo sâu sắc về lý thuyết xử lý song song, phương pháp sai phân và thuật toán thu gọn khối lượng tính toán.
- **Chuyên gia trong lĩnh vực mô phỏng kỹ thuật:** Sử dụng các phương pháp lặp song song để giải quyết các bài toán mô phỏng phức tạp trong cơ học, vật lý và kỹ thuật.

## Câu hỏi thường gặp

1. **Phương pháp lặp song song dựa trên chia miền là gì?**  
Là kỹ thuật phân chia miền tính toán thành các miền con độc lập, giải song song các bài toán con và cập nhật giá trị biên để đảm bảo hội tụ nghiệm tổng thể.

2. **Ưu điểm của thuật toán thu gọn khối lượng tính toán là gì?**  
Giảm đáng kể khối lượng tính toán khi giải hệ phương trình đại số, giúp tăng tốc độ xử lý và giảm yêu cầu bộ nhớ.

3. **Làm thế nào để chọn tham số lặp tối ưu?**  
Thông thường tham số lặp được chọn trong khoảng (0.2, 0.4) dựa trên phân tích lý thuyết và thực nghiệm để đạt tốc độ hội tụ nhanh nhất.

4. **Thư viện TK2004 hỗ trợ giải bài toán nào?**  
Hỗ trợ giải số các bài toán biên elliptic với điều kiện biên Dirichlet, Neumann và hỗn hợp trên miền hình chữ nhật.

5. **Độ phức tạp tính toán của các sơ đồ lặp song song là bao nhiêu?**  
Khoảng O(KMN log N), trong đó K là số bước lặp, M×N là kích thước lưới chia miền.

## Kết luận

- Luận văn đã xây dựng và phát triển các phương pháp lặp song song dựa trên tư tưởng chia miền để giải bài toán biên elliptic cấp hai với độ chính xác cao và hiệu quả tính toán vượt trội.  
- Thuật toán thu gọn khối lượng tính toán của Samarski-Nicolaev được áp dụng thành công, giảm độ phức tạp tính toán xuống còn O(MN log N).  
- Các sơ đồ lặp song song QD1 và QD2 cho thấy sự hội tụ tốt và khả năng xử lý song song hiệu quả trên nhiều bộ xử lý.  
- Thư viện TK2004 được xây dựng là công cụ hỗ trợ mạnh mẽ cho việc giải số các bài toán biên elliptic với điều kiện biên hỗn hợp.  
- Đề xuất tiếp tục nghiên cứu tối ưu tham số lặp, mở rộng số miền con và cải tiến giao thức truyền thông để nâng cao hiệu quả tính toán trong các hệ thống đa bộ xử lý hiện đại.

Áp dụng các phương pháp và thư viện đã phát triển vào các bài toán thực tế trong toán ứng dụng và kỹ thuật, đồng thời đào tạo nhân lực sử dụng hiệu quả các công cụ này.