Cholesky phân hủy các ma trận thưa thớt bằng cách sử dụng ma trận hoán vị

Question

Tôi quan tâm đến sự phân hủy Cholesky của các ma trận thưa thớt lớn. Vấn đề tôi gặp phải là các yếu tố Cholesky không nhất thiết phải thưa thớt (giống như sản phẩm của hai ma trận thưa thớt không nhất thiết là thưa thớt). Ví dụ cho một ma trận với số không chỉ dọc theo hàng đầu tiên, cột đầu tiên, và chéo các yếu tố Cholesky có 100% điền vào (các hình tam giác phía trên và phía trên là 100% dày đặc). Trong các image dưới màu xám là số không và màu trắng là số không.

Một giải pháp Tôi biết là để tìm một hoán vị P ma trận và làm phân hủy Cholesky của P ^T AP. Ví dụ với cùng một ma trận bằng cách áp dụng một ma trận hoán vị di chuyển hàng đầu tiên đến hàng cuối cùng và cột đầu tiên đến cột cuối cùng, các yếu tố Cholesky là thưa thớt.

Câu hỏi của tôi là làm thế nào để xác định P nói chung?

Để có được một ý tưởng về sự khác biệt của quá trình phân hủy Cholesky của Một và P ^T AP từ một ma trận thực tế hơn xem hình ảnh dưới đây. Tôi mất tất cả các hình ảnh từ http://www.seas.ucla.edu/~vandenbe/103/lectures/chol.pdf

Theo lecture notes

nhiều phương pháp dựa trên kinh nghiệm (mà chúng ta không bao gồm) tồn tại để lựa chọn tốt hoán vị ma trận P.

Tôi muốn biết những gì một trong những phương pháp này là (mã trong C, C++, hoặc thậm chí Java sẽ là lý tưởng).

Answer 1

Vấn đề tìm kiếm hoán vị tối ưu của các hàng và cột của ma trận cho một hệ số ma trận điền vào tối thiểu không phải là một traskial trask (như đã chỉ ra trong các chú thích). Do đó, thuật toán heuristic được sử dụng trong praxis.

Có một số thư viện triển khai phương pháp sắp xếp lại/sắp xếp theo phương pháp heuristic, thường dựa trên đồ thị-thuật toán cho đồ thị kề của ma trận. Một cố gắng giảm băng thông của ma trận kề kề tương ứng. Một cách dễ dàng để thực hiện algroithms là Cuthill-McKee Algorithm hoặc thuật toán Minimum-Degree Ordering. Thông tin thêm về vấn đề này có thể được tìm thấy trong Sách Yousef Saad: Iterative Methods for Sparse Linear Systems (2003), khi có nhiều người khác.

Nhiều thư viện thực hiện các thuật toán heuristic, như

• Suitesparse Một bộ sưu tập của thư viện cho người giải quyết trực tiếp cho largse hệ thống tuyến tính thưa thớt.phương pháp đặt hàng được thực hiện trong các thư viện của AMD, CAMD, COLAMD, và CCOLAMD
• (Par-)Metis Một thư viện cho Graph-phân vùng, nhưng cung cấp Matrix sắp xếp lại các thuật toán cũng
• Boost.Graph Làm việc trên đồ thị kề trực tiếp và cung cấp một số thuật toán đặt hàng, như đề cập Cuthill-McKee, và tối thiểu-Bằng đặt hàng
• (PT-)Scotch cho Graph-phân vùng và thưa thớt-ma trận sắp xếp lại

Một số các thư viện cũng cung cấp các phương pháp nhân tử Cholesky thưa thớt và có thể được sử dụng trực tiếp.