Thuật toán cho phép nhân ma trận dạng bậc hai với ma trận thô

Question

Tôi đang tối ưu hóa mã dựa trên thư viện Ma trận tùy chỉnh (sẽ không bị loại trừ khỏi dự án vì nó ở khắp mọi nơi. Điều này không tốt, nhưng đó là sự thật. ..) nhiều tính toán được thực hiện với ma trận 10-20 hàng và cột, nhiều tính toán bao gồm một hình thức bậc hai như

C = A*B*A' 

tôi nhận ra rằng thường A là thưa thớt và tôi muốn tận dụng thực tế này. Vì vậy, tôi đang tìm kiếm một thuật toán có thể xử lý trường hợp này. Tính ổn định số là quan trọng. Có điều gì tôi có thể sử dụng không? (Tôi không viết thư viện của mình nên tôi không biết liệu có nên xem xét bất kỳ cạm bẫy nào không?)

Phương pháp nhân "O" đơn giản của chúng tôi thực hiện nhanh hơn Eigen 3 trên nền tảng đích, vì tôi cần sự ổn định số và ma trận không phải là rất lớn, tôi đoán rằng thuật toán của Strassen cũng như thuật toán Coppersmith – Winograd không phải là những gì tôi đang tìm kiếm. Thay vào đó, nó chỉ là phép nhân dạng bậc hai theo cách cho phép tôi dễ dàng kiểm tra số không trong A.

Cảm ơn bạn đã đề xuất!

Answer 1

Có tồn tại this giấy, xử lý phép nhân ma trận thưa thớt nhanh. Thuật toán phát triển chia ma trận thưa thớt thành hai phần: Một mật độ dày đặc và thưa thớt và áp dụng thuật toán nhân nhanh trên đó. Vì vậy, đối với tôi nó trông giống như nó không phụ thuộc vào kích thước của ma trận, như bạn đã đề cập đối với Strassen, nhưng thực tế là nó là thưa thớt.

Answer 2

Có nhiều cách để thực hiện một ma trận thưa thớt theo các cách làm cho nhiều hơn cô đặc hơn một ma trận dày đặc. Một cách mà tôi làm điều đó như sau:

[0 0 0 0 0] 
[0 1 2 0 9] 
[0 0 0 2 0] 
[0 1 0 0 0] 

trở thành một mảng tuyến tính của các yếu tố khác không

typedef struct { 
    int row; 
    int col; 
    double entry; 
} Element; 

typedef SparseMatrix Element*; 

Vì vậy, ma trận bây giờ có một độ phức tạp không gian O (n) thay vì O (n^2) Đối với A * B, trong đó A và B là ma trận, bạn chỉ cần đi qua từng mảng cho các phần tử phù hợp (tức là a-> row == b-> col & & a-> col == b-> hàng), và có thể thêm một số với nhau (sản phẩm bên trong). Thuật toán này sẽ có độ phức tạp O (n^2) thay vì O (n^3). Điều này là bởi vì bạn có thể bỏ qua các hoạt động phù phiếm của việc lấy một sản phẩm bên trong mà sẽ dẫn đến số không.

Answer 3

kiểm tra Highly Parallel Sparse Matrix-Matrix Multiplication algorothm