Luận án Tiến sĩ: Giải hệ phương trình kích thước lớn và điều kiện xấu trên bó máy tính

ĐẠI HỌC QUỐC GIA HÀ NỘI TRƯỜNG ĐẠI HỌC KHOA HỌC TỰ NHIÊN Vũ Tiến Dũng GIẢI HỆ PHƯƠNG TRÌNH KÍCH THƯỚC LỚN VÀ ĐIỀU KIỆN XẤU TRÊN BÓ MÁY TÍNH LUẬN ÁN TIẾN SĨ TOÁN HỌC Hà Nội - 2014 ĐẠI HỌC QUỐC GIA HÀ NỘI TRƯỜNG ĐẠI HỌC KHOA HỌC TỰ NHIÊN Vũ Tiến Dũng GIẢI HỆ PHƯƠNG TRÌNH KÍCH THƯỚC LỚN VÀ ĐIỀU KIỆN XẤU TRÊN BÓ MÁY TÍNH Chuyên ngành: Bảo đảm toán học cho máy tính và hệ thống tính toán Mã số: 62 46 35 01 LUẬN ÁN TIẾN SĨ TOÁN HỌC Người hướng dẫn khoa học: GS. PHẠM KỲ ANH Hà Nội - 2014 LỜI CAM ĐOAN Tôi xin cam đoan đây là công trình nghiên cứu của riêng tôi dưới sự hướng dẫn của GS. Phạm Kỳ Anh. Các số liệu, kết quả trình bày trong luận án là trung thực và chưa từng được ai công bố trong bất kỳ công trình nào khác.

Nghiên cứu sinh Vũ Tiến Dũng i LỜI CẢM ƠN Trước hết tôi xin gửi lời cảm ơn chân thành và sâu sắc tới Thầy hướng dẫn, GS. Phạm Kỳ Anh. Trong suốt quá trình thực hiện luận án, tôi luôn nhận được sự giúp đỡ tận tình, quý báu của Thầy. Nhờ những ý tưởng mà Thầy đã gợi ý, những góp ý, hướng dẫn của Thầy, những tài liệu bổ ích mà Thầy đã cung cấp cũng như những cuộc trao đổi thú vị cùng Thầy về công việc nghiên cứu, tôi đã hoàn thành đề tài của mình.

Và hơn cả, trong suốt quá trình học tập trước đây và trong quá trình thực hiện luận án, tôi luôn cảm nhận được tình thương quý, tin yêu của thầy giành cho tôi, sự động viên khích lệ của thầy khi tôi gặp khó khăn tạo động lực cho tôi vững tin thực hiện quá trình nghiên cứu. Đối với cá nhân tôi, thầy không chỉ đơn thuần là người hướng dẫn khoa học mà còn là người cha thứ hai của tôi. Tôi xin chân thành cảm ơn các thầy cô và anh chị em trong Bộ môn Tin học, Khoa Toán-Cơ-Tin học, đặc biệt GS TS Đặng Huy Ruận, PGS TS Nguyễn Hữu Ngự, PGS TS Đỗ Trung Tuấn, PGS TS Lê Trọng Vĩnh, TS Nguyễn Thị Minh Huyền, đã luôn chia sẻ, động viên, tạo điều kiện thu xếp công việc thuận lợi, giúp đỡ tôi rất nhiều trong việc hoàn thành luận án này. Tôi xin chân thành cảm ơn các thầy cô, các anh chị và các bạn trong Xemina "Toán học tính toán" về những thảo luận và góp ý trong các buổi Xemina.

Đặc biệt, tôi xin chân thành cảm ơn GS TSKH Nguyễn Hữu Công, PGS TSKH Vũ Hoàng Linh, PGS TS Nguyễn Hữu Điển, GS TS Đặng Quang Á, PGS TSKH Phạm Huy Điển, PGS TS Nguyễn Minh Tuấn, TS Nguyễn Trung Hiếu đã giúp đỡ, góp những ý kiến xác đáng để luận án được hoàn thiện hơn. Tôi xin chân thành cảm ơn các thầy và anh chị em trong Trung tâm Tính toán Hiệu năng cao, ĐHKHTN, ĐHQG Hà Nội. Trong suốt thời gian học tập trước đây và quá trình nghiên cứu sinh, Trung tâm đã tạo điều kiện cho tôi được tìm hiểu tiếp cận các phương tiện, máy móc và tạo môi trường làm việc thuận lợi để tôi có thể thực hiện đề tài của mình. Tôi cũng rất biết ơn Trường ĐHKHTN, ĐHQG Hà Nội.

Công tác quản lý đào tạo và môi trường nghiên cứu của Trường đã góp phần không nhỏ để cho luận án này được hoàn thành đúng dự định. Xin chân thành cảm ơn TS Cao Văn Chung, Lê Trung Kiên, Nguyễn Trung ii Kiên, Nguyễn Thị Thanh Lan, Vũ Anh Mỹ, Đặng Văn Hiếu và các bạn khác, những người đã chia sẻ, giúp đỡ về nhiều mặt, để tôi có thể hoàn thành quá trình nghiên cứu của mình. Tôi xin gửi lời cảm ơn tới Quỹ Phát triển Khoa học Công nghệ Quốc gia Việt Nam (NAFOSTED). Luận án này được hỗ trợ một phần về mặt tài chính bởi Quỹ, trong khuôn khổ Đề tài Nghiên cứu khoa học cơ bản mã số 101.

Cuối cùng, tôi muốn bày tỏ lòng biết ơn sâu sắc tới mẹ và những người thân trong gia đình, những người đã cảm thông và chia sẻ mọi khó khăn cùng tôi trong suốt những năm tháng qua để tôi có thể hoàn thành luận án. Luận án này, và những gì tôi đang cố gắng thực hiện, là để gửi tới cha, mẹ, vợ và những người thân trong gia đình, với tất cả lòng biết ơn sâu sắc nhất. iii Mục lục Lời cam đoan. ii Danh mục các ký hiệu và chữ viết tắt.

viii Danh mục các bảng. x Danh mục các hình vẽ. xi Mở đầu. Kiến thức chuẩn bị.

Nguyên lý tính toán song song. Kiến trúc máy tính song song. Lập trình song song. Đánh giá hiệu quả của tính toán song song.

Bài toán kích thước lớn, điều kiện xấu và bài toán đặt không chỉnh 24 1. Bài toán kích thước lớn. Bài toán đặt không chỉnh và bài toán điều kiện xấu. Một số phương pháp hiệu chỉnh.

Quy trình giải một bài toán kích thước lớn và điều kiện xấu trên bó máy tính. Một số phương pháp tuần tự và song song giải hệ phương trình toán tử. 33 iv Chương 2. Phương pháp song song giải hệ phương trình toán tử tuyến tính và ứng dụng.

Phương pháp chỉnh lặp song song. Giải hệ phương trình đại số tuyến tính quá xác định và ứng dụng trong bài toán khôi phục ảnh. Phương pháp chỉnh lặp hiện song song và chỉnh lặp ẩn song song cho hệ phương trình đại số tuyến tính quá xác định. Ước lượng sai số của phương pháp.

Thử nghiệm số. Giải hệ phương trình đại số tuyến tính quá xác định. Bài toán khôi phục ảnh đa cấp xám. Phương pháp song song toàn phần giải một lớp phương trình đạo hàm riêng đại số.

Phân rã bài toán biên cho phương trình đạo hàm riêng đại số thành bài toán biên cho phương trình elliptic và phương trình parabolic. Phương pháp phân rã song song giải bài toán biên cho phương trình elliptic và parabolic. Thử nghiệm số. Phương pháp chỉnh lặp Gauss-Newton song song giải hệ phương trình toán tử phi tuyến và ứng dụng.

Phương pháp chỉnh lặp Gauss-Newton và phương pháp chỉnh lặp Gauss -Newton song song. Sự hội tụ của phương pháp chỉnh lặp Gauss-Newton song song. Áp dụng cho hệ phi tuyến dưới xác định. Hệ phương trình có cấu trúc thưa.

Mối liên hệ giữa phương pháp chỉnh lặp Gauss-Newton song song và các phương pháp chỉnh lặp song song. 97 Danh mục công trình khoa học của tác giả liên quan đến luận án. 99 Tài liệu tham khảo. 100 vi Danh mục các ký hiệu và chữ viết tắt h·, ·i Tích vô hướng (hoặc tích đối ngẫu).

kxk Chuẩn của véc tơ x. kDk Chuẩn của ma trận D. 0 F (x) Đạo hàm Frechet của F tại điểm x. cond(A) Số điều kiện của ma trận A.

>> Ký hiệu lớn hơn nhiều. AT Ma trận chuyển vị của ma trận A. Toeplitz Ma trận Toeplitz. vec(F) Phép dãn ma trận F thành véc tơ.

A? Toán tử liên hợp của toán tử A. H Không gian Hilbert. PIIRM (PEIRM) Phương pháp chỉnh lặp ẩn (hiện) song song. PEIRMm Phương pháp PEIRM với m bước lặp trong.

IRGNM Phương pháp chỉnh lặp Gauss Newton. PIRGNM Phương pháp chỉnh lặp song song Gauss Newton. PSU Phương pháp phân rã song song. PFS Phương pháp song song với bước phân.

LW Phương pháp lặp Landweber. TSVD Phương pháp khai triển kỳ dị chặt cụt. CGLS Phương pháp bình phương tối thiểu gradient liên hợp. x† Nghiệm của hệ phương trình.

vii IVP Bài toán giá trị ban đầu. BVP Bài toán biên. xnδ Nghiệm xấp xỉ thứ n của x†. nmax Tổng số bước lặp.

nmin Số n nhỏ nhất khi sai số tương đối (REN) của phương pháp tương ứng nhỏ hơn một giá trị cho trước. span(Vk ) Không gian con sinh bởi tập k véc tơ Vk = {v1 ,. IBVP Bài toán biên - ban đầu. SISD Đơn lệnh, đơn dòng dữ liệu.

SIMD Đơn lệnh, đa dòng dữ liệu. MISD Đa lệnh, đơn dòng dữ liệu. MIMD Đa lệnh, đa dòng dữ liệu. VPU Bộ xử lý véc tơ.

SM_MIMD Kiến trúc máy tính đa lệnh, đa dòng dữ liệu với bộ nhớ chia sẻ. DM_MIMD Kiến trúc máy tính đa lệnh, đa dòng dữ liệu với bộ nhớ phân tán. UMA Kiến trúc máy tính song song với bộ nhớ chia sẻ truy cập ngang quyền. SMP Máy tính đa bộ xử lý đối xứng.

NUMA Kiến trúc máy tính song song với bộ nhớ chia sẻ truy cập không ngang quyền. GPU Đơn vị xử lý đồ họa. CUDA Kiến trúc thiết bị tính toán hợp nhất. viii Danh mục các bảng Chương 2.1 Sai số tương đối của PIIRM và PEIRM theo số bước lặp .2 Sai số tương đối của PIIRM và PEIRM theo số bước lặp .3 Sai số tương đối của PIIRM, PEIRM và LW theo số bước lặp .4 Sai số tương đối của PIIRM, PEIRM và LW theo số bước lặp .5 Hệ số tăng tốc và Hiệu suất thực thi các phương pháp.6 Thời gian thực hiện thuận toán cải tiến và PEIRM1 .7 Hệ số tăng tốc và hiệu suất của phương pháp PEIRM1 .8 Kết quả với tỷ lệ hτ2 không đổi .9 Hệ số tăng tốc và hiệu suất của phương pháp PFS .10 Thời gian thực thi phương pháp PSU .11 Tốc độ và hiệu suất trên một node tính toán .12 Tốc độ và hiệu suất trên một node tính toán .13 Số các phép lặp .14 Thời gian thực hiện .1 Sai số tương đối và thời gian thực hiện chương trình tuần tự với η = 2.2 Chỉ số dừng của phương pháp PIRGNM với η = 0.3 Hiệu suất và tốc độ của phương pháp PIRGNM .4 Sai số tương đối và thời gian thực hiện chương trình tuần tự với η = 0.5 Chỉ số dừng của phương pháp PIRGNM với η = 0.6 Kết quả nhận được của hai phương pháp với cùng một số bước lặp cố định.7 Hiệu suất và tốc độ của phương pháp PIRGNM trên bó máy tính IBM 1350.

94 x Danh mục các hình vẽ Chương 1.1 Kiến trúc của máy tính với bộ xử lý mảng .4 Máy tính với bộ nhớ phân tán .5 Kiến trúc bó máy tính IBM1350 và IBM1600.1 Sai số tương đối của phương pháp PIIRM và PEIRM.2 Sai số tương đối của PIIRM và PEIRM.3 Sai số tương đối của phương pháp PIIRM, PEIRM và LW.4 Sai số tương đối của các phương pháp PIIRM, PEIRM và LW.6 Ảnh khôi phục .7 Ảnh khôi phục .10 Ảnh khôi phục .11 Ảnh khôi phục. 59 xi Mở đầu Nhiều vấn đề trong các lĩnh vực khai phá dữ liệu, chuẩn đoán bệnh bằng hình ảnh, tìm kiếm và bào chế dược phẩm đặc dụng, công nghệ đa phương tiện, phát triển đồ họa và thực tại ảo, dự báo thời tiết, cảnh báo động đất, sóng thần, vv.