Xây dựng SparseMatrix trong Eigen

Question

Tôi đang xây dựng một hệ thống tuyến tính thưa thớt với nhiều hạn chế (mềm). Tôi đang chuyển đổi một số mã được sử dụng để xây dựng ma trận với boost :: ublas, để Eigen. Tăng: ublas có một cách thuận tiện để tạo một ma trận thưa thớt với số lượng không xác định (hoặc ước tính), và có toán tử nhanh (int row, int col) để cập nhật các phần tử của nó.

Vấn đề là như sau:

• Sử dụng SparseMatrix :: setFromTriplets:
  hệ thống của tôi có nhiều hạn chế. Như một ngây thơ, ví dụ phóng đại 'hơi', giả sử rằng tôi có ma trận thưa thớt 100x100, với 500 nnz nhưng 1 tỷ ràng buộc dư thừa (tức là, các coeff khác không được sửa đổi một tỷ lần). setFromTriplets yêu cầu tôi lưu trữ 1 tỷ hệ số, hầu hết trong số đó sẽ được tổng kết để tạo thành bộ 500 hệ số không bằng không của tôi. Đó không phải là thực sự hiệu quả cũng không nhớ thân thiện. Tất nhiên, tôi có thể thay thế std :: vector của mình bằng std :: map, và thực hiện tích lũy các ràng buộc bằng tay, nhưng bằng cách nào đó, bỏ lỡ điểm có một lớp ma trận thưa thớt và điều đó cũng không hiệu quả.

• Sử dụng SparseMatrix :: chèn (i, j, val):
  Không hoạt động nếu phần tử đã có mặt. Vấn đề của tôi là có thể tích lũy các hệ số đã có.

• sử dụng SparseMatrix :: coeffRef (i, j):
  Tính năng này hoạt động và sẽ là chức năng tôi đang tìm kiếm. Tuy nhiên nó là một số đơn đặt hàng của cường độ chậm hơn so với tăng :: ublas. Tôi ngạc nhiên rằng tôi không thấy một chức năng tốt hơn cho điều đó. Tôi nghĩ rằng điều này là do số lượng số không không được biết trước, và buộc nhiều sự tái phân bổ (đó là những gì xảy ra trong thực tế). Tuy nhiên, việc sử dụng SparseMatrix :: reserve() không có hiệu lực, vì nó là một hàm chỉ hoạt động cho các ma trận nén (một chú thích trong nguồn nói "" Chức năng này không có ý nghĩa trong chế độ không nén "trước khi xác nhận) .. .. và, như tài liệu nói rằng "việc đưa một yếu tố mới vào một SparseMatrix chuyển đổi này sau đó để chế độ nén".

cách hiệu quả nhất để xây dựng một ma trận thưa thớt trong Eigen trong khi vẫn đang là gì thể cập nhật hệ số của nó Cảm ơn

nhiều lần

[EDIT: mẫu trường hợp sử dụng: ma trận 10x10 với 10 phi zer os. Để đơn giản, ma trận là đường chéo]

SparseMatrix<double> mat(10, 10); 
for (int i=0; i<10; i++) { 
    for (int j=0; j<1000000; j++) { 
    mat.coeffRef(i, i) += rand()%10; 
    } 
} 

=> hoạt động, nhưng đơn đặt hàng của cường độ chậm hơn so với các nhà điều hành ublas() (đối với ma trận lớn hơn và một khung cảnh thực tế hơn về khóa học).

std::vector<Eigen::Triplet<double> > triplets(10000000); 
int k=0; 
for (int i=0; i<10; i++) { 
    for (int j=0; j<1000000; j++) { 
    triplets[k++] = Eigen::Triplet<double>(i,i,rand()%10); 
    } 
} 
SparseMatrix<double> mat(10, 10); 
mat.setFromTriplets(triplets.begin(), triplets.end()); 

=> không nhớ thân thiện ...

Answer 1

Để làm insert của coeffRef hiệu quả, bạn cần phải dự trữ đủ không gian sử dụng mat.reserve(nnz) nơi nnz là một chứa số lượng ước tính của phi zero của mỗi cột. Nó là tốt hơn để đánh giá quá cao những con số này để tránh nhiều reallocations/bản sao. Một mẹo bổ sung khác là để đảm bảo rằng lần đầu tiên bạn truy cập vào phần tử (i,j), phần tử này là phần tử cuối cùng của cột j.

Nếu bạn có thể dễ dàng tính toán mẫu thưa thớt, thì cách khác là điền vào vectơ của bộ ba duy nhất với 0 cho giá trị, và sau đó coeffRef sẽ nhanh.