Đại số tuyến tính

Danh sách đầy đủ các thuật toán trong nhóm (Tổng: 10)

Đại số tuyến tính

Berlekamp-Massey Algorithm

Thời gian (Time) O(N^2)
Không gian (Space) O(N)

Mô tả nguyên lý

Tìm dãy hồi tiếp tuyến tính ngắn nhất sinh ra một chuỗi số cho trước.

Cài đặt mẫu (Implementation)

// Tự động điều chỉnh sai số đa thức sinh để tìm ra quan hệ truy hồi tuyến tính tối thiểu.
Đại số tuyến tính

Cholesky Decomposition

Thời gian (Time) O(N^3)
Không gian (Space) O(N^2)

Mô tả nguyên lý

Phân rã ma trận đối xứng xác định dương thành tích của ma trận tam giác và chuyển vị của nó.

Cài đặt mẫu (Implementation)

// Tính toán cực kỳ hiệu quả cho các bài toán tối ưu hóa và thống kê covariance.
Đại số tuyến tính

Coppersmith-Winograd Matrix Multiply

Thời gian (Time) O(N^2.373)
Không gian (Space) O(N^2)

Mô tả nguyên lý

Thuật toán nhân ma trận tối ưu lý thuyết với độ phức tạp bậc thấp.

Cài đặt mẫu (Implementation)

// Xây dựng tensor tính toán đại số tuyến tính nâng cao.
Đại số tuyến tính

Gauss-Jordan Elimination

Thời gian (Time) O(N^3)
Không gian (Space) O(N^2)

Mô tả nguyên lý

Khử Gauss-Jordan đưa ma trận về dạng bậc thang rút gọn để giải hệ phương trình.

Cài đặt mẫu (Implementation)

// Thực hiện các phép biến đổi hàng sơ cấp để biến ma trận hệ số thành ma trận đơn vị.
Đại số tuyến tính

LU Matrix Decomposition

Thời gian (Time) O(N^3)
Không gian (Space) O(N^2)

Mô tả nguyên lý

Phân rã ma trận vuông thành tích của một ma trận tam giác dưới (L) và tam giác trên (U).

Cài đặt mẫu (Implementation)

// Hỗ trợ giải hệ phương trình tuyến tính và tính định thức ma trận nhanh chóng.
Đại số tuyến tính

Power Iteration Eigenvalue Solver

Thời gian (Time) O(Iter * N^2)
Không gian (Space) O(N)

Mô tả nguyên lý

Tìm trị riêng có độ lớn lớn nhất và vector riêng tương ứng của ma trận vuông.

Cài đặt mẫu (Implementation)

// Lặp nhân ma trận với vector đơn vị và chuẩn hóa liên tục.
Đại số tuyến tính

QR Algorithm for Eigenvalues

Thời gian (Time) O(Iter * N^3)
Không gian (Space) O(N^2)

Mô tả nguyên lý

Thuật toán số học tìm toàn bộ các trị riêng của ma trận thông qua phân rã QR liên tiếp.

Cài đặt mẫu (Implementation)

// Lặp lại việc phân rã $A_k = Q_k R_k$ và gán $A_{k+1} = R_k Q_k$.
Đại số tuyến tính

QR Matrix Decomposition

Thời gian (Time) O(N^3)
Không gian (Space) O(N^2)

Mô tả nguyên lý

Phân rã ma trận thành một ma trận trực giao (Q) và một ma trận tam giác trên (R).

Cài đặt mẫu (Implementation)

// Sử dụng phép biến đổi Householder hoặc Gram-Schmidt để giải bài toán bình phương tối thiểu.
Đại số tuyến tính

Singular Value Decomposition (SVD)

Thời gian (Time) O(M^2 * N + N^3)
Không gian (Space) O(M * N)

Mô tả nguyên lý

Phân rã ma trận bất kỳ thành các giá trị kỳ dị và các vector riêng trực giao.

Cài đặt mẫu (Implementation)

// Nền tảng của nén dữ liệu, giảm chiều PCA và phân tích hệ thống tuyến tính.
Đại số tuyến tính

Strassen Matrix Multiplication

Thời gian (Time) O(N^2.807)
Không gian (Space) O(N^2)

Mô tả nguyên lý

Nhân hai ma trận vuông nhanh hơn thuật toán truyền thống bằng phương pháp chia để trị.

Cài đặt mẫu (Implementation)

// Giảm số phép nhân ma trận từ 8 xuống còn 7 phép nhân qua các ma trận phụ trung gian.