Thuật toán O(n log n) cho sản phẩm của ma trận Toeplitz và vectơ có độ dài chính xác nổi tiếng: đặt nó vào ma trận tuần hoàn, nhân nó với véc tơ (và số 0 tiếp theo) và trả về các phần tử n trên cùng của sản phẩm.Sản phẩm của hai ma trận Toeplitz?
Tôi đang tìm sự cố khi tìm thuật toán tốt nhất (theo thời gian) để nhân hai ma trận Toeplitz có cùng kích thước.
Có ai có thể cho tôi thuật toán cho điều này không?
Đây là thuật toán O (n^2) -time.
Để tính toán một trong các đường chéo của ma trận sản phẩm, chúng tôi cần tính toán các sản phẩm chấm trên các cửa sổ có chiều dài-n dài (2n-1) trượt ở chế độ khóa. Sự khác biệt giữa hai mục liên tiếp có thể được tính toán trong thời gian O (1).
Ví dụ, hãy xem xét các sản phẩm của
e f g h i o p q r s
d e f g h m o p q r
c d e f g l m o p q
b c d e f k l m o p
a b c d e j k l m o
Mục 1,1 là eo + fm + gl + hk + ij. Mục nhập 2,2 là dp + eo + fm + gl + hk hoặc 1,1 mục nhập trừ ij cộng với dp. Mục nhập 3,3 là cq + dp + eo + fm + gl hoặc mục nhập 2,2 trừ đi hk cộng với cq. Mục nhập 4,4 là br + cq + dp + eo + fm, v.v.
Nếu bạn thực hiện điều này trong điểm nổi, hãy chú ý đến catastrophic cancellation.
Sản phẩm của ma trận Toeplitz không nhất thiết là Toeplitz. Sản lượng được thể hiện như thế nào? –
Là ma trận nxn, không thấy có biểu diễn nào khác hiển thị tất cả dữ liệu có liên quan trong trường hợp này. Tôi không yêu cầu một thuật toán chạy nhanh hơn 'O (n^2)', tôi đơn giản tự hỏi liệu có một thuật toán nhanh hơn so với thường trình nhân ma trận chuẩn trong trường hợp này hay không. –
Có một thuật toán O (n^2 log n) có n phép nhân ma trận-vector. Nó sẽ không làm tôi ngạc nhiên nếu có một thuật toán O (n^2), nhưng tôi không thể nói rằng tôi muốn tìm nó. –