Tính nghịch đảo của ma trận rất lớn

Question

Tôi đang cố tính toán nghịch đảo của ma trận rất lớn (11300x21500) trong C++. Cho đến nay tôi đã thử các thư viện Eigen và Armadillo nhưng cả hai đều thất bại ở giai đoạn khởi tạo, nói rằng không có đủ bộ nhớ. Có cách nào để vượt qua tình trạng này không?

Cảm ơn trước

P.S
tôi nên sửa kích thước của ma trận để 21500x21500. Như UmNyobe đã đề xuất, đây không phải là ma trận vuông. Nó thực sự là ma trận quan sát, X, và tôi đang cố gắng để tính toán (X^TX) ^-1

Tôi có một bộ nhớ 8GB (trong một hệ thống 64bit), nhưng tôi đừng nghĩ rằng tôi đang sử dụng tất cả không gian bộ nhớ này. Trình quản lý tác vụ cho thấy việc sử dụng bộ nhớ tại thời điểm lỗi là 1GB. Có thể có một lệnh hệ điều hành trong Windows7 mà đóng một ứng dụng khi sử dụng bộ nhớ của nó vượt quá 1GB.

Nhân tiện, mục đích ban đầu của tôi là chạy hồi quy trên ma trận quan sát này.

Một điều nữa: hầu hết các cột trong mỗi hàng của ma trận quan sát X đều bằng không. Có thể có một cách để tận dụng lợi thế này, để hạn chế việc sử dụng bộ nhớ trong hoạt động đảo ngược?

Answer 1

Bạn không thể nghịch đảo ma trận không vuông.

http://en.wikipedia.org/wiki/Invertible_matrix

Answer 2

Giả sử ma trận là vuông, những gì có thể là bạn đang muốn tìm một thuật toán ma trận nghịch đảo tại chỗ.

Bạn nên xem this.

Answer 3

Giả sử một Matrix (11300 x 11300) của số nguyên (32 bit), bạn có

4*(11300^2)/(1024^3) = 0.4757 GB 

Nếu bạn đang sử dụng chính xác gấp đôi sau đó nhấp đúp con số này.

Nếu thư viện đang sử dụng thuật toán Strassen, yêu cầu bộ nhớ bổ sung có cùng độ lớn, thì bạn tăng gấp đôi số trước đó.

Vì vậy, đảo ngược ma trận đôi dựa trên kích thước này bằng Strassen hoặc gaussian sẽ tốn 1,9 GB.

Answer 4

Tôi muốn đề xuất giải pháp khác, chỉ hoạt động nếu bạn không quan tâm đến nghịch đảo của ma trận, nhưng trong sản phẩm nghịch đảo với vectơ. Ví dụ: giả sử rằng bạn muốn tìm sản phẩm của thời gian nghịch đảo của mình một vectơ v, tức là w := (X^T X)^{-1} v. Trong trường hợp này, bạn đang thực sự tìm kiếm một giải pháp cho vấn đề

Find w such that (X^T X) w = v 

Sử dụng thuật toán lặp đi lặp lại, người ta có thể tìm thấy w cho X và v trong phương trình trên mà không đảo ngượcX. Một khả năng mà tôi nghĩ đến là sử dụng Method of Conjugate Gradients.Thuật toán này có thể được thực hiện trong khoảng 10 dòng và chỉ yêu cầu để có thể tính toán sản phẩm (X^T X) y với một vector đã cho y. Trong trường hợp của chúng tôi, điều này thậm chí có thể được thực hiện theo hai bước, tức là tính z := X y và trong bước thứ hai X^T z, sẽ tiết kiệm dung lượng khi bạn không cần lưu trữ sản phẩm X^T X.

Answer 5

Mặc dù bạn đang biên soạn chương trình của mình trên máy 64 bit, bạn cũng nên đảm bảo rằng bạn đang sử dụng đúng thư viện 64 bit. Nếu không, chương trình có thể được biên dịch trong 32-bit và bạn vẫn sẽ nhận được cùng một vấn đề về bộ nhớ.

Đối với việc tính toán nghịch đảo, hàm nghịch đảo của OpenCV có thể hữu ích. Hãy chắc chắn sử dụng DECOMP_SVD nghịch đảo, vì tôi thấy nó có hiệu quả hơn với các ma trận đơn lẻ gần.