Giải quyết hệ thống tam giác trên thưa thớt

Question

Tôi đang cố gắng tìm ra cách giải quyết hiệu quả hệ thống tam giác thưa thớt, Au * x = b trong scipy thưa thớt.

Ví dụ, chúng ta có thể xây dựng một ma trận thưa thớt trên hình tam giác, Au, và một tay phải phía b với:

import scipy.sparse as sp 
import scipy.sparse.linalg as sla 
import numpy as np 

n = 2000 
A = sp.rand(n, n, density=0.4) + sp.eye(n) 
Au = sp.triu(A).tocsr() 
b = np.random.normal(size=(n)) 

Chúng ta có thể có được một giải pháp cho vấn đề sử dụng spsolve, tuy nhiên nó là rõ ràng rằng cấu trúc tam giác không bị lợi dụng. Điều này có thể được chứng minh bằng cách định thời gian giải pháp và so sánh nó với phương pháp giải quyết trong splu. (Ở đây sử dụng% thời gian kỳ diệu ipython của)

%time x1 = sla.spsolve(Au,b) 
CPU times: user 3.63 s, sys: 79.1 ms, total: 3.71 s 
Wall time: 1.1 s 

%time Au_lu = sla.splu(Au) 
CPU times: user 3.61 s, sys: 62.2 ms, total: 3.67 s 
Wall time: 1.08 s 

%time x2 = Au_lu.solve(b) 
CPU times: user 25 ms, sys: 332 µs, total: 25.4 ms 
Wall time: 7.01 ms 

Như Au đã trên bên tam giác cuộc gọi đến splu thực sự không nên làm nhiều bất cứ điều gì, tuy nhiên, như n được lớn cuộc gọi này trở nên đắt đỏ (cũng như việc sử dụng spsolve), trong khi thời gian giải quyết vẫn còn nhỏ.

Có cách nào để sử dụng bộ giải tam giác siêu của superLU mà không cần gọi đầu tiên không? Hoặc là có cách nào tốt hơn để làm điều này hoàn toàn?

Answer 1

Tôi e rằng đây không phải là một hướng dẫn khủng khiếp, nhưng bạn đã thử thay đổi hoán vị cột chưa? Khi tôi sử dụng "TỰ NHIÊN", tôi nhận được rất nhiều tốc độ.

%time x1 = sla.spsolve(Au, b, permc_spec="NATURAL") 
CPU time: user 46.7 ms, sys: 0 ns, total: 46.7 ms 
Wall time: 49 ms 

Đối với tôi, nó không hoàn toàn nhanh bằng cách sử dụng phương pháp giải quyết đầu ra hàm splu, nhưng dường như có được gần đúng (và tránh splu gọi). Có lẽ điều đó sẽ đủ? Scipy Docs