Tại sao eigs ('lm') nhanh hơn nhiều so với eigs ('sm')

Question

Tôi sử dụng eigs để tính vectơ riêng của các ma trận vuông thưa thớt lớn (hàng chục nghìn). Điều tôi muốn là bộ vectơ riêng nhỏ nhất. Nhưng

eigs(A, 10, 'sm')  % Note: A is the matrix 

chạy rất chậm.

Tuy nhiên, sử dụng eigs (A, 10, 'lm') cho tôi câu trả lời tương đối nhanh hơn. Và như tôi đã thử, thay thế 10 bằng A_width trong eigs (A, 10, 'lm') để điều này bao gồm tất cả các vectơ riêng, không giải quyết được vấn đề này, vì điều này làm cho nó chậm như sử dụng 'sm' .

Vì vậy, tôi muốn biết lý do tại sao tính toán các vectơ nhỏ nhất (sử dụng 'sm') chậm hơn nhiều so với tính toán lớn nhất?

BTW, nếu bạn có bất kỳ ý tưởng về cách sử dụng eigs với 'sm' nhanh như với 'lm', hãy cho tôi biết điều đó.

Answer 1

Vì eigs thực sự là chức năng của tệp m, chúng tôi có thể cấu hình nó. Tôi đã chạy một vài thử nghiệm cơ bản, và nó phụ thuộc rất nhiều vào bản chất của dữ liệu trong ma trận. Nếu chúng ta chạy các hồ sơ riêng rẽ trên hai dòng mã sau đây:

eigs(eye(1000), 10, 'lm'), and 
eigs(eye(1000), 10, 'sm'), 

sau đó trong trường hợp đầu tiên nó gọi arpackc (chức năng chính mà không làm việc - theo ý kiến ​​trong eigs nó có thể là từ here) một tổng cộng 22 lần. Trong trường hợp thứ hai nó được gọi là 103 lần.

Mặt khác, cố gắng nó với

eigs(rand(1000), 10, 'lm'), and 
eigs(rand(1000), 10, 'sm'), 

tôi nhận được kết quả nơi các tùy chọn 'lm' liên tục gọi arpackc nhiều lần so với các tùy chọn sm.

Tôi e rằng mình không biết chi tiết thuật toán và do đó không thể giải thích nó bằng bất kỳ ý nghĩa toán học nào sâu hơn, nhưng trang tôi liên kết gợi ý ARPACK là tốt nhất cho ma trận với một số cấu trúc. Vì ma trận được tạo ra bởi rand có cấu trúc nhỏ, có thể an toàn để giả định hành vi sau tôi mô tả không phải là những gì bạn mong đợi trong điều kiện hoạt động bình thường.

Tóm lại: nó chỉ đơn giản là lấy thuật toán lặp lại nhiều hơn để hội tụ khi bạn yêu cầu nó cho các giá trị riêng nhỏ nhất của ma trận có cấu trúc. Tuy nhiên, đây là một quá trình lặp lại, nó phụ thuộc rất nhiều vào dữ liệu thực tế bạn cung cấp.

Chỉnh sửa: Có rất nhiều thông tin và tài liệu tham khảo về phương pháp này here và chìa khóa để hiểu chính xác lý do tại sao điều này xảy ra chắc chắn có ở đâu đó trong đó.

Answer 2

Thuật toán được sử dụng trong hầu hết mọi chức năng tiêu chuẩn eigs là (một số biến thể) là Lanczos algorithm. Nó lặp lại và lặp đi lặp lại đầu tiên cung cấp cho bạn các giá trị riêng lớn nhất. Điều này giải thích khá nhiều mỗi quan sát bạn thực hiện:

1. giá trị riêng lớn nhất lấy số tiền ít nhất của lần lặp lại,
2. giá trị riêng nhỏ mất số tiền tối đa của lần lặp lại,
3. Tất cả các giá trị riêng cũng mất số tiền tối đa của lần lặp lại.

Có các thủ thuật để "đánh lừa" eigs để tính toán các giá trị riêng nhỏ nhất bằng cách thực sự biến chúng thành giá trị riêng lớn nhất của một vấn đề khác. Điều này thường được thực hiện bởi một tham số thay đổi. Trượt qua the Matlab documentation for eigs, tôi thấy rằng chúng có thông số sigma, có thể giúp bạn. Lưu ý cùng một tài liệu đề xuất thích hợp eig nếu ma trận phù hợp với bộ nhớ, vì eigs có các quirks dạng số của nó.

Answer 3

Lý do thực sự đơn giản hơn nhiều và do các vấn đề cơ bản trong việc giải quyết các vấn đề riêng biệt lớn. Đây là tất cả dựa trên giải quyết:

(1) A x = lam x 

Hầu hết các phương pháp giải pháp sử dụng một số định luật hàm mũ (ví dụ như một không gian con Krylov kéo dài trong cả hai phương pháp Lanczos và Arnoldi)

Cái này là loạt một sức mạnh hội tụ đến lớn nhất eigenvalue của (1). Do đó chúng tôi có các giá trị riêng biệt lớn nhất được tìm thấy bởi không gian con được mở rộng bởi: K^k = {A*r0,....,A^k*r0}, chỉ yêu cầu phép nhân vectơ ma trận (giá rẻ).

Để tìm nhỏ nhất, chúng ta phải tái cấu trúc (1) như sau:

(2) 1/lam x = A^(-1) x or A^(-1) x = invlam x 

Bây giờ giải quyết cho eigenvalue lớn nhất của (2) là tương đương với việc tìm kiếm các eigenvalue nhỏ nhất của (1). Trong trường hợp này, không gian con được mở rộng bởi K^k = {A^(-1)*r0,....,A^(-k)*r0}, yêu cầu giải quyết một số hệ thống tuyến tính (đắt tiền!).

Hy vọng điều này